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

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.

Links

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

Example

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.

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 *)

Crossrefs

Cf. A277847.

Sequence in context: A095771 A245933 A268318 * A007421 A239228 A346080

Adjacent sequences: A309411 A309412 A309413 * A309415 A309416 A309417

Keyword

nonn

Author

Brian Barsotti, Jul 29 2019

Status

approved