|
| |
|
|
A002541
|
|
a(n) = Sum_{k=1..n-1} floor((n-k)/k).
(Formerly M0970 N0362)
|
|
43
|
|
|
|
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
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
|
|
|
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
|
|
|
|
FORMULA
|
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) ~ n * (log(n) + 2*EulerGamma - 2). - Rok Cestnik, Dec 19 2020
|
|
|
EXAMPLE
|
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)
|
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n<2, 0,
numtheory[tau](n)-1+a(n-1))
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]
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
