For this problem I created all the admissible numbers below $n$ using a sieve. Next it was just a matter of finding the next largest prime number which I did using a combination of the sieve and list of primes both created earlier.
After a certain point, there are no more admissible numbers to be found. We could stop the sieve at this point, but going up until $\sqrt n$ means we will have enough primes at our disposal in the next step where we must find the next prime after a given number. If we stop sieving too soon, this could make things more difficult later on.
I keep thinking there has got to be a way to either make my code cleaner or speed up the algorithm here. However, running in under half a second in Pypy3 seems optimal enough.
def solve(n):
if n < 3:
return 0
top = int(n ** 0.5) + 1
sieve = [False, False] + [True] * (top - 1)
primes = []
new_admissibles, all_admissibles, admissibles = [], [], [1]
for p, isprime in enumerate(sieve):
if not isprime:
continue
primes.append(p)
num = p * p
while num <= top:
sieve[num] = False
num += p
for a in admissibles:
num = a * p
while num < n:
new_admissibles.append(num)
num *= p
all_admissibles.extend(new_admissibles)
admissibles, new_admissibles = new_admissibles, []
admissibles = all_admissibles
def pseudo_fortunate(k):
i = k + 2
while i <= top:
if sieve[i]:
return i - k
i += 1
while True:
for p in primes:
if i % p == 0:
break
else:
return i - k
i += 1
pseudos = {3: True}
for k in admissibles:
pseudos[pseudo_fortunate(k)] = True
return sum(pseudos)
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
import pytest
from problem import solve
_test_solve = (
(0, 0),
(1, 0),
(2, 0),
(3, 3),
(4, 3),
(5, 3),
(6, 3),
(7, 8),
(8, 8),
(9, 8),
(10, 8),
(11, 8),
(12, 8),
(13, 8),
(14, 8),
(15, 8),
(16, 8),
(17, 8),
(18, 8),
(19, 8),
(20, 8),
(21, 8),
(22, 8),
(23, 8),
(24, 8),
(25, 8),
(26, 8),
(27, 8),
(28, 8),
(29, 8),
(30, 8),
(31, 15),
(32, 15),
(33, 15),
(34, 15),
(35, 15),
(36, 15),
(37, 15),
(38, 15),
(39, 15),
(40, 15),
(41, 15),
(42, 15),
(43, 15),
(44, 15),
(45, 15),
(46, 15),
(47, 15),
(48, 15),
(49, 15),
(50, 15),
(10**2, 15),
(10**3, 48),
(10**4, 107),
(10**5, 231),
(10**6, 599),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)