Posts: 201
Threads: 37
Joined: Dec 2021
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
Posts: 377
Threads: 2
Joined: Jan 2021
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
Posts: 201
Threads: 37
Joined: Dec 2021
Jan-17-2022, 04:46 PM
(This post was last modified: Jan-17-2022, 07:15 PM by Yoriz.
Edit Reason: removed unnecessary quote of previous post
)
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
Posts: 377
Threads: 2
Joined: Jan 2021
(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.
Posts: 6,778
Threads: 20
Joined: Feb 2020
Jan-18-2022, 12:40 PM
(This post was last modified: Jan-18-2022, 12:40 PM by deanhystad.)
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)
Posts: 201
Threads: 37
Joined: Dec 2021
(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.
Posts: 201
Threads: 37
Joined: Dec 2021
Jan-18-2022, 02:56 PM
(This post was last modified: Jan-18-2022, 02:56 PM by Frankduc.)
(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
Posts: 6,778
Threads: 20
Joined: Feb 2020
Jan-18-2022, 03:59 PM
(This post was last modified: Jan-18-2022, 04:00 PM by deanhystad.)
[] is an empty list. It is being used exactly the same way you used [] in your program.
Posts: 201
Threads: 37
Joined: Dec 2021
Jan-18-2022, 05:46 PM
(This post was last modified: Jan-18-2022, 05:46 PM by Frankduc.)
(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.
|
