17
$\begingroup$

If you are first time reading this, you may want to read the summary section last.



Solution summary and questions

Sequence values

If the allowed operations are $(+,-,\times,\div)$ and parentheses $(\space)$, then the $f(n)$ is the number of consecutive integers we can make starting at $1$, given $n$ "digits" that each needs to be used exactly once. Equivalently, it is the largest integer we can make such that all smaller integers $\in\mathbb N$ can be made as well.

The $d$ is (optimal?) digit set used, where $d=\{d_1,\dots,d_n\}=(d_1,\dots,d_n)\in\mathbb N^n$.

So far I have the following data given $n=1,\dots,5$ digits to use (best so far):

\begin{array}{ccccccc} n & 1&2&3&4&5&6\\ f(n)& 1 & 3 & 10 & 52 & 351 & ? \\ d & \{1\} & \{1, 2\} & \{1, 2, 4\} & \{2, 3, 4, 22\} & \{3, 6, 8, 12, 37\} & ? \end{array}

The $1,3,10$ are optimal. The $52$ entry is probably optimal, but I'm not sure if this can be proven.

The $f(5)\ge 351$ can be obtained using $\{3, 6, 8, 12, 37\}$. I don't think it can be better.

Notice the weird similarity to the $A052446$ sequence. Pure coincidence?

$Q_1$: Is there any reason to suspect $f(4)=52,f(5)=351$ aren't the optimal solutions?

I haven't computed $f(n)$ for $n\ge6$ significatnly, I do not know how to do it efficiently.

There is a similar sequence such that $A142153(n-1)$$\approx f(n)$. The main difference being that linked sequence does not require all digits to be used when building a single number, giving it more freedom and expected larger terms than my sequence. The offset $(n-1)$ is due to it starting at $n=0$.

$Q_2$: Can we find (compute) significant (lower bounds) $f_d(n)$ for $n\ge 6$?

I've found so far $f_d(6)\ge 2200$ using $d=\{2, 10, 13, 30, 49, 56\}$.

This was done with a simple c++ search checking random digit sets: run it on repl.it.

I want to thank user TheSimpliFire for helping me run the code for $f(6)$. - The goal was to reach $f(6)\gt 3000$ if possible, but it looks hard unless the search can be optimized.


Lower bound

"Weak" lower exponential bound is known: $f(n)\gt 2^{n/3}$.

This is based on a related problem that allows only $1$'s and $(+,\times)$. - "Complexity of $n$".

This can be imporoved:

We can using $d=\{1,2,4,\dots,2^{n-1}\}$, show that the following lower bounds hold:

  • $f(n)\ge 2^n-1,n\ge 1$, which confirms optimal $f(1),f(2)=1,3$.
  • $f(n)\ge 2^n+2,n\ge 3$, which confirms optimal $f(3)=10$.
  • $f(n)\ge 2^n+10,n\ge 4$, which gives sub-optimal $f(4)\ge26$. Twice less than $f(4)=52$.

These bounds not hard to construct since this $d$ set has nice inductive properties.

But I haven't noticed a pattern that can be generalized to all $n$. It looks hard.

The best we can do with this set $d=\{d_i=2^{i-1},i=1,\dots,n\}$ of digits is:

$$f(n)\ge f_{d}(n)= 2^n-1+g(k)$$

where $g(k)=0,0,3,11,45,533\dots$ for $n\ge k$ where $k=1,2,3,4,5,6,\dots$

$Q_3:$ The $2^n$ grows slower than $g(k)$, for large $n$. Can we demystify $g(k)$ in terms of $n$?

Equivalently, What is the smallest number that can't be made using powers of two?

Seems $f_d(n)=2^n+g(k)\ll f(n)$ for large $n$ for this $d=\{d_i=2^{i-1},i=1,\dots,n\}$.

Notice this $d$ is optimal for $n\le 3$. Can we find better digit sets for $n\ge 4$?

$Q_4:$ What's a better set $d$ for which we can show higher lower bounds, in terms of on $n\ge 4$?



Problem

Up to how many consecutive integers $\in\mathbb N$, can be made using only the four basic operations:

  • $+$ addition, $-$ subtraction, $\times$ multiplication, $\div$ division

Given $n$ numbers ("digits") as building blocks, if parentheses are allowed?

The goal is to build all integers from $1$ to $N$, while maximizing $N$, for given $n$ amount of digits.

We are given $d\in\mathbb N^n$ natural numbers ("digits") to work with.

