How to get 100pts in Euler Sum?

How to get 100pts in Euler Sum? I could get only 50.

1 Like

Not a single cpp solution of 100 pts :stuck_out_tongue: waiting for editorial.

1 Like

Apparently all people who submit in cpp too did in python, i think to handle the overflow, I hope editorials are out soon. :smiley:

@ hacker_sk : Yes exactly. Why all the accepted solution are in python?

I saw your solution and the reason why it gets a WA is because of the imprecise value of e. Since n has a value of upto 10^4000 your e must be precise upto atleast 4000 digits.

However even with a precise value of e it times out. It is because division in python takes O(n^2) and the step a/=(a-1) takes 1.6*10^7 operations just for one divsion(I am assuming precise value of e).

So to rectify this you can use a continued fraction approach. A continued fraction gives a good approximation for e. For a given n we take a continued fraction of e for which the denominator is greater than n. This is to ensure precision. Then for the operation e=e/(e-1) since e=b/a we can write b=b-a and a will not change. Then the denominator also changes in the following steps. Now for generating the continued fraction for e look for oeis sequences – A007676,A007677,A113873,A113874.The first 2 are the values of numerator and denominator of convergents of e and the second 2 are their respective generators.

my solution.


My solution:
If we somehow express e as a fraction p/q then we will be able to calculate it as \sum_{i=1}^n [\frac{pi}{q}] in O(log n) time using this. To find p/q I used formula e=\sum_{i=1}^{\infty}\frac{1}{i!}\approx\frac{1}{k!}\sum_{i=1}^{k}\frac{k!}{i!} up to few thousand terms. Note that \frac{k!}{i!} is integer for i\leq k so we can have p=\sum_{i=1}^{k}\frac{k!}{i!} and q=k! but we still need to divide them by their gcd.

I first coded a solution in C++ using big integers but when submitting I learned that there is a source code limit (I guess to make it impossible to hardcode the digits of e) so I rewrote the solution in python because then I didn’t need to implement big integers. Without the source code limit it is solvable in C++ (although more painful).

The idea is to use continued fraction of e. For detail see: continued fraction of e. For a good enough approximation \frac{p_n}{q_n}, we have [ek]=[\frac{p_n}{q_n}k] for all k\le 10^{4000}. Here I used n=4001 in my code. Now the problem is to find \sum_{k=1}^{N}[\frac{p_n}{q_n}k]. There is a way to find this sum in a quick way and the runtime is equal to the runtime of finding gcd of p_n and q_n. For detail see: summing floor trick.

If you have got 50 it’s great. For 100 use Continued fraction of ‘e’ then with some some math you’ll figure out.
Keep Coding. Have Fun. :slight_smile:

1 Like

If you have got 50 it’s great. For 100 use Continued fraction of ‘e’ [][1] then with some some math you’ll figure out.
Keep Coding. Have Fun. :slight_smile:

Taylor Series approach

I see many people used continued fractions. Alternatively, you can solve this problem using Taylor Series of e:


For a good approximation, around M=3000 iterations is enough, and you can simplify:


With that, I was able to separate numerator and denominator, used python int throughout while doing the summing floor trick for irrational numbers. Here’s link to my solution :slight_smile:


You could also spigot algorithm for digits of e. Sadly I didn’t get the gcd the like algorithm as mentioned by @phben rather was coding a sum of beatty sequence … and hence I got only 50 points

I used both spigot algo(that too optimized for fast output) for calculation of e and used floor optimization but my solution gave TLE for 2nd Subtask.
Please if anyone could figure out mistake it is thankful

Because it’s not so easy to handle overflow(upto 8000 digits) in cpp i think. :smiley:

Yes the source code limit is low for including Big Integer but 2 people @hacker_sk and @usaxena95 managed to get 50 points. Really great I believe.


Because of constraints on source limit size. to import your big integer library with fast multiplication, division and mod operations will exceed atleast 2000 bytes.


nice solution indeed. short and precise.

1 Like

Unfortunately, I couldn’t prove well why M=3000 was enough. I tried doing Taylor series error approximation for 4000 digits of e, which gives M=1465, but that solution gave me WA. Probably have something to do with summing floor trick. If someone can help me with a good proof to approximate taylor series value (with summing floor), I would appreciate that.

Wow! This is great.