Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
Given a positive integer n, you must calculate the nth digit of \$e\$, where \$e\$ is Euler's number (2.71828...).
The format of the output can be a number or a string (e.g., 3 or '3')
# e = 2.71828...
nthDigit(3) => 8
nthDigit(1) => 7
nthDigit(4) => 2
Shortest code wins.
žtsè
Pretty convenient builtin ¯\_(ツ)_/¯
Try it online or verify the first ten digits or output the infinite list of digits.
Explanation:
žt # Push the infinite list of decimal value of e (including leading 2)
sè # And 0-based index the input-integer into it
# (after which the result is output implicitly)
Solution provided by @l4m2
-2 bytes thanks to @xnor
lambda n:`(100**n+1)**100**n`[n]
Very, very slow.
Verification up to \$166\$ digits. The idea for this verification comes from @l4m2: calculates \$x^{100^n}\$ by calculating x=x**10 repeatedly (\$2n\$ times), each time truncating \$x\$ to a few left most digits (the TIO link uses \$500\$ digits). By changing the truncation to round down or up, we obtain the lower and upper bound for the result. If the lower and upper bound agree to \$n\$ leftmost digits, we know that the exact calculation will also result in those \$n\$ digits.
I have verified that this solution works up to \$n = 333\$, using MAX_DIGITS = 1000.
How
This solution uses the following well known approximation of \$e\$: $$ e = \lim_{x \to \infty} \left(1 + \frac{1}{x} \right)^{x}$$ Substituting \$x = 100^n\$, we have: $$ e = \lim_{n \to \infty} \left(1 + \frac{1}{100^n} \right)^{100^n} = \lim_{n \to \infty} \frac{\left(100^n + 1 \right)^{100^n}}{\left(100^n\right)^{100^n}}$$ Since the denominator is a power of \$10\$, we can ignore it entirely.
According to this analysis on Math SE, the worst case error of this approximation is: $$ \Delta < \frac{3}{x} = \frac{3}{100^n}$$ which means roughly that every time \$n\$ increases by \$1\$, we gains 2 digits of precision.
...90... becomes ...89..., but even if I round up after each division, the result is still wrong. Even though my solution's error goes down by a factor of 10 every time n increases, the error can still be large enough to push patterns like ...200... down to ...199....
\$\endgroup\$
May 14, 2020 at 5:07
I?dF+k^1sF2sE2sN[q]sR[1lNlF*dsF/d0=RlE+sElN1+sNlLx]dsLx+lE*0k1/I%p
Or print more than 800 digits before TIO times out after a minute.
I've verified these 800 digits against the published value at a NASA web page with 2 million digits of e.
(It may be possible to shorten the code a bit by keeping some of the variables on the stack and accessing them via stack manipulation instead of using dc's registers.)
Explanation
I # 10.
? # Input value.
d # Push on stack for later.
F+k # Add 15 and make that the number of decimal places to calculate.
^ # 10 ^ input value, saved on stack for use at end.
1sF # 1!, stored in F.
2sE # 2 is starting value for e.
2sN # for (N=2; ... )
[q]sR # Macro R will be used to end loop.
[ # Start loop L.
1 # Push 1 for later.
lNlF*dsF # F = N! and push on stack.
/d # 1 / N!, duplicate on stack
0=R # If 1/N! == 0 (to the number of decimal places being computed), end loop.
lE+sE # Otherwise e += 1/N!
lN1+sN # N++
lLx # Go back to start of loop L
]dsLx # End macro, save it in L, and execute it.
+ # Get rid of extra 0 on stack.
lE # e, computed with sufficient accuracy
* # Multiply by 10^input value, which was saved on the stack early on.
0k1/ # Truncate to integer.
I% # Mod by 10 to get desired digit.
p # Print digit.
n=int(input())
N=n+3
q=2
e=[1]*N
exec('q=i=0;exec("q,e[i]=divmod(10*e[i]+q,N-i+1);i+=1;"*N);'*n)
print(q)
Try it online! (thanks to @SurculoseSputum)
This only uses small integers to calculate digits of \$e\$. With a modification to use a lazy upper bound for N, it uses the algorithm described in
A. H. J. Sale. "The calculation of \$e\$ to many significant digits." The Computer Journal, Volume 11, Issue 2, August 1968, Pages 229–230, https://doi.org/10.1093/comjnl/11.2.229
Essentially, the idea is that \$e\$ can be written in "base-factorial" as \$1.11111\dots\$, where digit \$n\$ has place value \$1/n!\$. The algorithm repeatedly multiplies this number by 10 to extract digits one at a time. In fact, if one were to record each value of q in the outer for loop, the result would be the first n digits of \$e\$.
One complexity is that we need to know how many digits in base-factorial to calculate. In this version, \$n+3\$ is (more than) sufficient. A previous version of this answer used an estimate from Taylor's theorem, and it looked for a value of N such that \$N!\geq 10^{n}\$, doing so by calculating all factorials until it exceeds this power of ten.
exec "..loop.."*n, and changing from a function to a program.
\$\endgroup\$
May 16, 2020 at 4:34
N (aka N=n+3), then this can be shorten to 95 bytes.
\$\endgroup\$
May 16, 2020 at 5:01
f=lambda n,p=1,q=1,k=1:k<n+9and f(n,p*k+1,q*k,k+1)or str(p*100**n/q)[n]
-1 byte, remove unneccesary whitespace.
f=lambda n,p=1,q=1,k=1:k<n+9and f(n,p*k+1,q*k,k+1) or str(p*100**n/q)[n]
-28 bytes simpler formula
Simpler algorithm based on more usual formula:
$$e = 1 + \frac 1 {1!} + \frac 1 {2!} + \frac 1 {3!} + \frac 1 {4!} + \cdots$$
But re-expressed as sequence of approximations:
$$1, 1+1, \frac{(2(1+1)+1)}2, \frac{(3(2(1+1)+1)+1)}{(3\cdot2)}, \frac{(4(3(2(1+1)+1)+1)+1)}{(4\cdot(3\cdot2))},...$$
These can be expressed as ratio of recurrence relations $\frac {p_k}, where
$$p_0 = q_0 = 1 \\ p_{k+1} = kp_k + 1, q_{k+1} = kq_k, \: \forall k \ge 1$$
f=lambda n,p=3,q=1,r=19,s=7,b=10,x=1,y=0:x-y and f(n,r,s,r*b+p,s*b+q,b+4,p*100**n//q,x) or str(x)[n]
+2 bytes because I mistakenly omitted f=
This approach is based on continued fractions. Not happy with it yet, but it seems good for a few hundred digits.
Based on the continued fraction:
$$e = 3 - \cfrac 2 {7 + \cfrac 1 {10 + \cfrac 1 {14 + \cfrac 1 {18 + \cfrac 1 {22 + \ddots}}}}}$$
Computed by the recurrence relation:
$$\frac {p_0} {q_0} = \frac 3 1 , \: \frac {p_1} {q_1} = \frac {19} 7 \\ \frac {p_{k+1}} {q_{k+1}} = \frac {p_k (4k+2) + p_{k-1}} {q_k (4k+2) + q_{k-1}}, \: \forall k \ge 1$$
which was arrived at after a first reading of An Essay on Continued Fractions by Leonard Euler.
⁵*³
¢‘µ*¢ŒṘḣ³Ṫ
A monadic link taking a single integer, plus a niladic helper link.
⁵*³
¢‘µ*¢ŒṘḣ³Ṫ
Link f:
*(10, input) # 10 * input
Main Link:
tail(head(str(*(Increment(f()), f())), input)) # str((f() + 1) * (f()))[:input][-1]
Ｐ←×ψ⁺²Ｎ¤≕EＴ¹
Try it online! Link is to verbose version of code. Inspired by @ASCII-only's comment and his answer to Bake a slice of Pi (compare my answer to Music with pi and e). Explanation:
Ｐ←×ψ⁺²Ｎ
Input n and print n+2 nulls to the left without moving the cursor, so it remains on the last null.
¤≕E
Fill the nulls with the expansion of Euler's number.
Ｔ¹
Trim away everything except the current character.
Previous 30-byte answer calculated the Maclaurin expansion of 100ⁿe to n+10 terms:
Ｎθ≔Ｘχ⊗θη≔⁰ζＦ⁺χθ«≧⁺ηζ≧÷⊕ι继Ｉζθ
Try it online! Link is to verbose version of code. Explanation:
Ｎθ
Input n.
≔Ｘχ⊗θη
Start with a term of 100ⁿ.
≔⁰ζ
Initialise the total to 0.
Ｆ⁺χθ«
Repeat n+10 times.
≧⁺ηζ
Add the current term to the total.
≧÷⊕ιη
Divide the term by the number of loop iterations.
»§Ｉζθ
Print the nth digit of the total.
Fill is still shorter anyway, so...
\$\endgroup\$
N[E, whatever + 1]
\$\endgroup\$
Jan 1, 2021 at 13:45
GetVariable("E") fails and I didn't know about N[].
\$\endgroup\$
> Input
> eᵢ
>> ≻1
>> 2ᶠ3
>> 4ⁿ1
>> Output 5
Run with python3 whispers\ v3.py euler.wisp < input.txt 2> /dev/null
Input is the first line in input.txt.
Euler digits builtin ftw!
scale=s=read();(e(1)*A^s+scale=0)%A/1
Input on stdin, output on stdout.
n-th digit, because it may have been rounded up. For example,ewith 4-decimal precision would give you2.7183, but actually the 4-th decimal is2, not3\$\endgroup\$