cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-5 of 5 results.

A143724 Triangle read by rows, inverse Möbius transform of a diagonalized matrix of A116477.

Original entry on oeis.org

1, 1, 2, 1, 0, 4, 1, 2, 0, 5, 1, 0, 0, 0, 9, 1, 2, 4, 0, 0, 7, 1, 0, 0, 0, 0, 0, 15, 1, 2, 0, 5, 0, 0, 0, 12, 1, 0, 4, 0, 0, 0, 0, 0, 18, 1, 2, 0, 0, 9, 0, 0, 0, 0, 15, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 28, 1, 2, 4, 5, 0, 7, 0, 0, 0, 0, 0, 16
Offset: 1

Views

Author

Gary W. Adamson, Aug 29 2008

Keywords

Comments

For n-th row of the triangle, the inverse Möbius transform extracts A116477(k) such that k divides n; 0 otherwise.
Row sums = A006218: (1, 3, 5, 8, 10, 14, 16, ...).

Examples

			First few rows of the triangle:
1;
1, 2;
1, 0, 4;
1, 2, 0, 5;
1, 0, 0, 0, 9;
1, 2, 4, 0, 0, 7;
1, 0, 0, 0, 0, 0, 15;
1, 2, 0, 5, 0, 0,  0, 12;
...
Example: The divisors of 8 are (1, 2, 4, 8) so row 8 = (1, 2, 0, 5, 0, 0, 0, 12).

Crossrefs

Cf. A006218, A051731, A116477.

Formula

Triangle read by rows, A051731 * (A116477 * 0^(n-k)); 1 <= k <= n.

Extensions

Diagonal sequence corrected to A116477 by Georg Fischer, Jun 27 2023

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.

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

Comments

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

Examples

			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.

References

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

Links

Crossrefs

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.

Programs

  • Haskell
    a006218 n = sum $ map (div n) [1..n]
-- Reinhard Zumkeller, Jan 29 2011
  • Magma
    [0] cat [&+[Floor(n/k):k in [1..n]]:n in [1..60]]; // Marius A. Burtea, Aug 25 2019
  • Maple
    with(numtheory): A006218 := n->add(sigma[0](i), i=1..n);
  • Mathematica
    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)
  • PARI
    a(n)=sum(k=1,sqrtint(n),n\k)*2-sqrtint(n)^2 \\ Charles R Greathouse IV, Oct 10 2010
  • Python
    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

Formula

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)

A122191 Triangle read by rows: T(n,m) = number of positive divisors of m that are coprime to n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 3, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 3, 2, 4, 1, 1, 1, 2, 1, 2, 2, 2, 1, 1, 2, 1, 3, 2, 2, 2, 4, 1, 1, 1, 2, 1, 1, 2, 2, 1, 3, 1, 1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 1, 1, 1, 2, 1, 2, 2, 1, 1, 3, 2, 2, 2, 2, 1
Offset: 1

Views

Author

Leroy Quet, Aug 24 2006

Keywords

Crossrefs

Cf. A116477.

Programs

  • Mathematica
    Flatten@Table[ Count[GCD[Divisors[m], n], 1], {n, 14}, {m, n}] (* Ray Chandler, Aug 29 2006 *)
  • PARI
    A122191(n,m) = {local(s);s=0;fordiv(m,d,s=s+(gcd(d,n)==1));s} \\ Michael B. Porter, Mar 01 2010

Extensions

Extended by Ray Chandler, Aug 29 2006

A332683 a(n) = Sum_{k=1..n, gcd(n, k) = 1} ceiling(n/k).

Original entry on oeis.org

1, 2, 5, 6, 12, 8, 20, 15, 23, 18, 37, 19, 47, 28, 38, 37, 66, 31, 76, 41, 61, 52, 96, 44, 96, 63, 89, 66, 129, 49, 141, 84, 109, 88, 129, 72, 176, 101, 132, 95, 198, 77, 210, 116, 142, 129, 232, 99, 226, 122, 186, 144, 269, 114, 232, 149, 214, 169, 305, 110
Offset: 1

Views

Author

Ilya Gutkovskiy, Feb 19 2020

Keywords

Comments

Moebius transform of A006590.

Crossrefs

Cf. A006590, A008683, A116477, A332682.

Programs

  • Mathematica
    Table[Sum[Boole[GCD[n, k] == 1] Ceiling[n/k], {k, 1, n}], {n, 1, 60}]
  • PARI
    a(n) = sum(k=1, n, if (gcd(n, k) == 1, ceil(n/k))); \\ Michel Marcus, Feb 21 2020

Formula

a(n) = Sum_{d|n} mu(n/d) * A006590(d).

A332684 a(n) = Sum_{k=1..n} mu(gcd(n, k)) * floor(n/k).

Original entry on oeis.org

1, 1, 3, 3, 8, 2, 14, 7, 14, 5, 27, 6, 35, 7, 19, 18, 50, 5, 58, 16, 32, 14, 74, 14, 68, 15, 54, 29, 101, 3, 111, 39, 59, 21, 83, 26, 140, 24, 70, 39, 158, 6, 168, 51, 74, 32, 186, 29, 170, 20, 101, 66, 217, 17, 157, 64, 117, 39, 247, 28, 261, 39, 121, 92, 194
Offset: 1

Views

Author

Ilya Gutkovskiy, Feb 19 2020

Keywords

Comments

Moebius transform of A116477.
Moebius transform applied twice to A006218.

Crossrefs

Cf. A006218, A007427, A008683, A116477.

Programs

  • Mathematica
    Table[Sum[MoebiusMu[GCD[n, k]] Floor[n/k], {k, 1, n}], {n, 1, 65}]
A007427[n_] := Sum[MoebiusMu[n/d] MoebiusMu[d], {d, Divisors[n]}]; A006218[n_] := Sum[DivisorSigma[0, k], {k, 1, n}]; Table[Sum[A007427[n/d] A006218[d], {d, Divisors[n]}], {n, 1, 65}]
  • PARI
    a(n) = sum(k=1, n, moebius(gcd(n, k))*(n\k)); \\ Michel Marcus, Feb 21 2020

Formula

a(n) = Sum_{d|n} mu(n/d) * A116477(d).
a(n) = Sum_{d|n} A007427(n/d) * A006218(d).
Showing 1-5 of 5 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.