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

Links

Luc Rousseau, First 200 rows, formatted as a simple linear sequence: (n, a(n)), n=1..20100.

Luc Rousseau, Basins of attraction illustrated for n = 1..10.

Luc Rousseau, Java program.

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

Adjacent sequences: A348885 A348886 A348887 * A348889 A348890 A348891

Keyword

nonn,tabl

Author

Luc Rousseau, Jan 26 2022

Status

approved