Problem (Rephrased from here):
- The radical of \$n\$, \$rad(n)\$, is the product of distinct prime factors of \$n\$. For example, \$504 = 2^3 × 3^2 × 7\$, so \$rad(504) = 2 × 3 × 7 = 42\$.
We shall define the triplet of positive integers \$(a, b, c)\$ to be an abc-hit if:
- \$GCD(a, b) = GCD(a, c) = GCD(b, c) = 1\$
- \$a < b\$
- \$a + b = c\$
- \$rad(abc) < c\$
If \$(a,b,c)\$ is an abc-hit such that \$c<120000\$, Find sum of all \$c\$.
My code solves this problem in just under 2.5 minutes. Ideally I would like it to run in under a minute if possible. Originally I calculated the radicals using prime factorization, switching to a prime sieve reduced the running time by more than half. I can't (or don't know how to) identify any further bottlenecks that might slow down the program.
My code:
import math
def problem_one_hundred_and_twenty_seven() -> int:
answer = 0
limit = 120000
# limit = 1000
# Modified sieve of Eratosthenes
rad = [0] + [1] * limit
for i in range(2, len(rad)):
if rad[i] == 1:
for j in range(i, len(rad), i):
rad[j] *= i
for c in range(limit):
for a in range(1, c // 2):
if rad[a] * rad[c] >= c:
continue
b = c - a
if b <= a:
continue
# If gcd(a, b) = 1 then gcd(c,b) = gcd(a+b,b) = gcd(a,b) = gcd(a,a+b) = gcd(a,c) = 1.
# If a, b, c are all co-prime then rad(a * b * c) = rad(a) * rad(b) * rad(c).
# If gcd(a, b) != 1 then they share a prime factor, => gcd(rad(a), rad(b)) != 1.
# so gcd(rad(a), rad(b)) = 1 => gcd(a, b) = 1
if math.gcd(a, b) == 1 and rad[a] * rad[b] * rad[c] < c:
# print(a, b, c)
answer += c
return answer
if __name__ == "__main__":
start_time = time.time()
print(problem_one_hundred_and_twenty_seven())
end_time = time.time()
print(f"Found in {end_time - start_time} seconds")