Perfect power

Demonstration, with Cuisenaire rods, of the perfect power nature of 4, 8, and 9

In mathematics, a perfect power is a positive integer that can be resolved into equal factors, and whose root can be exactly extracted. i.e., a positive integer that can be expressed as an integer power of another positive integer. More formally, n is a perfect power if there exist natural numbers m > 1, and k > 1 such that mk = n. In this case, n may be called a perfect kth power. If k = 2 or k = 3, then n is called a perfect square or perfect cube, respectively. Sometimes 0 and 1 are also considered perfect powers (0k = 0 for any k > 0, 1k = 1 for any k).

Examples and sums

A sequence of perfect powers can be generated by iterating through the possible values for m and k. The first few ascending perfect powers in numerical order (showing duplicate powers) are (sequence A072103 in the OEIS):

${\displaystyle 2^{2}=4,\ 2^{3}=8,\ 3^{2}=9,\ 2^{4}=16,\ 4^{2}=16,\ 5^{2}=25,\ 3^{3}=27,}$  ${\displaystyle 2^{5}=32,\ 6^{2}=36,\ 7^{2}=49,\ 2^{6}=64,\ 4^{3}=64,\ 8^{2}=64,\dots }$

The sum of the reciprocals of the perfect powers (including duplicates such as 34 and 92, both of which equal 81) is 1:

${\displaystyle \sum _{m=2}^{\infty }\sum _{k=2}^{\infty }{\frac {1}{m^{k}}}=1.}$

which can be proved as follows:

${\displaystyle \sum _{m=2}^{\infty }\sum _{k=2}^{\infty }{\frac {1}{m^{k}}}=\sum _{m=2}^{\infty }{\frac {1}{m^{2}}}\sum _{k=0}^{\infty }{\frac {1}{m^{k}}}=\sum _{m=2}^{\infty }{\frac {1}{m^{2}}}\left({\frac {m}{m-1}}\right)=\sum _{m=2}^{\infty }{\frac {1}{m(m-1)}}=\sum _{m=2}^{\infty }\left({\frac {1}{m-1}}-{\frac {1}{m}}\right)=1\,.}$

The first perfect powers without duplicates are:

(sometimes 0 and 1), 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, 243, 256, 289, 324, 343, 361, 400, 441, 484, 512, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1000, 1024, ... (sequence A001597 in the OEIS)

The sum of the reciprocals of the perfect powers p without duplicates is:[1]

${\displaystyle \sum _{p}{\frac {1}{p}}=\sum _{k=2}^{\infty }\mu (k)(1-\zeta (k))\approx 0.874464368\dots }$

where μ(k) is the Möbius function and ζ(k) is the Riemann zeta function.

According to Euler, Goldbach showed (in a now-lost letter) that the sum of 1/p − 1 over the set of perfect powers p, excluding 1 and excluding duplicates, is 1:

${\displaystyle \sum _{p}{\frac {1}{p-1}}={{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{8}}+{\frac {1}{15}}+{\frac {1}{24}}+{\frac {1}{26}}+{\frac {1}{31}}}+\cdots =1.}$

This is sometimes known as the Goldbach–Euler theorem.

Detecting perfect powers

Detecting whether or not a given natural number n is a perfect power may be accomplished in many different ways, with varying levels of complexity. One of the simplest such methods is to consider all possible values for k across each of the divisors of n, up to ${\displaystyle k\leq \log _{2}n}$ . So if the divisors of ${\displaystyle n}$  are ${\displaystyle n_{1},n_{2},\dots ,n_{j}}$  then one of the values ${\displaystyle n_{1}^{2},n_{2}^{2},\dots ,n_{j}^{2},n_{1}^{3},n_{2}^{3},\dots }$  must be equal to n if n is indeed a perfect power.

This method can immediately be simplified by instead considering only prime values of k. This is because if ${\displaystyle n=m^{k}}$  for a composite ${\displaystyle k=ap}$  where p is prime, then this can simply be rewritten as ${\displaystyle n=m^{k}=m^{ap}=(m^{a})^{p}}$ . Because of this result, the minimal value of k must necessarily be prime.

If the full factorization of n is known, say ${\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{r}^{\alpha _{r}}}$  where the ${\displaystyle p_{i}}$  are distinct primes, then n is a perfect power if and only if ${\displaystyle \gcd(\alpha _{1},\alpha _{2},\ldots ,\alpha _{r})>1}$  where gcd denotes the greatest common divisor. As an example, consider n = 296·360·724. Since gcd(96, 60, 24) = 12, n is a perfect 12th power (and a perfect 6th power, 4th power, cube and square, since 6, 4, 3 and 2 divide 12).

