definition of primes for higher hyperoperations

Question

I was reading yesterday when I came across the history of counting. There was some evidence of an early understanding of prime numbers. I thought that I would try changing the definition of primality from something like:

domain: Z+ except 1. P is prime if the only way to express it as A*B is P*1 for any integers A and B.

to something like:

domain: Z+ except 1. P is prime if the only way to express it as A^B is P^1 for any integers A and B.

(Notice the operation change from '*' to '^'.) I am just wondering what this more general definition, replacing factors with hyper roots, is called. I have written a (hugely inefficient) Java program that raises every base A to every power B where A < P and B < P to check the primality of P. So far I have found that this 'hyperprimality' is much more common than regular primality. (Also, 4 is always 'hypercomposite': 4 = 2 ^^^...^ 2 in up-arrow notation).

So I ask you: What is this called and where can I find out more?

Answer 1

Just a quick comment on your java program.... To see if you can find a $B$ so that $$P = A^B$$ you can first check if $$\gcd(A,P) = A$$ If this is not true, then you can skip all the trials.

If you can quickly estimate $\log_2 P$ and $\log_2 A$, then you have an estimate on $B$. So you do not need try all the powers.

Finally, if you know $B>B_0$ then you can quickly calculate $A^{B_0}$ very efficiently by divide and conquer algorithm. If you don't mind recursion, the code will look look like this (the code is more like C/C++ than Java

pow(A,B) {
  if (B ==0) return 1; 
  else {
      C=pow(A,B/2); // Integer division
      if (even(B)) return C*C;
       else return C*C*A;
   }
}

Answer 2

Another quick comment on your java-program: Concerning the distribution of "hyper-primes", we find that non-hyper-primes are so rare that the series of their inverses converges: $$\sum_{2\leq a^b}\frac{1}{a^b} = \sum_{a=2}^\infty \sum_{b=2}^\infty \frac{1}{a^b}=\sum_{a=2}^\infty \frac{1}{a(a-1)} = 1.$$ This gives you a measure for the density of hyper-primes in the natural numbers. Note that for "normal" prime numbers, both series diverge, meaning that there are quite a lot of both of them: $$\sum_{p \; \text{prime}}\frac{1}{p} = \infty, \sum_{p \; \text{not prime}} \frac{1}{p} = \infty$$