A279907 Triangle read by rows: T(n,k) is the smallest power of n that is divisible by k, or -1 if no such power exists.

0, 0, 1, 0, -1, 1, 0, 1, -1, 1, 0, -1, -1, -1, 1, 0, 1, 1, 2, -1, 1, 0, -1, -1, -1, -1, -1, 1, 0, 1, -1, 1, -1, -1, -1, 1, 0, -1, 1, -1, -1, -1, -1, -1, 1, 0, 1, -1, 2, 1, -1, -1, 3, -1, 1, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 0, 1, 1, 1, -1, 1, -1, 2, 2, -1, -1, 1, 0, -1, -1, -1, -1, -1, -1

Offset: 1

Author

Michael De Vlieger, Dec 26 2016

Keywords

• tabl
• sign
• easy

Comments

T(n,1) = 0 since 1 | n^0.

T(n,p) = 1 for prime divisors p of n since p | n^1.

T(n,d) = 1 for divisors d > 1 of n since d | n^1.

Row n for prime p have maximum value 1, since all k < p are coprime to p, and k | p^1 only when k = p.

Values greater than 1 pertain only to composite k of composite n > 4, but not in all cases. T(n,k) = 1 for squarefree kernels k of composite n.

T(n,k) = -1 for numbers k > 1 coprime to n and for numbers that are products of at least one prime q coprime to n and one prime p | n.

T(n,k) is nonnegative for all numbers k for which n^k (mod k) = 0, i.e., all the prime divisors p of k also divide n.

The largest possible value s in row n of T = floor(log_2(n)), since the largest possible multiplicity of any number m <= n pertains to perfect powers of 2, as 2 is the smallest prime. This number s first appears at T(2^s + 2, 2^s) for s > 1.

If T(n,k) is positive, 1/k terminates T(n,k) digits after the radix point in base n. If T(n,k) is negative, 1/k is recurrent in base n.

From Robert Israel, Dec 28 2016: (Start)

T(a*b,c*d) = max(T(a,c),T(b,d)) if GCD(a,b)=1, GCD(b,d)=1,T(a,c)>=0 and T(b,d)>=0.

T(n,a*b) = max(T(n,a),T(n,b)) if GCD(a,b)=1 and T(n,a)>=0 and T(n,b)>=0. (End)

Examples

			The triangle T(n,k) begins (with -1 shown as "." for clarity):
n\k 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...
1:  0
2:  0  1
3:  0  .  1
4:  0  1  .  1
5:  0  .  .  .  1
6:  0  1  1  2  .  1
7:  0  .  .  .  .  .  1
8:  0  1  .  1  .  .  .  1
9:  0  .  1  .  .  .  .  .  1
10: 0  1  .  2  1  .  .  3  .  1
11: 0  .  .  .  .  .  .  .  .  .  1
12: 0  1  1  1  .  1  .  2  2  .  .  1
13: 0  .  .  .  .  .  .  .  .  .  .  .  1
14: 0  1  .  2  .  .  1  3  .  .  .  .  .  1
15: 0  .  1  .  1  .  .  .  2  .  .  .  .  .  1
...
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..11325 (rows 1 <= n <= 150)

Crossrefs

Cf.: A010846 (number of nonnegative k in row n), A162306 (k with nonnegative values in a(n)), A051731 (k with values 0 or 1), A000005 (number of k in row n with values 0 or 1), A272618 (k with values > 1), A243822 (number of k in row n with values > 1), A007947.

Programs

Maple

f:= proc(n,k) local Fk,Fn,i;
   if k = 1 then return 0 fi;
   Fk:= ifactors(k)[2];
   Fn:= map(t -> padic:-ordp(n,t[1]),Fk);
   if min(Fn) = 0 then -1 else max(seq(ceil(Fk[i,2]/Fn[i]),i=1..nops(Fk))) fi
end proc:
seq(seq(f(n,k),k=1..n),n=1..20); # Robert Israel, Dec 28 2016

Mathematica

Table[Boole[k == 1] + (Boole[#[[-1, 1]] == 1] (-1 + Length@ #) /. 0 -> -1) &@ NestWhileList[Function[s, {#1/s, s}]@ GCD[#1, #2] & @@ # &, {k, n}, And[First@ # != 1, ! CoprimeQ @@ #] &], {n, 16}, {k, n}] // Flatten (* or *)
Table[SelectFirst[Range[0, Floor@ Log2@ n], PowerMod[n, #, k] == 0 &] /. k_ /; MissingQ@ k -> -1, {n, 12}, {k, n}] // TableForm (* Version 10.2 *)