|
%I #13 Oct 27 2019 14:29:04
%S 0,0,2,1,0,2,3,2,2,0,4,2,0,3,2,3,2,2,5,1,3,4,6,2,1,0,2,3,9,2,4,3,4,2,
%T 3,2,5,5,2,2,0,3,7,4,2,6,10,3,3,1,2,1,7,2,4,3,5,9,8,2,5,4,3,4,0,4,10,
%U 2,6,3,7,2,3,5,2,5,4,2,4,3,2,0,6,3,2,7,9,4,2,2,3
%N Start with 0, a(n) is the smallest number of iterations: x -> (x^2+1) mod n needed to run into a cycle.
%C Let f(0) = 0, f(k+1) = (f(k)^2+1) mod n, then a(n) is the smallest i such that f(i) = f(j) for some j > i.
%C Obviously a(n) <= A000224(n): f(1), f(2), ..., f(A000224(n)+1) are all of the form (s^2+1) mod n, so there must exists 0 <= i < j <= A000224(n)+1 such that f(i) = f(j), and a(n) <= i <= A000224(n). The equality seems to hold only for n = 3.
%C k divides A003095(m) for some m > 0 if and only if a(k) = 0, in which case all the indices m such that k divides A003095(m) are m = t*A248218(k), t = 0, 1, 2, 3, ...
%e A003095(n) mod 3: 0, 1, (2). {A003095(n) mod 3} enters into the cycle (2) from the 2nd term on, so a(3) = 2.
%e A003095(n) mod 7: 0, 1, 2, (5). {A003095(n) mod 7} enters into the cycle (5) from the 3rd term on, so a(7) = 3.
%e A003095(n) mod 29: 0, 1, 2, 5, 26, 10, 14, 23, 8, (7, 21). {A003095(n) mod 29} enters into the cycle (7, 21) from the 9th term on, so a(29) = 9.
%e A003095(n) mod 37: 0, 1, 2, 5, 26, (11). {A003095(n) mod 37} enters into the cycle (11) from the 5th term on, so a(37) = 5.
%e A003095(n) mod 41: (0, 1, 2, 5, 26, 21, 32). {A003095(n) mod 41} enters into the cycle (0, 1, 2, 5, 26, 21, 32) from the very beginning, so a(41) = 0.
%o (PARI) a(n) = my(v=[0],k); for(i=2, n+1, k=(v[#v]^2+1)%n; v=concat(v, k); for(j=1, i-1, if(v[j]==k, return(j-1))))
%Y Cf. A003095, A248218 (cycle length), A328700, A000224.
%K nonn
%O 1,3
%A _Jianing Song_, Oct 26 2019
|
