A086145 - OEIS

%I #25 Aug 18 2017 19:16:20

%S 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,

%T 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,

%U 18,3,6,18,18,18,9,9,2,1,11,11,11,22,11,22,11,11,22,22,11,11,22

%N 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.

%C The length of row n is A006093(n).

%C From _J. H. Conway_, Sep 06 2003: (Start)

%C "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.

%C "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.

%C "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.

%C "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)."

%C (End)

%C This is the prime-indexed rows of A057593. - _Franklin T. Adams-Watters_, Jan 19 2006

%C 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]

%H T. D. Noe, <a href="/A086145/b086145.txt">Rows n=1..50, flattened</a>

%e Triangle T(n,k) begins (with offsets 1):

%e [1]

%e [1, 2]

%e [1, 4, 4, 2]

%e [1, 3, 6, 3, 6, 2]

%e [1, 10, 5, 5, 5, 10, 10, 10, 5, 2]

%e [1, 12, 3, 6, 4, 12, 12, 4, 3, 6, 12, 2]

%e [1, 8, 16, 4, 16, 16, 16, 8, 8, 16, 16, 16, 4, 16, 8, 2]

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

%o (PARI) 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

%Y Cf. A006093, A057593, A174842.

%K nonn,tabf

%O 1,3

%A _Benoit Cloitre_, Sep 06 2003

%E Name improved by _T. D. Noe_, Apr 01 2010

%E Prepended 1 for p=2 by _T. D. Noe_, Apr 01 2010