We define $f_d(n)$ as maximal $N$ reachable using digits $d$, and $f(n)$ as maximal $f_d(n)$, given $n$.


Example

Lets take $n=4,f_d(4)$ for example. We can try using $d=\{4,4,4,4\}$ four fours,

\begin{array}{} 1 &= (4 + 4 - 4) \div 4 \\ 2 &= 4 - ((4 + 4) \div 4) \\ 3 &= (4 + 4 + 4) \div 4 \\ 4 &= ((4 - 4) \times 4) + 4 \\ 5 &= ((4\times4)+4)\div4 \\ 6 &= ((4 + 4) \div 4) + 4 \\ 7 &= 4 - (4\div4 - 4) \\ 8 &= (4 + 4 + 4) - 4\\ 9 &= (4\div4 + 4) + 4 \end{array}

And see that $f_{\{4,4,4,4\}}(4)=9$, because if you try hard enough, $10$ can't be made!

This means that $f(4)\ge f_d(4)= 9$ is at least nine.

We probably need a better set of digits $d$ to use, to make $10$ and beyond.


Definitions

The digit set $d$ allows duplicate digits, and exactly $n$ digits (elements), and all digits (elements) must be used exactly once.

Given a fixed set of $n$ digits $d=\{d_1,\dots,d_n\}$, we can construct consecutive integers from $1$ to $N\in\mathbb N$ using the basic operations and parentheses, but we can't construct $N+1$. Then we define the value $f_d(n)=N$.

Then we can define $f(n)=\max f_d(n)=N_{\text{max}}$, for $d\in\mathbb N^n$. That is, maximized $N$ obtained by using the optimal set of digits $d=\{d_1,\dots,d_n\}$ for a given case of using $n$ digits.

How to efficiently calculate, practically prove, $f(n)$ for given $n$?

The sets of digits are not ordered, so naturally:

WLOG we can assume $d_1\le d_2\le \dots \le d_n\implies d_n=\max\{d_1,\dots,d_n\}$. Keep this in mind.


Clarifications

All integers $1,2,3,\dots,N$ must be constructed; Using all digits from digit set $d$ exactly once.

"Concatenation" is not allowed. That is, combining digits like $\{1,1\}$ to make $11$ is forbidden.

We are after optimal $d=\{d_1,\dots,d_n\}$ that will allow us to construct the longest such sequence by applying the basic operations $+,-,\times,\div$ to the given digit set, when talking about maximal $N$.


Solving small cases

Cases $n=1,2$

Trivially, $f(1)=1$ for $d=\{1\}$, since we can't apply binary operations to a single digit.

It can be easily seen that $f(2)=3$ is best, using optimal digits set $d=\{1,2\}$, here:

$$\begin{array}{} 1 &= 2 - 1 \\ 2 &= 2 \times 1 \\ 3 &= 2 + 1 \\ \end{array}$$

This is optimal: Since if we are given $d=\{d_1,d_2\}$, if not $d_2-d_1=1$ or not $d_1=d_2$, we can't make $1$, thus $f_d(2)=0$ in these $d$ cases. And we can't make $2$ unless they either add up to two, differ by two, or one is two times other. The only case that also extends to $3$, is the $d=\{1,2\}$ making this $f(2)=3$ proof easy.

Case $n=3$

It can be shown $f(3)=10$ if you observe enough cases. It can be seen that $f_d(3)= 3$ at best, if $d_3$ is too large. I have checked the rest (small enough) cases computationally.

The optimal set is $d=\{1,2,4\}$ and the solutions can be seen below:

$$\begin{array}{} 1 = 4 - (1 + 2) \\ 2 = 4 - (1 \times 2) \\ 3 = (1 - 2) + 4 \\ 4 = (2 - 1) \times 4 \\ 5 = 4 - (1 - 2) \\ 6 = (1 \times 2) + 4 \\ 7 = (1 + 2) + 4 \\ 8 = (1 \times 2) \times 4 \\ 9 = 1 + (2 \times 4) \\ 10 = (1 + 4) \times 2 \\ \end{array}$$

Case $n=4$

The $f(4)=52$ is a conjectured solution, using $d=\{2,3,4,22\}$.

The previous records are $f_{\{1, 2, 5, 6\}}(4)=43, f_{\{1, 2, 5, 8\}}(4)=51$.

I have checked all $d_4\lt 64$, and tabulated maximal $N=y$ for subsets of digits such that $d_4=x$:

enter image description here

Is it possible to prove $f(4)=52$?

Update: I extended the calculations to $d_4\le 100$ and the $52$ indeed seems to be optimal.

