A290602 -id:A290602 - cp's OEIS frontend

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

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, 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, 1, 12, 3, 6, 4, 12, 12, 4, 3, 6, 12, 2, 1

Offset: 2

Gottfried Helms, Oct 05 2000

From Wolfdieter Lang, Sep 04 2017: (Start)
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.
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)

			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:
n \ k 1   2   3  4   5   6   7   8  9  10  11  12  13  14 15 16 17 ...
2:    1
3:    1   2
4:    1   1   2
5:    1   4   4  2
6:    1   2   1  1   2
7:    1   3   6  3   6   2
8:    1   1   2  1   2   1   2
9:    1   6   1  3   6   1   3   2
10:   1   4   4  2   1   1   4   4  2
11:   1  10   5  5   5  10  10  10  5   2
12:   1   2   2  1   2   1   2   2  1   1   2
13:   1  12   3  6   4  12  12   4  3   6  12   2
14:   1   3   6  3   6   2   1   1  3   6   3   6   2
15:   1   4   4  2   2   1   4   4  2   1   2   4   4  2
16:   1   1   4  1   4   1   2   1  2   1   4   1   4  1  2
17:   1   8  16  4  16  16  16   8  8  16  16  16   4  16  8  2
18:   1   6   1  3   6   1   3   2  1   1   6   1   3   6  1  1  2
... Reformatted and extended. - _Wolfdieter Lang_, Sep 04 2017
From _Wolfdieter Lang_, Sep 04 2017: (Start)
The  table imin(n, k) begins:
n \ k 1   2   3   4   5   6   7   8  9  10  11  12  13  14  15  16 17 ...
2:    0
3:    0   0
4:    0   2   0
5:    0   0   0   0
6:    0   1   1   1   0
7:    0   0   0   0   0   0
8:    0   3   0   2   0   3   0
9:    0   0   2   0   0   2   0   0
10:   0   1   0   1   1   1   0   1  0
11:   0   0   0   0   0   0   0   0  0   0
12:   0   2   1   1   0   2   0   1  1   2   0
13:   0   0   0   0   0   0   0   0  0   0   0   0
14:   0   1   0   1   0   1   1   1  0   1   0   1   0
15:   0   0   1   0   1   1   0   0  1   1   0   1   0   0
16:   0   4   0   2   0   4   0   2  0   4   0   2   0   4   0
17:   0   0   0   0   0   0   0   0  0   0   0   0   0   0   0   0
18:   0   1   2   1   0   2   0   1  1   1   0   2   0   1   2   1  0
... (End)

Michael De Vlieger, Table of n, a(n) for n = 2..19901 (rows 2 <= n <= 200).

Cf. A057594, A057595.
Cf. A086145 (prime rows), A216327 (entries with gcd(n,k) = 1), A139366.
Cf. A038566, A216327, A290601, A290602.

