cp's OEIS Frontend

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

%I A366471 #25 Oct 23 2023 21:59:50
%S A366471 1,3,6,11,16,22,29,39,50,60,71,84,97,111,126,147,164,184,203,224,245,
%T A366471 267,290,316,345,371,402,431,460,490,521,559,592,626,661,702,739,777,
%U A366471 816,858,899,941,984,1029,1076,1122,1169,1222,1277,1331,1382,1435,1488,1546,1601,1659,1716,1774,1833,1894,1955
%N A366471 Number of increasing geometric progressions in {1,2,3,...,n} with rational ratio.
%H A366471 Scott R. Shannon, <a href="/A366471/b366471.txt">Table of n, a(n) for n = 1..1000</a>
%F A366471 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.
%e A366471 For n = 6, the a(6) = 22 GPs are: all 6 singletons, all 15 pairs, and one triple 1,2,4.
%p A366471 with(numtheory);
%p A366471 A366471 := proc(n) local a,s,u2,u1,k,p;
%p A366471 a := n;
%p A366471 u1 := 1+floor(log(n)/log(2));
%p A366471 for k from 2 to u1 do
%p A366471    u2 := floor(n^(1/(k-1)));
%p A366471    s := add(phi(p)*floor(n/p^(k-1)),p=2..u2);
%p A366471    a := a+s;
%p A366471 od;
%p A366471 a;
%p A366471 end;
%p A366471 [seq(A366471(n),n=1..100)];
%Y A366471 See A078651 for case of integral ratios, also A051336 for APs.
%Y A366471 Row sums of A366472.
%Y A366471 Cf. A365677 (length >= 3), A000010.
%K A366471 nonn
%O A366471 1,2
%A A366471 _Scott R. Shannon_ and _N. J. A. Sloane_, Oct 23 2023