How many distinct terms are in the sequence generated by for 2 ≤ a ≤ N and 2 ≤ b ≤ N?
Constraints:
2 <= N <= 10^5
The previous brute force solution only works fine when N is small. It takes around 10 seconds to get an answer when N = 1000, then becomes unbearable for N = 100000.
Apparently, it is much faster to find out the number of duplicates. Then the answer is the difference between the total number of the powers and the number of duplicates.
A power is a duplicate of another if
is a square, a cube or a n-th power. For example,
is a duplicate of
;
is a duplicate of
In general, if is a n-th power, then there exists an integer
such that
That is, . Therefore,
is a duplicate of
, i.e.
from math import sqrt, log2
from collections import defaultdict
def p29(N):
d = defaultdict(list)
for x in range(2, int(sqrt(N)) + 1): # x: base number
for n in range(2, int(log2(N)) + 1): # n: power
a = x ** n # a: n-th power
if a > N: break
d[a].append(n)
dup_cnt = 0
for a in d.keys():
power = set()
for n in d[a]:
for k in range(1, n):
for m in range(1, N // n + 1):
if m * k == 1: continue
power.add(m * k)
dup_cnt += len(power)
return (N - 1) ** 2 - dup_cnt