A003988 -id:A003988 - cp's OEIS frontend

A006218 a(n) = Sum_{k=1..n} floor(n/k); also Sum_{k=1..n} d(k), where d = number of divisors (A000005); also number of solutions to x*y = z with 1 <= x,y,z <= n.

0, 1, 3, 5, 8, 10, 14, 16, 20, 23, 27, 29, 35, 37, 41, 45, 50, 52, 58, 60, 66, 70, 74, 76, 84, 87, 91, 95, 101, 103, 111, 113, 119, 123, 127, 131, 140, 142, 146, 150, 158, 160, 168, 170, 176, 182, 186, 188, 198, 201, 207, 211, 217, 219, 227, 231, 239, 243, 247, 249

Offset: 0

N. J. A. Sloane

The identity Sum_{k=1..n} floor(n/k) = Sum_{k=1..n} d(k) is Equation (10), p. 58, of Apostol (1976). - N. J. A. Sloane, Dec 06 2020
The "Dirichlet divisor problem" is to find a precise asymptotic estimate for this sequence - see formula lines below, also Apostol (1976), Chap. 3.
Number of increasing arithmetic progressions where n+1 is the second or later term. - Mambetov Timur, Takenov Nurdin, Haritonova Oksana (timus(AT)post.kg; oksanka-61(AT)mail.ru), Jun 13 2002. E.g., a(3) = 5 because there are 5 such arithmetic progressions: (1, 2, 3, 4); (2, 3, 4); (1, 4); (2, 4); (3, 4).
Binomial transform of A001659.
Area covered by overlapped partitions of n, i.e., sum of maximum values of the k-th part of a partition of n into k parts. - Jon Perry, Sep 08 2005
Equals inverse Mobius transform of A116477. - Gary W. Adamson, Aug 07 2008
The Polymath project (see the Tao-Croot-Helfgott link) sketches an algorithm for computing a(n) in essentially cube root time, see section 2.1. - Charles R Greathouse IV, Oct 10 2010 [Sladkey gives another. - Charles R Greathouse IV, Oct 02 2017]
The Dirichlet inverse starts (offset 1) 1, -3, -5, 1, -10, 16, -16, 1, 2, 33, -29, -6, -37, 55, 55, -1, -52, -5, -60, ... - R. J. Mathar, Oct 17 2012
The inverse Mobius transforms yields A143356. - R. J. Mathar, Oct 17 2012
An improved approximation vs. Dirichlet is: a(n) = log(Gamma(n+1)) + 2n*gamma. Using sample ranges of {n = k^2-k to k^2 + (k-1)} the means of the new error term are < +- 0.5 up to k=150, except on two values of k. These ranges appear to give means closest to zero for such small sample sizes. It is not clear sample means remain < +- 0.5 at larger k. The standard deviations are ~(n*log(n))^(1/4)/2, with n near sample range center. - Richard R. Forberg, Jan 06 2015
The values of n for which a(n) is even are given by 4*m^2 <= n <= 4*m(m+1) for m >= 0. Example: for m=1 the values of n are 4 <= n <= 8 for which a(4) to a(8) are even. - G. C. Greubel, Sep 30 2015
For n > 0, a(n) = count(x|y), 1 <= y <= x <= n, that is, the number of pairs in the ordered list of x and y, where y divides x, up to and including n. - Torlach Rush, Jan 31 2017
a(n) is also the total number of partitions of all positive integers <= n into equal parts. - Omar E. Pol, May 29 2017
a(n) is the rank of the join of the set of elements of rank n in Young's lattice, the lattice of all integer partitions ordered by inclusion of their Ferrers diagrams. - Geoffrey Critzer, Jul 11 2018
a(n) always has the same parity as floor(sqrt(n)) = A000196(n): see A211264 (proof in Diophante link). - Bernard Schott, Feb 13 2021
From Omar E. Pol, Feb 16 2021: (Start)
Apart from initial zero this is the convolution of A341062 and A000027.
Nonzero terms convolved with A341062 gives A055507. (End)
From Bernard Schott, Apr 17 2022: (Start)
a(n-1) is the number of lattice points in the first quadrant lying under the hyperbola x*y = n, excluding the lattice points on the axes.
a(n) is the number of lattice points in the first quadrant lying on or under the hyperbola x*y = n, excluding the lattice points on the axes. (Reference Hari Kishan). (End)
Let tiles Tn (for n >= 1) be initially placed on square n on an infinite 1D board. At each step, the leftmost unblocked tile (i.e., the top tile in the leftmost stack) jumps forward exactly n squares. Tiles can stack, and only the top tile of a stack can move. This sequence gives the step number when tile n moves for the first time. - Ali Sada, May 23 2025

			a(3) = 5 because 3 + floor(3/2) + 1 = 3 + 1 + 1 = 5. Or tau(1) + tau(2) + tau(3) = 1 + 2 + 2 = 5.
