Skip to content

Instantly share code, notes, and snippets.

@archywillhe
Created October 12, 2015 16:47
Show Gist options
  • Save archywillhe/d25740dc27cb98e62036 to your computer and use it in GitHub Desktop.
Save archywillhe/d25740dc27cb98e62036 to your computer and use it in GitHub Desktop.
On a Mac Air it can only compute up to F(107) in a minute. It uses a "generator" concept to generate the number of possible premutations for each "generator" and sum them up.
from math import *
def euclid(a,b):
#Euclidean algorithm
#compute the greatest common denominator
if (b == 0):
return a
else:
return euclid(b, a % b)
def F(L):
m = 0
x = 2
maxX= int(sqrt(L))
collection = 0
while not(x>maxX):
a = 1
while(a<x):
y = x+a
if a==1 or euclid(x,y)==1:
if not(x*y>L):
generated = int(L/(x*y))
#b = 1;
# while not(b>generated):
# print x*b, y*b, x*y*b
# b+= 1
collection += generated
#print x, y, x*y, ' generator generated ',generated,'permutation(s)'
a+=1
x+=1
return collection
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment