A216327 -id:A216327 - 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

A216325 Number of divisors of the degree of the minimal polynomial for 2*cos(Pi/n), n >= 1.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 2, 3, 2, 3, 2, 3, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 2, 4, 4, 6, 3, 6, 4, 4, 4, 5, 4, 5, 6, 6, 6, 6, 6, 5, 6, 6, 4, 6, 6, 4, 2, 5, 4, 6, 5, 8, 4, 6, 6, 8, 6, 6, 2, 5, 8, 8, 6, 6, 8, 6, 4, 6, 4, 8, 4, 8, 9, 9, 6, 9, 8, 8, 4, 6, 4, 8, 2, 8, 6, 8, 6, 8, 6, 8, 9, 6, 8, 4, 9, 6, 10, 8

Offset: 1

Wolfdieter Lang, Sep 27 2012

nonn

For the minimal polynomials C(n,x) of the algebraic number rho = 2*cos(Pi/n), n >= 1, see their coefficient table A187360. Their degree is delta(n)= phi(2*n)/2, if n >= 2, and delta(1) = 1, with Euler's totient A000010. The delta sequence is given in A055034. a(n) is the number of divisors of delta(n).
a(n) is also the number of distinct Modd n orders given in the table A216320 in row n. (For Modd n see a comment on A203571).
See the analog A062821(n), with the number of divisors of phi(n). The corresponding order table is A216327.

			a(8) = 3 because C(8,x) = x^4 - 4*x^2 + 2, with degree delta(8) = A055034(8) = 4, and the three divisors of 4 are 1, 2 and 4. tau(4) = A000005(4) = 3.

Cf. A062821 (analog).

a(n) = tau(delta(n)), n >= 1, with tau = A000005 (number of divisors), delta defined in a comment above and given as delta(n) = A055034(n).

A342754 Irregular triangle read by rows: T(n, k) is the number i of iterations that every scytale of length n and k > 1 sides must process its own ciphertext before the initial plaintext returns, where k | n, k > 1 and (n-1) | (k^i-1).

Original entry on oeis.org

2, 4, 4, 3, 3, 2, 6, 6, 10, 5, 5, 10, 12, 12, 6, 6, 4, 2, 4, 8, 16, 16, 8, 18, 9, 9, 18, 4, 4, 6, 6, 11, 11, 11, 11, 11, 11, 2, 20, 20, 3, 3, 18, 9, 9, 18, 28, 28, 14, 14, 28, 28, 5, 5, 5, 5, 8, 8, 10, 10, 16, 16, 12, 12, 6, 2, 6, 12, 12, 36, 36, 18, 18, 12, 6, 4, 4, 6, 12

Offset: 1

Rodrigo Panchiniak Fernandes, Mar 20 2021

Each number in this sequence is the number of times a scytale has to be fed with its own ciphertext until the apparatus generates back the initial plaintext because for every n/m integer, n > m > 1 and every integer i > 1, n^x mod (m-1) != n^i+1 mod (m-1). Tertium non datur: if n^i mod (m-1) = n^i+1 mod (m-1), i = i + 1, an absurdity. And this is why a recursive scytale does not freeze. Moreover, according to modular arithmetic, if n mod m = 1, then n +- (i*m) mod m = 1. This is why after a certain number of iterations the scytale returns the initial plaintext. Finally, for every integer y > 1, if n^i mod (m-1) = 1, then n^(y*i) mod (m-1) = 1, i < y*i. And this is why there is a first number of iterations for returning the initial plaintext, QED.

			Irregular triangle begins:
  00|01|02|03|04|05|06|...
  01|  |  |  |  |  |  |
  02|  |  |  |  |  |  |
  03|  |  |  |  |  |  |
  04|  | 2|  |  |  |  |
  05|  |  |  |  |  |  |
  06|  | 4| 4|  |  |  |
  07|  |  |  |  |  |  |
  08|  | 3|  | 3|  |  |
  09|  |  | 2|  |  |  |
  10|  | 6|  |  | 6|  |
  11|  |  |  |  |  |  |
  12|  |10| 5| 5|  |10|
  13|  |  |  |  |  |  |
  ...

Rodrigo Panchiniak Fernandes, OpenPGPjs in Drupal: Practical Privacy-Driven Web Development, Apress (Springer), 2021, 35-40. (in press)

Rodrigo Panchiniak Fernandes, Table of n, a(n) for n = 1..10000
Rodrigo Panchiniak Fernandes, Initial question, Cryptography Stack Exchange.
Wikipedia, Scytale

Row n is contained in row n-1 of A216327.

Cf. A139366.

// m = 1..10000
let n = 0n;
let a = [];
for (let m = 1n; m < 10001n; m = m + 1n){
  for (let k = 2n; k <= m; k = k + 1n){
    if ((m % k) == 0n){
      let xmod = 1n;
      for (let x = 1n; xmod != 0n; x = x + 1n){
        xmod = ((k ** x) - 1n) % (m - 1n);
        if (xmod == 0n && x != 1n){
          a[n] = x;
          n++;
        }
      }
    }
  }
}
console.info(a.join(','));

with(numtheory): seq(seq(order(d,n-1), d in divisors(n) minus {1,n}), n=1..60); # Ridouane Oudra, Apr 03 2025

row(n)={if(n==1, [], my(v=divisors(n)); vector(#v, i, znorder(Mod(v[i], n-1))))} \\ Andrew Howroyd, Mar 23 2021

Let n and k represent the length of the message and the number of sides of the scytale, respectively, with 1 < k < n. For each k that divides n, T(n,k) is the minimum integer i, 1 < i < n, such that n-1 divides k^i - 1.

T(n,k) = A139366(n-1,k), with k|n and 1 < k < n. - Ridouane Oudra, Apr 03 2025

A372305 a(n) = Product_{k=2..n-1} MultiplicativeOrder(k,n) where gcd(k,n)=1.

Original entry on oeis.org

1, 1, 2, 2, 32, 2, 648, 8, 648, 32, 12500000, 8, 214990848, 648, 2048, 2048, 562949953421312, 648, 11712917736940032, 2048, 3359232, 12500000, 1377791989621882898843648, 128, 5120000000000000000, 214990848, 11712917736940032

Offset: 1

Darío Clavijo, Apr 25 2024

nonn

All terms are even for n>=3.

Cf. A000079, A036391, A249435.

Row products of triangle A216327.

Table[Times @@ Map[MultiplicativeOrder[#, n] &, Select[Range[2, n - 1], CoprimeQ[n, #] &]], {n, 2, 27}] (* Michael De Vlieger, Apr 25 2024 *)

a(n) = prod(k=2, n-1, if (gcd(k,n)==1, znorder(Mod(k,n)), 1)); \\ Michel Marcus, Apr 26 2024

from sympy import n_order, gcd, prod
a = lambda n: prod(n_order(k,n) for k in range(2, n) if gcd(k,n)==1)
print([a(n) for n in range(1, 28)])

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

A216325 Number of divisors of the degree of the minimal polynomial for 2*cos(Pi/n), n >= 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A342754 Irregular triangle read by rows: T(n, k) is the number i of iterations that every scytale of length n and k > 1 sides must process its own ciphertext before the initial plaintext returns, where k | n, k > 1 and (n-1) | (k^i-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

JavaScript

Maple

PARI

Formula

A372305 a(n) = Product_{k=2..n-1} MultiplicativeOrder(k,n) where gcd(k,n)=1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Python