cp's OEIS Frontend

A309414 Number of squaring iterations necessary to achieve the minimal residue class (mod n).

%I A309414 #23 Nov 27 2020 06:18:55
%S A309414 0,0,1,1,2,1,1,2,1,2,1,1,2,1,2,2,4,1,1,2,1,1,1,2,2,2,2,1,2,2,1,3,1,4,
%T A309414 2,1,2,1,2,2,3,1,1,1,2,1,1,2,1,2,4,2,2,2,2,2,1,2,1,2,2,1,1,4,2,1,1,4,
%U A309414 1,2,1,2,3,2,2,1,1,2,1,2,2,3,1,1,4,1,2,2,3,2,2,1,1,1,2,3,5,1,1,2,2,4,1,2,2
%N A309414 Number of squaring iterations necessary to achieve the minimal residue class (mod n).
%C A309414 Starting with the integers {0, 1, ..., n-1}, a(n) represents the number of times you must apply the function f = (x)-> x^2 mod n to each element of a set in order to reach the smallest possible residue class modulo n.
%H A309414 Alois P. Heinz, <a href="/A309414/b309414.txt">Table of n, a(n) for n = 1..20000</a>
%e A309414 Under modulo 5, {0,1,2,3,4} becomes {0,1,4} through the first squaring iteration, which itself becomes {0,1} through the second iteration. This residue class cannot be reduced any further, so a(5) = 2.
%p A309414 a:= proc(n) local c, s, i, h; c, s:= n, {$0..n-1};
%p A309414       for i from 0 do s:= map(x-> irem(x^2, n), s);
%p A309414         h:= nops(s); if c=h then return i else c:= h fi
%p A309414       od
%p A309414     end:
%p A309414 seq(a(n), n=1..120);  # _Alois P. Heinz_, Jul 30 2019
%t A309414 a[n_] := Module[{c = n, s = Range[0, n-1], i, h}, For[i = 0, True, i++, s = Mod[#^2, n]& /@ s // Union; h = Length[s]; If[c==h, Return[i], c = h]]];
%t A309414 Array[a, 120] (* _Jean-François Alcover_, Nov 27 2020, after _Alois P. Heinz_ *)
%Y A309414 Cf. A277847.
%K A309414 nonn
%O A309414 1,5
%A A309414 _Brian Barsotti_, Jul 29 2019