A similar problem to $f(4)$, but roots and exponentiation are allowed, was asked.


Computing larger cases

Cases $n\ge 5$

Is it possible to set up bounds or make progress in calculating these cases?

If not, can we optimize the computation?

I'm running a brute force search.

For this result, all sets of digits with $d_5\le 15$ have been checked with record being $f_{\{2, 8, 9, 12, 13\}}=271$. But this is going on too slow in my python code to extend further. (Code based on this four fours solver.)

So I've decided to not brute force all sets, but try ones with $d_1,d_2=1,2$ or $d_1,d_2=2,3$ and $d_3\le d_4/2$, for $d_5\ge 20$. I've reached $d_5=45$ so far, with these restrictions on $d_1,d_2,d_3$.

This is where $f_{\{2, 3, 7, 8, 38\}}=324$ was found: seen solutions.

Update: I've implemented the search in c++ which is faster now.

I've checked all digits up to $d_5 \le 35$ so far, where the best was $f(5)=333$.

I've also checked a restricted search where $d_5\le 120$ but $d_4\le 12$ so far, which is where the newest $f(5)=351$ was found. I've also checked a restricted search where $d_5\le 60$ but $d_4\le 24$ so far, with no better results.


Growth of $f(n)$?

Can we analyse and give bounds on growth of $f(n)$?

The best I have so far is: using $d_i=2^{i-1}$ to show $f(n)\gt 2^n,n\gt 2$.

Here is "weak" linear bound (explicit construction) example to get inspired:


Weak linear lower bound (explicitly constructive)

For $d$, we pick $\{1,\dots,1\}$ all $1$'s. We can then make $1,\dots,2n-4$ easily:

$$\begin{array}{} 1 &= (1+1)-(1\times1\times\dots\times 1) &= 2 - 1\\ 2 &= (1+1)\times(1\times1\times\dots\times 1) &= 2 \times 1\\ 3 &= (1+1)+(1\times1\times\dots\times 1) &= 2 + 1\\ 4 &= (1+1)+1+(1\times1\times\dots\times 1) &= 2 + 1 + 1\\ \dots & & \\ n &= (1+1)+(1+1+1+\dots+ 1) &= 2 + (n-2) \\ n &= (1+1)\times(1+1)+(1+1+\dots+ 1) &= 2\cdot2 + (n-4) \\ n+1 &= (1+1)\times(1+1+1)+(1+\dots+ 1) &= 2\cdot3 + (n-5) \\ n+2 &= (1+1)\times(1+1+1+1)+(1+\dots+ 1) &= 2\cdot4 + (n-6) \\ \dots & & \\ 2n-4 &= (1+1)\times(1+1+1+\dots+ 1) &= 2(n-2) + (n-n) \end{array}$$

We have now shown $f(n)\ge 2n-4$ with this trivial digit set.

Note that this works if we replace $(1+1)$ with $(d_n\div d_{n-1})$ if $d_{n-1}=d_n/2$, so we also have an infinite family of digit sets that can achieve at least $2n-4$, since $d_n\in\mathbb N$ can be any digit.

Perhaps instead of $(1+1)$, we can use this and pick $d_n/2=2n-3$ to continue the construction? Note that we could also replace other $1$'s with similar substitutions and keep the initial construction still valid.

Can we do better with this idea, and show it is better than exponential bound given below?

This idea was discussed by user @Countingstuff in the comments (second-by-date comment).


Exponential lower bound (based on a related problem)

The bound is "weak" due to ignoring $(-,\div)$ operations, and due to using only $1$'s as digits.

Lets restrict the problem to only $(+,\times)$ operations, and define this restricted $\overline{f}(n)$. We have:

$$ f(n)\ge \overline{f}(n) $$

By definition. For $\overline{f_d}$, optimal $d$ consists of pure $1$'s, since otherwise, $N=1$ can't be made.

Now this becomes related to the "Complexity of natural number $n$" problem. That is, $a(N)$ - minimal number of $1$'s for expressing $N$ using $1$'s and $+,\times$. Now, this has known bounds:

$3\log_2N \ge a(N) \ge 3\log_3N$,$\space$ [R. K. Guy, Unsolved Problems in Number Theory, Sect. F26.].

The upper bound is obtained by expanding $N$ in binary with Horner's algorithm. Improving the upper bound is still an open problem.

We will use the upper bound for $a(N)$ to get the "weak" lower bound for $f(n)$.

