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