A248218 Period in residues modulo n in iteration of x^2 + 1 starting at 0.

1, 2, 1, 2, 3, 2, 1, 2, 3, 6, 2, 2, 4, 2, 3, 2, 6, 6, 1, 6, 1, 2, 2, 2, 3, 4, 3, 2, 2, 6, 1, 2, 2, 6, 3, 6, 1, 2, 4, 6, 7, 2, 1, 2, 3, 2, 4, 2, 6, 6, 6, 4, 2, 6, 6, 2, 1, 2, 3, 6, 10, 2, 3, 2, 12, 2, 2, 6, 2, 6, 11, 6, 6, 2, 3, 2, 2, 4, 4, 6, 9, 14, 5, 2, 6

Offset: 1

Author

Vaclav Kotesovec, Oct 04 2014

Keywords

• nonn

Comments

a(n) is a period in the sequence A003095 modulo n.

For n <= 10000 is the maximal period a(7921) = 1232.

For n <= 100000 is the maximal period a(73205) = 7260.

For n <= 500000 is the maximal period a(357911) = 54670.

From Hermann Stamm-Wilbrandt, Jun 21 2021: (Start)

357911 = 71^3; a(71^2) = 770; a(71^3) = 71 * a(71^2); a(71^4) = 71 * a(71^3); a(71^5) = 71 * a(71^4); a(71^6) = 71 * a(71^5). 770/71^2 = 0.15274747073993255306, so cycle length is linear in n for these composite numbers. a(71^6) = 19566994370.

Let A(n) be number of start values that end on same cycle as start value 0. A(71^2) = 3711; A(71^3) = 71 * A(71^2); A(71^4) = 71 * A(71^3); A(71^5) = 71 * A(71^4). 3711/71^2 = 0.73616345963102559016, so majority of start values end on start value 0 cycle. (End)

Linear cycle length for a(71^i) with 2 <= i <= 5 sounds bad for runtime of Pollard-Rho factorization algorithm (heuristic claim assumes square root cycle length). The opposite is true, every value on start value 0 cycle has same remainder mod 71 as the value after applying "x -> (x^2 + 1) mod n" 11 times, so factorization completes quickly. - Hermann Stamm-Wilbrandt, Jun 29 2021

Examples

			n=5, residues are 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, ..., period is 3, a(5)=3.
n=7, residues are 1, 2, 5, 5, 5, 5, 5, ..., final period is 1, therefore a(7)=1.
n=10, residues are 1, 2, 5, 6, 7, 0, 1, 2, 5, 6, 7, 0, 1, 2, ..., a(10)=6.
n=43, residues are 1, 2, 5, 26, 32, 36, 7, 7, 7, 7, ..., a(43) = 1.
n=229, residues are 1, 2, 5, 26, 219, 101, 126, 76, 52, 186, 18, 96, 57, 44, 105, 34, 12, 145, 187, 162, 139, 86, 69, 182, 149, 218, 122, 0, 1, 2, 5, 26, 219, 101, 126, 76, 52, 186, 18, 96, 57, 44, 105, 34, 12, 145, 187, 162, 139, 86, 69, 182, 149, 218, 122, 0, 1, 2, 5, 26, ..., period is 28, a(229)=28.
This program is for experiments (n<100): Rest[NestList[Mod[#^2+1, n] &, 0, 100]]
		

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 1..100000
• Hermann Stamm-Wilbrandt, analyze.c
• Hermann Stamm-Wilbrandt, period.c
• Wikipedia, Pollard's Rho algorithm.

Crossrefs

Cf. A248219, A256342-A256349, A003095, A247981, A001175.

Programs

C

/* See analyze.c in the Links section. This program computes a(n) for n < 2^31, all periods for any starting value. See also period.c which only computes period length, but with arbitrary precision gmplib. This allowed to compute a(71^6). - Hermann Stamm-Wilbrandt, Jun 22 2021 */

Mathematica

Table[m=Rest[NestList[Mod[#^2+1,n]&,0,1000]]; period=0; j=1; While[j<=Length[m] && period==0,If[m[[Length[m]-j]]==m[[Length[m]]],period=j]; j++]; period,{n,1,1000}]

PARI

A248218(m,t=0,u=[t])=until(#Set(u=concat(u,t=(t^2+1)%m))<#u,);for(i=1,#u,t==u[#u-i]&&return(i)) \\ M. F. Hasler, Mar 25 2015

Formula

a(LCM(i,j)) = LCM(a(i),a(j)). - Robert Israel, Mar 08 2021