login
A348888
Triangle read by rows: T(n,k) = number of basins of attraction of the multiplication by k in the integers modulo n, n >= 1, 0 <= k < n.
1
1, 1, 2, 1, 3, 2, 1, 4, 1, 3, 1, 5, 2, 2, 3, 1, 6, 2, 2, 3, 4, 1, 7, 3, 2, 3, 2, 4, 1, 8, 1, 5, 1, 6, 1, 5, 1, 9, 3, 1, 5, 3, 1, 5, 5, 1, 10, 2, 4, 3, 2, 5, 4, 2, 6, 1, 11, 2, 3, 3, 3, 2, 2, 2, 3, 6, 1, 12, 2, 3, 3, 8, 1, 9, 2, 4, 3, 7
OFFSET
1,3
COMMENTS
Using dynamical systems terminology, let Z/nZ be the phase space and let the multiplication by k be the evolution function. T(n,k) is by definition the number of basins of attraction.
When n is prime and k > 0, {0} is always a basin of attraction. The other ones are d cycles of size (n-1)/d, where d is a divisor of n-1, by an application of Lagrange's theorem to (Z/nZ)*.
In the general case, the basins of attraction are not necessarily cycles (e.g., they can be stars) and there can be a mix of several shapes. See illustration, section links.
FORMULA
T(n,0) = 1.
T(n,1) = n, for n > 1.
T(n,n-1) = floor(n/2) + 1.
T(n,k) = 1 iff k is nilpotent in Z/nZ, i.e., k is a multiple of rad(n)=A007947(n).
n is squarefree iff no k > 0 satisfies T(n,k) = 1.
T(p,k) - 1 divides p-1, for p prime and k > 0.
EXAMPLE
When n=6 and k=2, the multiplication by 2 in Z/6Z sends 0 to 0, 1 to 2, 2 to 4, 3 to 0, 4 to 2, 5 to 4. Schematically this is
3 --> 0 <--+ 1 --> 2 <--+
| | | |
+----+ +--> 4 <-- 5
There are 2 basins of attraction, so T(6,2)=2.
The triangle begins:
\ k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
n \
1 1
2 1 2
3 1 3 2
4 1 4 1 3
5 1 5 2 2 3
6 1 6 2 2 3 4
7 1 7 3 2 3 2 4
8 1 8 1 5 1 6 1 5
9 1 9 3 1 5 3 1 5 5
10 1 10 2 4 3 2 5 4 2 6
11 1 11 2 3 3 3 2 2 2 3 6
12 1 12 2 3 3 8 1 9 2 4 3 7
13 1 13 2 5 3 4 2 2 4 5 3 2 7
14 1 14 3 4 3 4 4 2 7 6 2 6 2 8
15 1 15 5 2 9 2 5 6 5 3 3 10 2 6 8
16 1 16 1 7 1 8 1 9 1 12 1 7 1 8 1 9
PROG
(Java) // see link.
CROSSREFS
Cf. A007947.
Sequence in context: A108371 A138530 A002341 * A128260 A083368 A112379
KEYWORD
nonn,tabl
AUTHOR
Luc Rousseau, Jan 26 2022
STATUS
approved