A309428 Irregular triangle read by rows: T(n,k) is the multiplicative order of {{A038566(n,k), 1}, {0, 1}} modulo n, n >= 1, 1 <= k <= A000010(n).

1, 2, 3, 2, 4, 2, 5, 4, 4, 2, 6, 2, 7, 3, 6, 3, 6, 2, 8, 4, 8, 2, 9, 6, 9, 6, 9, 2, 10, 4, 4, 2, 11, 10, 5, 5, 5, 10, 10, 10, 5, 2, 12, 4, 6, 2, 13, 12, 3, 6, 4, 12, 12, 4, 3, 6, 12, 2, 14, 6, 6, 6, 6, 2, 15, 4, 6, 12, 4, 10, 12, 2, 16, 8, 16, 4, 16, 8, 16, 2, 17, 8, 16, 4, 16, 16, 16, 8

Offset: 1

Author

Jianing Song, Sep 18 2019

Keywords

• nonn
• tabf

Comments

Let M = {{r, 1}, {0, 1}}, then M^e = {{r^e, 1 + r + r^2 + ... + r^(e-1)}, {0, 1}}. As a result, for gcd(r, n) = 1, the multiplicative order of {{r, 1}, {0, 1}} modulo n is n if r == 1 (mod n) and ord(r,n*(r-1)) otherwise, where ord(r,t) is the multiplicative order of r modulo t.

Examples

			Table starts
  1,
  2,
  3, 2,
  4, 2,
  5, 4, 4, 2,
  6, 2,
  7, 3, 6, 3, 6, 2,
  8, 4, 8, 2,
  9, 6, 9, 6, 9, 2,
  10, 4, 4, 2,
  11, 10, 5, 5, 5, 10, 10, 10, 5, 2,
  12, 4, 6, 2,
  13, 12, 3, 6, 4, 12, 12, 4, 3, 6, 12, 2,
  14, 6, 6, 6, 6, 2,
  15, 4, 6, 12, 4, 10, 12, 2,
  16, 8, 16, 4, 16, 8, 16, 2,
  17, 8, 16, 4, 16, 16, 16, 8, 8, 16, 16, 16, 4, 16, 8, 2,
  18, 6, 18, 6, 18, 2,
  19, 18, 18, 9, 9, 9, 3, 6, 9, 18, 3, 6, 18, 18, 18, 9, 9, 2,
  20, 4, 4, 4, 10, 4, 4, 2,
  ...
For n = 14 and k = 4, let M = {{A038566(n,k), 1}, {0, 1}} = {{9, 1}, {0, 1}}, then:
- M^2 mod 14 = {{11, 10}, {0, 1}};
- M^3 mod 14 = {{1, 7}, {0, 1}};
- M^4 mod 14 = {{9, 8}, {0, 1}};
- M^5 mod 14 = {{11, 3}, {0, 1}};
- M^6 mod 14 = {{1, 0}, {0, 1}}.
So T(14,4) = d(14,9) = 6.
		

Crossrefs

Cf. A000010, A038566, A174824.

Programs

PARI

row(n) = my(v=vector(n,i,i),u=vector(eulerphi(n),i,n)); v=select(i->gcd(n,i)==1,v); for(i=2, #v, u[i]=znorder(Mod(v[i], n*(v[i]-1)))); u

Formula

For gcd(n,r) = 1, 1 <= r <= n, let d(n,r) be the multiplicative order of {{r, 1}, {0, 1}}, then T(n,k) = d(n,A038566(k)).

(a) If p is an odd prime, then d(p^e,r) = p^e if r == 1 (mod p), ord(r,p^e) otherwise;

(b) d(2^e,r) = 2^(e+1-v2(r+1)), where v2(t) is the 2-adic valuation of t;

(c) For gcd(m,n) = 1, d(m*n,r) = lcm(d(m,r mod m),d(n,r mod n)).

The LCM of the n-th row is A174824(n).