Python Forum

Hello,

I am trying to count the number of pairs but in the end i only want the variable count give the total.

import itertools

lim = int(input("Generate prime numbers up to : "))
listo = []
def prime_eratosthenes(lim):
    prime_list = []
    
    for i in range(2, lim+1):
        if i not in prime_list:
            print (i, end = ' ')
            listo.append(i)
            for j in range(i*i, lim+1, i):
                prime_list.append(j)
               # print(j)

    return listo
    

  
  


def printPairs(lim):
    primes = prime_eratosthenes(lim)
    for i in range(0, len(primes)):
        for j in range(i+1, len(primes)):
            if (primes[i]*primes[j])==lim:
                print(' ')
                print("Primes multiply that gives: ",lim)
                print(primes[i], primes[j])
                
printPairs(lim)
print('')
print('Primes sum that gives:', lim)
  

som = 0
count = 0
for L in range(0, len(listo)+1):
    for subset in itertools.combinations(listo, L):
        som = sum(subset)
        if (som == lim):
            print(som, subset)
            count += 1 
            print("Number of pairs: ", count)

            
            
            

Output:
Generate prime numbers up to : 10
2 3 5 7  
Primes multiply that gives:  10
2 5

Primes sum that gives: 10
10 (3, 7)
Number of pairs:  1
10 (2, 3, 5)
Number of pairs:  2
> 

Its only repeating number of pairs 1, 2 ...
I just want the total 2 pairs

Thank you

Do you mean like this?

import itertools
 
lim = int(input("Generate prime numbers up to : "))
listo = []
def prime_eratosthenes(lim):
    prime_list = []
     
    for i in range(2, lim+1):
        if i not in prime_list:
            print (i, end = ' ')
            listo.append(i)
            for j in range(i*i, lim+1, i):
                prime_list.append(j)
               # print(j)
 
    return listo
     
 
   
   
 
 
def printPairs(lim):
    primes = prime_eratosthenes(lim)
    for i in range(0, len(primes)):
        for j in range(i+1, len(primes)):
            if (primes[i]*primes[j])==lim:
                print(' ')
                print("Primes multiply that gives: ",lim)
                print(primes[i], primes[j])
                 
printPairs(lim)
print('')
print('Primes sum that gives:', lim)
   
 
som = 0
count = 0
for L in range(0, len(listo)+1):
    for subset in itertools.combinations(listo, L):
        som = sum(subset)
        if (som == lim):
            print(som, subset)
            count += 1 

print("Number of pairs: ", count)

Output:
Generate prime numbers up to : 10
2 3 5 7  
Primes multiply that gives:  10
2 5

Primes sum that gives: 10
10 (3, 7)
10 (2, 3, 5)
Number of pairs:  2

Yes exactly i have done that but if i input 100 it wont return the number of pairs. Maybe its the compiler that has a limit.

Also is it possible to initialize the variable count at the top so that the numbers count appear just after Primes sum that gives:?

TY

(Jan-17-2022, 04:46 PM)Frankduc Wrote: [ -> ]Also is it possible to initialize the variable count at the top so that the numbers count appear just after Primes sum that gives:?

Do you mean like this?

import itertools
  
lim = int(input("Generate prime numbers up to : "))
listo = []
def prime_eratosthenes(lim):
    prime_list = []
      
    for i in range(2, lim+1):
        if i not in prime_list:
            print (i, end = ' ')
            listo.append(i)
            for j in range(i*i, lim+1, i):
                prime_list.append(j)
               # print(j)
  
    return listo
      
def printPairs(lim):
    primes = prime_eratosthenes(lim)
    for i in range(0, len(primes)):
        for j in range(i+1, len(primes)):
            if (primes[i]*primes[j])==lim:
                print(' ')
                print("Primes multiply that gives: ",lim)
                print(primes[i], primes[j])
                  
