Tukukkk

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 2D list of polynomials, represented by numbers (see example). Each polynomial $P(x)$ satisfies the following conditions:

1. $P(x) + p$ is prime for $1 le x le p - 2$ (where $x$ is an integer), and $P(0) = 0$ (it has no attached constants).




2. 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).




3. 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 each 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 the polynomial $11 - 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.

Thank you very much!