Fibonacci and Primes

Computer Science Level 5

$\large S(N)=\sum F_p$

Define the summation above for all primes $p$ less than $N$ .

The Fibonacci sequence $\{F_n\}$ is defined by $F_0=0,F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ for all integers $n\geq 2$ .

It is given that

$\begin{aligned} S(10)&=&21 \\ S(10^2)&\equiv & 350775433\pmod{10^9+7} \\ S(10^3)& \equiv & 347000363\pmod{10^9+7} \end{aligned}$

Find the value of $S(10^7)$ modulo $10^9+7$ .

The answer is 223971178.

3 solutions

Russelle Guadalupe
Jun 8, 2015

Here is the code in C++. It runs in about 100-200 ms to get the answer $223971178$ . We precompute the primes $p$ less than $10^7$ and then evaluate $\sum F_p$ .

#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
#define ll long long
#define N 10000000
#define mod 1000000007

bool arr[N+1];
ll primes[664580];
ll fib[N+1];

void init() {
    for(int i = 0; i < N+1; i++) { arr[i] = true; }
    arr[0] = arr[1] = false;
    for(int i = 2; i*i < N+1; i++) {
        if(arr[i]) {
            for(int j = 2; j*i < N+1; j++) {
                arr[j*i] = false;
            }
        }
    }
    primes[0] = 0;
    primes[1] = 2;
    int c = 2;
    for(int i = 3; i < N+1; i+=2) { if(arr[i]) primes[c++] = i; }
    fib[0] = 0;
    fib[1] = 1;
    for(int i = 2; i < N+1; i++) { fib[i] = (fib[i-1]+fib[i-2]) % mod; }
}

int main () {
    init();
    ll sum = 0;
    ll n =N;
    for(int i = 1; i < 664580; i++) {
        if(primes[i] <= n) { sum = (sum+fib[primes[i]]) % mod; }
    }
    printf("%lld\n", sum);
    return 0;
}

Rushikesh Jogdand
Jul 22, 2016

fib=[0,1]
for i in range(10**7-1):
    fib.append((fib[-1]+fib[-2])%int(10**9+7))          #taking mod 10**9+7 is the key step
su=0
su+=fib[2]+fib[3]
a,b=5,7
from gmpy import is_prime as p
while b<1000000:
    for i in [a,b]:
        if p(i):su+=fib[i]
    a+=6
    b+=6
print(su%(10**9+7))

Zawad Abdullah
Jun 19, 2015

I wrote a C code for this. It took almost 0.45 seconds to run.

#include<stdio.h>
#include<math.h>
int ara[10000001];
long int fib[10000001];
void sieve(void)
{
    int i, j, sq;
    for(i = 4; i < 10000001; i += 2)
    {
        ara[i] = 1;
    }
    sq = sqrt(10000001);
    for(i = 3; i <= sq; i += 2)
    {
        if(!ara[i])
        {
            for(j = i*i; j < 10000001; j += 2*i)
            {
                ara[j] = 1;
            }
        }
    }
}
long int fibo(void)
{
    int i;
    long int sum = 0;
    sieve();
    fib[0] = 0, fib[1] = 1;
    for(i = 2; i < 10000001; i++)
    {
        fib[i] = (fib[i-1] + fib[i-2])%1000000007;
        if(!ara[i])
        {
            sum = (sum + fib[i])%1000000007;
        }
    }
    return sum;
}
int main()
{
    int k;
    k = fibo();
    printf("%ld\n", k);
    return 0;
}

Fibonacci and Primes

The answer is 223971178.

3 solutions

0 pending reports