A365677 Number of increasing geometric progressions in {1,2,3,...,n} with rational ratio and length >= 3.

0, 0, 0, 1, 1, 1, 1, 3, 5, 5, 5, 6, 6, 6, 6, 11, 11, 13, 13, 14, 14, 14, 14, 16, 20, 20, 24, 25, 25, 25, 25, 31, 31, 31, 31, 36, 36, 36, 36, 38, 38, 38, 38, 39, 41, 41, 41, 46, 52, 56, 56, 57, 57, 61, 61, 63, 63, 63, 63, 64, 64, 64, 66, 79, 79, 79, 79, 80, 80, 80, 80, 86, 86, 86, 90, 91, 91

Offset: 1

Author

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

Keywords

• nonn

Examples

			a(9) = 5 as {1,2,...,9} contains the geometric progressions [1,2,4], [1,2,4,8], [2,4,8], [1,3,9], [4,6,9].
		

Links

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

Crossrefs

Cf. A366471, A078651, A051336.

Formula

a(n) = A366471(n) - n*(1 + (n-1)/2) = Sum_{k=3 .. 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.