CODEWITHSUNDEEP
pythonlistmathgoldbach-conjecture
Hendrik
Hendrik

Reputation: 47

In a list of lists, how do I count the amount of equal sums I have in my list?

I am pretty new to Python and struggle to count my amount of equal sums in my list of lists. I create a list of numbers (list oneven), according to Goldbach every number is equal to three Primenumbers. I now have a list of all combination of prime numbers, now I want to count the amount of combinations that every number in list oneven has, and print it out. I tried using "import Collections" which wouldn't work due to my code not being hashable. Then I tired adding a number to an empty list which rises to the equal sums but I get the error message:

IndexError: list assignment index out of range

Here is my code with which I am struggling:

lijst2 = []
lijst = []
for i in oneven:
    for a in priemgetallen:
        for b in priemgetallen:
            if a >= b:
                c = i - a - b
                if c in priemgetallen and b >= c:
                    lijst.append([c,b,a])
for item in lijst:
    if sum(item) in lijst2:
        lijst2[sum(item)] = lijst2.get(sum(item))+1
    else:
        lijst2[sum(item)] = 1

for k,v in lijst2.items():
    print(str(k)+':'+str(v))

lijst2 = set(lijst)
print(lijst2)

Incase you are interested in what I am trying to do, I am trying to write a counter for Goldbachs theory, so here is my entire Code:

oneven = []
for i in range(7,102,2):
    oneven.append(i)

priemgetallen = [2]
counter = 3
while priemgetallen[-1] < oneven[-1]:
    priemgetallendelers = []
    for i in range (1,counter+1):
        if counter % i == 0:
            priemgetallendelers.append(i)
    if len(priemgetallendelers) == 2:
        priemgetallen.append(counter)
        counter += 1
    else:
        counter +=1

lijst2 = []
lijst = []
for i in oneven:
    for a in priemgetallen:
        for b in priemgetallen:
            if a >= b:
                c = i - a - b
                if c in priemgetallen and b >= c:
                    lijst.append([c,b,a])
for item in lijst:
    if sum(item) in lijst2:
        lijst2[sum(item)] = lijst2.get(sum(item))+1
    else:
        lijst2[sum(item)] = 1

for k,v in lijst2.items():
    print(str(k)+':'+str(v))

lijst2 = set(lijst)
print(lijst2)

At the end it should look a bit like this:

 7 =  2 +  2 +  3

 9 =  2 +  2 +  5
   =  3 +  3 +  3

11 =  2 +  2 +  7
   =  3 +  3 +  5

13 =  3 +  3 +  7
   =  3 +  5 +  5

Options to write: 7, 9, 11, ...:
1, 2, 2, 2, 3, 4, 3, 5, 5, 5, 7, 7, 6, 9, 8,

Upvotes: 0

Views: 95

Answers (1)

SergGr
SergGr

Reputation: 23788

There a few places where your code is rather inefficient. First of all, if you know the top limit of the primes you'll need, then Sieve of Eratosthenes is a much more efficient way to generate primes:

def primes_sieve(limit):
    if limit < 2:
        return []
    res = [2]
    odd_cnt = ((limit + 1) / 2)
    odd_sieve = [True] * odd_cnt
    odd_sieve[0] = False  # 1 is not a prime
    for (i, isprime) in enumerate(odd_sieve):
        if isprime:
            prime = 2 * i + 1
            res.append(prime)
            for n in xrange(i * (prime + 1), odd_cnt, prime):  # Mark factors non-prime, we can safely start at prime^2
                odd_sieve[n] = False
    return res

Then your loops with inner checks if a >= b: and if c in priemgetallen and b >= c: are very inefficient. It is much more efficient to iterate through primes with 3 nested loops, get sum and add it to the corresponding "bin". Also by remembering current index in the "outer" iteration and starting from it you can optimize your code by both removing the check and iterating less. The only trick is to filter out triplets of form [2, odd_prime, odd_prime] that produce even numbers. IMHO the easiest way to do it is just to run a separate loop for [2, 2, odd_prime] triplets.

def goldbach(limit = 101):
    primes = primes_sieve(limit)
    primes_except_2 = primes[1:]
    primes_len = len(primes_except_2)

    triplets = [[] for i in xrange(limit + 1)]

    # explicitly handle case [2,2,prime]
    # all other cases [2, prime, prime] generate even results
    for ci in xrange(primes_len):
        c = primes_except_2[ci]
        s = 4 + c # 2 + 2 + c
        if s > limit:
            break
        else:
            triplets[s].append([2, 2, c])

    for ai in xrange(primes_len):
        a = primes_except_2[ai]
        for bi in xrange(ai, primes_len):
            b = primes_except_2[bi]
            for ci in xrange(bi, primes_len):
                c = primes_except_2[ci]
                s = a + b + c
                if s > limit:
                    break
                else:
                    triplets[s].append([a, b, c])

    for k, v in enumerate(triplets):
        if len(v) > 0:
            print(str(k) + ':' + str(v))

goldbach(31) produces following output:

7:[[2, 2, 3]]
9:[[2, 2, 5], [3, 3, 3]]
11:[[2, 2, 7], [3, 3, 5]]
13:[[3, 3, 7], [3, 5, 5]]
15:[[2, 2, 11], [3, 5, 7], [5, 5, 5]]
17:[[2, 2, 13], [3, 3, 11], [3, 7, 7], [5, 5, 7]]
19:[[3, 3, 13], [3, 5, 11], [5, 7, 7]]
21:[[2, 2, 17], [3, 5, 13], [3, 7, 11], [5, 5, 11], [7, 7, 7]]
23:[[2, 2, 19], [3, 3, 17], [3, 7, 13], [5, 5, 13], [5, 7, 11]]
25:[[3, 3, 19], [3, 5, 17], [3, 11, 11], [5, 7, 13], [7, 7, 11]]
27:[[2, 2, 23], [3, 5, 19], [3, 7, 17], [3, 11, 13], [5, 5, 17], [5, 11, 11], [7, 7, 13]]
29:[[3, 3, 23], [3, 7, 19], [3, 13, 13], [5, 5, 19], [5, 7, 17], [5, 11, 13], [7, 11, 11]]
31:[[3, 5, 23], [3, 11, 17], [5, 7, 19], [5, 13, 13], [7, 7, 17], [7, 11, 13]]

You may also optimize triplets inside goldbach in a way similar to the one used in primes_sieve to store only odd indices (and not store empty lists for even ones) but I didn't bother.

Upvotes: 0

Related Questions