language: Python (python 2.6.4)
date: 489 days 10 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def gcd(a, b):
  if b == 0: return a
  return gcd(b, a % b)
 
def go(max, p):
  n = 2
  res = 0
  while True:
    # Find the number of valid progressions with n^(p-1) as highest term
    k = max // (n**(p-1))
    if k == 0: break
 
    # Find all d that's relatively prime to n to avoid non-simple fractions
    for d in xrange(1, n):
      if gcd(n, d) == 1:
        res += k
 
    n += 1
  return res
 
print go(4000000000, 6)