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

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, 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, 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

Offset: 1

Author

Brian Barsotti, Jul 29 2019

Keywords

• nonn

Comments

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.

Examples

			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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..20000

Crossrefs

Cf. A277847.

Programs

Maple

a:= proc(n) local c, s, i, h; c, s:= n, {$0..n-1};
      for i from 0 do s:= map(x-> irem(x^2, n), s);
        h:= nops(s); if c=h then return i else c:= h fi
      od
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Jul 30 2019

Mathematica

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]]];
Array[a, 120] (* Jean-François Alcover, Nov 27 2020, after Alois P. Heinz *)