Prime X-nacci modded Terms

[xgeutzu]

I will copy - paste the problem here:

The standard Fibonacci sequence is represented by the sum of the previous 2 terms. Generally, it can be expressed as:

Fn = Fn-1 + Fn-2
Just as well, we can express an X-nacci sequence where the next number is the sum of the previous X number of terms. The general form for this would be:

Fn = Fn-1 + Fn-2 + ... + Fn-x
The sequence for any X-nacci always begins with the first X terms being 1. So for a 4-Nacci sequence the start would be:

1 1 1 1 4 7 13 25 ...
But realizing that the values of any X-nacci sequence terms get large rather quickly, we want to mod the resulting number by 1,000,000 to keep the values of the terms from 0 to 999,999. The formula will still be the same except you need to mod the result:

Fn = (Fn-1 + Fn-2 + ... + Fn-x) MOD 1,000,000
How many of the first 1,000,000 terms of a 25-nacci sequence that is modded by 1,000,000 are prime?

 #include <iostream>

using namespace std;

bool prim(unsigned long int n);

int main()
{
   int vect_fib[27];

   for(int i=1;i<26;i++)
        vect_fib[i] = 1;

    vect_fib[26] = 25; int count = 0;

    for(int k=0;k<1000000;k++)
    {
        if(vect_fib[26] > 1000000)    vect_fib[26] = vect_fib[26] % 1000000;

        if(prim(vect_fib[26])) ++count;

        cout << endl;

        //move every fib term to the left, lefting space on vect_fib[26] for a new term
        for(int i=0;i<26;i++)
            vect_fib[i]=vect_fib[i+1];

        //generating a new fib term
        for(int i=24;i>0;i--)
            vect_fib[26] = vect_fib[26] + vect_fib[i];

        for(int i=0;i<27;i++)
            cout << vect_fib[i] << " ";

    }

    cout << count;

}

bool prim(unsigned long int n) {
  unsigned long int i;

  for (i = 2; i <= n / 2; i++)
    if (n % i == 0)
      return false;
  return true;
}

running time : 527 sec.

count == 159,372 but it says to me that the answer is wrong.

do anybody have any hint, suggestion ?

[keskiverto]

You have 26 terms in the vector already. How many more to check with line 16?

[xgeutzu]

ok..

 for(int k=26;k<1000000;k++)

now i got 159,366 , and it is still a wrong answer.

[keskiverto]

The logic of the sum. vect_fib[N] should be the sum of vect_fib[0]..vect_fib[N-1], should it not?

Overall, do not write "magic numbers" (25, 26, 27) all over the code. Set named constants at start.

[xgeutzu]

#include <iostream>

bool prim(int n);

int main()
{
    int v[1000001], count = 0;

    for(int i=0;i<25;i++)
        v[i] = 1;
    v[25] = 25;

    for(int i=26;i<1000000;i++)
    {
        v[i] = 0;
        for(int x=1;x<26;x++)
            v[i] = v[i] + v[i-x];

        if(v[i]>1000000) v[i] = v[i] % 1000000;

        if(prim(v[i])) ++count;
    }

    std::cout << count;

}

bool prim(int n) {
  int i;

  for (i = 2; i <= n / 2; i++)
    if (n % i == 0)
      return false;
  return true;
}

ET 193 sec.


this is my last work... i'm getting 159,366 ... and it says to me that it is a wrong answer... i've also tried to and 25 - first 25 terms ( 1, 1, 1, ..25times.. 1, 1) , but also a wrong answer...

can anyone hel me ?

[dhayden]

EDIT: Pay no attention to this post. As xgeutzu points out below it's all wrong. Guess I needed more coffee that morning. :(

In your latest post, line 17 overwrites v[i] each time through the loop. It should be v[i] += v[i-x];
The problem calls for checking the first 1 million terms so line 13 should be for(int i=26;i<=1000000;i++)

If this doesn't work then try printing out the first 30 or so terms to see if they look reasonable.

[xgeutzu]

thank you for your reply !

v[i] = v[i] + v[i-x] is the same shit with v[i] += v[i-x], however I did the change and i got the same result;

i put i<1000000, because i starts from 0, so from =0 to <1,000,000, are 1,000,000 terms, however i did the change and i got the same result;

i did that, i printed out the prime numbers from v[0] to v[30] and it looks good
{ 97, 193, 769}

[norm b]

Is execution time a consideration?

You can speed things up by going to the square root of n, in lieu of n/2, in your function prim().

[xgeutzu]

thank you for your hint, but no, ET isn't a consideration

[norm b]

How many of the first 1,000,000 terms of a 25-nacci sequence that is modded by 1,000,000 are prime?

Try putting your counter inside if/mod?

if(v[i]>1000000) {
    v[i] = v[i] % 1000000;
    if(prim(v[i])) ++count;
}

[dhayden]

Line 19 does the mod check already. I think Norm B's change isn't right since it only checks primes when the unmodd'ed value is over 1,000,000.

[xgeutzu]

i check manually for the first 30 numbers of the 25-nacci, it gives me 28 (with the first 25 of 1 included), I did then with the code that I writed, same 28. I don't get it what is wrong ?!

[dhayden]

I don't know what's wrong either. I googled it and found another person who had the same answer as you.

[cire]

I don't get it what is wrong ?!

You aren't generating the fibonacci sequence, for one. You might want to start with that.

[dhayden]

You aren't generating the fibonacci sequence

The problem doesn't call for the fibonacci sequence. It uses a modification of it.

[norm b]

Don't know whether this will give you the correct answer or not, but in some cases v[i] % 1000000 == 1. 1 is not a prime number.
Check your prim() function.

[xgeutzu]

@norm b
You're the man !!!!!!!

i modify the prime function and it works !!!

my prime function:

bool prim(long n) {
    long i;

    if(n<2) return false;
    if(n==2) return true;
    if(n%2==0) return false;
    for(i=3;(i*i)<=n;i+=2)
        if(n%i==0) return false;
    return true;
}

[dhayden]

Yes, kudos to Norm B!!! Thanks for pointing out the problem.