login
A365677
Number of increasing geometric progressions in {1,2,3,...,n} with rational ratio and length >= 3.
4
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,8
LINKS
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.
EXAMPLE
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].
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved