OFFSET
1,3
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
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Wikipedia, Dirichlet Hyperbola Method
FORMULA
a(n) = Sum_{i=1..n-1} Sum_{j=1..floor((n-1)/i)} (n - i*j).
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)*[2n+2-i*(1+floor(n/i)]. - Daniel Hoying, May 31 2020
EXAMPLE
a(2): [1,2]; a(3): [1,2],[1,3],[2,3],[1,2,3].
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Robert E. Sawyer (rs.1(AT)mindspring.com)
STATUS
approved