A051336 -id:A051336 - cp's OEIS frontend

A078582 Duplicate of A051336.

1, 3, 7, 13, 22, 33, 48, 65, 86, 110, 138, 168, 204, 242, 284, 330, 381, 434, 493, 554

Offset: 1

dead

A054519 Number of increasing arithmetic progressions of nonnegative integers ending in n, including those of length 1 or 2.

1, 2, 4, 6, 9, 11, 15, 17, 21, 24, 28, 30, 36, 38, 42, 46, 51, 53, 59, 61, 67, 71, 75, 77, 85, 88, 92, 96, 102, 104, 112, 114, 120, 124, 128, 132, 141, 143, 147, 151, 159, 161, 169, 171, 177, 183, 187, 189, 199, 202, 208, 212, 218, 220, 228, 232, 240, 244, 248

Offset: 0

Henry Bottomley, Apr 07 2000

a(0)=1, a(n) = a(n-1) + sigma_0(n) (A000005). - Ctibor O. Zizka, Nov 08 2008
a(n) is the index of the n-th term of A027750 whose value is 1. - Michel Marcus, Oct 15 2015
From Gus Wiseman, Jun 07 2019: (Start)
Also the number of subsets of {1..n} that are closed under taking the difference of two strictly decreasing terms. For example, the a(0) = 1 through a(6) = 15 subsets are:
  {}  {}   {}     {}       {}         {}           {}
      {1}  {1}    {1}      {1}        {1}          {1}
           {2}    {2}      {2}        {2}          {2}
           {1,2}  {3}      {3}        {3}          {3}
                  {1,2}    {4}        {4}          {4}
                  {1,2,3}  {1,2}      {5}          {5}
                           {2,4}      {1,2}        {6}
                           {1,2,3}    {2,4}        {1,2}
                           {1,2,3,4}  {1,2,3}      {2,4}
                                      {1,2,3,4}    {3,6}
                                      {1,2,3,4,5}  {1,2,3}
                                                   {2,4,6}
                                                   {1,2,3,4}
                                                   {1,2,3,4,5}
                                                   {1,2,3,4,5,6}
(End)

			a(3)=6 because the six increasing progressions (3), (2,3), (1,2,3), (0,1,2,3), (1,3) and (0,3) all end in 3.

Marius A. Burtea, Table of n, a(n) for n = 0..10000 (term 0..1000 from T. D. Noe).
Wikipedia, Arithmetic progression

Cf. A000005, A006218, A027750, A051336. Left edge of A056535.

Cf. A007862, A049988, A175342, A238423, A295370, A325849.

[1] cat [&+[Ceiling((k+1)/(i+1)): i in [1..k+1]]: k in [1..60]]; // Marius A. Burtea, Jun 10 2019

IBI:= {{}}: a[0]:= 1: for n from 1 to 45 do IBI:= IBI union map(t -> t union {n}, select(t -> (t minus map(q -> n-q, t)={}), IBI)); a[n]:= nops(IBI) od: seq(a[n], n=0..45); # Zerinvary Lajos, Mar 18 2007
with(numtheory):a[1]:=2: for n from 2 to 59 do a[n]:=a[n-1]+tau(n) od: seq(a[n], n=0..45); # Zerinvary Lajos, Mar 21 2009
map(`+`, ListTools:-PartialSums(map(numtheory:-tau, [$0..1000])),1); # Robert Israel, Oct 15 2015

