login
A366471
Number of increasing geometric progressions in {1,2,3,...,n} with rational ratio.
5
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
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
KEYWORD
nonn
AUTHOR
STATUS
approved