period[lst_] := Module[{n, i, j}, n=Length[lst]; For[j=2, j <= n, j++, For[i=1, iJean-François Alcover, Feb 04 2015 *)

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

Name changed and table extended by Wolfdieter Lang, Sep 04 2017

A290600 Irregular triangle T(n, k) read by rows: positive numbers non-coprime to A002808(n) and smaller than A002808(n), sorted increasingly.

Original entry on oeis.org

2, 2, 3, 4, 2, 4, 6, 3, 6, 2, 4, 5, 6, 8, 2, 3, 4, 6, 8, 9, 10, 2, 4, 6, 7, 8, 10, 12, 3, 5, 6, 9, 10, 12, 2, 4, 6, 8, 10, 12, 14, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 3, 6, 7, 9, 12, 14, 15, 18

Offset: 1

Wolfdieter Lang, Aug 30 2017

The length of row n is A290599(n).

Row n gives the complement of row A038566(A002808(n), k) with respect to [1, 2, ..., A002808(n) - 1].

			The irregular triangle T(n, k) begins (N(n) = A002808(n)):
  n   N(n) \ k  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
  1   4         2
  2   6         2  3  4
  3   8         2  4  6
  4   9         3  6
  5   10        2  4  5  6  8
  6   12        2  3  4  6  8  9 10
  7   14        2  4  6  7  8 10 12
  8   15        3  5  6  9 10 12
  9   16        2  4  6  8 10 12 14
  10  18        2  3  4  6  8  9 10 12 14 15 16
  11  20        2  4  5  6  8 10 12 14 15 16 18
  12  21        3  6  7  9 12 14 15 18
  13  22        2  4  6  8 10 11 12 14 16 18 20
  14  24        2  3  4  6  8  9 10 12 14 15 16 18 20 21 22
  15  25        5 10 15 20
  ...

Cf. A002808, A038566, A290599, A290601, A290602.

Table[With[{c = FixedPoint[n + PrimePi@ # + 1 &, n + PrimePi@ n + 1]}, Select[Range[c - 1], ! CoprimeQ[#, c] &]], {n, 12}] // Flatten (* Michael De Vlieger, Sep 03 2017 *)

T(n, k) = k-th entry in the list of increasingly sorted numbers of the set {m = 1..A002808(n)-1: gcd(n, m) not equal to 1}.

A290601 Irregular triangle read by rows: T(n, k) gives the least positive integer imin such that the sequence {A290600(n, k)^i}_{i >= imin} (mod A002808(n)) is periodic.

Original entry on oeis.org

2, 1, 1, 1, 3, 2, 3, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 2, 4, 2, 4, 2, 4, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 3, 1, 1, 3, 2, 3, 1, 1, 3, 2, 1, 3, 2, 2, 2, 2

Offset: 1

Wolfdieter Lang, Aug 30 2017

The length of row n is A290599(n).
The corresponding period lengths are given in A290602(n, k).
Conjecture:There exists always an imin >= 1 such that the power sequence A290600(n, k)^i (mod A002808(n)) is periodic for i >= imin. Otherwise T(n, k) is undefined, and one could use T(n, k) = -1. See below for a proof.
This entry resulted from finding the correct initial exponent i for the power sequence considered in triangle A057593 for composite n and gcd(n, k) not equal to 1.
It is clear that the sequence {A290600(n, k)^i}_{i >= 1} is never congruent to 1 (mod A002808(n)) for k = 1..A290599(n). Proof by contradiction. Therefore one can replace 'least positive integer' with 'least nonnegative integer' in the name of this sequence.
The values of these powers of A290600(n, k) modulo A290599(n) are 0 or any of the row entries of A290600(n, k).
To prove periodicity of {A290600(n, k)^i (mod A290599(n))} of the type (imin,P) (starting at i = imin with period length P) one has to solve, with given K = A290600(n, k) and N = A002808(n), the congruence  K^imin * (K^P - 1) == 0 (mod N).
The above conjecture is trivially true because {K^i}{i >= 0} (mod N) becomes (or is) always periodic (K and N positive integer). This follows from the fact that at most N values are possible, namely {0, 1, ..., N-1} and for i >= N one of these values has to appear for the second time, leading to periodicity. Thus the above sequence where gcd(N, K) is not 1 is also defined. - _Wolfdieter Lang, Sep 05 2017

			The irregular triangle T(n, k) begins (N(n) = A002808(n)):
n   N(n) \ k  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
1   4         2
2   6         1  1  1
3   8         3  2  3
4   9         2  2
5   10        1  1  1  1  1
6   12        2  1  1  2  1  1  2
7   14        1  1  1  1  1  1  1
8   15        1  1  1  1  1  1
9   16        4  2  4  2  4  2  4
10  18        1  2  1  2  1  1  1  2  1  2  1
11  20        2  1  1  2  1  2  1  2  1  1  2
12  21        1  1  1  1  1  1  1  1
13  22        1  1  1  1  1  1  1  1  1  1  1
14  24        3  1  2  3  1  1  3  2  3  1  1  3  2  1  3
15  25        2  2  2  2
...
T(4, 1) = 2 because A290600(4, 1) = 3, A002808(4) = 9 and {3^i}_{i>=2} (mod 9) = {repeat(0)}, but 3^0 == 1 (mod 9) and  3^1 == 3 (mod 9).
T(4, 2) = 2 because A290600(4, 2) = 6 and  {6^i}_{i>=2} (mod 9) == {repeat(0)}, and 6^0 (mod 9) = 1, 6^1 (mod 9) = 6.
Example for a proof of periodicity of type (1,6) for K = A290600(10, 1) = 2, N = A002808(10) = 18: 2^imin*(2^P - 1) == 0 (mod 18). gcd(2^imin, 18) = 2, and with imin = 1 one has  2^P == 1 (mod 9). Since gcd(2, 9) = 1, a solution exists (Euler): P = phi(9) = 6.

Cf. A002808, A057593, A290599, A290600, A290602.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A290600 Irregular triangle T(n, k) read by rows: positive numbers non-coprime to A002808(n) and smaller than A002808(n), sorted increasingly.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A290601 Irregular triangle read by rows: T(n, k) gives the least positive integer imin such that the sequence {A290600(n, k)^i}_{i >= imin} (mod A002808(n)) is periodic.

Views

Author

Keywords

Comments

Examples

Crossrefs