Gaps in prime powers

David Radcliffe

A prime power is a number of the form $p^k$ where $p$ is prime and $k \ge 1$. We say that two prime powers are consecutive if there exists no other prime power between them.

For each positive integer $k$, let $a(k)$ be the least integer $N$ so that $N$ and $N+k$ are consecutive prime powers, if one exists.

This Python script computes all values of $a(k)$ so that $a(k) + k < 10^9$. The prime powers are stored in a min-heap and generated as needed.

In [3]:
from sympy import primerange
from heapq import heappush, heappop

top = 10**9
heap = [(3, 3), (4, 2)]
last = 2
primes = primerange(5, top)
seen = {}

while heap:
    n, p = heappop(heap)
    gap = n - last
    if not (gap in seen):
        seen[gap] = last
    last = n
    m = n * p
    if m < top:
        heappush(heap, (m, p))
    if n == p:
        try:
            m = primes.next()
            if m < top:
                heappush(heap, (m, m))
        except:
            pass

for x, y in sorted(seen.items()):
    print "a(%d) = %d" % (x, y)
a(1) = 2
a(2) = 5
a(3) = 13
a(4) = 19
a(5) = 32
a(6) = 53
a(7) = 1024
a(8) = 89
a(9) = 512
a(10) = 139
a(11) = 536870912
a(12) = 199
a(14) = 293
a(15) = 65521
a(16) = 1831
a(17) = 8192
a(18) = 1069
a(20) = 887
a(21) = 524288
a(22) = 1129
a(24) = 4177
a(26) = 2477
a(27) = 16384
a(28) = 2971
a(29) = 131072
a(30) = 1331
a(32) = 5591
a(34) = 8467
a(35) = 33554432
a(36) = 9551
a(38) = 30593
a(39) = 33554393
a(40) = 19333
a(42) = 16141
a(43) = 16777216
a(44) = 15683
a(46) = 81463
a(48) = 28229
a(50) = 31907
a(52) = 19609
a(54) = 35617
a(56) = 82073
a(57) = 268435399
a(58) = 44293
a(60) = 43331
a(62) = 34061
a(64) = 89689
a(66) = 162143
a(68) = 134513
a(70) = 173359
a(72) = 31397
a(74) = 404597
a(76) = 212701
a(78) = 188029
a(80) = 542603
a(82) = 265621
a(84) = 461717
a(86) = 155921
a(88) = 544279
a(90) = 404851
a(92) = 927869
a(94) = 1100977
a(96) = 360653
a(98) = 604073
a(100) = 396733
a(102) = 1444309
a(104) = 1388483
a(106) = 1098847
a(108) = 2238823
a(110) = 1468277
a(112) = 370261
a(114) = 492113
a(116) = 5845193
a(118) = 1349533
a(120) = 1895359
a(122) = 3117299
a(124) = 6752623
a(126) = 1671781
a(128) = 3851459
a(130) = 5518687
a(132) = 1357201
a(134) = 6958667
a(136) = 6371401
a(138) = 3826019
a(140) = 7621259
a(142) = 10343761
a(144) = 11981443
a(146) = 6034247
a(148) = 2010733
a(150) = 13626257
a(152) = 8421251
a(154) = 4652353
a(156) = 17983717
a(158) = 49269581
a(160) = 33803689
a(162) = 39175217
a(164) = 20285099
a(166) = 83751121
a(168) = 37305713
a(170) = 27915737
a(172) = 38394127
a(174) = 52721113
a(176) = 38089277
a(178) = 39389989
a(180) = 17051707
a(182) = 36271601
a(184) = 79167733
a(186) = 147684137
a(188) = 134065829
a(190) = 142414669
a(192) = 123454691
a(194) = 166726367
a(196) = 70396393
a(198) = 46006769
a(200) = 378043979
a(202) = 107534587
a(204) = 112098817
a(206) = 232423823
a(208) = 192983851
a(210) = 20831323
a(212) = 215949407
a(214) = 253878403
a(216) = 202551667
a(218) = 327966101
a(220) = 47326693
a(222) = 122164747
a(224) = 409866323
a(226) = 519653371
a(228) = 895858039
a(230) = 607010093
a(232) = 525436489
a(234) = 189695659
a(236) = 216668603
a(238) = 673919143
a(240) = 391995431
a(242) = 367876529
a(244) = 693103639
a(246) = 555142061
a(248) = 191912783
a(250) = 387096133
a(252) = 630045137
a(260) = 944192807
a(276) = 649580171
a(282) = 436273009