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