2

I am writing a program to generate a sequence of numbers such that they are not of the form $p^{2^n}$, where $n$ can be a whole number ( i.e $ n \in \{ 0, 1, 2, 3, \ldots \} $ ).

I could use the following approach (solve for n):

$$ p^{2^n} = N \\ 2^n log(p) = log(N) \\ n log(2) = log(\frac{log(N)}{log(p)})\\ n = \frac{1}{log(2)} . log(\frac{log(N)}{log(p)}) $$

I can increment $p$ and test if $n$ is a whole number. But for numbers which are not of the said form, I don't know when to stop the program and decide that this is not a number of the said form.

deostroll
  • 267
  • 1
    I would try to stay away from non-integer computations if possible. What language are you using? By $p$ do you mean prime or you just picked the letter $p$? – peter.petrov Apr 16 '20 at 13:39
  • First test if the number is a perfect power (this can be done efficiently), if it is not apply a primality test. – Peter Apr 16 '20 at 13:40

2 Answers2

3

There's a simpler approach that relies on the relation $$p^{2^n}=(((p^2)^2)\dots)^2$$ So to test whether or not a number is of the form $p^{2^n}$, repeatedly take square roots until you get a number that isn't a perfect square. (There are efficient integer square root algorithms.) Then test whether the number that's left is a prime – it is a prime iff the original number is of the form $p^{2^n}$.

Parcly Taxel
  • 103,344
0

Here's an other approach : assume you're given the int $N$.

  • Enumerate numbers $2\leqslant i \leqslant \sqrt{N}$ until you find a divisor $d$ of $N$ ($d$ is then prime)
  • Initialize a boolean $oddPower$ to True, and an int $residual$ to $\frac{N}{d}$.
  • While $d$ divides $residual$, do :
    $residual := \frac{N}{d}$
    $oddPower := \textrm{ not } odd_power$
  • if $oddPower$, return True else return $residual \textrm{ != } 1$.

This function returns true if $N$ is not an even power of a prime, false otherwise.

Olivier Roche
  • 5,319
  • 9
  • 16