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.
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