printPairs(lim)
som = 0
count = 0
for L in range(0, len(listo)+1):
    for subset in itertools.combinations(listo, L):
        som = sum(subset)
        if (som == lim):
            print(som, subset)
            count += 1 

print('')
print('Primes sum that gives:', lim)
print("Number of pairs: ", count)

Also, if you give it an 85 or 86 to chew on, you can see how long it takes. I think 100 is just overloading something.

Primes up to 100 is not a big list.
Primes < 10 are 2, 3, 5, 7: 4 numbers
primes < 100 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97: 25 numbers

However, the number of possible combinations of these numbers grows very quickly.
Adding up all the combinations of the numbers in the primes(10) list taken 1 at a time, 2 at a time, 3 at a time and 4 at a time = 15 combinations.
The list of primes < 20 has only 8 numbers but 255 combinations.
The list of primes < 50 has 15 numbers and 32767 combinations.
The list of primes < 100 has 25 numbers and a wopping 33,554,431 combinations.

If n is the number of prime numbers, the number of combinations is 2^n - 1.

But this is not even the correct solution, because I don't see any prohibition against using 2*2*2 = 8, but (2,2,2) is not returned when you ask for all combinations of (2, 3, 5, 7) taken 3 at a time. To include combinations like (2, 2, 2) you need to use itertools.combinations_with_replacement(). Now primes < 10 has 69 combinations to test, primes < 20 has 12869 combinations, and I gave up when primes < 50 came up with 155,117,519 combinations.

I think the code below works and it is really efficient when compared to using combinations. products(100) recursively calls itself 99 times to compute the 1 product.

sums(100) calls itself 547,013 times to compute 48,899 sums. That means it finds a sum almost 1 in 10 tries. Using combinations you don't get all the sums and it only finds a sum about 1 in 1000 tries. Using combinations with replacement the hit to miss ration is probably around 1 in 1 million.

def prime_numbers(end):
    """Compute primes up to and including end using sieve of Eratosthenes algorithm"""
    primes = []
    not_primes = []
    end += 1
    for p in range(2, end):
        if p not in not_primes:
            primes.append(p)
            for np in range(p*p, end, p):
                not_primes.append(np)
    return primes

def products(target, choices, partial_product=1, values=None, solutions=None):
    """
    Recursively find all combinations of choices whose product equals target.
    choices is list of numbers (here primes) that can be used as multiplicands.
    Save successful product lists in solutions.  Save partial product list
    in values.
    """
    if values is None:   # First call.  Create values and solutions lists for recursions
        products.count = 0
        choices = choices.copy()
        choices.sort()   # Solution requires choices to be sorted
        return products(target, choices, partial_product, [], [])

    products.count += 1
    for index, choice in enumerate(choices):
        attempt = values + [choice]
        if (product := partial_product * choice) < target:
            # Add choice as a multiplicand
            products(target, choices[index:], product, attempt, solutions)
        else:
            # Add solution if product == target.  Either way there are
            # no remaining solutions in this thread
            if product == target:
                solutions.append(attempt)
            break
    return solutions

def sums(target, choices, values=None, solutions=None):
    """
    Recursively find all combinations of choices whose sum equals target.
    choices is list of values that can be used as addends.
    Save successful sum lists in solutions.  Save partial sum list
    in values.
    """
    if values is None:   # First call.  Create values and solutions lists for recursions
        sums.count = 0
        choices = choices.copy()
        choices.sort()   # Solution requires choices to be sorted
        return sums(target, choices, [], [])

    sums.count += 1
    sum_values = sum(values)
    for index, choice in enumerate(choices):
        # Add choice as addend
        attempt = values + [choice]
        if choice < target:
            sums(target-choice, choices[index:], attempt, solutions)
        else:
            # Add sum to solution if sum == target.  Either way there
            # are no solutions remaining in this thread.
            if choice == target:
                solutions.append(attempt)
            break
    return solutions

target = 100
primes = prime_numbers(target)
print("Products", target, products(target, primes), products.count)
print("Sums", target, len(sums(target, primes)), sums.count)

