22
\$\begingroup\$

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 ; 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
\$\endgroup\$
4
  • 3
    \$\begingroup\$ Hi! Did you calculate these numbers? Are you suggesting that oeis a(8) is wrong? \$\endgroup\$
    – ZaMoC
    May 21, 2023 at 14:18
  • \$\begingroup\$ Unfortunately, the first link is now dead :( \$\endgroup\$ May 21, 2023 at 20:01
  • 2
    \$\begingroup\$ @ZaMoC tio.run/##FY2xCsIwEEB3v8Ldi80NLoIuYicHEcEhnBKbWA/… \$\endgroup\$ May 22, 2023 at 0:18
  • 3
    \$\begingroup\$ nice! Since you are a contributor to oeis, I think you should update the entry and also add the mma code \$\endgroup\$
    – ZaMoC
    May 22, 2023 at 1:22

11 Answers 11

7
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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!

\$\endgroup\$
6
  • 1
    \$\begingroup\$ To construct the limit in Mathematica, with n[x_] = x/(E^(-LambertW[-1, -Log[x]/x]) - x) we have Assuming[0 < x < E, Series[n[x], {x, E, 1}]] returning -E/(2 (x - E)) - 11/12 - 5 (x - E)/(72 E) + O[x - E]^2. \$\endgroup\$
    – Roman
    Jun 9, 2023 at 6:47
  • 1
    \$\begingroup\$ In 05AB1E you can do °Džr*1%·/žr*12z+ï for 17 bytes, although both this and your implementation fail for values larger than 7 due to floating-point inaccuracies \$\endgroup\$ Jun 9, 2023 at 10:44
  • 1
    \$\begingroup\$ Ah yes, of course with a modulo operation! Yes, 05AB1E is not very precise; but that's no fault of the code. \$\endgroup\$
    – Roman
    Jun 9, 2023 at 12:51
  • 1
    \$\begingroup\$ Oh, using modulo \$10^{-d}\$ you can get the 05AB1E solution to 14 bytes. I only thought about mod 1. \$\endgroup\$ Jun 9, 2023 at 14:30
  • 1
    \$\begingroup\$ Yes, see the solution I’ve written up elsewhere! \$\endgroup\$
    – Roman
    Jun 9, 2023 at 14:51
4
\$\begingroup\$

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.

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

Wolfram Language (Mathematica), 51 bytes

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

Try it online!

-2 bytes from @Roman

\$\endgroup\$
1
  • \$\begingroup\$ 51 bytes \$\endgroup\$
    – Roman
    Jun 8, 2023 at 19:40
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 46 bytes

NθP×ψ⁺²θ¤≕E≔¹ηW‹÷×XχθX⊕ηηXηηI⪫ΦKD⁺²θ→⊖λω≦⊕η⎚Iη

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

Nθ

Input d.

P×ψ⁺²θ¤≕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.

W‹÷×XχθX⊕ηηXηηI⪫ΦKD⁺²θ→⊖λω

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

≦⊕η

... increment n.

⎚Iη

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:

≔XχNθ≔¹η≔⁰ζW↨÷÷×θX⊕η⊕ηXηη⟦⊕ηη⟧±¹≦⊗ηW∧⊖⁻ηζ÷⁺ηζ²¿↨E⟦ηι⟧÷×θX⊕κκXκκ±¹≔ιζ≔ιηIη

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

≔XχNθ

Input 10ᵈ.

≔¹η≔⁰ζ

Start with bounds of 0 and 1.

W↨÷÷×θX⊕η⊕ηXηη⟦⊕ηη⟧±¹≦⊗η

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

W∧⊖⁻ηζ÷⁺ηζ²¿↨E⟦ηι⟧÷×θX⊕κκXκκ±¹≔ιζ≔ιη

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

Iη

Output the resulting n.

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

Vyxal, 124 bitsv1, 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
\$\endgroup\$
6
  • \$\begingroup\$ I'm not sure I understand this: if I delete the command (so the evaluation is just to n decimal places, right?), then input of 0 gives an output of 2. But since 1**10 is the same as 1, why didn't it stop there as the first positive integer to satisfy the condition...? Subsequent outputs for 1 & 2 seem Ok, as I expected from looking at how n increases fast compared to d... \$\endgroup\$ May 24, 2023 at 13:03
  • \$\begingroup\$ @DominicvanEssen Sorry, that should read 10 ** n rather than n ** 10 \$\endgroup\$
    – lyxal
    May 24, 2023 at 13:11
  • \$\begingroup\$ Ah! Thanks. Do you happen to have a 1-byte n+1 that you could use instead, so the code could actually run for d>0...? (I realise that this is completely optional for code-golfing, of course...) \$\endgroup\$ May 24, 2023 at 13:47
  • \$\begingroup\$ @DominicvanEssen in testing, n+1 didn't actually generate enough decimals for d=1. Neither did n+2, which are the only n + x built-ins - hence that would make the answer invalid \$\endgroup\$
    – lyxal
    May 24, 2023 at 13:51
  • \$\begingroup\$ Hm, that's funny. I would imagine that when d=1, any number of decimal places greater than 2 would be irrelevant, since it'll be sliced to d+2 = 1 decimal place anyway (with a value of 2.7). And 2 decimal places is what you'd already get for n+1 when n=1... \$\endgroup\$ May 24, 2023 at 14:07
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ May 24, 2023 at 13:24
1
\$\begingroup\$

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 to account for the dot.

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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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