A348888 - OEIS

%I #25 Mar 09 2022 16:34:01

%S 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,

%T 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,

%U 12,2,3,3,8,1,9,2,4,3,7

%N 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.

%C 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.

%C 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)*.

%C 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.

%H Luc Rousseau, <a href="/A348888/b348888.txt">First 200 rows, formatted as a simple linear sequence: (n, a(n)), n=1..20100.</a>

%H Luc Rousseau, <a href="/A348888/a348888.pdf">Basins of attraction illustrated for n = 1..10.</a>

%H Luc Rousseau, <a href="/A348888/a348888.java.txt">Java program.</a>

%F T(n,0) = 1.

%F T(n,1) = n, for n > 1.

%F T(n,n-1) = floor(n/2) + 1.

%F T(n,k) = 1 iff k is nilpotent in Z/nZ, i.e., k is a multiple of rad(n)=A007947(n).

%F n is squarefree iff no k > 0 satisfies T(n,k) = 1.

%F T(p,k) - 1 divides p-1, for p prime and k > 0.

%e 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

%e   3 --> 0 <--+    1 --> 2 <--+

%e         |    |          |    |

%e         +----+          +--> 4 <-- 5

%e There are 2 basins of attraction, so T(6,2)=2.

%e The triangle begins:

%e     \ k  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15

%e    n \

%e    1     1

%e    2     1  2

%e    3     1  3  2

%e    4     1  4  1  3

%e    5     1  5  2  2  3

%e    6     1  6  2  2  3  4

%e    7     1  7  3  2  3  2  4

%e    8     1  8  1  5  1  6  1  5

%e    9     1  9  3  1  5  3  1  5  5

%e   10     1 10  2  4  3  2  5  4  2  6

%e   11     1 11  2  3  3  3  2  2  2  3  6

%e   12     1 12  2  3  3  8  1  9  2  4  3  7

%e   13     1 13  2  5  3  4  2  2  4  5  3  2  7

%e   14     1 14  3  4  3  4  4  2  7  6  2  6  2  8

%e   15     1 15  5  2  9  2  5  6  5  3  3 10  2  6  8

%e   16     1 16  1  7  1  8  1  9  1 12  1  7  1  8  1  9

%o (Java) // see link.

%Y Cf. A007947.

%K nonn,tabl

%O 1,3

%A _Luc Rousseau_, Jan 26 2022