Problems & Puzzles:
intervals between consecutive perfect powers.
JM Bergot sent
one more nice puzzle:
When does the interval between two
consecutive perfect powers contain NO primes? These
intervals must certainly be small in number; can anyone find
all of them?
Bergot gave two examples: 32 to 36;
121 to 125. Of course there are two more intervals before: 8 to 9 & 25
In an elementary & search with
Ubasic I found quickly (21 seconds) six more, for a
total of 10 intervals of this type, but surfing the web I
learned that T. D. Noe have discovered & published all these
solutions before (March 2006 , see
consequently he must be properly mentioned as the author of all
the known ranges.
Primes free intervals between consecutive perfect
8 to 9
2^3 to 3^2
25 to 27
5^2 to 3^3
32 to 36
2^5 to 6^2
121 to 125
11^2 to 5^3
2187 to 2197
3^7 to 13^3
3125 to 3136
5^5 to 56^2
32761 to 32768
181^2 to 32^3
79507 to 79524
43^3 to 282^2
97336 to 97344
46^3 to 312^2
503284356 to 503284375
22434^2 to 55^5
Is there a 11th case?
T. D. Noe
comments "No other n<10^12. There is a
conjecture that this sequence is finite"
Q2. Can you argument the
A001597 in particular
explore the links section.
2. If you are decided to seek in depth for more solutions
perhaps is good to read this
D. J. Bernstein.
Contributions came from Patrick Capelle & Giovanni Resta.
Sorry to disturb you with a detail without importance.
In the introduction of the puzzle 424, you wrote :
"In an elementary & search with Ubasic I found quickly (21 seconds)
six more, for a total of 10 intervals of this type, but surfing the
web I learned that T. D. Noe have discovered & published all these
solutions before (March 2006 , see A116086) and consequently he must
be properly mentioned as the author of all the known ranges."
In his contribution (A116086, Mar 28 2006), T.D. Noe mentioned the
reference March 2006 NMBRTHRY Archives , where we can find two
interesting references :
1. Between any two powers - at least cubes - is there a prime? (23
Mar 2006, and reply 28 mar 2006).
2. Primes between two powers (new version) (25 Mar 2006, and reply
28 Mar 2006).
It means that he knew them before sending his contribution. So, it
seems to me that T.D. Noe was not "the author of all the known
ranges". Is it correct ? He published the results but didn't
discover them. I don't know if the 10 exeptions were known before
march 2006. Perhaps that T.D. Noe, Zhi-Wei SUN, Kevin Buzzard, J.
Mc. Laughlin, C. Pomerance and Stephan Redmond could say more on
Ror puzzle 424, I have searched up to 1.6 x 10^19 but I did not
find any new solution.
Apparently, the average gap between perfect powers grows faster than
the average gap between primes, so it is difficult to find another
(B.t.w., there is no need of a test for determining if a number is a
perfect power or not.)
I used a very simple method.
My target was the square of 4x10^9 (because that number
fits well in an unsigned long long integer (64 bits).
Since 2^63 < 1.6x10^19 < 2^64, then a number in that range can be at
most a 63-th power.
I initializated an array of 62 long long integers to 1^2, 1^3, 1^4,
1^5,...., 1^63 and a variable LastPower to 0.
The procedure is then the following:
At every round, I select the smallest of the 62 members of the array
(If there is more than one "minimum", it does not matter which one I
Suppose that the smallest at that moment is 123^3. Then I set
CurrentPower to 123^3 and I replace in the array 123^3 with 124^3.
Then I examine the interval between LastPower and CurrentPower to
see if there is at least a prime number. Once I've finished (usually
when I find a prime number...)
I set LastPower to CurrentPower and I repeat from the beginning,
that is I select the next smallest perfect power and so on.
Clearly, if LastPower=CurrentPower I simply update the array and I
have nothing to check. (This happens because, for example, every 4th
power is also a square, etc.etc.)
The method works because in this way I generate all the perfect
in the right order, since at each step the array contains the
smallest 2nd, 3rd, 4th,... 63rd, perfect power not jet considered.
The selection of the minimum can be accelerated maintaining
the values in a heap instead of a simple array.
D. Noe wrote:
My role in this puzzle was verifying the numbers and submitting them
OEIS. I now report that there are no other terms less than 10^16. It
that the problem originated with Stephen Redmond and Zhi-Wei Sun.