A366471 Number of increasing geometric progressions in {1,2,3,...,n} with rational ratio.

1, 3, 6, 11, 16, 22, 29, 39, 50, 60, 71, 84, 97, 111, 126, 147, 164, 184, 203, 224, 245, 267, 290, 316, 345, 371, 402, 431, 460, 490, 521, 559, 592, 626, 661, 702, 739, 777, 816, 858, 899, 941, 984, 1029, 1076, 1122, 1169, 1222, 1277, 1331, 1382, 1435, 1488, 1546, 1601, 1659, 1716, 1774, 1833, 1894, 1955

Offset: 1

Author

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

Keywords

• nonn

Examples

			For n = 6, the a(6) = 22 GPs are: all 6 singletons, all 15 pairs, and one triple 1,2,4.
		

Links

• Scott R. Shannon, Table of n, a(n) for n = 1..1000

Crossrefs

See A078651 for case of integral ratios, also A051336 for APs.

Row sums of A366472.

Cf. A365677 (length >= 3), A000010.

Programs

Maple

with(numtheory);
A366471 := proc(n) local a,s,u2,u1,k,p;
a := n;
u1 := 1+floor(log(n)/log(2));
for k from 2 to u1 do
   u2 := floor(n^(1/(k-1)));
   s := add(phi(p)*floor(n/p^(k-1)),p=2..u2);
   a := a+s;
od;
a;
end;
[seq(A366471(n),n=1..100)];

Formula

a(n) = Sum_{k=1 .. 1+floor(log_2(n))} Sum_{p=2..floor(n^(1/(k-1)))} phi(p)*floor(n/p^(k-1)) where phi is the Euler phi-function A000010.