8
\$\begingroup\$

Challenge

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')

Example

# e = 2.71828...

nthDigit(3) => 8
nthDigit(1) => 7
nthDigit(4) => 2

Shortest code wins.

\$\endgroup\$
9
  • 9
    \$\begingroup\$ Language like "You cannot use any external libraries or constants" is not up to our standards of clarity on this site. The best way to fix this problem is to remove the restriction, since it doesn't do anything good for your challenge in the first place. \$\endgroup\$ – Wheat Wizard May 14 '20 at 1:37
  • 5
    \$\begingroup\$ @applemonkey496 It doesn't solve the challenge anyway because a floating-point number doesn't have infinite precision (the output can't be right after 15 digits or so). \$\endgroup\$ – Bubbler May 14 '20 at 3:42
  • 3
    \$\begingroup\$ Is there an upper bound on \$n\$ for this challenge? \$\endgroup\$ – Dingus May 14 '20 at 5:27
  • 2
    \$\begingroup\$ Even with arbitrary precision, it's not straightforward to get the n-th digit, because it may have been rounded up. For example, e with 4-decimal precision would give you 2.7183, but actually the 4-th decimal is 2, not 3 \$\endgroup\$ – Luis Mendo May 14 '20 at 10:14
  • 1
    \$\begingroup\$ @MitchellSpector It would probably work for 05AB1E for 1 byte but it's just pseudocode. \$\endgroup\$ – Wezl May 14 '20 at 18:18

12 Answers 12

8
\$\begingroup\$

05AB1E, 4 bytes

ž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)
\$\endgroup\$
8
\$\begingroup\$

Python 2, 34 32 bytes

Solution provided by @l4m2
-2 bytes thanks to @xnor

lambda n:`(100**n+1)**100**n`[n]

