login
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).
0
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,2
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.
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).
EXAMPLE
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.
PROG
(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
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Jianing Song, Sep 18 2019
STATUS
approved