Project Euler Solution 50: Consecutive prime sum

Here we have Problem 50: Consecutive prime sum about prime numbers which are sums of other prime numbers.

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?

I had to try a few approaches here. There are around 78,000 primes below a million. If one takes all possible partial sums one would end up with about half of that number squared, which are just too many combinations. The number needs to be reduced.

We again have a parametrization issue. We need to find the start and the end of the sequence such that the sequence is the longest. It therefore makes sense to parametrize the sequence length first and then go over the start positions. But which sequence length is possible? If we start at 78,000, we have a lot of work to do.

The smallest numbers are the first one in the list of prime numbers. We can see how many we can add up before it will exceed a million. I wrote this function for that:

def get_max_sequence_length(primes: list[int]) -> int:
    accumulator = 0
    for i, prime in enumerate(primes, 1):
        accumulator += prime
        if accumulator > 1_000_000:
            return i

And surprisingly the result is 547, one cannot have a longer sequence. We then start with these sequence lengths and just iterate through all possible beginnings. In order to not recompute the sum every time I just subtract the smallest number and add the largest. This way we have a moving sum. And when I'm done with a certain length, I can go to the next one. As always, we are using the sieve from Solution 7: 10001st prime.

def solution() -> int:
    ceiling = 1_000_000
    primes = prime_sieve(ceiling)
    prime_set = set(primes)
    max_prime = primes[-1]
    for length in range(get_max_sequence_length(primes), 0, -1):
        rolling_sum = sum(primes[:length])
        for begin in range(len(primes) - length):
            end = begin + length
            rolling_sum += primes[end] - primes[begin]
            if rolling_sum > max_prime:
                break
            if rolling_sum in prime_set:
                return rolling_sum

This gets the correct result in 373 ms, which I find pretty reasonable.