Try it online!

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.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Is yur code or my optimize wrong? \$\endgroup\$ – l4m2 May 14 '20 at 3:48
  • \$\begingroup\$ @l4m2 My solution is wrong unfortunately :( At first I thought your optimization slightly lowered the result due to truncation, e.g ...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\$ – Surculose Sputum May 14 '20 at 5:07
  • \$\begingroup\$ So can this be wrong? (though it's much slower it's same length) \$\endgroup\$ – l4m2 May 14 '20 at 5:13
  • 1
    \$\begingroup\$ My link's for such purpose \$\endgroup\$ – l4m2 May 14 '20 at 6:47
  • 1
    \$\begingroup\$ Python's exponentiation actually right-associates so you can cut those parens. \$\endgroup\$ – xnor May 14 '20 at 12:13
4
\$\begingroup\$

dc, 66 bytes

I?dF+k^1sF2sE2sN[q]sR[1lNlF*dsF/d0=RlE+sElN1+sNlLx]dsLx+lE*0k1/I%p

Try it online!

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.
\$\endgroup\$
3
\$\begingroup\$

Python 3, 146 105 bytes

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ +1 for this spigot algorithm (these algorithms are nice -- they produce one digit at a time as they run). I did a version in dc based on an algorithm similar to this one; unfortunately it came out to be longer than the dc answer that i posted earlier. (I golfed it down to 101 bytes, which isn't even close to the 66 bytes in the answer I posted.) \$\endgroup\$ – Mitchell Spector May 15 '20 at 21:16
  • \$\begingroup\$ 119 bytes by replacing the loops with exec "..loop.."*n, and changing from a function to a program. \$\endgroup\$ – Surculose Sputum May 16 '20 at 4:34
  • \$\begingroup\$ If you accept a larger value of N (aka N=n+3), then this can be shorten to 95 bytes. \$\endgroup\$ – Surculose Sputum May 16 '20 at 5:01
  • \$\begingroup\$ @SurculoseSputum Thanks! I modified it to be Python 3 compatible, which loses 10 bytes to your 95. \$\endgroup\$ – Kyle Miller May 25 '20 at 18:14
2
\$\begingroup\$

05AB1E, 8 bytes

°D>smI<è

Try it online!

Very, very slow.

\$\endgroup\$
2
\$\begingroup\$

SageMath, 35 33 bytes

lambda n:str(N(e,digits=n+9))[-9]

Try it online!

Very, very fast!

\$\endgroup\$
8
  • \$\begingroup\$ Fastest gun or fastest code? \$\endgroup\$ – user92069 May 14 '20 at 11:40
  • 1
    \$\begingroup\$ @Λ̸̸ You've got to ask yourself one question: "Do I feel lucky?" Well, do ya, punk? :P \$\endgroup\$ – Noodle9 May 14 '20 at 11:53
  • \$\begingroup\$ You're lucky because you answered the question just before the question is closed. \$\endgroup\$ – user92069 May 14 '20 at 11:56
  • \$\begingroup\$ @Λ̸̸ Oh wow! I am the lucky one today! :D \$\endgroup\$ – Noodle9 May 14 '20 at 11:58
  • 1
    \$\begingroup\$ @Λ̸̸ That's nothing; I can still answer questions after they're closed! \$\endgroup\$ – Neil May 14 '20 at 12:21
2
\$\begingroup\$

Python 2, 98 100, 72 bytes

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]

Try it online!

-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$$

old answer

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=

Try it online!

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.

\$\endgroup\$
1
\$\begingroup\$

Jelly, 14 bytes

⁵*³
¢‘µ*¢ŒṘḣ³Ṫ

Try it online!

A monadic link taking a single integer, plus a niladic helper link.

Explained

⁵*³
¢‘µ*¢ŒṘḣ³Ṫ

Link f:
    *(10, input) # 10 * input

Main Link:
    tail(head(str(*(Increment(f()), f())), input)) # str((f() + 1) * (f()))[:input][-1]
\$\endgroup\$
3
  • \$\begingroup\$ Do you mean 2-indexing? Since the question requires the digits after the decimal point. \$\endgroup\$ – user92069 May 14 '20 at 1:51
  • \$\begingroup\$ @Λ̸̸ Well, whatever it is, it's the same as the other answers \$\endgroup\$ – Lyxal May 14 '20 at 1:58
  • \$\begingroup\$ Here's how to do the same thing in 8 bytes. \$\endgroup\$ – Jonathan Allan May 14 '20 at 15:17
1
\$\begingroup\$

Wolfram Language (Mathematica), 21 bytes

Floor[E 10^#]~Mod~10&

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 30 12 bytes

P←×ψ⁺²N¤≕ET¹

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:

P←×ψ⁺²N

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.

T¹

Trim away everything except the current character.

Previous 30-byte answer calculated the Maclaurin expansion of 100ⁿe to n+10 terms:

Nθ≔Xχ⊗θη≔⁰ζF⁺χθ«≧⁺ηζ≧÷⊕ι继Iζθ

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input n.

≔Xχ⊗θη

Start with a term of 100ⁿ.

≔⁰ζ

Initialise the total to 0.

F⁺χθ«

Repeat n+10 times.

≧⁺ηζ

Add the current term to the total.

≧÷⊕ιη

Divide the term by the number of loop iterations.

»§Iζθ

Print the nth digit of the total.

\$\endgroup\$
4
  • \$\begingroup\$ or of course, the cheaty way \$\endgroup\$ – ASCII-only Jan 1 at 6:52
  • \$\begingroup\$ @ASCII-only Ah, so I guess you can get Pi that way without Fill()ing it too? Although, it turns out that using Fill is still shorter anyway, so... \$\endgroup\$ – Neil Jan 1 at 13:39
  • \$\begingroup\$ yeah, this is just the direct translation of mathematica's N[E, whatever + 1] \$\endgroup\$ – ASCII-only Jan 1 at 13:45
  • \$\begingroup\$ @ASCII-only Ah, because for Music with pi and e I did wonder how to get the relevant number of digits, since just trying to stringify GetVariable("E") fails and I didn't know about N[]. \$\endgroup\$ – Neil Jan 1 at 16:30
1
\$\begingroup\$

Whispers v3, 52 bytes

> Input
> eᵢ
>> ≻1
>> 2ᶠ3
>> 4ⁿ1
>> Output 5

Try it on repl.it!

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!

\$\endgroup\$
0
\$\begingroup\$

bc -l, 37 bytes

scale=s=read();(e(1)*A^s+scale=0)%A/1

Try test cases online!

Input on stdin, output on stdout.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.