10
$\begingroup$

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)?

  • 0
    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 useful2011-11-21

2 Answers 2

3

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.

  • 1
    The number of distinct prime factors of $n$.2011-11-29
3

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