login
Triangle T(n, k) giving period length of the periodic sequence k^i (i >= imin) mod n (n >= 2, 1 <= k <= n-1).
5

%I #30 Sep 09 2017 04:46:10

%S 1,1,2,1,1,2,1,4,4,2,1,2,1,1,2,1,3,6,3,6,2,1,1,2,1,2,1,2,1,6,1,3,6,1,

%T 3,2,1,4,4,2,1,1,4,4,2,1,10,5,5,5,10,10,10,5,2,1,2,2,1,2,1,2,2,1,1,2,

%U 1,12,3,6,4,12,12,4,3,6,12,2,1

%N Triangle T(n, k) giving period length of the periodic sequence k^i (i >= imin) mod n (n >= 2, 1 <= k <= n-1).

%C From _Wolfdieter Lang_, Sep 04 2017: (Start)

%C i) If gcd(n, k) = 1 then imin = imin(n, k) = 0 and the length of the period P = T(n, k) = order(n, k), given in A216327 corresponding to the numbers of A038566. This is due to Euler's theorem. E.g., T(4, 3) = 2 because A216327(4, 2) = 2 corresponding to A038566(4, 2) = 3.

%C ii) If gcd(n, k) is not 1 then the smallest nonnegative index imin = imin(n, k) is obtained from A290601 with the corresponding length of the period given in A290602. Also in this case the sequence always becomes periodic, because one of the possible values from {0, 1, ..., n-1} has to appear a second time because the sequence has more than n entries. Example: T(4, 2) = 1 because imin is given by A290601(1, 1) = 2 (corresponding to the present n = 4, k = 2 values) with the length of the period P given by A290602(1, 1) = 1. (End)

%H Michael De Vlieger, <a href="/A057593/b057593.txt">Table of n, a(n) for n = 2..19901</a> (rows 2 <= n <= 200).

%e If n=7, k=2, (imin = 0) the sequence is 1,2,4,1,2,4,1,2,4,... of period 3, so T(7,2) = 3. The triangle T(n, k) begins:

%e n \ k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...

%e 2: 1

%e 3: 1 2

%e 4: 1 1 2

%e 5: 1 4 4 2

%e 6: 1 2 1 1 2

%e 7: 1 3 6 3 6 2

%e 8: 1 1 2 1 2 1 2

%e 9: 1 6 1 3 6 1 3 2

%e 10: 1 4 4 2 1 1 4 4 2

%e 11: 1 10 5 5 5 10 10 10 5 2

%e 12: 1 2 2 1 2 1 2 2 1 1 2

%e 13: 1 12 3 6 4 12 12 4 3 6 12 2

%e 14: 1 3 6 3 6 2 1 1 3 6 3 6 2

%e 15: 1 4 4 2 2 1 4 4 2 1 2 4 4 2

%e 16: 1 1 4 1 4 1 2 1 2 1 4 1 4 1 2

%e 17: 1 8 16 4 16 16 16 8 8 16 16 16 4 16 8 2

%e 18: 1 6 1 3 6 1 3 2 1 1 6 1 3 6 1 1 2

%e ... Reformatted and extended. - _Wolfdieter Lang_, Sep 04 2017

%e From _Wolfdieter Lang_, Sep 04 2017: (Start)

%e The table imin(n, k) begins:

%e n \ k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...

%e 2: 0

%e 3: 0 0

%e 4: 0 2 0

%e 5: 0 0 0 0

%e 6: 0 1 1 1 0

%e 7: 0 0 0 0 0 0

%e 8: 0 3 0 2 0 3 0

%e 9: 0 0 2 0 0 2 0 0

%e 10: 0 1 0 1 1 1 0 1 0

%e 11: 0 0 0 0 0 0 0 0 0 0

%e 12: 0 2 1 1 0 2 0 1 1 2 0

%e 13: 0 0 0 0 0 0 0 0 0 0 0 0

%e 14: 0 1 0 1 0 1 1 1 0 1 0 1 0

%e 15: 0 0 1 0 1 1 0 0 1 1 0 1 0 0

%e 16: 0 4 0 2 0 4 0 2 0 4 0 2 0 4 0

%e 17: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

%e 18: 0 1 2 1 0 2 0 1 1 1 0 2 0 1 2 1 0

%e ... (End)

%t period[lst_] := Module[{n, i, j}, n=Length[lst]; For[j=2, j <= n, j++, For[i=1, i<j, i++, If[lst[[i]] == lst[[j]], Return[{i-1, j-i}]]]]; Return[{0, 0}]]; T[n_, k_] := Module[{t, p}, t=Table[PowerMod[k, i, n], {i, 0, 2n}]; p=period[t][[2]]; p]; Table[T[n, k], {n, 2, 14}, {k, 1, n - 1}] // Flatten (* _Jean-François Alcover_, Feb 04 2015 *)

%Y Cf. A057594, A057595.

%Y Cf. A086145 (prime rows), A216327 (entries with gcd(n,k) = 1), A139366.

%Y Cf. A038566, A216327, A290601, A290602.

%K nonn,tabl,nice

%O 2,3

%A _Gottfried Helms_, Oct 05 2000

%E Constraint on k changed from 2 <= k <= n to 1 <= k < n, based on comment from _Franklin T. Adams-Watters_, Jan 19 2006, by _David Applegate_, Mar 11 2014

%E Name changed and table extended by _Wolfdieter Lang_, Sep 04 2017