a(4) = 8 because 4 + floor(4/2) + floor(4/3) + 1 = 4 + 2 + 1 + 1 = 8. Or
tau(1) + tau(2) + tau(3) + tau(4) = 1 + 2 + 2 + 3 = 8.
a(5) = 10 because 5 + floor(5/2) + floor(5/3) + floor (5/4) + 1 = 5 + 2 + 1 + 1 + 1 = 10. Or tau(1) + tau(2) + tau(3) + tau(4) + tau(5) = 1 + 2 + 2 + 3 + 2 = 10.

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976.
K. Chandrasekharan, Introduction to Analytic Number Theory. Springer-Verlag, 1968, Chap. VI.
K. Chandrasekharan, Arithmetical Functions. Springer-Verlag, 1970, Chapter VIII, pp. 194-228. Springer-Verlag, Berlin.
P. G. L. Dirichlet, Werke, Vol. ii, pp. 49-66.
M. N. Huxley, The Distribution of Prime Numbers, Oxford Univ. Press, 1972, p. 7.
M. N. Huxley, Area, Lattice Points and Exponential Sums, Oxford, 1996; p. 239.
Hari Kishan, Number Theory, Krishna, Educational Publishers, 2014, Theorem 1, p. 133.
H. L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 56.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Nurdin N. Takenov and Oksana Haritonova, Representation of positive integers by a special set of digits and sequences, in Dolmatov, S. L. et al. editors, Materials of Science, Practical seminar "Modern Mathematics".
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, Exercise 3.6.13 on page 107.

N. J. A. Sloane, Table of n, a(n) for n = 0..20000 (first 1000 terms from T. D. Noe)
Dorin Andrica and Ovidiu Bagdasar, On some results concerning the polygonal polynomials, Carpathian Journal of Mathematics (2019) Vol. 35, No. 1, 1-11.
D. Andrica and E. J. Ionascu, On the number of polynomials with coefficients in [n], An. St. Univ. Ovidius Constanța, Vol. 22(1),2014, 13-23.
R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333-340. See Eq. 1.5.
D. Berkane, O. Bordellès, and O. Ramaré, Explicit upper bounds for the remainder term in the divisor problem, Math. Comp. 81:278 (2012), pp. 1025-1051.
Peter J. Cameron and Hamid Reza Dorbidi, Minimal cover groups, arXiv:2311.15652 [math.GR], 2023. See p. 13.
Diophante, A1712, La même parité (in French).
Xiaoxi Duan and M. W. Wong, The Dirichlet divisor problem, traces and determinants for complex powers of the twisted bi-Laplacian, J. of Math. Analysis and Applications, Volume 410, Issue 1, Feb 01 2014, Pages 151-157
L. Hoehn and J. Ridenhour, Summations involving computer-related functions, Math. Mag., 62 (1989), 191-196.
M. N. Huxley, Exponential Sums and Lattice Points III, Proc. London Math. Soc., 87 (2003), pp. 591-609.
Vaclav Kotesovec, Graph - The asymptotic ratio (1000000 terms)
Richard Sladkey, A successive approximation algorithm for computing the divisor summatory function, arXiv:1206.3369 [math.NT], 2012.
Terence Tao, Ernest Croot III, and Harald Helfgott, Deterministic methods to find primes, Math. Comp. 81 (2012), 1233-1246; also at arXiv:1009.3956 [math.NT], 2010-2012.

