25
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Based on what you say for $n=1$ and $n=2$, we may use $-$ as either the negation operator on one number or the subtraction operator between two numbers? $\endgroup$
    – 2'5 9'2
    Mar 24, 2019 at 4:53
  • $\begingroup$ @alex.jordan Yes. $\endgroup$
    – YuiTo Cheng
    Mar 24, 2019 at 4:59
  • $\begingroup$ OK. I wonder if you did not allow $-$ to be unary negation, if then the sequence might appear in OEIS. We have an overloaded symbol, $-$. And one of its meanings happens to be unary negation. It's odd that we don't have a symbol for unary inversion. Well, we do: $^{-1}$. But it does not reuse the division symbol $\div$. All this is just to say that it feels like the special double meaning for $-$, that is not mirrored with $\div$, could break what would otherwise be a simpler pattern in the sequence of counts. $\endgroup$
    – 2'5 9'2
    Mar 24, 2019 at 5:22
  • $\begingroup$ @alex.jordan If we disallow $-$ to be a unary operator, will things become vastly simpler? $\endgroup$
    – YuiTo Cheng
    Mar 24, 2019 at 5:27
  • 1
    $\begingroup$ @alex.jordan: I once toyed with the idea of "$/$" for unary inversion. (So, "$/2$" means "$1/2$" in the same way that "$-2$" means "$0-2$".) I still kinda like it. :) $\endgroup$
    – Blue
    Mar 25, 2019 at 20:09

2 Answers 2

Reset to default
9
+50
$\begingroup$

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.

$\endgroup$
14
  • $\begingroup$ You mentioned we can do it 'inductively', do you have any clue about the recurrence relation? $\endgroup$
    – YuiTo Cheng
    Feb 20, 2019 at 13:31
  • $\begingroup$ Not sure, but it isn't gonna be nice. actually, different values for $x$ instead of $2$ give different results: using $3$ gives $2$, $7$, $21$, $67$, using $4$ gives $2$,$7$,$21$,$77$. Interestingly, when I tried to get the generic result, where $x$ is just $x$, I did get some partial results in the realm of restricted lattice walks: $2$,$7$,$23$,$91$, $347$ appears twice in OEIS. $\endgroup$
    – Dan Uznanski
    Feb 20, 2019 at 13:39
  • $\begingroup$ Interesting. What about the original power tower question? Compared with this, which one do you think is simpler? $\endgroup$
    – YuiTo Cheng
    Feb 20, 2019 at 13:45
  • $\begingroup$ for generic $x$ in the power tower thing you're getting exactly the Catalan Numbers. But assuming you have the ability to actually store the numbers you're working with, the power tower version is vastly simpler: there's only one operator instead of 10. $\endgroup$
    – Dan Uznanski
    Feb 20, 2019 at 13:46
  • 1
    $\begingroup$ What about the case without bracket? $\endgroup$
    – YuiTo Cheng
    Feb 21, 2019 at 3:36
3
$\begingroup$

@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 $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .