|
| |
|
|
A248218
|
|
Period in residues modulo n in iteration of x^2 + 1 starting at 0.
|
|
16
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
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.
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
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
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]]
|
|
|
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}]
|
|
|
PROG
|
(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
(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 */
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