(Jan-17-2022, 07:37 PM)BashBedlam Wrote: [ -> ]

(Jan-17-2022, 04:46 PM)Frankduc Wrote: [ -> ]Also is it possible to initialize the variable count at the top so that the numbers count appear just after Primes sum that gives:?

Do you mean like this?

import itertools
  
lim = int(input("Generate prime numbers up to : "))
listo = []
def prime_eratosthenes(lim):
    prime_list = []
      
    for i in range(2, lim+1):
        if i not in prime_list:
            print (i, end = ' ')
            listo.append(i)
            for j in range(i*i, lim+1, i):
                prime_list.append(j)
               # print(j)
  
    return listo
      
def printPairs(lim):
    primes = prime_eratosthenes(lim)
    for i in range(0, len(primes)):
        for j in range(i+1, len(primes)):
            if (primes[i]*primes[j])==lim:
                print(' ')
                print("Primes multiply that gives: ",lim)
                print(primes[i], primes[j])
                  
printPairs(lim)
som = 0
count = 0
for L in range(0, len(listo)+1):
    for subset in itertools.combinations(listo, L):
        som = sum(subset)
        if (som == lim):
            print(som, subset)
            count += 1 

print('')
print('Primes sum that gives:', lim)
print("Number of pairs: ", count)

Also, if you give it an 85 or 86 to chew on, you can see how long it takes. I think 100 is just overloading something.

No i mean print: print("Number of pairs: ", count) above

som = 0
count = 0
for L in range(0, len(listo)+1):
    for subset in itertools.combinations(listo, L):
        som = sum(subset)
        if (som == lim):
            print(som, subset)
            count += 1 

In C# you can place count = 0 at the top right after listo and than print wherever you want count.
Like this:

import itertools
count = 0
lim = int(input("Generate prime numbers up to : "))
listo = []
def prime_eratosthenes(lim):
    prime_list = []
    
    for i in range(2, lim+1):
        if i not in prime_list:
            print (i, end = ' ')
            listo.append(i)
            for j in range(i*i, lim+1, i):
                prime_list.append(j)
               # print(j)

    return listo
    

  
  


def printPairs(lim):
    primes = prime_eratosthenes(lim)
    for i in range(0, len(primes)):
        for j in range(i+1, len(primes)):
            if (primes[i]*primes[j])==lim:
                print(' ')
                print("Primes multiply that gives: ",lim)
                print(primes[i], primes[j])
                
printPairs(lim)
print('')
print('Primes sum that gives:', lim)
print("Number of pairs: ", count) 
 

som = 0


for L in range(0, len(listo)+1):
    for subset in itertools.combinations(listo, L):
        som = sum(subset)
        if (som == lim):
            print(som, subset)
            count += 1 

but number of pairs will return 0.
Yes at 100 it is a lot. For now i am using an online compiler.

(Jan-18-2022, 12:40 PM)deanhystad Wrote: [ -> ]Primes up to 100 is not a big list.
Primes < 10 are 2, 3, 5, 7: 4 numbers
primes < 100 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97: 25 numbers

However, the number of possible combinations of these numbers grows very quickly.
Adding up all the combinations of the numbers in the primes(10) list taken 1 at a time, 2 at a time, 3 at a time and 4 at a time = 15 combinations.
The list of primes < 20 has only 8 numbers but 255 combinations.
The list of primes < 50 has 15 numbers and 32767 combinations.
The list of primes < 100 has 25 numbers and a wopping 33,554,431 combinations.

If n is the number of prime numbers, the number of combinations is 2^n - 1.

But this is not even the correct solution, because I don't see any prohibition against using 2*2*2 = 8, but (2,2,2) is not returned when you ask for all combinations of (2, 3, 5, 7) taken 3 at a time. To include combinations like (2, 2, 2) you need to use itertools.combinations_with_replacement(). Now primes < 10 has 69 combinations to test, primes < 20 has 12869 combinations, and I gave up when primes < 50 came up with 155,117,519 combinations.

