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

Author

Sébastien Dumortier, Apr 12 2021

Keywords

• nonn

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.

Examples

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

Links

• 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.

Crossrefs

Cf. A000010, A018253, A060594, A329152.

Programs

Mathematica

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

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

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