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