login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002541 a(n) = Sum_{k=1..n-1} floor((n-k)/k).
(Formerly M0970 N0362)
20
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

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(n)=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

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

T. D. Noe, Table of n, a(n) for n = 1..1000

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)/2)) - n + 1. - Jon Perry, May 26 2004

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

EXAMPLE

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)

MATHEMATICA

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

PROG

(Haskell)

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

-- Reinhard Zumkeller, Jul 05 2013

(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

CROSSREFS

Antidiagonal sums of array A003988. Antidiagonal sums of A004199.

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

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

Sequence in context: A296058 A189205 A137169 * A239953 A321324 A259558

Adjacent sequences:  A002538 A002539 A002540 * A002542 A002543 A002544

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from David W. Wilson

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 17 22:17 EDT 2019. Contains 324200 sequences. (Running on oeis4.)