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

%I #78 Oct 07 2021 20:28:42

%S 0,1,4,9,17,27,41,57,77,100,127,156,191,228,269,314,364,416,474,534,

%T 600,670,744,820,904,991,1082,1177,1278,1381,1492,1605,1724,1847,1974,

%U 2105,2245,2387,2533,2683,2841,3001,3169,3339,3515,3697,3883,4071,4269,4470

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

%C 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).

%C Appears to be the partial sums of A006218. - _N. J. A. Sloane_, Nov 24 2008

%C 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

%C Apart from initial zero this is the convolution of A341062 and the nonzero terms of A000217. - _Omar E. Pol_, Feb 16 2021

%H Alois P. Heinz, <a href="/A078567/b078567.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Dirichlet_hyperbola_method">Dirichlet Hyperbola Method</a>

%F a(n) = Sum_{i=1..n-1} Sum_{j=1..floor((n-1)/i)} (n - i*j).

%F Convolution of A000027 and A000005. - _Vladeta Jovovic_, Apr 08 2006

%F Row sums of triangle A134546. - _Gary W. Adamson_, Oct 31 2007

%F a(n) = Sum_{i=1..n} (n-i) * A000005(i). - _Wesley Ivan Hurt_, May 08 2016

%F G.f.: (x/(1 - x)^2)*Sum_{k>=1} x^k/(1 - x^k). - _Ilya Gutkovskiy_, Jan 02 2017

%F a(n) = Sum_{k=1..n-1} Sum_{i=1..n-1} floor(k/i). - _Wesley Ivan Hurt_, Sep 14 2017

%F a(n) = Sum_{k=1..n-1} Sum_{i|k} (n-k). - _Daniel Hoying_, May 26 2020

%F 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

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

%p b:= proc(n) option remember; `if`(n<1, [0$2],

%p (p-> p+[numtheory[tau](n), p[1]])(b(n-1)))

%p end:

%p a:= n-> b(n)[2]:

%p seq(a(n), n=1..55); # _Alois P. Heinz_, Oct 07 2021

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

%t Table[Sum[(n - i) DivisorSigma[0, i], {i, n}], {n, 47}] (* or *)

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

%o (PARI) a(n)=sum(i=1,n, numdiv(i)*(n-i)) \\ _Charles R Greathouse IV_, Feb 18 2017

%o (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

%o (Python)

%o from math import isqrt

%o def A078567(n):

%o m = isqrt(n-1)

%o 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

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

%K nonn,easy

%O 1,3

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