If $N_0$ some number, notice that $a(N_0)$ defines the price of building $N_0$, in terms of the amount of digits. And since the price $a(N)$ is bounded above by a monotone increasing function, if we can build $N_0$ with at least the bound given amount of digits, we can also build numbers $1,\dots, N_0$ with that many or less digits, thus $N\ge N_0$.

Also, an important fact is that if we can build $N_0$ with $n$ digits, we can build it with $\ge n$ digits as well. This is due to optimal $d$ being a set of $1$'s for restricted $\overline{f_d}$, so we can multiply two digits $1$'s to reduce the case of digits, down to $n$, for every case $\gt n$.

So, by the definition of $a(N)$ and $\overline{f}(n)$ we have:

$$\begin{array}{} k(N)\ge a(N_0) \implies \overline{f}(k(N_0))\ge N_0 \\ \end{array}$$

So we can use the result on bounds of $a(N)$ to establish:

$$ 3\log_2N_0 \ge a(N_0) \implies \overline{f}(3\log_2 N_0)\ge N_0 \implies \overline{f}(n)\ge 2^{n/3} $$

By substitution $n=3\log_2 N_0\implies N_0=2^{n/3}$. We have obtained:

An exponential lower bound for the original problem, $f(n)\ge 2^{n/3}$ follows from $f(n)\ge\overline{f}(n)$.

But note that $f(n)\gt 2^{n/3}$ it actually certainly strict. For example, last two digits can be $d_0,d_0$ where $d_0=\frac12 2^{(n-1)/3}$. The $(d_0/d_0)=1$ leaves us with $n-1$ case of $1$'s, so we can reach $2^{(n-1)/3}$ at least. Now use $(d_0+d_0)=2^{(n-1)/3}$. Now we are left with $n-2$ case of $1$'s free to use again. Which means we can reach at least $2^{(n-1)/3}+2^{(n-2)/3}\gt 2^{n/3},n\gt 3$.

I believe $f(n)\gg \overline{f}(x)\ge 2^{n/3}$ is actually much greater than this "weak" bound.


Questions regarding bounds

Can we improve this by getting a "non-weak", and better bound? - Perhaps use the fact that $(-,\div)$ allows extending the explicit weak linear construction I mentioned earlier?

Can we obtain non-trivial upper bounds?

A trivial upper bound can be the upper bound on number of (not necessarily consecutive) distinct positive integers that can be built with the given operations and $n$ digits.

I'm not sure how I would establish a non-trivial upper bound. - Bound that uses the fact that integers are consecutive. Idea is to find upper bound on the "hole" that breaks the consecutive sequence?


Update on lower bound

The $f(n)\gt 2^n,n\gt 2$ was included in the summary section at the beginning, more details are there.



Partial answers answering any point of this question are appreciated.

$\endgroup$
7
  • $\begingroup$ It's not clear why $\{1,3\}$ isn't a better two-digit set. $\endgroup$ Aug 17, 2019 at 10:23
  • 3
    $\begingroup$ I only have an observation for your last question. Suppose f(n) = N, so f(n) >= N -1 and either N or N - 1 even. But now take D = {d_1, ..., d_n} a witness to f(n). Now consider D = {d_1, ..., d_n, N, N / 2, N /2}, (or (N - 1) / 2 if N - 1 even). Well with D we can make 1 to N in the way from before + (N - N / 2 - N / 2), and can also make N + 1 to N via the same from before + (N + N / 2 - N / 2). Meaning d_(n + 3) >= 2(d_(n) - 1) implying some exponentional bound. $\endgroup$ Aug 17, 2019 at 10:35
  • $\begingroup$ @PeterTaylor Forgive me for not clarifying that properly. - Just to clarify fully: $\{1,3\}$ has maximal $N=0$ since it can't build $1$. When finding $f(n)=N$ where $N$ is maximal, we need to be able to build all consecutive numbers from $1$ to $N$. We can't have any holes in the sequence. We also must use all digits in the set; Like puzzle pieces from a puzzle box. I hope everything else is clear enough. $\endgroup$
    – Vepir
    Aug 17, 2019 at 11:17
  • $\begingroup$ Is non-exact division allowed ? $\endgroup$
    – user65203
    Aug 18, 2019 at 20:50
  • $\begingroup$ @YvesDaoust Integer division is not allowed. The $\div$ is an exact fraction. Neither is rounding, floor, ceiling, or other functions that are not the classic four basic operations $(+,-,\times,\div)$. $\endgroup$
    – Vepir
    Aug 18, 2019 at 20:55

0

Your Answer

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

Browse other questions tagged or ask your own question.