cp's OEIS Frontend

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

%I A248218 #77 Aug 23 2021 22:45:18
%S A248218 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,
%T A248218 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,
%U A248218 6,2,6,11,6,6,2,3,2,2,4,4,6,9,14,5,2,6
%N A248218 Period in residues modulo n in iteration of x^2 + 1 starting at 0.
%C A248218 a(n) is a period in the sequence A003095 modulo n.
%C A248218 For n <= 10000 is the maximal period a(7921) = 1232.
%C A248218 For n <= 100000 is the maximal period a(73205) = 7260.
%C A248218 For n <= 500000 is the maximal period a(357911) = 54670.
%C A248218 From _Hermann Stamm-Wilbrandt_, Jun 21 2021: (Start)
%C A248218 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.
%C A248218 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)
%C A248218 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
%H A248218 Vaclav Kotesovec, <a href="/A248218/b248218.txt">Table of n, a(n) for n = 1..100000</a>
%H A248218 Hermann Stamm-Wilbrandt, <a href="https://gist.github.com/Hermann-SW/83deac0d8977f33b56b548641c26c590">analyze.c</a>
%H A248218 Hermann Stamm-Wilbrandt, <a href="https://gist.github.com/Hermann-SW/eeb0770b891f8e89573585761ab38998">period.c</a>
%H A248218 Wikipedia, <a href="https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm">Pollard's Rho algorithm</a>.
%F A248218 a(LCM(i,j)) = LCM(a(i),a(j)). - _Robert Israel_, Mar 08 2021
%e A248218 n=5, residues are 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, ..., period is 3, a(5)=3.
%e A248218 n=7, residues are 1, 2, 5, 5, 5, 5, 5, ..., final period is 1, therefore a(7)=1.
%e A248218 n=10, residues are 1, 2, 5, 6, 7, 0, 1, 2, 5, 6, 7, 0, 1, 2, ..., a(10)=6.
%e A248218 n=43, residues are 1, 2, 5, 26, 32, 36, 7, 7, 7, 7, ..., a(43) = 1.
%e A248218 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.
%e A248218 This program is for experiments (n<100): Rest[NestList[Mod[#^2+1, n] &, 0, 100]]
%t A248218 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}]
%o A248218 (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
%o A248218 (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 */
%Y A248218 Cf. A248219, A256342-A256349, A003095, A247981, A001175.
%K A248218 nonn
%O A248218 1,2
%A A248218 _Vaclav Kotesovec_, Oct 04 2014