Right edge of A056535. Cf. A000005, A001659, A052511, A143236.
Row sums of triangle A003988, A010766 and A143724.
A061017 is an inverse.
It appears that the partial sums give A078567. - N. J. A. Sloane, Nov 24 2008
Cf. A116477, A051731, A055507, A161700, A004125, A212120, A341062.

a006218 n = sum $ map (div n) [1..n]
-- Reinhard Zumkeller, Jan 29 2011

[0] cat [&+[Floor(n/k):k in [1..n]]:n in [1..60]]; // Marius A. Burtea, Aug 25 2019

with(numtheory): A006218 := n->add(sigma[0](i), i=1..n);

Table[Sum[DivisorSigma[0, k], {k, n}], {n, 70}]
FoldList[Plus, 0, Table[DivisorSigma[0, x], {x, 61}]] //Rest (* much faster *)
Join[{0},Accumulate[DivisorSigma[0,Range[60]]]] (* Harvey P. Dale, Jan 06 2016 *)

PARI
```
a(n)=sum(k=1,n,n\k)
```

a(n)=sum(k=1,sqrtint(n),n\k)*2-sqrtint(n)^2 \\ Charles R Greathouse IV, Oct 10 2010

from sympy import integer_nthroot
def A006218(n): return 2*sum(n//k for k in range(1,integer_nthroot(n,2)[0]+1))-integer_nthroot(n,2)[0]**2 # Chai Wah Wu, Mar 29 2021

a(n) = n * ( log(n) + 2*gamma - 1 ) + O(sqrt(n)), where gamma is the Euler-Mascheroni number ~ 0.57721... (see A001620), Dirichlet, 1849. Again, a(n) = n * ( log(n) + 2*gamma - 1 ) + O(log(n)*n^(1/3)). The determination of the precise size of the error term is an unsolved problem (the so-called Dirichlet divisor problem) - see references, especially Huxley (2003).
The bounds from Chandrasekharan lead to the explicit bounds n log(n) + (2 gamma - 1) n - 4 sqrt(n) - 1 <= a(n) <= n log(n) + (2 gamma - 1) n + 4 sqrt(n). - David Applegate, Oct 14 2008
a(n) = 2*(Sum_{i=1..floor(sqrt(n))} floor(n/i)) - floor(sqrt(n))^2. - Benoit Cloitre, May 12 2002
G.f.: (1/(1-x))*Sum_{k >= 1} x^k/(1-x^k). - Benoit Cloitre, Apr 23 2003
For n > 0: A027750(a(n-1) + k) = k-divisor of n, = k <= A000005(n). - Reinhard Zumkeller, May 10 2006
a(n) = A161886(n) - n + 1 = A161886(n-1) - A049820(n) + 2 = A161886(n-1) + A000005(n) - n + 2 = A006590(n) + A000005(n) - n = A006590(n+1) - n - 1 = A006590(n) + A000005(n) - n for n >= 2. a(n) = a(n-1) + A000005(n) for n >= 1. - Jaroslav Krizek, Nov 14 2009
D(n) = Sum_{m >= 2, r >= 1} (r/m^(r+1)) * Sum_{j = 1..m - 1} * Sum_{k = 0 .. m^(r+1) - 1} exp{ 2*k*pi i(p^n + (m - j)m^r) / m^(r+1) } where p is some fixed prime number. - A. Neves, Oct 04 2010
Let E(n) = a(n) - n(log n + 2 gamma - 1). Then Berkane-Bordellès-Ramaré show that |E(n)| <= 0.961 sqrt(n), |E(n)| <= 0.397 sqrt(n) for n > 5559, and |E(n)| <= 0.764 n^(1/3) log n for x > 9994. - Charles R Greathouse IV, Jul 02 2012
a(n) = Sum_{k = 1..floor(sqrt(n))} A005408(floor((n/k) - (k-1))). - Gregory R. Bryant, Apr 20 2013
Dirichlet g.f. for s > 2: Sum_{n>=1} a(n)/n^s = Sum_{k>=1} (Zeta(s-1) - Sum_{n=1..k-1} (HurwitzZeta(s,n/k)*n/k^s))/k. - Mats Granvik, Sep 24 2017
From Ridouane Oudra, Dec 31 2022: (Start)
a(n) = n^2 - Sum_{i=1..n} Sum_{j=1..n} floor(log(i*j)/log(n+1));
a(n) = floor(sqrt(n)) + 2*Sum_{i=1..n} floor((sqrt(i^2 + 4*n) - i)/2);
a(n) = n + Sum_{i=1..n} v_2(i)*round(n/i), where v_2(i) = A007814(i). (End)

A010766 Triangle read by rows: row n gives the numbers floor(n/k), k = 1..n.

Original entry on oeis.org

1, 2, 1, 3, 1, 1, 4, 2, 1, 1, 5, 2, 1, 1, 1, 6, 3, 2, 1, 1, 1, 7, 3, 2, 1, 1, 1, 1, 8, 4, 2, 2, 1, 1, 1, 1, 9, 4, 3, 2, 1, 1, 1, 1, 1, 10, 5, 3, 2, 2, 1, 1, 1, 1, 1, 11, 5, 3, 2, 2, 1, 1, 1, 1, 1, 1, 12, 6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 13, 6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1

Offset: 1

N. J. A. Sloane

Number of times k occurs as divisor of numbers not greater than n. - Reinhard Zumkeller, Mar 19 2004
Viewed as a partition, row n is the smallest partition that contains every partition of n in the usual ordering. - Franklin T. Adams-Watters, Mar 11 2006
Row sums = A006218. - Gary W. Adamson, Oct 30 2007
A014668 = eigensequence of the triangle. A163313 = A010766 * A014668 (diagonalized) as an infinite lower triangular matrix. - Gary W. Adamson, Jul 30 2009
A018805(T(n,k)) = A242114(n,k). - Reinhard Zumkeller, May 04 2014
Viewed as partitions, all rows are self-conjugate. - Matthew Vandermast, Sep 10 2014
Row n is the partition whose Young diagram is the union of Young diagrams of all partitions of n (rewording of Franklin T. Adams-Watters's comment). - Harry Richman, Jan 13 2022

			Triangle starts:
   1:  1;
   2:  2,  1;
   3:  3,  1, 1;
   4:  4,  2, 1, 1;
   5:  5,  2, 1, 1, 1;
   6:  6,  3, 2, 1, 1, 1;
   7:  7,  3, 2, 1, 1, 1, 1;
   8:  8,  4, 2, 2, 1, 1, 1, 1;
   9:  9,  4, 3, 2, 1, 1, 1, 1, 1;
  10: 10,  5, 3, 2, 2, 1, 1, 1, 1, 1;
  11: 11,  5, 3, 2, 2, 1, 1, 1, 1, 1, 1;
  12: 12,  6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1;
  13: 13,  6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1;
  14: 14,  7, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1;
  15: 15,  7, 5, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1;
  16: 16,  8, 5, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1;
  17: 17,  8, 5, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1;
  18: 18,  9, 6, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1;
  19: 19,  9, 6, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1;
  20: 20, 10, 6, 5, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1;
  ...

Florian Cajori, A History of Mathematical Notations, Dover edition (2012), par. 407.

T. D. Noe, Rows n = 1..50 of triangle, flattened

Another version of A003988.
Finite differences of rows: A075993.
Cf. related triangles: A002260, A013942, A051731, A163313, A277646, A277647.
Cf. related sequences: A006218, A014668, A115725.
Columns of this triangle:
T(n,1) = n,
T(n,2) = A008619(n-2) for n>1,
T(n,3) = A008620(n-3) for n>2,
T(n,4) = A008621(n-4) for n>3,
T(n,5) = A002266(n) for n>4,
T(n,n) = A000012(n) = 1.
Rows of this triangle (with infinite trailing zeros):
T(1,k) = A000007(k-1),
T(2,k) = A033322(k),
T(3,k) = A278105(k),
T(4,k) = A033324(k),
T(5,k) = A033325(k),
T(6,k) = A033326(k),
T(7,k) = A033327(k),
T(8,k) = A033328(k),
T(9,k) = A033329(k),
T(10,k) = A033330(k),
...
T(99,k) = A033419(k),
T(100,k) = A033420(k),
T(1000,k) = A033421(k),
T(10^4,k) = A033422(k),
T(10^5,k) = A033427(k),
T(10^6,k) = A033426(k),
T(10^7,k) = A033425(k),
T(10^8,k) = A033424(k),
T(10^9,k) = A033423(k).

a010766 = div
a010766_row n = a010766_tabl !! (n-1)
a010766_tabl = zipWith (map . div) [1..] a002260_tabl
-- Reinhard Zumkeller, Apr 29 2015, Aug 13 2013, Apr 13 2012

seq(seq(floor(n/k),k=1..n),n=1..20); # Robert Israel, Sep 01 2014

Flatten[Table[Floor[n/k],{n,20},{k,n}]] (* Harvey P. Dale, Nov 03 2012 *)

a(n)=t=floor((-1+sqrt(1+8*(n-1)))/2);(t+1)\(n-t*(t+1)/2) \\ Edward Jiang, Sep 10 2014

T(n, k) = sum(i=1, n, (i % k) == 0); \\ Michel Marcus, Apr 08 2017

G.f.: 1/(1-x)*Sum_{k>=1} x^k/(1-y*x^k). - Vladeta Jovovic, Feb 05 2004
Triangle A010766 = A000012 * A051731 as infinite lower triangular matrices. - Gary W. Adamson, Oct 30 2007
Equals A000012 * A051731 as infinite lower triangular matrices. - Gary W. Adamson, Nov 14 2007
Let T(n,0) = n+1, then T(n,k) = (sum of the k preceding elements in the previous column) minus (sum of the k preceding elements in same column). - Mats Granvik, Gary W. Adamson, Feb 20 2010
T(n,k) = (n - A048158(n,k)) / k. - Reinhard Zumkeller, Aug 13 2013
T(n,k) = 1 + T(n-k,k) (where T(n-k,k) = 0 if n < 2*k). - Robert Israel, Sep 01 2014
T(n,k) = T(floor(n/k),1) if k>1; T(n,1) = 1 - Sum_{i=2..n} A008683(i)*T(n,i). If we modify the formula to T(n,1) = 1 - Sum_{i=2..n} A008683(i)*T(n,i)/i^s, where s is a complex variable, then the first column becomes the partial sums of the Riemann zeta function. - Mats Granvik, Apr 27 2016

Cross references edited by Jason Kimberley, Nov 23 2016

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

Original entry on oeis.org

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

N. J. A. Sloane

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

			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)

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).

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

