# An interesting way of producing positive integers

If we define $$\cal N _1 := \{ 1\}$$ and by induction $$\cal N_{n+1}:=\{x\in \mathbb N | \exists a,b \in\cal N_n : x= a+b \text{ or }x=ab \text{ or }x=a^b \}$$ it's easy to prove that, for every $m \in \mathbb N\backslash \{0\}$, there exists $n\le m$ such that $m\in \cal N_n$.

If we define $\deg (n):= \min\{m\in \mathbb N | \;n\in\cal N_m\}$ (let's call it degree of n), can you find a way to calculate the degree of every positive integer (which is at least better than brute force)?

-
An easy upper bound is $\deg(n) \le \log_2(n) + 1$. (The number of steps using only addition.) – p.s. Nov 20 '11 at 16:15
The right bound should be $\deg(n) \le \lceil{\log_2(n)}\rceil + 1$. Ah well, Eric beat me to it... – Raskolnikov Nov 20 '11 at 17:19
@Raskolnikov: ;) but I accidentally didn't put in \leq so I will delete my comment. – Eric Naslund Nov 20 '11 at 17:46
Yes, thank you for this upper bound! It's not what I directly wanted but I appreciate it since it's both simple to prove and useful – Lorenzo Cavallina Nov 21 '11 at 14:46

It's very unlikely, even if you remove exponentiation and leave only addition and multiplication.

As Erdos said of the Collatz conjecture, "Mathematics is not yet ready for such problems." The difficulty is the mixture of addition and multiplication, which leaves the problem with little exploitable structure. Other very difficult problems of this nature, in addition to the Collatz conjecture, include the Goldbach conjecture, the infinitude of primes of the form $x^2+1$, etc.

While I'd be surprised if there were an easy way to exactly compute the degree of a number, you can of course try to prove bounds. One obvious improvement to p.s.'s, for composite numbers: $$\deg(n) \leq 1+\log_2 \omega(n) + \log_2 \max(P(n), Q(n))$$ where $P(n)$ is the largest prime in $n$'s prime factorization and $Q(n)$ is the largest power.

-
I don't understand what you mean by $\omega(n)$. – Lorenzo Cavallina Nov 29 '11 at 12:00
The number of distinct prime factors of $n$. – user7530 Nov 29 '11 at 12:29

The problem with just addition is already a hard problem and the subject of much research. The keyphrase to search for is addition chain.

-