I think the code below works and it is really efficient when compared to using combinations. products(100) recursively calls itself 99 times to compute the 1 product.

sums(100) calls itself 547,013 times to compute 48,899 sums. That means it finds a sum almost 1 in 10 tries. Using combinations you don't get all the sums and it only finds a sum about 1 in 1000 tries. Using combinations with replacement the hit to miss ration is probably around 1 in 1 million.

def prime_numbers(end):
    """Compute primes up to and including end using sieve of Eratosthenes algorithm"""
    primes = []
    not_primes = []
    end += 1
    for p in range(2, end):
        if p not in not_primes:
            primes.append(p)
            for np in range(p*p, end, p):
                not_primes.append(np)
    return primes

def products(target, choices, partial_product=1, values=None, solutions=None):
    """
    Recursively find all combinations of choices whose product equals target.
    choices is list of numbers (here primes) that can be used as multiplicands.
    Save successful product lists in solutions.  Save partial product list
    in values.
    """
    if values is None:   # First call.  Create values and solutions lists for recursions
        products.count = 0
        choices = choices.copy()
        choices.sort()   # Solution requires choices to be sorted
        return products(target, choices, partial_product, [], [])

    products.count += 1
    for index, choice in enumerate(choices):
        attempt = values + [choice]
        if (product := partial_product * choice) < target:
            # Add choice as a multiplicand
            products(target, choices[index:], product, attempt, solutions)
        else:
            # Add solution if product == target.  Either way there are
            # no remaining solutions in this thread
            if product == target:
                solutions.append(attempt)
            break
    return solutions

def sums(target, choices, values=None, solutions=None):
    """
    Recursively find all combinations of choices whose sum equals target.
    choices is list of values that can be used as addends.
    Save successful sum lists in solutions.  Save partial sum list
    in values.
    """
    if values is None:   # First call.  Create values and solutions lists for recursions
        sums.count = 0
        choices = choices.copy()
        choices.sort()   # Solution requires choices to be sorted
        return sums(target, choices, [], [])

    sums.count += 1
    sum_values = sum(values)
    for index, choice in enumerate(choices):
        # Add choice as addend
        attempt = values + [choice]
        if choice < target:
            sums(target-choice, choices[index:], attempt, solutions)
        else:
            # Add sum to solution if sum == target.  Either way there
            # are no solutions remaining in this thread.
            if choice == target:
                solutions.append(attempt)
            break
    return solutions

target = 100
primes = prime_numbers(target)
print("Products", target, products(target, primes), products.count)
print("Sums", target, len(sums(target, primes)), sums.count)

Quick reply to deanHystad. I have not review all of the code. The code you provide are always interesting and a bit sophisticated for me.
Very informative that part about Mersenne prime. Interesting: https://en.wikipedia.org/wiki/Mersenne_prime

I am not sure about that part print("Sums", target, len(sums(target, primes)), sums.count)
Sums 10 5 18
18 stands for number of times it calculates to reach 10?
What about return sums(target, choices, [], []) what use have the [] ? idexation


Thank you

[] is an empty list. It is being used exactly the same way you used [] in your program.

(Jan-18-2022, 03:59 PM)deanhystad Wrote: [ -> ][] is an empty list. It is being used exactly the same way you used [] in your program.

Ok so its the way to say that values and solutions are now list. Did not know we could do that.

I am a bit confuse. If i print("list of sums" ,sums(target,primes))

It will return :
list of sums [[2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 3, 5], [3, 7], [5, 5]]
The primes are only 2,3,5,7
Why [2, 2, 2, 2, 2] should be included? List combination from primes under 10 is enough. Why invent new combinations? Of course you want to list all combinations possible that return 10. Is it still a prime combination if you repeat one prime numbers to satisfied the condition? Maybe we could investigate this.