login
Irregular triangle read by rows: T(n,k) (n >= 1, k >= 1) = number of increasing geometric progressions in {1,2,3,...,n} of length k with rational ratio.
2

%I #10 Oct 23 2023 22:07:34

%S 1,2,1,3,3,4,6,1,5,10,1,6,15,1,7,21,1,8,28,2,1,9,36,4,1,10,45,4,1,11,

%T 55,4,1,12,66,5,1,13,78,5,1,14,91,5,1,15,105,5,1,16,120,8,2,1,17,136,

%U 8,2,1,18,153,10,2,1,19,171,10,2,1,20,190,11,2,1,21,210,11,2,1,22,231,11,2,1,23,253,11,2,1,24,276,12,3,1

%N Irregular triangle read by rows: T(n,k) (n >= 1, k >= 1) = number of increasing geometric progressions in {1,2,3,...,n} of length k with rational ratio.

%F T(n,k) = Sum_{p=2..floor(n^(1/(k-1)))} phi(p)*floor(n/p^(k-1)) where phi is the Euler phi-function A000010 and k runs from 1 to 1+floor(log_2(n))}.

%e Triangle begins:

%e [1],

%e [2, 1],

%e [3, 3],

%e [4, 6, 1],

%e [5, 10, 1],

%e [6, 15, 1],

%e [7, 21, 1],

%e [8, 28, 2, 1],

%e [9, 36, 4, 1],

%e [10, 45, 4, 1],

%e [11, 55, 4, 1],

%e [12, 66, 5, 1],

%e [13, 78, 5, 1],

%e [14, 91, 5, 1],

%e [15, 105, 5, 1],

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

%e ...

%p with(numtheory);

%p A366472 := proc(n) local v,u2,u1,k,i,p;

%p v := Array(1..100, 0);

%p v[1] := n;

%p u1 := 1+floor(log(n)/log(2));

%p for k from 2 to u1 do

%p u2 := floor(n^(1/(k-1)));

%p v[k] := add(phi(p)*floor(n/p^(k-1)),p=2..u2);

%p od;

%p [seq(v[i],i=1..u1)];

%p end;

%p for n from 1 to 36 do lprint(A366472(n)); od:

%Y Row sums give A366471.

%Y First three columns are A000027, A000217, A132345.

%Y Cf. A000010.

%K nonn,tabf

%O 1,2

%A _Scott R. Shannon_ and _N. J. A. Sloane_, Oct 23 2023