A366472 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.

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

Offset: 1

Author

Scott R. Shannon and N. J. A. Sloane, Oct 23 2023

Keywords

• nonn
• tabf

Examples

			Triangle begins:
  [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, 55, 4, 1],
  [12, 66, 5, 1],
  [13, 78, 5, 1],
  [14, 91, 5, 1],
  [15, 105, 5, 1],
  [16, 120, 8, 2, 1],
...
		

Crossrefs

Row sums give A366471.

First three columns are A000027, A000217, A132345.

Cf. A000010.

Programs

Maple

with(numtheory);
A366472 := proc(n) local v,u2,u1,k,i,p;
v := Array(1..100, 0);
v[1] := n;
u1 := 1+floor(log(n)/log(2));
for k from 2 to u1 do
   u2 := floor(n^(1/(k-1)));
   v[k] := add(phi(p)*floor(n/p^(k-1)),p=2..u2);
  od;
[seq(v[i],i=1..u1)];
end;
for n from 1 to 36 do lprint(A366472(n)); od:

Formula

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)).