login
a(n) = Sum_{k=1..n-1} floor((n-k)/k).
(Formerly M0970 N0362)
43

%I M0970 N0362 #101 Jul 31 2024 09:21:54

%S 0,1,2,4,5,8,9,12,14,17,18,23,24,27,30,34,35,40,41,46,49,52,53,60,62,

%T 65,68,73,74,81,82,87,90,93,96,104,105,108,111,118,119,126,127,132,

%U 137,140,141,150,152,157,160,165,166,173,176,183,186,189,190,201,202,205

%N a(n) = Sum_{k=1..n-1} floor((n-k)/k).

%C Number of pairs (a, b) with 1 <= a < b <= n, a | b.

%C The sequence shows how many digit "skips" there have been from 2 to n, a skip being either a prime factor or product thereof. Every time you have a place where you have X skips and the next skip value is X+1, you will have a prime number since a prime number will only add exactly one more skip to get to it. a(n) = Sum_{x=2..n} floor(n/x) - Sum_{x=2..n-1} floor( (n-1)/x) = 1 when prime. - Marius-Paul Dumitrean (marius(AT)neldor.com), Feb 19 2007

%C A027749(a(n)+1) = n; A027749(a(n)+2) = A020639(n+1). - _Reinhard Zumkeller_, Nov 22 2003

%C Number of partitions of n into exactly 2 types of part, where one part is 1, e.g., n=7 gives 1111111, 111112, 11122, 1222, 11113, 133, 1114, 115 and 16, so a(7)=9. - _Jon Perry_, May 26 2004

%C The sequence of partial sums of A032741. Idea of proof: floor((n-k)/k) - floor((n-k-1)/k) only increases by 1 when k | n. - _George Beck_, Feb 12 2012

%C Also the number of integer partitions of n whose non-1 parts are all equal and with at least one non-1 part. - _Gus Wiseman_, Oct 07 2018

%D J. P. Gram, Undersoegelser angaaende maengden af primtal under en given graense, Det Kongelige Danskevidenskabernes Selskabs Skrifter, series 6, vol. 2 (1884), 183-288; see Tab. VII: Vaerdier af Funktionen psi(n) og andre numeriske Funktioner, pp. 281-288, especially p. 281.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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

%F a(n) = -n + Sum_{k=1..n} tau(k). - _Vladeta Jovovic_, Oct 17 2002

%F G.f.: 1/(1-x) * Sum_{k>=2} x^k/(1-x^k). - _Benoit Cloitre_, Apr 23 2003

%F a(n) = Sum_{i=2..n} floor(n/i). - _Jon Perry_, Feb 02 2004

%F a(n) = (Sum_{i=2..n} ceiling((n+1)/i)) - n + 1. - _Jon Perry_, May 26 2004 [corrected by _Jason Yuen_, Jul 31 2024]

%F a(n) = A006218(n) - n. Proof: floor((n-k)/k)+1 = floor(n/k). Then Sum_{k=1..n-1} floor((n-k)/k)+(n-1)+1 = Sum_{k=1..n-1} floor(n/k) + floor(n/n) = Sum_{k=1..n} floor(n/k); i.e., a(n) + n = A006218(n). - Philippe LALLOUET (philip.lallouet(AT)wanadoo.fr), Jun 23 2007

%F a(n) = A161886(n) - (2n-1). - _Eric Desbiaux_, Jul 10 2013

%F a(n+1) = Sum_{k=1..n} A004199(n-k+1,k). - _L. Edson Jeffery_, Aug 31 2014

%F a(n) = -Sum_{i=1..n} floor((n-2i+1)/(n-i+1)). - _Wesley Ivan Hurt_, May 08 2016

%F a(n) = Sum_{i=1..floor(n/2)} floor((n-i)/i). - _Wesley Ivan Hurt_, Nov 16 2017

%F a(n) = Sum_{k=1..n-1} (A000005(n-k) - 1). - _Gus Wiseman_, Oct 07 2018

%F a(n) ~ n * (log(n) + 2*EulerGamma - 2). - _Rok Cestnik_, Dec 19 2020

%e From _Gus Wiseman_, Oct 07 2018: (Start)

%e The integer partitions whose non-1 parts are all equal and with at least one non-1 part:

%e (2) (3) (4) (5) (6) (7) (8) (9)

%e (21) (22) (41) (33) (61) (44) (81)

%e (31) (221) (51) (331) (71) (333)

%e (211) (311) (222) (511) (611) (441)

%e (2111) (411) (2221) (2222) (711)

%e (2211) (4111) (3311) (6111)

%e (3111) (22111) (5111) (22221)

%e (21111) (31111) (22211) (33111)

%e (211111) (41111) (51111)

%e (221111) (222111)

%e (311111) (411111)

%e (2111111) (2211111)

%e (3111111)

%e (21111111)

%e (End)

%p a:= proc(n) option remember; `if`(n<2, 0,

%p numtheory[tau](n)-1+a(n-1))

%p end:

%p seq(a(n), n=1..100); # _Alois P. Heinz_, Jun 12 2021

%t Table[Sum[Floor[(n-k)/k],{k,n-1}],{n,100}] (* _Harvey P. Dale_, May 02 2011 *)

%o (Haskell)

%o a002541 n = sum $ zipWith div [n - 1, n - 2 ..] [1 .. n - 1]

%o -- _Reinhard Zumkeller_, Jul 05 2013

%o (PARI) a(n)=sum(k=1,n-1, n\k-1) \\ _Charles R Greathouse IV_, Feb 07 2017

%o (PARI) first(n)=my(v=vector(n),s); for(k=1,n, v[k]=-k+s+=numdiv(k)); v \\ _Charles R Greathouse IV_, Feb 07 2017

%o (Python)

%o from math import isqrt

%o def A002541(n): return (sum(n//k for k in range(1,isqrt(n)+1))<<1)-isqrt(n)**2-n # _Chai Wah Wu_, Oct 20 2023

%Y Antidiagonal sums of array A003988. Antidiagonal sums of A004199.

%Y Cf. A000005, A006218, A020639, A027749, A032741.

%Y Cf. A003238, A070776, A126656, A320224, A320225, A320226.

%K nonn,easy,nice

%O 1,3

%A _N. J. A. Sloane_

%E More terms from _David W. Wilson_