Proficient.
Put your skills to the test.

Problem summary

The Tribonacci sequence starts 0,0,1 and each later term is the sum of the preceding three. Find the least positive period of the sequence modulo P, or −1 if no such period exists.

Constraints

2≤P≤1000.

Worked example

An independently prepared example for this explanation.

10

124

Solution analysis

1. The state is the current triple of consecutive residues. Its transition (a,b,c)→(b,c,a+b+c mod q) is invertible: the preceding first value is c−a−b modulo q. Therefore the initial state always returns, with no nonperiodic prefix.
2. Factor P into pairwise coprime prime powers q. Simulate each smaller modulus until the state (0,0,1) returns, then take the least common multiple of these periods. The Chinese remainder theorem says a triple returns modulo P exactly when it returns modulo every prime power.
3. For P=10, the component periods modulo 2 and 5 are 4 and 31, so the answer is lcm(4,31)=124. Modulo 2 the residues repeat as 0,0,1,1. Factoring avoids simulating a potentially much longer combined period.

Why it works

Invertibility on a finite state space forces every state to lie on a cycle, so the first return gives the exact period for each prime power. A return modulo P is equivalent to simultaneous component returns, whose first positive time is their least common multiple.

Watch out. Test the whole triple, not one zero. The requested period is positive. Use 64-bit arithmetic for the least common multiple.

An independently written complete program with standard headers.

#include<iostream>
#include<numeric>
// Algorithm: The state is the current triple of consecutive residues.
using namespace std;
long long period(int modulus){
    int a=0;
    int b=0;
    int c=1;
    long long length=0;
    do{
        int next=(a+b+c)%modulus;
        a=b;
        b=c;
        c=next;
        length++;
    }
    while(a!=0||b!=0||c!=1);
    return length;
}
int main(){
    int modulus;
    cin>>modulus;
    int remaining=modulus;
    long long answer=1;
    for(int prime=2;prime*prime<=remaining;prime++){
        if(remaining%prime==0){
            int power=1;
            while(remaining%prime==0){
                power*=prime;
                remaining/=prime;
            }
            long long component=period(power);
            answer=answer/gcd(answer,component)*component;
        }
    }
    if(remaining>1){
        long long component=period(remaining);
        answer=answer/gcd(answer,component)*component;
    }
    cout<<answer<<'\n';
}