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

Links

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

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.

Example

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

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)];

Crossrefs

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

Row sums of A366472.

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

Sequence in context: A310113 A310114 A111582 * A024401 A333709 A266252

Adjacent sequences: A366468 A366469 A366470 * A366472 A366473 A366474

Keyword

nonn

Author

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

Status

approved