|
| |
|
|
A078567
|
|
Number of arithmetic subsequences of [1..n] with length > 1.
|
|
6
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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).
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)*[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
|
Cf. A000005, A000027, A000217, A006218, A051336, A134546, A341062.
Sequence in context: A033607 A019572 A048205 * A033617 A033613 A033608
Adjacent sequences: A078564 A078565 A078566 * A078568 A078569 A078570
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
Robert E. Sawyer (rs.1(AT)mindspring.com)
|
|
|
STATUS
|
approved
|
| |
|
|
