PyClasses/NumberAlgorithms.py

#Python/pyClasses/NumberAlgorithms.py
#Matthew Ellison
# Created: 07-21-21
#Modified: 07-21-21
#This file contains my library of number functions
"""
	Copyright (C) 2021  Matthew Ellison

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU Lesser General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU Lesser General Public License for more details.

	You should have received a copy of the GNU Lesser General Public License
	along with this program.  If not, see <https://www.gnu.org/licenses/>.
"""


import itertools
import math


#Generate an infinite sequence of prime numbers using the Sieve of Eratosthenes
#Based on code by David Eppstein found at https://code.activestate.com/recipes/117119/
def primeGenerator():
	#Return 2 the first time, this lets us skip all even numbers later
	yield 2

	#Dictionary to hold the primes we have already found
	dict = {}

	#Start checking for primes with the number 3 and skip all even numbers
	for possiblePrime in itertools.count(3, 2):
		#If possiblePrime is not in the dictionary it is a new prime number
		#Return it and mark its next multiple
		if possiblePrime not in dict:
			yield possiblePrime
			dict[possiblePrime * possiblePrime] = [possiblePrime]
		#If possiblePrime is in the dictionary it is a composite number
		else:
			#Move each witness to its next multiple
			for num in dict[possiblePrime]:
				dict.setdefault(num + num + possiblePrime, []).append(num)
			#We no longer need this, free the memory
			del dict[possiblePrime]

#Generate an inifinite sequence of fibonacci numbers
def fibGenerator():
	#Set this so the first returned number is 1 and the second is also 1
	a, b = 0, 1

	while(True):
		yield b
		a, b = b, a + b

#This function returns a list with all the prime numbers <= goalNumber
def getPrimes(goalNumber: int) -> list:
	gen = primeGenerator()	#The prime number generator
	primes = []		#The list of prime numbers

	#If the number is <= 1 return a blank list
	#?Should this throw an exception if goalNumber < 0
	if(goalNumber <= 1):
		return primes

	#There is at least 1 prime number
	primes.append(next(gen))

	#Loop until you find all the prime numbers requested
	while(primes[len(primes) - 1] < goalNumber):
		primes.append(next(gen))

	if(primes[len(primes)- 1] > goalNumber):
		primes.pop()

	return primes

#This function gets a certain number of primes
def getNumPrimes(numberOfPrimes: int) -> list:
	gen = primeGenerator()	#The prime number generator
	primes = []		#The list of prime numbers

	#If the number is < 1 return a blank list
	#?Should this throw an exception if numberOfPrimes < 0
	if(numberOfPrimes < 1):
		return primes

	#Count how many primes you are adding to the list and stop when you reach the requested length
	for _ in range(1, numberOfPrimes + 1):
		primes.append(next(gen))

	#Return the list with all the prime numbers
	return primes

#This function determines whether a number is prime
def isPrime(possiblePrime: int) -> bool:
	if(possiblePrime <= 3):
		return possiblePrime > 1
	elif(((possiblePrime % 2) == 0) or ((possiblePrime % 3) == 0)):
		return False
	for cnt in range(5, int(math.sqrt(possiblePrime)) + 1, 6):
		if(((possiblePrime % cnt) == 0) or ((possiblePrime % (cnt + 2)) == 0)):
			return False
	return True

#This is a function that returns all the factors of goalNumber
def getFactors(goalNumber: int) -> list:
	prime_factors_list = []
	while goalNumber % 2 == 0:
		prime_factors_list.append(2)
		goalNumber /= 2
	for i in range(3, int(math.sqrt(goalNumber))+1, 2):
		if goalNumber % i == 0:
			prime_factors_list.append(i)
			goalNumber /= i
	if goalNumber > 2:
		prime_factors_list.append(int(goalNumber))
	prime_factors_list.sort()
	return prime_factors_list

#This function returns all the divisors of goalNumber
def getDivisors(goalNumber: int) -> list:
	divisors = []
	#Start by checking that the number is positive
	if(goalNumber <= 0):
		return divisors
	#If the number is 1 return just itself
	elif(goalNumber == 1):
		divisors.append(1)
		return divisors

	#Start at 3 and loop through all numbers < (goalNumber / 2 ) looking for a number that divides it evenly
	topPossibleDivisor = math.ceil(math.sqrt(goalNumber))
	possibleDivisor = 1
	while(possibleDivisor <= topPossibleDivisor):
		#If you find one add it and the number it creates to the list
		if((goalNumber % possibleDivisor) == 0):
			divisors.append(possibleDivisor)
			#Account for the possibility sqrt(goalNumber) being a divisor
			if(possibleDivisor != topPossibleDivisor):
				divisors.append(goalNumber / possibleDivisor)
			#Take care of a few occations where a number was added twice
			if(divisors[len(divisors) - 1] == (possibleDivisor + 1)):
				possibleDivisor += 1
		possibleDivisor += 1

	#Sort the list before returning for neatness
	divisors.sort()
	#Return the list
	return divisors

#This function returns the numth Fibonacci number
def getFib(goalSubscript: int) -> int:
	gen = fibGenerator()	#The fibonacci number generator

	#Loop through the numbers up to the subscript we want
	for _ in range(1, goalSubscript):
		next(gen)

	#The next number is F(goalSub), return it
	return next(gen)

#This function returns a list of all Fibonacci numbers <= num
def getAllFib(goalNumber: int) -> list:
	gen = fibGenerator()	#The Fibonacci number generator
	fibNums = []	#A list to save the Fibonacci numbers

	#If the number is <= 0 return an empty list
	if(goalNumber <= 0):
		return fibNums

	#There is at least one number in the list now
	fibNums.append(next(gen))

	#Loop to generate the rest of the Fibonacci numbers
	while(fibNums[len(fibNums) - 1] <= goalNumber):
		fibNums.append(next(gen))

	#At this point the most recent number is > goalNumber, so remove it
	fibNums.pop()
	return fibNums

#This function returns the GCD of the two numbers sent to it
def gcd(num1: int, num2: int) -> int:
	while((num1 != 0) and (num2 != 0)):
		if(num1 > num2):
			num1 %= num2
		else:
			num2 %= num1
	return num1 | num2

#Returns the factorial of the number passed in
def factorial(num: int) -> int:
	fact = 1
	for cnt in range(1, num + 1):
		fact *= cnt
	return fact

#Converts a number to its binary equivalent
def toBin(num: int) -> str:
	#Convert the number to a binary string
	return "{0:b}".format(num)