A365677 -id:A365677 - cp's OEIS frontend

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

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

nonn

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

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

See A078651 for case of integral ratios, also A051336 for APs.
Row sums of A366472.
Cf. A365677 (length >= 3), A000010.

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

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.

A365047 a(n) is the number of three-term geometric progressions, with rational ratio > 0, formed by the terms a(n-1), a(n-1-k) and a(n-1-2k), where k >= 1 and n - 1 - 2k >= 0.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 2, 0, 0, 2, 0, 3, 0, 4, 2, 0, 0, 4, 1, 0, 1, 0, 2, 1, 0, 3, 0, 5, 0, 4, 1, 0, 2, 0, 2, 0, 5, 0, 4, 1, 3, 0, 4, 1, 1, 1, 2, 1, 4, 2, 0, 4, 1, 0, 3, 0, 3, 0, 2, 2, 1, 4, 0, 5, 0, 3, 0, 6, 0, 3, 1, 3, 0, 5, 0, 6, 0, 5, 0, 6, 0, 6, 0, 8, 0, 8, 0, 9, 1, 2, 1, 1, 2

Offset: 0

Scott R. Shannon, Oct 21 2023

nonn

The sequence is dominated by the count of three-term progressions consisting of three 0's. The 0 terms alternate between long runs on the even and odd n values, so the larger nonzero terms alternate between counting the progressions on these two subsequences, leading to two interrupted lines on the graph of the terms, along with the much lower counts of other three-term subsequences. See the attached image.

			a(3) = 1 and a(2) = a(1) = a(0) = 0 form a progression with ratio 1 separated by one term.
a(8) = 1 as a(7) = a(5) = a(3) = 1 for a progression with ratio 1 separated by two terms.
a(12) = 2 as a(11) = a(8) = a(5) = 1 form a progression with ratio 1 separated by three terms, while a(11) = a(7) = a(3) = 1 form a progression with ratio 1 separated by four terms.
a(20) = 2 as a(19) = 4, a(15) = 2, a(11) = 1 form a progression with ratio 1/2 separated by four terms, while a(19) = 4, a(12) = 2, a(5) = 1  form a progression with ratio 1/2 separated by seven terms.
a(170) = 1 as a(169) = 16, a(131) = 12, a(93) = 9 form a progression with ratio 3/4 separated by thirty-eight terms. This is the first series with a ratio that is not an integer or an integer reciprocal.

Scott R. Shannon, Table of n, a(n) for n = 0..10000
Scott R. Shannon, Image of the first 50000 terms.

Cf. A366907 (length>=3), A132345, A365677, A308638, A078651, A051336.

A366907 a(n) is the number of geometric progressions with three or more terms, with rational ratio > 0, formed by the terms a(n-1), a(n-1-k), a(n-1-2k),...,a(n-1-tk) where k>=1, t>=2, and n-1-t*k>=0.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 0, 2, 0, 4, 1, 0, 1, 0, 0, 2, 0, 3, 0, 3, 0, 6, 0, 7, 0, 9, 0, 13, 0, 12, 0, 15, 0, 21, 0, 20, 0, 22, 0, 30, 0, 30, 0, 31, 0, 38, 0, 39, 0, 43, 0, 47, 0, 46, 0, 53, 0, 61, 0, 57, 0, 59, 0, 69, 0, 72, 0, 72, 0, 78, 0, 79, 0, 84, 0, 91, 0, 90, 0, 96, 0, 103, 0, 98, 0, 105, 0, 116

Offset: 0

Scott R. Shannon, Oct 27 2023

nonn

The sequence is dominated by the count of progressions consisting of three or more 0's. Very rarely the count of these zero-progressions forms a new progression of its own, which forms a short series of small terms and resets the subsequent count of the zero-progressions to a lower value. In the first 10^5 terms this only happens three times - at a(10) (which is not readily noticeable on the graph of the terms), a(644), and a(61434). See the attached images.

			a(3) = 1 and a(2) = a(1) = a(0) = 0 form a progression with ratio 1 separated by one term.
a(7) = 2 as a(6) = a(4) = a(2) = 0 form a three-term progression with ratio 1 separated by two terms, while a(6) = a(4) = a(2) = a(0) = 0 form a four-term progression with ratio 1 separated by two terms.
a(10) = 1 as a(9) = 4, a(7) = 2, a(5) = 1 form a three-term progression with ratio 1/2 separated by two terms.

Scott R. Shannon, Table of n, a(n) for n = 0..10000.
Scott R. Shannon, Image of the first 1000 terms.
Scott R. Shannon, Image of the first 100000 terms.

Cf. A365047 (length=3), A132345, A365677, A308638, A078651, A051336.

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A365047 a(n) is the number of three-term geometric progressions, with rational ratio > 0, formed by the terms a(n-1), a(n-1-k) and a(n-1-2k), where k >= 1 and n - 1 - 2k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A366907 a(n) is the number of geometric progressions with three or more terms, with rational ratio > 0, formed by the terms a(n-1), a(n-1-k), a(n-1-2k),...,a(n-1-tk) where k>=1, t>=2, and n-1-t*k>=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A365047 a(n) is the number of three-term geometric progressions, with rational ratio > 0, formed by the terms a(n-1), a(n-1-k) and a(n-1-2*k), where k >= 1 and n - 1 - 2*k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A366907 a(n) is the number of geometric progressions with three or more terms, with rational ratio > 0, formed by the terms a(n-1), a(n-1-k), a(n-1-2*k),...,a(n-1-t*k) where k>=1, t>=2, and n-1-t*k>=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A365047 a(n) is the number of three-term geometric progressions, with rational ratio > 0, formed by the terms a(n-1), a(n-1-k) and a(n-1-2k), where k >= 1 and n - 1 - 2k >= 0.

A366907 a(n) is the number of geometric progressions with three or more terms, with rational ratio > 0, formed by the terms a(n-1), a(n-1-k), a(n-1-2k),...,a(n-1-tk) where k>=1, t>=2, and n-1-t*k>=0.