editing

approved

(PARI) minWSS=2^64; \\ PrimeGrid search

(PARI) fibmod(n, m)=((Mod([1, 1; 1, 0], m))^n)[1, 2]

entry(n)=if(n==1, return(1)); my(f=factor(n), v); v=vector(#f~, i, if(f[i, 1]>9.2e18]>=minWSS, entryp(f[i, 1]^f[i, 2]), entryp(f[i, 1])*f[i, 1]^(f[i, 2] - 1))); if(f[1, 1]==2&&f[1, 2]>1, v[1]=3<<max(f[1, 2]-2, 1)); lcm(v)

a(n)=if(n==1, return(1)); my(k=entry(n)); forstep(i=k, n^2, k, if(fibmod(i-1, n)==1, return(i))) \\ Charles R Greathouse IV, Feb 13 2014; updated Dec 14 2016; updated Aug 24 2021; updated Jul 08 2024

approved

editing

proposed

approved

editing

proposed

Alois P. Heinz: ok, thanks ...

Observed: a(p^2) = p*a(p) for all p <= 5*10^5, so a(n) = lcm(a(p1)*p1^(e1-1), ..., a(pk)*pk^(ek-1), where n = p1^e1*...*pk^ek is the prime factorization of n. - A.H.M. Smeets, Oct 30 2023

A.H.M. Smeets: deleted it

proposed

editing

A.H.M. Smeets: I agree

editing

proposed

Kevin Ryde: The "Observed" is known statements and over half of it is in existing formulas.  Set back to editing accordingly.

Observed: a(p^2) = p*a(p) for all p <= 5*10^5, so a(n) = lcm(a(p1)*p1^(e1-1), ..., a(pk)*pk^(ek-1), where n = p1^e1...*...*pk^ek is the prime factorization of n. - A.H.M. Smeets, Oct 30 2023

proposed

editing

editing

proposed

Michel Marcus: please pay attention to the result after editing

Kevin Ryde: I was unclear when I said "various n".  What I meant was various n.  Factoring turns about n = x*y*z of work into instead about x+y+z of work.  Various n with not-terribly-big factors are handled hugely faster by using Wall's result (if I'm right it's Wall's!).

Kevin Ryde: About 10^5, I saw a paper by Elsenhans and Jahnel suggesting Wall was at primes < 10^4 in 1960, and the state of the art in 2004 was primes < 10^14.  The present state is a worthwhile thing to refer to, but the repeat of the preceding formula has to go.

Observed: a(p^2) = p*a(p) for all p <= 5*10^5, so a(n) = lcm(a(p1)*p1^(e1-1), ..., a(pk)*pk^(ek-1), where n = p1^e1...pk^ek is the prime factorization of n. _. - _A.H.M. Smeets_, Oct 30 2023