4

For a task on ProjectEuler I've written code that uses brute force to find the longest chain of primes below 100 that add up to a prime, and the code does give the correct results. So for numbers below 100 the answer is 2 + 3 + 5 + 7 + 11 + 13 = 41

import math

def prime(n):
    for x in xrange(2,int(math.sqrt(n)+1)):
        if n%x == 0:
            return False
    return True

primes = []

for x in xrange(2,100):
    if prime(x):
        primes += [x]

record = 0
i = 0

for num in primes:
    i += 1
    chain = [num]
    for secnum in xrange(i,len(primes)-1):
        chain += [primes[secnum]]
        if len(chain) > record and sum(chain) in primes:
            record = len(chain)
            seq = chain
            print seq

print seq

When I run this code I get

[2, 3]
[2, 3, 5, 7]
[2, 3, 5, 7, 11, 13]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89]

That last line is extremely confusing to me. In my mind the two print statements should give the same reult. How did my variable seq get assigned to that long list? The last list doesn't even meet the requirements of the if statement wherein seq is assigned. I'm sure this is some really silly brain fart, but I just can't figure out what I screwed up

mitghi
  • 889
  • 7
  • 20
sakana
  • 97
  • 1
  • 5

2 Answers2

7

seq = chain creates another reference to the same chain list. You then print that list, but the loop doesn't stop.

You continue to expand chain, and since seq is just a reference to that list, you'll see those changes once the loop has ended. During the remaining for loop iterations chain / seq continues to change, but the if condition is no longer met so you don't see these changes take place.

You continue to expand chain here:

chain += [primes[secnum]]

This uses augmented assignment; it doesn't create a new list but extends the existing list. It is equivalent to chain.extend(primes[secnum]).

You can fix this by creating a copy of chain to store in seq:

seq = chain[:]
Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
1

In python you can use + operator to join two lists together. So [1] + [2] will yield [1,2]

    chain += [primes[secnum]]
    if len(chain) > record and sum(chain) in primes:
        record = len(chain)
        seq = chain
        print seq

chain variable is getting bigger by += operator which is joining chain ( a list ) to another list . So it will get bigger and when you print seq, because seq is equal to chain now, you get the latest result.

mitghi
  • 889
  • 7
  • 20