a[0]=1; a[n_] := a[n] = a[n-1] + DivisorSigma[0, n]; Table[a[n], {n, 0, 45}] (* Jean-François Alcover, Oct 05 2012, after Ctibor O. Zizka *)
nxt[{n_,a_}]:={n+1,a+DivisorSigma[0,n+1]}; Transpose[NestList[nxt,{0,1},50]][[2]] (* Harvey P. Dale, Oct 15 2012 *)
Table[Length[Select[Subsets[Range[n]],SubsetQ[#,Subtract@@@Reverse/@Subsets[#,{2}]]&]],{n,0,10}] (* Gus Wiseman, Jun 07 2019 *)

vector(100, n, n--; sum(k=1, n, n\k) + 1) \\ Altug Alkan, Oct 15 2015

a(n) = A051336(n+1) - A051336(n) = a(n-1) + A000005(n) = A006218(n)+1.
G.f.: (1-x)^(-1) * (1 + Sum_{j>=1} x^j/(1-x^j)). - Robert Israel, Oct 15 2015
a(n) = Sum_{i=1..n+1} ceiling((n+1)/(i+1)). - Wesley Ivan Hurt, Sep 15 2017

A078567 Number of arithmetic subsequences of [1..n] with length > 1.

Original entry on oeis.org

0, 1, 4, 9, 17, 27, 41, 57, 77, 100, 127, 156, 191, 228, 269, 314, 364, 416, 474, 534, 600, 670, 744, 820, 904, 991, 1082, 1177, 1278, 1381, 1492, 1605, 1724, 1847, 1974, 2105, 2245, 2387, 2533, 2683, 2841, 3001, 3169, 3339, 3515, 3697, 3883, 4071, 4269, 4470

Offset: 1

Robert E. Sawyer (rs.1(AT)mindspring.com)

The number of arithmetic subsequences of [1..n] with successive-term increment i and length k is n-i*(k-1) for i > 0, k > 0, n > i*(k-1).
Appears to be the partial sums of A006218. - N. J. A. Sloane, Nov 24 2008
The O(n^(1/2)) formula can be derived via Dirichlet hyperbola method (see Wikipedia link below) applied to a(n) = Sum_{k=1..n-1} Sum_{i*j=k} (sqrt(n)*sqrt(n)-i*j), where we've written the formula in this form to show which functions are being Dirichlet convoluted. - Daniel Hoying, May 31 2020
Apart from initial zero this is the convolution of A341062 and the nonzero terms of A000217. - Omar E. Pol, Feb 16 2021

			a(2): [1,2]; a(3): [1,2],[1,3],[2,3],[1,2,3].

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Wikipedia, Dirichlet Hyperbola Method

Cf. A000005, A000027, A000217, A006218, A051336, A134546, A341062.

b:= proc(n) option remember; `if`(n<1, [0$2],
      (p-> p+[numtheory[tau](n), p[1]])(b(n-1)))
    end:
a:= n-> b(n)[2]:
seq(a(n), n=1..55);  # Alois P. Heinz, Oct 07 2021

a[n_]:=-(-1 + n) n + Sum[-(1/2) Ceiling[n/(1 + k)] (-1 - k - 2 n + (1 + k) Ceiling[n/(1 + k)]), {k, 0, n - 2}]; (* Lorenz H. Menke, Jr., Feb 17 2017 *)
Table[Sum[(n - i) DivisorSigma[0, i], {i, n}], {n, 47}] (* or *)
With[{nn = 46}, {0}~Join~Table[First[ListConvolve @@ Transpose@ Take[#, n]], {n, nn}] &@ Table[{n, DivisorSigma[0, n]}, {n, nn}]] (* Michael De Vlieger, Feb 18 2017 *)

a(n)=sum(i=1,n, numdiv(i)*(n-i)) \\ Charles R Greathouse IV, Feb 18 2017

a(n)={n--; sqrtint(n)^2*(1/4 * (1+sqrtint(n))^2-n-1) + sum(i=1, sqrtint(n), (n\i)*(2*n + 2 - i*(1+n\i)))} \\ Andrew Howroyd, May 31 2020

from math import isqrt
def A078567(n):
    m = isqrt(n-1)
    return m**2*(1+m)**2//4-m**2*n+sum((n-1)//i*(2*n-i*(1+(n-1)//i)) for i in range(1,m+1)) # Chai Wah Wu, Oct 07 2021

a(n) = Sum_{i=1..n-1} Sum_{j=1..floor((n-1)/i)} (n - i*j).
Convolution of A000027 and A000005. - Vladeta Jovovic, Apr 08 2006
Row sums of triangle A134546. - Gary W. Adamson, Oct 31 2007
a(n) = Sum_{i=1..n} (n-i) * A000005(i). - Wesley Ivan Hurt, May 08 2016
G.f.: (x/(1 - x)^2)*Sum_{k>=1} x^k/(1 - x^k). - Ilya Gutkovskiy, Jan 02 2017
a(n) = Sum_{k=1..n-1} Sum_{i=1..n-1} floor(k/i). - Wesley Ivan Hurt, Sep 14 2017
a(n) = Sum_{k=1..n-1} Sum_{i|k} (n-k). - Daniel Hoying, May 26 2020
a(n+1) = floor(sqrt(n))^2*(1/4*(1+floor(sqrt(n)))^2 - n - 1) + Sum_{i=1..floor(sqrt(n))} floor(n/i)*(2*n + 2 - i*(1+floor(n/i))). - Daniel Hoying, May 31 2020

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

Original entry on oeis.org

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.

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

Original entry on oeis.org

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

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

nonn

			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].

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

Cf. A366471, A078651, A051336.

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.

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

A078582 Duplicate of A051336.

Views

Author

Keywords

A054519 Number of increasing arithmetic progressions of nonnegative integers ending in n, including those of length 1 or 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A078567 Number of arithmetic subsequences of [1..n] with length > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

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.