Antidiagonal sums of array A003988. Antidiagonal sums of A004199.
Cf. A000005, A006218, A020639, A027749, A032741.
Cf. A003238, A070776, A126656, A320224, A320225, A320226.

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

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

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

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

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

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

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

More terms from David W. Wilson

A350103 Triangle read by rows. Number of self-measuring subsets of the initial segment of the natural numbers strictly below n and cardinality k. Number of subsets S of [n] with S = distset(S) and |S| = k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 4, 2, 1, 1, 1, 1, 5, 2, 1, 1, 1, 1, 1, 6, 3, 2, 1, 1, 1, 1, 1, 7, 3, 2, 1, 1, 1, 1, 1, 1, 8, 4, 2, 2, 1, 1, 1, 1, 1, 1, 9, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 10, 5, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 11, 5, 3, 2, 2, 1, 1, 1, 1, 1, 1

Offset: 0

Peter Luschny, Dec 14 2021

We use the notation [n] = {0, 1, ..., n-1}. If S is a subset of [n] then we define the distset of S (set of distances of S) as {|x - y|: x, y in S}. We call a subset S of the natural numbers self-measuring if and only if S = distset(S).

			Triangle starts:
[ 0] [1]
[ 1] [1, 1]
[ 2] [1, 1,  1]
[ 3] [1, 1,  2, 1]
[ 4] [1, 1,  3, 1, 1]
[ 5] [1, 1,  4, 2, 1, 1]
[ 6] [1, 1,  5, 2, 1, 1, 1]
[ 7] [1, 1,  6, 3, 2, 1, 1, 1]
[ 8] [1, 1,  7, 3, 2, 1, 1, 1, 1]
[ 9] [1, 1,  8, 4, 2, 2, 1, 1, 1, 1]
[10] [1, 1,  9, 4, 3, 2, 1, 1, 1, 1, 1]
[11] [1, 1, 10, 5, 3, 2, 2, 1, 1, 1, 1, 1]
[12] [1, 1, 11, 5, 3, 2, 2, 1, 1, 1, 1, 1, 1]
.
The first  column is 1,1,...  because {} = distset({}) and |{}| = 0.
The second column is 1,1,... because {0} = distset({0}) and |{0}| = 1.
The third  column is n-1  because {0, j} = distset({0, j}) and |{0, j}| = 2 for j = 1..n - 1.
The main diagonal is 1,1,... because [n] = distset([n]) and |[n]| = n (these are the complete rulers A103295).

