How powerful must this e approximation be?

Question

This challenge was inspired by this non-challenge about the natural logarithm base \$e\$ and the following pandigital approximation to \$e\$ appearing on a Math Magic page: $$\left|(1+9^{-4^{7×6}})^{3^{2^{85}}}-e\right|$$ $$\approx2.01×10^{-18457734525360901453873570}$$ It is fairly well-known that $$e=\lim_{n\to\infty}\left(1+\frac1n\right)^n$$ It is less well-known that the limit expression is strictly monotonically increasing over the positive real numbers. These facts together imply that for every nonnegative integer \$d\$ there is a least positive integer \$n=f(d)\$ such that the first \$d\$ decimal places of \$(1+1/n)^n\$ agree with those of \$e\$. \$f(d)\$ is OEIS A105053.

For example, \$(1+1/73)^{73}=2.69989\dots\$ and \$(1+1/74)^{74}=2.70013\dots\$, so \$f(1)=74\$.

Task

Given a nonnegative integer \$d\$, output \$n=f(d)\$ as described above. Your code must theoretically be able to give the correct answer for any value of \$d\$.

This is code-golf; fewest bytes wins.

Test cases

The corresponding digits of \$e\$ are given for reference.

    d, n
(2. 0, 1
(7) 1, 74
(1) 2, 164
(8) 3, 4822
(2) 4, 16609
(8) 5, 743325
(1) 6, 1640565
(8) 7, 47757783
(2) 8, 160673087
(8) 9, 2960799523
(4) 10, 23018638268
(5) 11, 150260425527
(9) 12, 30045984061852
(0) 13, 30045984061852
(4) 14, 259607904633050
(5) 15, 5774724907212535

Answer 1

Python, 126 bytes

f=lambda k,s=2,r=0:(P:=10**k*(t:=s+1)**t//s**s,p:=P//t,s%2*((x:=p<r)+s)or f(k,s+[s,x*(S:=s&-s)-S//2][r>0],r or(p==P//s)*p))[2]

Attempt This Online!

Previous Python, 144 bytes

def f(k):
 o=p=0;P=n=1
 while p<P//n:n*=2;m=n+1;P=10**k*m**m//n**n;p=P//m
 while n+~o:T=n+o>>1;o,n,*_=[o,T,n][10**k*(T+1)**T//T**T<p:]
 return n

Attempt This Online!

Not the golfiest, but should, in theory, give exact values for arbitrary inputs. In practice, times out for d>4 on ato.

How?

Takes advantage of Python's inbuilt bigints. Uses

\$(1+1/n)^n<e<(1+1/n)^{n+1}\$

to compute the correct digits and an upper bound for n and then pinpoints n by bisection. As we always have to first compute the nth power of n+1 and only then can divide by the nth power of n this is still expensive.

Answer 2

Wolfram Language (Mathematica), 34 33 28 bytes (26 25 24 characters)

⌊E/2/Mod[E,10^-#]+1/12⌋&

Try it online!

–5 bytes thanks to @CommandMaster

The exact formula is $$ n(\zeta)=\left\lceil\frac{\zeta}{e^{-W_{-1}\left(-\frac{\ln\zeta}{\zeta}\right)}-\zeta}\right\rceil=\left\lceil\frac{e}{2(e-\zeta)}-\frac{11}{12}+O(e-\zeta)\right\rceil \approx\left\lfloor\frac{e}{2(e-\zeta)}+\frac{1}{12}\right\rfloor $$ with $$ \zeta=10^{-d}\lfloor10^de\rfloor $$ being Euler's number rounded down to d digits, and W the Lambert function. The given series-expansion of n(ζ) seems to be good enough to evaluate the task.

Note that we can freely replace the ceiling function ⌈…⌉ with the shifted floor function ⌊…⌋+1 because the argument cannot be an exact integer because e is irrational.

Here's the exact formula, golfed to 54 bytes (46 characters), to verify that the above series expansion gives correct results:

⌈#/(E^(-LambertW[-1,-Log@#/#])-#)⌉&@⌊E,10^-#⌋&

Try it online to verify up to d=2000. For higher values of d, let's estimate the probability of failure. The series expansion of n(ζ) underestimates the true n(ζ) by about 5(e-ζ)/(72 e), which is the next term in the series-expansion of n(ζ). But e-ζ<10^(-d), and so the probability of this underestimation crossing an integer (and thus fouling up the ceiling function) is less than 5×10^(-d)/(72 e). Summing these probabilities (assumed independent!) from d=2001 to infinity, we get a failure probability of around 3×10^(-2003). There were a lot of assumptions in this derivation (assuming independence, irrationality, ergodicity, etc.); but I think it indicates that we cannot expect any failures as d becomes large.

NB: I've checked up to d=10000 and found no deviations, thus pushing the expected failure probability to 3×10^(-10003).

PS: I've got °Džr*ïs/žrD;r-/TÌz+ï as a 05AB1E translation, but it does not seem very golfed (20 bytes). Help would be appreciated!

Answer 3

R, 59 52 bytes

\(d){while(exp(1)%/%10^-d-(1+1/F)^F%/%10^-d)F=F+1;F}

Attempt This Online! Only works up to d = 4 in practice, afterwards produces different results due to numerical precision issues.

Credit for -7 bytes to Dominic van Essen.

Answer 4

Wolfram Language (Mathematica), 51 bytes

(k=0;While[⌊10^#(1+1/++k)^k⌋!=⌊E*10^#⌋];k)&

Try it online!

-2 bytes from @Roman

Answer 5

Haskell, 63 bytes

n d=[n|n<-[1..],floor(10**d*(1+1/n)**n)==floor(10**d*exp 1)]!!0

Try it online!

Haskell, 204 bytes, fast

n d=b.(\(v,w)->(last v,head w)).break p$map(2^)[0..]where
 i=fromInteger
 f=floor.(*10**i d)
 e=f$exp 1
 p n=e==f((1+1/i n)**i n)
 b(a,z)|let m=div(a+z)2=if m==a then z else if p m then b(a,m) else b(m,z)

Try it online!

Haskell, 299 bytes, unlimited by f64

import Data.Ratio
n d=b.(\(v,w)->(last v,head w)).break p$map(2^)[0..]where
 f=floor.(*10^d)
 e=f.sum.scanl1(*).map(1%)$1:[1..until(\i->product[1..i]>10^d)(1+)1]
 p n=(e==).f.sum.take(16+d)$scanl(*)1[(n-k+1)%(k*n)|k<-[1..n]]
 b(a,z)|let m=div(a+z)2=if m==a then z else if p m then b(a,m) else b(m,z)

Try it online!

Answer 6

Charcoal, 46 bytes

ＮθＰ×ψ⁺²θ¤≕E≔¹ηＷ‹÷×ＸχθＸ⊕ηηＸηηＩ⪫ΦＫＤ⁺²θ→⊖λω≦⊕η⎚Ｉη

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

Ｎθ

Input d.

Ｐ×ψ⁺²θ¤≕E

Write e to d decimal places to the canvas. (I don't know a better way of extracting arbitrary numbers of decimal places of e in Charcoal.)

≔¹η

Start with n=1.

Ｗ‹÷×ＸχθＸ⊕ηηＸηηＩ⪫ΦＫＤ⁺²θ→⊖λω

While 10ᵈ(1+⅟ₙ)ⁿ is less than 10ᵈe...

≦⊕η

... increment n.

⎚Ｉη

Remove e from the canvas and output the final value of n.

73 bytes for a less inefficient version based on @loopywalt's original Python answer:

≔ＸχＮθ≔¹η≔⁰ζＷ↨÷÷×θＸ⊕η⊕ηＸηη⟦⊕ηη⟧±¹≦⊗ηＷ∧⊖⁻ηζ÷⁺ηζ²¿↨Ｅ⟦ηι⟧÷×θＸ⊕κκＸκκ±¹≔ιζ≔ιηＩη

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

≔ＸχＮθ

Input 10ᵈ.

≔¹η≔⁰ζ

Start with bounds of 0 and 1.

Ｗ↨÷÷×θＸ⊕η⊕ηＸηη⟦⊕ηη⟧±¹≦⊗η

Double the bounds until the first d decimal places of 10ᵈ(1+⅟ₙ)ⁿ are the same for both n and n+1.

Ｗ∧⊖⁻ηζ÷⁺ηζ²¿↨Ｅ⟦ηι⟧÷×θＸ⊕κκＸκκ±¹≔ιζ≔ιη

Binary search to find the smallest value of n with the same first d decimal places.

Ｉη

Output the resulting n.

Answer 7

Vyxal, 124 bits^v1, 15.5 bytes

Ė›$eke"$↵vḞ?⇧vẎ≈)ṅ

Try it Online!

Times out for all d except 0. Might be due to the fact that to even find the right number for d > 0 a minimum of \$10^{74}\$ digits of \$e\$ and the approximation need to be calculated.

Explained

Ė›$eke"n↵vḞ?⇧vẎ≈)ṅ 
                )ṅ # find the first positive integer n where
Ė›$e               # (1 + 1/n) ^ n
    ke"            # paired with the exact value of e
       ?n↵vḞ        # both evaluated to 10 ** n decimal places - guarantees enough digits will be generated to avoid rounding errors
           ?⇧vẎ    # each sliced to the first d + 2 characters (the 2, then the dot point, then d decimals) 
               ≈   # are all the same

Answer 8

APL, 44 bytes (SBCS)

{1∘+⍣((⊢*⍨1+÷)⍤⊣=⍥((10*⍵)∘(÷⍤⊣×⌊⍤×))(*1⍨))1}

Explanation:

                                        1   Starting from 1,
1∘+                                         increment
   ⍣                                        until
     (⊢*⍨1+÷)⍤⊣                             (1+1/n)^n
               =                            is equal to
                                    *1⍨     e
                ⍥                           after both arguments to equal are processed by
                  (10*⍵)∘(÷⍤⊣×⌊⍤×)          rounding to input significant figures

Tested until d = 7, afterwards it gets too slow. Will probably eventually fail because of precision issues.

Answer 9

05AB1E, 17 (or 15) bytes

∞.Δz>ymþSžt‚I>δ£Ë

In theory works for an arbitrary value of \$n\$, but in practice times out for \$n\geq5\$ on TIO.

Try it online or verify the first few test cases.

Here a 2 bytes shorter approach which works up to \$n=15\$ (in theory again, in practice it also times out at \$n\geq5\$):

∞.Δz>ymžr‚IÌδ£Ë

Try it online or verify the first few test cases

Explanation:

∞.Δ            # Find the first positive integer `n` that's truthy for:
   z           #  Pop and push 1/n
    >          #  Increase it by 1
     ym        #  Take that to the power n
   þ           #  Remove the dot by only leaving its digits
    S          #  Convert this integer to a list of digits
       ‚       #  Pair it with
     žt        #  The infinite list of e: [2,7,1,...]
          δ    #  Map over the pair,
        I>     #  using the input+1 as argument:
           £   #   Only leave that many digits from both lists
            Ë  #  Check if the lists in the pair are the same
               # (after which the found integer is output implicitly as result)

In the 15-bytes answer, þS are both removed; the infinite list of digits of \$e\$ žt is replaced with its decimal value žr (\$2.718281828459045\$); and the input+1 I> is replaced with the input+2 IÌ to account for the dot.

Answer 10

Scala, 91 bytes

Golfed version. Try it online!

d=>Stream.from(1).find(n=>floor(pow(10,d)*pow(1+1.0/n,n))==floor(pow(10,d)*E)).getOrElse(0)

Ungolfed version. Try it online!

import scala.math._

object Main extends App {
  def n(d: Int): Int = {
    Stream.from(1).find(n => {
      val lhs = floor(pow(10, d) * pow(1+1.0/n, n))
      val rhs = floor(pow(10, d) * E)
      lhs == rhs
    }).getOrElse(0)
  }

  (1 to 5).foreach(d => println(n(d)))
}

Answer 11

05AB1E, 14 bytes

(°žrDr%/;12z+ï

Try it online!

Direct translation of my Mathematica solution, with help from @CommandMaster. Works only up to d=7 because of machine-precision issues.

disassembly:

      stack
----------------------------------
      n
(     -n
°     10^(-n)
žr    10^(-n)  e
D     10^(-n)  e  e
r     e  e  10^(-n)
%     e  e%10^(-n)
/     e/(e%10^(-n))
;     e/(e%10^(-n))/2
12    e/(e%10^(-n))/2  12
z     e/(e%10^(-n))/2  1/12
+     e/(e%10^(-n))/2+1/12
ï     floor(e/(e%10^(-n))/2+1/12)