A366472 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

Table of n, a(n) for n=1..94.

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

EXAMPLE

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

...

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:

CROSSREFS

Row sums give A366471.

First three columns are A000027, A000217, A132345.

Cf. A000010.

Sequence in context: A350844 A083041 A318611 * A130067 A282906 A032303

Adjacent sequences: A366469 A366470 A366471 * A366473 A366474 A366475

KEYWORD

nonn,tabf

AUTHOR

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

STATUS

approved