#By Jacob Ford import time def isPrime(n): #returns true or false if n <= 1: return False elif n == 2: return True for z in [2] + range(3,n,2): if n % z == 0: return False return True def primes(n): #returns list of unique prime factors in ascending order if n == 2: return [2] divisor = 2 primeFactors = [] endLoop = n/2+1 while divisor <= endLoop: if n % divisor == 0: n = n / divisor if isPrime(divisor) and divisor not in primeFactors: primeFactors += [divisor] endLoop = n / divisor + 1 divisor = 2 else: divisor += 1 if n != 1 and n not in primeFactors: primeFactors += [n] return primeFactors def Q(n): if n == 0: return 2 elif n > 1: return primes(n)[0] def L(m,n): if n == 1: return 1 m = float(m) primeFactors = primes(n) if primeFactors[0]<=m: return 0 else: product = n for z in primeFactors: product *= (1-m/z) return int(round(product)) def R(m,n): #returns tuple (Q,L,R,H (m,n)) iterations = 1 #to fit with the document, this starts at 1, not 0 L1 = L(m,n) Q1 = Q(n) n = L1 while n >= 2: n = L(m,n) iterations += 1 return Q1,L1,iterations,n def output(): divider = "#############################################" print "Enter a value for m and hit enter." m = int(raw_input('m = ')) print "Enter a starting value." low = int(raw_input('lowest value of n = ')) print "Enter the value you want to calculate up to." high = int(raw_input('highest value of n = ')) #print "For the following questions, type 0 for no or 1 for yes." #q = input('Do you want the output to include Q(n)?') #l = input('Do you want the output to include Lm(n)?') #r = input('Do you want the output to include Rm(n)?') #h = input('Do you want the output to include Hm(n)?') qList = [] lList = [] rList = [] hList = [] start = time.clock() for z in range(low,high+1): output = R(m,z) qList += [output[0]] lList += [output[1]] rList += [output[2]] hList += [output[3]] print print "Q(n):" print for z in qList: print z print for z in range(4): print divider print print "L(m,n):" print for z in lList: print z print for z in range(4): print divider print print "R(m,n):" print for z in rList: print z print for z in range(4): print divider print print "H(m,n):" print for z in hList: print z elapsed = (time.clock() - start) #print elapsed,'seconds taken' #remove the first '#' to see time taken while(True): output() print print "Enter 1 to do more calculations" cont = raw_input("Continue? ") if cont != '1': break #timing (for m = 2): # 1 - 100 : 0.854943315778 seconds taken # 1 - 500 : 4.28940875281 seconds taken # 1 - 2500: 19.9785490368 seconds taken