This python script processes the list of factors for fibonacci numbers from index 1 to 9999 listed in https://mersennus.net/fibonacci/fibonacci.txt and https://mersennus.net/fibonacci/lucas.txt

Home   »   This python script processes the list of factors for fibonacci numbers from index 1 to 9999 listed in https://mersennus.net/fibonacci/fibonacci.txt and https://mersennus.net/fibonacci/lucas.txt

import re

# processes string list of factors to int, 
# and marks if there exists a final prime factor.
def splitToMultiplicity(factors):
	normFactors = []
	for factor in factors:
		if factor.isdigit():
			normFactors.append(int(factor))
		if factor[-1] == '*':
			normFactors.append(int(factor[:-1]))

	findLast = factors[-1][0] == 'P'
	return (normFactors, findLast)

def getFinalPrime(n, factors):
	nLCM = lcm(factors)
	finalPrime = n // nLCM
	if math.gcd(nLCM, finalPrime) != 1:
		finalPrime //= math.gcd(nLCM, finalPrime)

def getLucas(): 
	p = re.compile(r' +')

	# Handle Lucas Factors

	lucasFactors = [[-1, [], [], []] for i in range(10000)]
	lucasFactors[0] = [0, [2], [], []]
	lucasFactors[1] = [1, [], [], []]
	with open("data/allLucasFactors.txt") as f:
		for line in f:
			rawtext = p.split(line)

			L = int(re.findall(r'\d+', rawtext[0])[0])

			factors = []

			if (len(rawtext) > 2):
				for ind in rawtext[1].strip('()').split(','):
					if ind.isdigit():
						for factor in lucasFactors[int(ind)][1] + lucasFactors[int(ind)][2] + lucasFactors[int(ind)][3]:
							if factor not in factors:
								factors.append(factor)
					if ind[-1] == 'A':
						for factor in lucasFactors[int(ind[:-1])][2]:
							if factor not in factors:
								factors.append(factor)
					elif ind[-1] == 'B':
						for factor in lucasFactors[int(ind[:-1])][3]:
							if factor not in factors:
								factors.append(factor)

			splitFactors = splitToMultiplicity(rawtext[-1].strip('\n').split('.'))

			for factor in splitFactors[0]:
				factors.append(factor)

			if (splitFactors[1]):
				currLucas = -1
				if (rawtext[0][-1] == 'A'):
					currLucas = 5 * (mem_fib(L // 5) ** 2) - 5 * mem_fib(L // 5) + 1
				elif (rawtext[0][-1] == 'B'):
					currLucas = 5 * (mem_fib(L // 5) ** 2) + 5 * mem_fib(L // 5) + 1
				else: 
					currLucas = mem_lucas(L)

				finalPrime = getFinalPrime(currLucas, factors)
				if(finalPrime != 1):
					factors.append(finalPrime)

			if (rawtext[0][-1] == 'A'):
				lucasFactors[L][2] = factors
			elif (rawtext[0][-1] == 'B'):
				lucasFactors[L][3] = factors
			else:
				lucasFactors[L][0] = L
				lucasFactors[L][1] = factors
	return lucasFactors

def getFibonacci():
	p = re.compile(r' +')

	# Handle Odd Fibonacci Factors
	fibFactors = [[-1, []] for i in range(10000)]

	fibFactors[0] = [0, []]
	fibFactors[1] = [1, []]
	fibFactors[2] = [2, []]

	with open("data/oddFibFactors.txt") as f:
		for i, line in enumerate(f):
			L = i * 2 + 3
			factors = []

			rawtext = p.split(line)
			if (len(rawtext) > 2):
				for ind in rawtext[1].strip('()').split(','):
					for factor in fibFactors[int(ind)][1]:
						if factor not in factors:
							factors.append(factor)

			splitFactors = splitToMultiplicity(rawtext[-1].strip('\n').split('.'))
			fibn = mem_fib(L)

			for factor in splitFactors[0]:
				factors.append(factor)

			if (splitFactors[1]):
				finalPrime = getFinalPrime(mem_fib(L), factors)
				if(finalPrime != 1):
					factors.append(finalPrime)

			fibFactors[L][0] = L
			fibFactors[L][1] = list(dict.fromkeys(factors))

	lucasFactors = getLucas()

	for i in range(4, 10000, 2):
		factors = []
		L = i
		while(L % 2 == 0):
			L //= 2
			factors += lucasFactors[L][1] + lucasFactors[L][2] + lucasFactors[L][3]
		factors += fibFactors[L][1]

		fibFactors[i][0] = i 
		fibFactors[i][1] = list(dict.fromkeys(factors))
	return fibFactors

def getSanitizedFactors():
	fibFactors = getFibonacci()

	sanitized = [[-1, [], []] for i in range(10000)]

	for L in range(10000):
		sanitized[L] = [L, list(filter(lambda x: x % L == 1, fibFactors[L][1])), list(filter(lambda x: x % L == L - 1, fibFactors[L][1]))]
	return sanitized

sanitizedFactors = getSanitizedFactors()

Leave a Reply

Your email address will not be published. Required fields are marked *