# What is the natural density of hyper prime numbers?

What do we mean by hyper prime numbers? Well, roughly speaking they are natural numbers which are prime with respect to hyperoperators in arithmetic such as exponentiation, tetration, pentation, et cetera.

The common soul of these generalized prime numbers is their irreducibility to the smaller numbers with respect to the given hyperoperator; the same property that distinguishes usual primes from other natural numbers. In fact, such numbers don't arise as a non-trivial combination of smaller building blocks. The underlying combination method could be multiplication, exponentiation or any other hyperoperation.

Definition 1. We call addition, multiplication, exponentiation, tetration,... , the $1$-hyperoperator, $2$-hyperoperator, $3$-hyperoperator, $4$-hyperoperator, ... respectively and use the $*_n$ notation to denote the $n$-hyperoperator for $n\geq 1$.

Definition 2. For any $n\geq 1$, the natural number $p>1$ is called a $n$-hyperprime number if there are no $i,j<p$ such that $p=i*_{n}j$.

Remark 1. Note that according to the definition, there are no $1$-hyperprime numbers, simply because every natural number greater than $1$ arises as the addition of two smaller natural numbers. $2$-hyperprime numbers are exactly the usual prime numbers and the set of $3$-hyperprime numbers consists of usual primes and numbers like $12$ which don't arise as the exponentiation of two smaller numbers. In general, if $p>1$ is a $m$-hyperprime number for some $m\geq 1$ then it is $n$-hyperprime for any $n>m$.

Remark 2. It is intuitively clear that almost all natural numbers are hyperprime in some sense, simply because the hyperoperator $*_n$ gets violently powerful when $n$ grows. Thus for almost any natural number $p>1$ one may find sufficiently large $n$ such that even the smallest combinations of natural numbers like $2*_{n}3$ and $3*_{n}2$ exceed $p$. So based on the increasing nature of hyperoperators, $p$ could not arise as the $*_n$ combination of any smaller numbers and is a $n$-hyperprime number. The only (magical?) exception is the eternally composite number $4$ which is NOT $n$-hyperprime for any $n\geq 1$ because $\forall n\geq 1~~~4=2*_{n}2$.

Now the first question is: "How many hyperprimes of any type are there?" We know that there are no $1$-hyperprimes. Also, there are very few $2$-hyperprime numbers in the sense that the natural density of the set of prime numbers in $\mathbb{N}$ is $0$. Roughly speaking, the usual prime numbers are so rare among natural numbers that one may assume that there is almost no such number!

But as stated, there is a promising increasing trend among hyperprime numbers of higher order. When $n$ gets larger and larger, the $n$-hyperoperator skips more and more numbers in its range (while receiving non-trivial input) leaving them as $n$-hyperprimes. Consequently, the corresponding set of $n$-hyperprime numbers gets rapidly larger by varying $n$. So one may cover almost the entire set of natural numbers this way eventually. Thus it is natural to ask:

Question 1. Where is the first place that almost all natural numbers are prime with respect to a hyperoperator?

Precisely, what is the least natural number $n$ such that the set of all $n$-hyperprime numbers is of natural density $1$ in $\mathbb{N}$?

What about the other values in between? Is there a natural number $n$ such that the natural density of the set of all $n$-hyperprime numbers lies in the interval $(0,1)$? (And so we have a balanced number of prime numbers, neither too few nor too many!)

In order to answer the above question one may need to figure out the distribution of hyperprime numbers in $\mathbb{N}$ which in the case of usual prime numbers is given by Prime Number Theorem that provides the $\frac{k}{ln(k)}$ estimation for the number of $2$-hyperprime numbers in the interval $[1, k]$.

Question 2. What is the analogy of Prime Number Theorem for $n$-hyperprimes in general? In other words, what is the growth rate of the $n$-hyperprime counting function $\pi_{n}(x)$ which assigns the number of $n$-hyperprime numbers $\leq x$ to the real number $x$? For $n=2$ it is known to be $\frac{x}{ln (x)}$.

Finally, one may ask about the analogy of Fundamental Theorem of Arithmetic in the case of hyperprimes. Although, we are not dealing with a commutative hyperoperator for $n\geq 3$ but it is still meaningful and interesting to wonder whether every natural number has a unique representation in terms of $n$-hyper combination of $n$-hyperprime numbers or not? For instance, $8^{9^{10}}$ is a natural number. While $8=2^3$ and $9=3^2$ aren't $3$-hyperprime but this number has a representation $2^{3^{21}}$ via $3$-hyperprime numbers $2, 3, 21$. Does such a representation exist for every other number? Is it unique?

Question 3. Does a variant of Fundamental Theorem of Arithmetic hold for any $n$-hyperoperator using the mentioned notion of $n$-hyperprimeness?

Precisely, is it true that for every natural numbers $n>1$ and $k>1$, there is $s\geq 1$ and a unique sequence of $n$-hyperprime numbers $p_1, \cdots, p_{s}$ such that $k=p_s *_{n}(\cdots (p_3 *_{n}(p_2 *_{n} p_1)))$?

• The $3$-hypercomposites already have density $0$. From $1$ to $n$ there are at most (roughly) $n^{1/2}+\dots+n^{1/\log_2(n)}$. – MTyson Apr 28 '18 at 2:42
• The reason we have so few "2-primes" is because the operation of multiplication is very relaxed. It is commutative and satisfies unique factorization. The higher operations would be very restrictive meaning that almost all numbers are hyperprime. I believe it would be very difficult to say something about all hyperoperators. Take the difference between addition and multiplication, "1-primes" don't really relate to "2-primes". So it is very unlikely any hyperoperators are related. Each hyperoperation would be interesting in its own right, although imo past tetration its pretty boring. – Ali Caglayan Apr 28 '18 at 13:42
• @MTyson (+1) That is interesting! I think your comment could be posted as an answer. Could you please explain how you obtained this estimation? – Morteza Azad Apr 28 '18 at 15:52
• @AliCaglayan Well, in principle the commutative nature of an arithmetic operator actually contributes to the increase in the number of its corresponding primes because it reduces the number of composite numbers by making combinations such as $i*j$ and $j*i$ equal. In a non-commutative operator $i, j$ are likely to produce two different composite numbers. Also, as it is mentioned in the question 3, it is not immediately clear if the hyperoperators satisfy a variant of unique factorization or not. I think it is actually the high growth speed of hyperoperators which makes them have many primes. – Morteza Azad Apr 28 '18 at 16:06
• @AliCaglayan By the way, the hyperoperators aren't useless or pure generalizations at all. For some applications of hyperoperators you may take a look at the Ackermann function in computability, Graham's number and Shelah's primitive recursive bound for van Der Warden numbers in Ramsey theory or their potential use in set theory and cardinal arithmetic. – Morteza Azad Apr 28 '18 at 16:17

The answer to Question 1 is that the $3$-hyperprimes have density $1$.
For any $k\ge 2$ there are only $\lfloor n^{1/k}\rfloor$ numbers are of the form $a^k$ between $1$ and $n$. When $k>\log_2(n)$ (i.e. $2^k>n$) only $1$ is of that form. Hence there are at most $n^{1/2}+\cdots+n^{1/\log_2(n)}=O(n^{1/2}\log(n))$ $3$-hypercomposites from $1$ to $n$.