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