cp's OEIS Frontend

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

%I A078567 #85 Jun 03 2025 04:20:04
%S A078567 0,1,4,9,17,27,41,57,77,100,127,156,191,228,269,314,364,416,474,534,
%T A078567 600,670,744,820,904,991,1082,1177,1278,1381,1492,1605,1724,1847,1974,
%U A078567 2105,2245,2387,2533,2683,2841,3001,3169,3339,3515,3697,3883,4071,4269,4470
%N A078567 Number of arithmetic subsequences of [1..n] with length > 1.
%C A078567 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 A078567 Appears to be the partial sums of A006218. - _N. J. A. Sloane_, Nov 24 2008
%C A078567 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 A078567 Apart from initial zero this is the convolution of A341062 and the nonzero terms of A000217. - _Omar E. Pol_, Feb 16 2021
%H A078567 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 A078567 Wikipedia, <a href="https://en.wikipedia.org/wiki/Dirichlet_hyperbola_method">Dirichlet Hyperbola Method</a>
%F A078567 a(n) = Sum_{i=1..n-1} Sum_{j=1..floor((n-1)/i)} (n - i*j).
%F A078567 Convolution of A000027 and A000005. - _Vladeta Jovovic_, Apr 08 2006
%F A078567 Row sums of triangle A134546. - _Gary W. Adamson_, Oct 31 2007
%F A078567 a(n) = Sum_{i=1..n} (n-i) * A000005(i). - _Wesley Ivan Hurt_, May 08 2016
%F A078567 G.f.: (x/(1 - x)^2)*Sum_{k>=1} x^k/(1 - x^k). - _Ilya Gutkovskiy_, Jan 02 2017
%F A078567 a(n) = Sum_{k=1..n-1} Sum_{i=1..n-1} floor(k/i). - _Wesley Ivan Hurt_, Sep 14 2017
%F A078567 a(n) = Sum_{k=1..n-1} Sum_{i|k} (n-k). - _Daniel Hoying_, May 26 2020
%F A078567 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
%e A078567 a(2): [1,2]; a(3): [1,2],[1,3],[2,3],[1,2,3].
%p A078567 b:= proc(n) option remember; `if`(n<1, [0$2],
%p A078567       (p-> p+[numtheory[tau](n), p[1]])(b(n-1)))
%p A078567     end:
%p A078567 a:= n-> b(n)[2]:
%p A078567 seq(a(n), n=1..55);  # _Alois P. Heinz_, Oct 07 2021
%t A078567 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 A078567 Table[Sum[(n - i) DivisorSigma[0, i], {i, n}], {n, 47}] (* or *)
%t A078567 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 A078567 (PARI) a(n)=sum(i=1,n, numdiv(i)*(n-i)) \\ _Charles R Greathouse IV_, Feb 18 2017
%o A078567 (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 A078567 (Python)
%o A078567 from math import isqrt
%o A078567 def A078567(n):
%o A078567     m = isqrt(n-1)
%o A078567     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 A078567 Cf. A000005, A000027, A000217, A006218, A051336, A134546, A341062.
%K A078567 nonn,easy
%O A078567 1,3
%A A078567 Robert E. Sawyer (rs.1(AT)mindspring.com)