Winston de Greef, Table of n, a(n) of the first 150 rows, flattened (n = 0..11324)
Peter Luschny, Illustrating self-measuring subsets of {0, 1, 2, 3}.

Cf. A350102 (row sums), A349976, A103295, A003988, A010766, A123706.

T := (n, k) -> ifelse(k < 2, 1, floor((n - 1) / (k - 1))):
seq(print(seq(T(n, k), k = 0..n)), n = 0..12);

distSet[s_] := Union[Map[Abs[Differences[#][[1]]] &, Union[Sort /@ Tuples[s, 2]]]]; T[n_, k_] := Count[Subsets[Range[0, n - 1]], ?((ds = distSet[#]) == # && Length[ds] == k &)]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* _Amiram Eldar, Dec 16 2021 *)

T(n, k) = if(k<=1, 1, (n - 1) \ (k - 1)) \\ Winston de Greef, Jan 31 2024

# generating and counting (slow)
def isSelfMeasuring(R):
    S, L = Set([]), len(R)
    R = Set([r - 1 for r in R])
    for i in range(L):
        for j in (0..i):
            S = S.union(Set([abs(R[i] - R[i - j])]))
    return R == S
def A349976row(n):
    counter = [0] * (n + 1)
    for S in Subsets(n):
        if isSelfMeasuring(S): counter[len(S)] += 1
    return counter
for n in range(10): print(A349976row(n))

T(n, k) = floor((n - 1) / (k - 1)) for k >= 2.

T(n, k) = 1 if k = 0 or k = 1 or n >= k >= floor((n + 1)/2).

cp's OEIS Frontend

A372523 Triangle read by rows: T(n, k) is equal to n/k if k | n, else to the concatenation of A003988(n, k) = floor(n/k) and A051127(k, n) = n mod k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A380390 Array read by ascending antidiagonals: A(n, k) is equal to n/k if k | n, else to the concatenation of A003988(n, k) = floor(n/k) and A380389(n - k*floor(n/k), k).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A006218 a(n) = Sum_{k=1..n} floor(n/k); also Sum_{k=1..n} d(k), where d = number of divisors (A000005); also number of solutions to x*y = z with 1 <= x,y,z <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A010766 Triangle read by rows: row n gives the numbers floor(n/k), k = 1..n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A350103 Triangle read by rows. Number of self-measuring subsets of the initial segment of the natural numbers strictly below n and cardinality k. Number of subsets S of [n] with S = distset(S) and |S| = k.

Views

Author

Keywords

Comments

Examples

Links