Very amateur programmer and first-time poster here.
The program I wrote asks the user for a prime number, a lower and upper bound, and a degree (all of these are integers). I want to generate a list of polynomials, represented by its coefficients (see example). Each polynomial \$P(x)\$ satisfies the following conditions:
\$P(x) + p\$ is prime for \$1 \le x \le p - 2\$ (where \$x\$ is an integer), and \$P(0) = 0\$.
Each coefficient is an integer and is confined by the user's bounds inclusively (i.e., the coefficient may equal a bound but may not be less/greater than it).
The highest degree a polynomial can have is the user's given degree. (The user may choose to include just polynomials with this degree or polynomials with lower degrees in the final list).
The program then finds each polynomial with these conditions and prints a list of primes that it generates.
Example:
Enter the prime number you want to find a poly for: 11
Enter the lower bound: -3
Enter the higher bound: 3
Enter the degree of the polynomial: 3
Press n if you do not want to include lower degree polynomials: n
possible combos (including constant func):
215
################################################
poly generating finished
[[11, -2, 0, 2]]
List of primes that [11, -2, 0, 2] generates:
[11, 11, 23, 59, 131, 251, 431, 683, 1019, 1451]
There are 1 good polynomials for 11 with bounds -3 to 3 inclusive up to degree 3
Here, \$[11, -2, 0, 2]\$ represents \$p=11\$ with the polynomial \$- 2x + 2x^3\$.
The general idea is that we start with a polynomial where every coefficient is the lower bound, check if the polynomial is a "good" or "prime" polynomial (satisfies the first condition), and add it to the list of prime polynomials if it is. Repeat with the next polynomial (list of numbers) until every combination has been exhausted.
from math import sqrt; from itertools import count, islice
import itertools
from itertools import product
#is n prime?
def isPrime(n):
#https://stackoverflow.com/questions/4114167/checking-if-a-number-is-a-prime-number-in-python
return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))
#find P(x) using the polyList to represent the polynomial
def findSingleValue(polyList, x):
#https://stackoverflow.com/questions/18093509/how-can-i-create-functions-that-handle-polynomials
return sum((a*x**i for i,a in enumerate(polyList)))
#is the polynomial prime for x <= p - 1?
def isPolyPrime(polyList, prime):
#polyValue = 0
for x in range(prime - 1):
polyValue = sum((a*x**i for i,a in enumerate(polyList)))
if not isPrime(polyValue):
return False
return True
#generate the next combo, given the previous combo
def genCombo(combo, LB, HB):
deg = len(combo)
combo = list(combo)
index = deg - 1
while index >= 0:
if combo[index] < HB:
combo[index] += 1
index = -1
elif combo[index] == HB:
combo[index] = LB
index -= 1
combo = tuple(combo)
return combo
#main function
def verifyPrime():
prime = int(input("Enter the prime number you want to find a poly for: "))
LB = int(input("Enter the lower bound: "))
HB = int(input("Enter the higher bound: "))
deg = int(input("Enter the degree of the polynomial: "))
lowDegPoly= input("Press n if you do not want to include lower degree polynomials: ")
allCombosNum = (abs(HB - LB))**deg - 1
#creates list of all possible tuples that represent a poly
print("possible combos (including constant func): ")
print(allCombosNum)
goodPolyList = []
combo = ()
#create the first combo - this is used as the basis to generate more combos
for x in range(deg):
combo += (LB,)
for x in range(allCombosNum):
polyList = []
polyList.append(prime)
for coef in combo:
polyList.append(coef)
#now has a list of the prime and coefs; p + a1*x + a2*x^2 + ...
isGoodPoly = isPolyPrime(polyList, prime)
if isGoodPoly and not(lowDegPoly == "n" and combo[deg - 1] == 0):
goodPolyList.append(polyList)
#personal usage: keeps track of how many more combos it needs to go through
numLeft = allCombosNum - x
if (numLeft % 100000) == 0:
print(numLeft)
#create the next combo
combo = genCombo(combo, LB, HB)
print("################################################")
print("poly generating finished")
print()
print(goodPolyList)
#bonus stuff
#goes over items in the goodPolyList and shows what primes each generates
for item in goodPolyList:
primeList = []
for x in range(prime - 1):
primeList.append(findSingleValue(item, x))
print()
print("List of primes that" , item, "generates: ")
print(primeList)
print()
print("There are" , len(goodPolyList) , "good polynomials for", prime ,
"with bounds" , LB , " to" , HB, "inclusive up to degree" , deg)
verifyPrime()
verifyPrime()
(As you see I've used a couple snippets of code from stackoverflow. Admittedly this is for simplicity's sake as I don't quite understand them.)
I am mostly concerned with speed since I intend to go through a very high amount of polynomials. However, since I am still very new at this, any feedback is appreciated, particularly in keeping code clean, comments/variable names -- basic stuff (but again, any feedback is fine). If it matters, this code will be for my personal use and not for any school assignment/project.