A343292 Number of distinct results produced when generating a graphical image of each row of the multiplication table modulo n.

1, 2, 3, 4, 4, 6, 5, 8, 7, 9, 7, 12, 8, 12, 13, 14, 10, 16, 11, 18, 17, 18, 13, 24, 16, 21, 19, 24, 16, 28, 17, 26, 25, 27, 25, 32, 20, 30, 29, 36, 22, 38, 23, 36, 35, 36, 25, 44, 29, 41, 37, 42, 28, 46, 37, 48, 41, 45, 31, 56, 32, 48, 47, 50, 43, 58, 35, 54, 49, 60

Offset

1,2

Comments

The k-th row of the multiplication tables can be shown graphically by drawing a line for each i from i to k * i (mod n). The direction of the lines is not important.

Links

Table of n, a(n) for n=1..70.

Michael De Vlieger, Scatterplot of (n, a(n)) for n=1..2^16.

Michael De Vlieger, Annotated scatterplot of (n, a(n)) for n=1..240, labeling a(n), with color function related to ratio (a(n)+(n+3)/2)/((n-3)/2), black for prime n. Red dashed line has slope 1. Blue dashed line = (a(n)+3)/2.

Michael De Vlieger, Annotated scatterplot of (n, (a(n)+(n+3)/2)/((n-3)/2)) for n=1..2^12, the highest values are labeled a(n).

Steve Phelps, Modular Times Table, GeoGebra.

Formula

a(n) = n - A329152(n) = n - (A000010(n) - A060594(n))/2. - Andrew Howroyd, Apr 12 2021

a(p) = (p + 3)/2 for p prime. - Michael De Vlieger, Apr 13 2021

Example

Modulo 11, the 2 and 6 time tables, the 3 and 4 time tables, the 5 and 9 time tables, and the 7 and 8 time tables give the same pattern. So there are only 7 different time tables (0,1,2,3,5,7 and 10).

Mathematica

{1}~Join~Array[# - (EulerPhi[#] - Sum[Boole[Mod[k^2, #] == 1], {k, #}])/2 &, 69, 2] (* Michael De Vlieger, Apr 13 2021 *)

Prog

(PARI)
G(n, r)={Set(vector(n, i, my(j=i*r%n); [min(i, j), max(i, j)]))}
a(n)={#Set(vector(n, k, concat(G(n, k-1))))} \\ Andrew Howroyd, Apr 12 2021
(PARI) \\ here b(n) is A060594(n).
b(n)={my(o=valuation(n, 2)); 2^(omega(n>>o)+max(min(o-1, 2), 0))}
a(n)={n - (eulerphi(n)-b(n))/2} \\ Andrew Howroyd, Apr 12 2021

Crossrefs

Cf. A000010, A018253, A060594, A329152.

Sequence in context: A063655 A111234 A117248 * A079788 A146288 A244361

Adjacent sequences: A343289 A343290 A343291 * A343293 A343294 A343295

Keyword

nonn

Author

Sébastien Dumortier, Apr 12 2021

Status

approved