Numbers of distinct values obtained by inserting $+ - \times \div ()$ in $\underbrace{2\quad2 \quad2 \quad2\quad...\quad 2}_{n \text{ times}}$

Question

This question is inspired by How many values of $2^{2^{2^{.^{.^{.^{2}}}}}}$ depending on parenthesis? (By the way, I sincerely hope this kind of questions can receive more attention)

Insert $+ - \times \div ()$ in $$\underbrace{2\quad2 \quad2 \quad2\quad...\quad 2}_{n \text{ times}}$$ Denote the number of distinct values which can be obtained in this way by $D(n)$. Is there a general formula (or recurrence relation at least) for $D(n)$?

This is basically the $+ - \times \div ()$ version of @barakmanos question. It seems this question is easier than the power tower version. Or maybe not?

For $n=1$ , there is only $2$ values $-2,2$;

For $n=2$, there are $5$ values $-4,-1,0,1,4$;

For $n=3$, there are $13$ values $-8,-6,-3,-2,-1,-\frac{1}{2},0,\frac{1}{2},1,2,3,6,8$;

And for $n=4$ I'm reluctant to calculate with bare hands. (See @DanUznanki answer for what follows)

Any idea is appreciated. Sorry if this is a duplicate.

Edit: My research shows that the version with distinct generic variables $a_1,a_2,...,a_n$ is solved. See A182173 for your reference.

Answer 1

It looks like we can do this "inductively": for the calculations of size $n$, we can take values from the list for $1 \le k\le n/2$, and values from the list for $(n-k)$, and operate on them using the 64 different operation orders.

Fortunately, it's really only 10 classes of operation, because many are duplicates:

• There's four values we can get from addition and subtraction: $a+b$, $-(a+b)$, $a-b$, and $b-a$.
• There's only two we can get from multiplication: $ab$ and $-ab$.
• There are four cases we can get from division: $a/b$, $b/a$, $-a/b$, and $-b/a$.

Also conveniently we only need to try the nonnegative entries in previous lists.

So for $n=4$, we have:

$-16$, $-12$, $-10$, $-8$, $-6$, $-5$, $-4$, $-3$, $-5/2$, $-2$, $-3/2$, $-1$, $-2/3$, $-1/2$, $-1/3$, $-1/4$, $0$, $1/4$, $1/3$, $1/2$, $2/3$, $1$, $3/2$, $2$, $5/2$, $3$, $4$, $5$, $6$, $8$, $10$, $12$, $16$

Which is $33$ entries.

I've written a short script which finds them all, and told it to run up to $n=10$, which gave the following sizes: $2,5,13,33,77,185,441,1051,2523,6083$. Apparently this sequence is not in OEIS, nor is the positive-values-only version! I am very surprised.

Answer 2

@Dan Uznanski if your results are correct i noticed that the ratio between the successive terms of the sum is almost constant. So maybe:

Conjecture

$$D(n) \sim K^n $$

Where:

$$2.3\leq K \leq 2.5 $$