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

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

Author

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

Keywords

• nonn
• easy

Comments

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

Examples

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

Links

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

Crossrefs

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

Programs

Maple

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

Mathematica

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 *)

PARI

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

PARI

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

Python

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

Formula

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