Gaps between perfect powers

In 2002 Romanian mathematician Preda Mihăilescu proved that the only pair of consecutive perfect powers is 23 = 8 and 32 = 9, thus proving Catalan's conjecture.

Pillai's conjecture states that for any given positive integer k there are only a finite number of pairs of perfect powers whose difference is k. This is an unsolved problem.[2]

Calculation by recursion for positive integers

As an alternate way to calculate perfect powers, the recursive approach has yet to be found useful. It is based on the observation that the difference between ab and (a+1)b where ${\displaystyle a>b}$  may not be constant, but if you take the difference of successive differences, b times, there is a constant b! factor. For example, 94 = 6561, and 104 is 10000. the difference is 3439. The difference between 84 and 94 is 2465, meaning the difference of differences is 974. A step further and you have 204. One step further, and you have 24, which is equal to 4!. One step further and collating this 'key' row from progressively larger exponents yields a triangle similar to Pascal's, but with a differing formula for generation. A part of this table is shown below:

Define the following function on the range of positive integers:

${\displaystyle K(a,b)=1}$  where a = 1 or a = b
${\displaystyle K(a,b)=0}$  where b > a
${\displaystyle K(a,b)=bK(a-b,b)+(a-b+1)K(a-b+1,b-1)}$  elsewhere

This function generates the following output:

b
a
1 2 3 4 5 6
1 1 0 0 0 0 0
2 1 1 0 0 0 0
3 1 4 1 0 0 0
4 1 11 11 1 0 0
5 1 26 66 26 1 0
6 1 57 302 302 57 1

Also define the following function on the range of positive integers: (This is very closely related to the Binomial Theorem and Pascal's Triangle)

${\displaystyle P(a,b)=1}$  where a = 1 or b = 1
${\displaystyle P(a,b)=P(a-1,b)+P(a,b-1)}$  elsewhere

The table this generates can be seen as pascal's triangle fallen over to the left, so that what were rows on Pascal's triangle have become diagonal series in the table.

b
a
1 2 3 4 5 6 7 8
1 1 1 1 1 1 1 1 1
2 1 2 3 4 5 6 7 8
3 1 3 6 10 15 21 28 36
4 1 4 10 20 35 56 84 120
5 1 5 15 35 70 126 210 330
6 1 6 21 56 126 252 462 792
7 1 7 28 84 210 462 924 1716
8 1 8 36 120 330 792 1716 3432

It can then be stated that:

${\displaystyle a^{b}=\sum _{x=1}^{b}\,\!P(a-x+1,b+1)K(b,x)}$

Example:

${\displaystyle 7^{3}=\sum _{x=1}^{b}P(8-x,4)K(3,x)=P(7,4)K(3,1)+P(6,4)K(3,2)+P(5,4)K(3,3)}$

Expanding P(7,4)

{\displaystyle {\begin{aligned}P(7,4)&=P(7,3)+P(6,4)=P(7,2)+2P(6,3)+P(5,4)\\&=P(7,1)+3P(6,2)+3P(5,3)+P(4,4)\\&=1+3P(6,1)+6P(5,2)+4P(4,3)+P(3,4)\\&=4+6P(5,1)+10P(4,2)+5P(3,3)+P(2,4)\\&=10+10P(4,1)+15P(3,2)+6P(2,3)+P(1,4)\\&=21+15P(3,1)+21P(2,2)+6P(1,3)\\&=42+21P(2,1)+21P(1,2)=84\end{aligned}}}

Or you can look up the values on the table and get P(6,4) = 56, and P(5,4) = 35.

By definition, K(3,1) = 1. Expanding K(3,2)

${\displaystyle K(3,2)=2K(1,2)+2K(2,1)=4}$

By definition, K(3,3) = 1.

{\displaystyle {\begin{aligned}7^{3}&=P(7,4)K(3,1)+P(6,4)K(3,2)+P(5,4)K(3,3)=84\times 1+56\times 4+35\times 1=343\\7^{4}&=P(7,5)K(4,1)+P(6,5)K(4,2)+P(5,5)K(4,3)+P(4,5)K(4,4)=210\times 1+126\times 11+70\times 11+35\times 1=2401\\7^{5}&=462\times 1+252\times 26+126\times 66+56\times 26+21\times 1=16807\end{aligned}}}

This calculation method can be used for all integer power calculations, as negative integers act the same way, simply applying the negative if the exponent is odd.