3
$\begingroup$

Given the numbers 1, 2, ..., n the puzzle is to try to make a number as close as possible to the mathematical constant $e$ using only the four mathematical operations +, -, *, / and parentheses (brackets). You don't have to use all the numbers and you are not allowed to stick digits together to make new numbers for example. Each number can be used at most once. Recall that $e \approx 2.7182818284590452353602874713\dots$.

  • So if n = 1 the best answer is 1, clearly;
  • for n = 2 it is 3,
  • for n = 3 it is $3 - 1/2 = 2.5$, and
  • for n = 4 it is $3-1/4 = 2.75$.
  • for n = 5 it is $3+1/((2/5)-4)=2.722222\dots$.

Give your best answer for n = 1 up to 20. That is, give a possibly different answer for each n up to 20.

This is related.

Improve this question
$\endgroup$
3
  • $\begingroup$ @bobble No, although 1-4 seem optimal. $\endgroup$
    – Simd
    Commented Jan 6 at 15:19
  • $\begingroup$ 2 is definitely optimal… $\endgroup$
    – Someone
    Commented Jan 7 at 16:29
  • 1
    $\begingroup$ Oooh I only saw the Pi version of this question. Looks fun! $\endgroup$
    – Dmitry Kamenetsky
    Commented Feb 8 at 8:43

2 Answers 2

Reset to default
4
$\begingroup$

An incomplete answer. Sorry about the lack of spoiler format – tables do not work inside it.

I think my answers from 1 to 7 are optimal because the generating code completed. Beyond there not all the digits are being used. The 8 and 9 are no better than 7, and after 10 I'm not even finding results that are good enough to post.

Max Used Value Error Expression
1 1 1.0000000000000000 1.7182818284590451 $ 1 $
2 2 3.0000000000000000 0.2817181715409549 $ 1 + 2 $
3 3 2.5000000000000000 0.2182818284590451 $ 3 - \frac{1}{2} $
4 3 2.7500000000000000 0.0317181715409549 $ 3 - \frac{1}{4} $
5 5 2.7222222222222223 0.0039403937631772 $ \frac{1}{\frac{2}{5} - 4} + 3 $
6 6 2.7187500000000000 0.0004681715409549 $ 2 - \frac{\frac{1}{4} - 6}{3 + 5} $
7 7 2.7182539682539684 0.0000278602050767 $ 3 - \frac{1}{7} - \frac{\frac{5}{6}}{2 + 4} $
8 7 2.7182539682539684 0.0000278602050767 $ \frac{\frac{5}{6}}{2 - 8} - (\frac{1}{7} - 3) $
9 8 2.7182539682539684 0.0000278602050767 $ (\frac{3}{7} - 4 \times 5) \times (\frac{1}{9} - \frac{2}{8}) $
10 8 2.7182795698924731 0.0000022585665720 $ \frac{\frac{4}{3} - 6 \times 9}{\frac{5}{8} - 2 \times 10} $
11 8 2.7182866556836904 0.0000048272246453 $ \frac{(1 - 4) \times 5 \times 10}{\frac{9}{11} - 7 \times 8} $

Some of the expressions could be arranged more cleanly but that's the way they came out of my home-made number contraption.

Method:

I work with three tree structures, keyed by value. There is a main 'library' tree which starts empty, and two others which alternate in usage. Initially the library is empty, and I insert each of the permitted values into a 'working' tree.

The loop begins by inserting every item from the working tree into the library tree.
It then parses the working tree again, making arithmetic operations with each library entry, checking for number duplications, and it builds a 'next' working tree with the results. It then swaps the working trees, clears the next working tree and repeats the loop. The $O(n^2)$ complexity is not very efficient.

Each tree node is keyed by value, and has a linked list of all the ways the value can be made. A new value using the same numbers as before replaces the old one if there were fewer operations needed to build it, or is discarded. If an existing value uses a subset of the new value's source numbers, the new value is discarded. Otherwise it is added to the node's linked list.

Whenever a new value is inserted into the tree, it's difference from $e$ is calculated, and the best one is remembered.

Above $7$ I run out of storage memory.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Our of interest, does 2721/1001 figure in your list at all? $\endgroup$
    – Simd
    Commented Jan 7 at 17:56
  • $\begingroup$ No, because I do not keep values outside the range -1000 to +1000. That could mean my 'definite' answers are incomplete. I could try another run without that limitation, or a broader constraint. $\endgroup$
    – Weather Vane
    Commented Jan 7 at 18:03
  • $\begingroup$ For which range do you expect 2721 and 1001 to be generated from distinct numbers? The 2721 and 1001 are both larger than $6!$, and of course the base numbers can't be replicated. $\endgroup$
    – Weather Vane
    Commented Jan 7 at 23:25
  • $\begingroup$ I only mentioned it because it is an optimal fractional approximation of e according to johndcook.com/blog/2021/03/27/smallest-fraction . For my related question about pi, 355/113 does appear. $\endgroup$
    – Simd
    Commented Jan 7 at 23:29
  • $\begingroup$ I had wondered if I could use one of the series for $e$ shown here but they all use the base numbers more than once, especially $1$. $\endgroup$
    – Weather Vane
    Commented Jan 7 at 23:34
2
$\begingroup$

step1: Continued fractions
Continued fractions give good approximation with relative low numbers:
continued fraction e = 2; 1,2, 1,1,4, 1,1,6, 1,1,8, 1,1,10, 1,1,12, 1,1,14 ....
step 2: Prime factorizations
-it must be possible to make the denominator without use of divide!
- multiplications should be used as much as possible to get to high numbers
- N/PxQxR can be written as a/P+ b/Q+ c/R if P,Q,R are relative prime, which gives a lot of flexibility

2;1,2,1,1,4,1,1,6,1,1 = 2721/1001 (error 1.1E-7)

= 2721/(7x11x13)
= 4/7+2x8/(5+6) +9/(10+3) Old solution n=10
Solution for n=9:
= 3 + 2/77 - 4/13 = 3 + 2/(8x9+5) + 4/(6+7)

2;1,2,1,1,4,1,1,6,1,1,8 = 23225/8544 (error 6.7E-9)

23225/(3x32x89) = 5x2/6 + 11/(4x8) + 7x(12-3)/(9x10-1) Old solution n=12
Solution for n=11:
= 2+ 1/96 + 26/89 = 3+1/(8x(5+7) + (6x4+2) /(9x11-10)

2;1,2,1,1,4,1,1,6,1,1,8,1,1 = 49171/18089 (error 7.7e-10)

3- 5,096/18089 = 3 - 2x2x2x7x7x13/18089
Solution for N=14:
3 - 4x7x13x14/((((2+5+12)x8x6-11)x9x10) -1)

Improve this answer
$\endgroup$

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