A057593 -id:A057593 - cp's OEIS frontend

A086145 Triangle read by rows in which T(n,k) is the least positive integer s such that p divides k^s-1, where p=prime(n) and k ranges from 1 to p-1.

1, 1, 2, 1, 4, 4, 2, 1, 3, 6, 3, 6, 2, 1, 10, 5, 5, 5, 10, 10, 10, 5, 2, 1, 12, 3, 6, 4, 12, 12, 4, 3, 6, 12, 2, 1, 8, 16, 4, 16, 16, 16, 8, 8, 16, 16, 16, 4, 16, 8, 2, 1, 18, 18, 9, 9, 9, 3, 6, 9, 18, 3, 6, 18, 18, 18, 9, 9, 2, 1, 11, 11, 11, 22, 11, 22, 11, 11, 22, 22, 11, 11, 22

Offset: 1

Benoit Cloitre, Sep 06 2003

The length of row n is A006093(n).
From J. H. Conway, Sep 06 2003: (Start)
"Let's ask for the exact power of some prime p that divides a^K - 1. Then the assertion is that if k is the smallest positive number for which p itself divides a^k - 1 and a^k - 1 is exactly divisible by p^i, then a^K - 1 will be divisible by p precisely when K is a multiple of k and then the exact power of p that divides it will be p^(i+j), where p^j is the exact power of p that divides K/k.
"In other words, the first time you get a multiple of p you can "accidentally" get a higher power than the first, but from then on you can only get more p's by putting them into the exponent.
"Examples: the first time 3^K - 1 is divisible by 11 is at 3^5 - 1, which is divisible precisely by 11^2. So 3^K - 1 will be divisible by 11^(2+j) only when KI is divisible by 5 times 11^j.
"Similarly, 2^1092 - 1 happens to be divisible by just 1093^2, so 2^(1092.1093^j) - 1 will be divisible by just 1093^(2+j)."
(End)
This is the prime-indexed rows of A057593. - Franklin T. Adams-Watters, Jan 19 2006
T(n,k) is the multiplicative order of k (mod prime(n)). Note that each row has many numbers that are the same. These numbers are counted in A174842. [T. D. Noe, Apr 01 2010]

			Triangle T(n,k) begins (with offsets 1):
[1]
[1, 2]
[1, 4, 4, 2]
[1, 3, 6, 3, 6, 2]
[1, 10, 5, 5, 5, 10, 10, 10, 5, 2]
[1, 12, 3, 6, 4, 12, 12, 4, 3, 6, 12, 2]
[1, 8, 16, 4, 16, 16, 16, 8, 8, 16, 16, 16, 4, 16, 8, 2]

T. D. Noe, Rows n=1..50, flattened

Cf. A006093, A057593, A174842.

Flatten[Table[MultiplicativeOrder[ #,p] & /@ Range[p-1], {p, Prime[Range[10]]}]] (* T. D. Noe, Apr 01 2010 *)

tabf(nn) = {for (n=1, nn, p = prime(n); for (k=1, p-1, print1(znorder(Mod(k, p)), ", ");); print(););} \\ Michel Marcus, Feb 05 2015

Name improved by T. D. Noe, Apr 01 2010

Prepended 1 for p=2 by T. D. Noe, Apr 01 2010

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.

A057594 Triangle T(n,k) giving floor( (2*p mod n-1)/2), where p = period of sequence k^i (i=0,1,2,...) mod n (n >= 2, 2<=k<=n).

Original entry on oeis.org

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

Offset: 2

Gottfried Helms, Oct 05 2000

Cf. A057593, A057595.

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, 2 n}]; p = period[t][[2]]; Floor[Mod[2 p, n - 1]/2]]; Table[T[n, k], {n, 2, 13}, {k, 2, n}] // Flatten (* Jean-François Alcover, Feb 04 2015 *)

A057595 Triangle T(n,k) giving 2*p mod n-1, where p = period of sequence k^i (i=0,1,2,...) mod n (n >= 2, 2<=k<=n).

Original entry on oeis.org

0, 0, 0, 2, 1, 2, 0, 0, 0, 2, 4, 2, 2, 4, 2, 0, 0, 0, 0, 4, 2, 2, 4, 2, 4, 2, 4, 2, 4, 2, 6, 4, 2, 6, 4, 2, 8, 8, 4, 2, 2, 8, 8, 4, 2, 0, 0, 0, 0, 0, 0, 0, 0, 4, 2, 4, 4, 2, 4, 2, 4, 4, 2, 2, 4, 2, 0, 6, 0, 8, 0, 0, 8, 6, 0, 0, 4, 2

Offset: 2

Gottfried Helms, Oct 05 2000

			0; 0,0; 2,1,2; 0,0,0,2; ...

Cf. A057593, A057594.

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, 2 n}]; p = period[t][[2]]; Mod[2 p, n - 1]]; Table[T[n, k], {n, 2, 13}, {k, 2, n}] // Flatten (* Jean-François Alcover, Feb 04 2015 *)

cp's OEIS Frontend

A086145 Triangle read by rows in which T(n,k) is the least positive integer s such that p divides k^s-1, where p=prime(n) and k ranges from 1 to p-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

A057594 Triangle T(n,k) giving floor( (2*p mod n-1)/2), where p = period of sequence k^i (i=0,1,2,...) mod n (n >= 2, 2<=k<=n).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A057595 Triangle T(n,k) giving 2*p mod n-1, where p = period of sequence k^i (i=0,1,2,...) mod n (n >= 2, 2<=k<=n).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica