Open Source · 7 Languages · 900+ Problems

Project Euler Solutions

Complete solutions in C++, Python & Java — with step-by-step mathematical explanations

All Problems

Problem 304: Primonacci

Project Euler Problem 304 Solution

EulerSolve provides an optimized solution for Project Euler Problem 304, Primonacci, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let $p_1,p_2,\dots,p_m$ be the first $m$ primes strictly larger than a huge starting value $A$. The task is to compute $\sum_{i=1}^{m}F_{p_i}\pmod{M},$ where $F_n$ is the Fibonacci sequence and the official parameters are extremely large. Mathematical Approach 1) Why prime generation must be segmented The primes we need live near $A\approx 10^{14}$. A naive primality test for each number in that region would be far too slow, and a full sieve up to $A$ is impossible in memory. The right tool is a segmented sieve. We scan blocks $[L,H],$ and mark composites inside that block using all base primes up to $\sqrt{H}$. 2) Why primes up to $\sqrt{H}$ are enough If $x\in [L,H]$ is composite, then $x=ab$ with $1<a\le b$. Hence $a\le \sqrt{x}\le \sqrt{H}.$ So every composite in the segment has a prime divisor not exceeding $\sqrt{H}$. Therefore, after marking multiples of all primes $p\le \sqrt{H}$, every remaining unmarked number in the segment is prime. 3) Where marking starts inside a segment For a fixed base prime $p$, the first multiple of $p$ inside the current segment is $\left\lceil\frac{L}{p}\right\rceil p.$ But we must also avoid marking the prime $p$ itself when $p\in[L,H]$....

Detailed mathematical approach

Problem Summary

Let $p_1,p_2,\dots,p_m$ be the first $m$ primes strictly larger than a huge starting value $A$. The task is to compute

$\sum_{i=1}^{m}F_{p_i}\pmod{M},$

where $F_n$ is the Fibonacci sequence and the official parameters are extremely large.

Mathematical Approach

1) Why prime generation must be segmented

The primes we need live near $A\approx 10^{14}$. A naive primality test for each number in that region would be far too slow, and a full sieve up to $A$ is impossible in memory. The right tool is a segmented sieve.

We scan blocks

$[L,H],$

and mark composites inside that block using all base primes up to $\sqrt{H}$.

2) Why primes up to $\sqrt{H}$ are enough

If $x\in [L,H]$ is composite, then $x=ab$ with $1<a\le b$. Hence

$a\le \sqrt{x}\le \sqrt{H}.$

So every composite in the segment has a prime divisor not exceeding $\sqrt{H}$. Therefore, after marking multiples of all primes $p\le \sqrt{H}$, every remaining unmarked number in the segment is prime.

3) Where marking starts inside a segment

For a fixed base prime $p$, the first multiple of $p$ inside the current segment is

$\left\lceil\frac{L}{p}\right\rceil p.$

But we must also avoid marking the prime $p$ itself when $p\in[L,H]$. Therefore the correct starting point is

$\max\!\left(p^2,\left\lceil\frac{L}{p}\right\rceil p\right).$

This is exactly what the code computes before it walks through the segment in steps of $p$.

4) Fibonacci values via fast doubling

Once the prime indices $p_i$ are known, we still cannot generate Fibonacci numbers linearly up to index $10^{14}$. The code instead computes $(F_n,F_{n+1})$ with fast doubling.

Using the addition formulas

$F_{m+n}=F_mF_{n+1}+F_{m-1}F_n,$

and substituting $m=n=k$, one obtains the standard doubling identities

$F_{2k}=F_k(2F_{k+1}-F_k),$

$F_{2k+1}=F_k^2+F_{k+1}^2.$

Thus from $(F_k,F_{k+1})$ we can compute $(F_{2k},F_{2k+1})$, and then decide whether $n$ is even or odd. Each recursive step halves the index, so the running time is $O(\log n)$.

5) Why modular arithmetic can be applied early

All arithmetic is needed only modulo $M$. Since Fibonacci recurrences use only addition, subtraction, and multiplication, we may reduce after every operation:

$F_n \bmod M$

can be computed without ever forming the enormous exact integer $F_n$. This is why the solution remains fast even though the indices are gigantic.

6) Small worked checkpoint

The C++ code contains a cross-check on a much smaller range:

$A=1000,\qquad m=30,\qquad M=10^9+7.$

The first few primes after $1000$ are

$1009,\ 1013,\ 1019,\ 1021,\ 1031,\dots$

and the corresponding Fibonacci residues begin as

$F_{1009}\equiv 529241575,\qquad F_{1013}\equiv 613716502,\qquad F_{1019}\equiv 506824938\pmod{10^9+7}.$

For the first $30$ such primes, the checkpoint sum is

$\sum_{i=1}^{30}F_{p_i}\equiv 682050181\pmod{10^9+7}.$

The program compares its segmented-sieve result with a brute-force prime search on that small input.

7) Safe preprocessing bounds

Because the main search scans segments whose upper endpoint is roughly $A+\text{segment\_size}$, it is enough to precompute base primes up to a safe constant slightly larger than

$\sqrt{A+\text{segment\_size}}.$

For $A\approx 10^{14}$, this is about $10^7$, which explains the base-prime sieve limit used in the implementations.

How the Code Works

The solver has three clean stages:

1. generate base primes with an ordinary sieve up to a safe square-root bound;

2. run a segmented sieve to extract the first $m$ primes after $A$;

3. compute each $F_{p_i}\bmod M$ by fast doubling and accumulate the sum modulo $M$.

The helper fib_pair_mod(n, mod) returns $(F_n,F_{n+1})$, so each prime index is handled independently in logarithmic time.

Complexity Analysis

The segmented sieve is essentially linear in the total length of the scanned blocks, up to the usual harmonic marking cost from small primes. The Fibonacci part costs

$O(m\log A),$

because each of the $m$ prime indices needs one logarithmic fast-doubling evaluation. Memory usage is modest: one segment bitmap plus the base-prime list.