Consecutive prime sum

Solved on
Uploaded on

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

Brute-force solution


def brute():
    primes = [2]
    max_reps = 1
    max_prime = 0
    for i in range(3, 1000000, 2):
        if is_prime(i, primes):
            primes.append(i)
            sequence = []
            for k in range(len(primes)):
                sequence.append(primes[k])
                can_break = False
                while sum(sequence) > i:
                    sequence.remove(sequence[0])
                    if len(sequence) < max_reps:
                        can_break = True
                        break
                if can_break: break
                if sum(sequence) == i:
                    if len(sequence) > max_reps:
                        max_reps = len(sequence)
                        max_prime = i
    print(max_prime, max_reps)



def is_prime(num, primes):
    root = num**(1 / 2) + 1
    for prime in primes:
        if prime > root: return True
        if num % prime == 0: return False
    return True

Strategic solution


def strategic():
    primes = [2]
    max_reps = 1
    max_prime = 0
    for i in range(3, 1000000, 2):
        if is_prime(i, primes):
            primes.append(i)
            sequence = [primes[j] for j in range(max_reps)]
            j = max_reps
            while sum(sequence) != i:
                while sum(sequence) < i:
                    sequence.append(primes[j])
                    j = j + 1
                can_break = False
                while sum(sequence) > i:
                    sequence.remove(sequence[0])
                    if len(sequence) < max_reps:
                        can_break = True
                        break
                if can_break: break
            if sum(sequence) == i:
                if len(sequence) > max_reps:
                    max_reps = len(sequence)
                    max_prime = i
    print(max_prime, max_reps)

Execution


#brute()
strategic()

# 61758th
# 53659th level 2

Output


brute: 997651