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

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, 65, 68, 73, 74, 81, 82, 87, 90, 93, 96, 104, 105, 108, 111, 118, 119, 126, 127, 132, 137, 140, 141, 150, 152, 157, 160, 165, 166, 173, 176, 183, 186, 189, 190, 201, 202, 205

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

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

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

A027749(a(n)+1) = n; A027749(a(n)+2) = A020639(n+1). - Reinhard Zumkeller, Nov 22 2003

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

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

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

Examples

			From _Gus Wiseman_, Oct 07 2018: (Start)
The integer partitions whose non-1 parts are all equal and with at least one non-1 part:
  (2)  (3)   (4)    (5)     (6)      (7)       (8)        (9)
       (21)  (22)   (41)    (33)     (61)      (44)       (81)
             (31)   (221)   (51)     (331)     (71)       (333)
             (211)  (311)   (222)    (511)     (611)      (441)
                    (2111)  (411)    (2221)    (2222)     (711)
                            (2211)   (4111)    (3311)     (6111)
                            (3111)   (22111)   (5111)     (22221)
                            (21111)  (31111)   (22211)    (33111)
                                     (211111)  (41111)    (51111)
                                               (221111)   (222111)
                                               (311111)   (411111)
                                               (2111111)  (2211111)
                                                          (3111111)
                                                          (21111111)
(End)
		

References

• 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.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)

Crossrefs

Antidiagonal sums of array A003988. Antidiagonal sums of A004199.

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

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

Programs

Haskell

a002541 n = sum $ zipWith div [n - 1, n - 2 ..] [1 .. n - 1]
-- Reinhard Zumkeller, Jul 05 2013

Maple

a:= proc(n) option remember; `if`(n<2, 0,
      numtheory[tau](n)-1+a(n-1))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Jun 12 2021

Mathematica

Table[Sum[Floor[(n-k)/k],{k,n-1}],{n,100}] (* Harvey P. Dale, May 02 2011 *)

PARI

a(n)=sum(k=1,n-1, n\k-1) \\ Charles R Greathouse IV, Feb 07 2017

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

Python

from math import isqrt
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

Formula

a(n) = -n + Sum_{k=1..n} tau(k). - Vladeta Jovovic, Oct 17 2002

G.f.: 1/(1-x) * Sum_{k>=2} x^k/(1-x^k). - Benoit Cloitre, Apr 23 2003

a(n) = Sum_{i=2..n} floor(n/i). - Jon Perry, Feb 02 2004

a(n) = (Sum_{i=2..n} ceiling((n+1)/i)) - n + 1. - Jon Perry, May 26 2004 [corrected by Jason Yuen, Jul 31 2024]

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

a(n) = A161886(n) - (2n-1). - Eric Desbiaux, Jul 10 2013

a(n+1) = Sum_{k=1..n} A004199(n-k+1,k). - L. Edson Jeffery, Aug 31 2014

a(n) = -Sum_{i=1..n} floor((n-2i+1)/(n-i+1)). - Wesley Ivan Hurt, May 08 2016

a(n) = Sum_{i=1..floor(n/2)} floor((n-i)/i). - Wesley Ivan Hurt, Nov 16 2017

a(n) = Sum_{k=1..n-1} (A000005(n-k) - 1). - Gus Wiseman, Oct 07 2018

a(n) ~ n * (log(n) + 2*EulerGamma - 2). - Rok Cestnik, Dec 19 2020

Extensions

More terms from David W. Wilson