A006590 -id:A006590 - 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)

A049820 a(n) = n - d(n), where d(n) is the number of divisors of n (A000005).

Original entry on oeis.org

0, 0, 1, 1, 3, 2, 5, 4, 6, 6, 9, 6, 11, 10, 11, 11, 15, 12, 17, 14, 17, 18, 21, 16, 22, 22, 23, 22, 27, 22, 29, 26, 29, 30, 31, 27, 35, 34, 35, 32, 39, 34, 41, 38, 39, 42, 45, 38, 46, 44, 47, 46, 51, 46, 51, 48, 53, 54, 57, 48, 59, 58, 57, 57, 61, 58, 65

Offset: 1

Clark Kimberling

a(n) is the number of non-divisors of n in 1..n. - Jaroslav Krizek, Nov 14 2009
Also equal to the number of partitions p of n such that max(p)-min(p) = 1. The number of partitions of n with max(p)-min(p) <= 1 is n; there is one with k parts for each 1 <= k <= n. max(p)-min(p) = 0 iff k divides n, leaving n-d(n) with a difference of 1. It is easiest to see this by looking at fixed k with increasing n: for k=3, starting with n=3 the partitions are [1,1,1], [2,1,1], [2,2,1], [2,2,2], [3,2,2], etc. - Giovanni Resta, Feb 06 2006 and Franklin T. Adams-Watters, Jan 30 2011
Number of positive numbers in n-th row of array T given by A049816.
Number of proper non-divisors of n. - Omar E. Pol, May 25 2010
a(n+2) is the sum of the n-th antidiagonal of A225145. - Richard R. Forberg, May 02 2013
For n > 2, number of nonzero terms in n-th row of triangle A051778. - Reinhard Zumkeller, Dec 03 2014
Number of partitions of n of the form [j,j,...,j,i] (j > i). Example: a(7)=5 because we have [6,1], [5,2], [4,3], [3,3,1], and [2,2,2,1]. - Emeric Deutsch, Sep 22 2016

			a(7) = 5; the 5 non-divisors of 7 in 1..7 are 2, 3, 4, 5, and 6.
The 5 partitions of 7 with max(p) - min(p) = 1 are [4,3], [3,2,2], [2,2,2,1], [2,2,1,1,1] and [2,1,1,1,1,1]. - _Emeric Deutsch_, Mar 01 2006

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
G. E. Andrews, M. Beck, N. Robbins, Partitions with fixed differences between largest and smallest parts, arXiv preprint arXiv:1406.3374 [math.NT], 2014-2015.

Cf. A000005.
One less than A062968, two less than A059292.
Cf. A161664 (partial sums).
Cf. A060990 (number of solutions to a(x) = n).
Cf. A045765 (numbers not occurring in this sequence).
Cf. A236561 (same sequence sorted into ascending order), A236562 (with also duplicates removed), A236565, A262901 and A262903.
Cf. A262511 (numbers that occur only once).
Cf. A055927 (positions of repeated terms).
Cf. A245388 (positions of squares).
Cf. A155043 (number of steps needed to reach zero when iterating a(n)), A262680 (number of nonzero squares encountered).
Cf. A259934 (an infinite trunk of the tree defined by edge-relation a(child) = parent, conjectured to be unique).
Cf. tables and arrays A047916, A051731, A051778, A173540, A173541.
Cf. also arrays A225145, A262898, A263255 and tables A263265, A263267.
Other related sequences: A006218, A006590, A051953, A070824, A094181, A062249, A067391, A076627, A128508, A131187, A134156, A140826, A161886, A177235, A177236, A227874, A228453, A230653, A230654, A231167, A245197, A253473.

List([1..80],n->n-Tau(n)); # Muniru A Asiru, Sep 28 2018

a049820 n = n - a000005 n  -- Reinhard Zumkeller, Feb 06 2012

A049820 := n->n-numtheory[tau](n):
seq(A049820(n), n=1..100);

Table[n - DivisorSigma[0, n], {n, 100}] (* Wesley Ivan Hurt, Nov 19 2014 *)
Array[(# - DivisorSigma[0, #])&, 70] (* Vincenzo Librandi, Dec 29 2015 *)

PARI
```
a(n)=n-numdiv(n)
```

(define (A049820 n) (- n (A000005 n))) ;; Antti Karttunen, Nov 27 2015

a(n) = Sum_{k=1..n} ceiling(n/k)-floor(n/k). - Benoit Cloitre, May 11 2003
G.f.: Sum_{k>0} x^(2*k+1)/(1-x^k)/(1-x^(k+1)). - Emeric Deutsch, Mar 01 2006
a(n) = A006590(n) - A006218(n) = A161886(n) - A000005(n) - A006218(n) + 1 for n >= 1. - Jaroslav Krizek, Nov 14 2009
a(n) = Sum_{k=1..n} A000007(A051731(n,k)). - Reinhard Zumkeller, Mar 09 2010
a(n) = A076627(n) / A000005(n). - Reinhard Zumkeller, Feb 06 2012
For n >= 2, a(n) = A094181(n) / A051953(n). - Antti Karttunen, Nov 27 2015
a(n) = Sum_{k=1..n} ((n mod k) + (-n mod k))/k. - Wesley Ivan Hurt, Dec 28 2015
G.f.: Sum_{j>=2} (x^(j+1)*(1-x^(j-1))/(1-x^j))/(1-x). - Emeric Deutsch, Sep 22 2016
Dirichlet g.f.: zeta(s-1)- zeta(s)^2. - Ilya Gutkovskiy, Apr 12 2017
a(n) = Sum_{i=1..n-1} sign(i mod n-i). - Wesley Ivan Hurt, Sep 27 2018

Edited by Franklin T. Adams-Watters, Jan 30 2012

A027052 Triangular array T read by rows: T(n,0) = T(n,2n) = 1 for n >= 0, T(n,1)=0 for n >= 1, T(n,2)=1 for n >= 2 and for n >= 3, T(n,k) = T(n-1,k-3) + T(n-1, k-2) + T(n-1,k-1) for 3 <= k <= 2n-1. T(n,k)=0 for k < 0 or k > 2n.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 1, 0, 1, 2, 3, 4, 1, 1, 0, 1, 2, 3, 6, 9, 8, 1, 1, 0, 1, 2, 3, 6, 11, 18, 23, 18, 1, 1, 0, 1, 2, 3, 6, 11, 20, 35, 52, 59, 42, 1, 1, 0, 1, 2, 3, 6, 11, 20, 37, 66, 107, 146, 153, 102, 1, 1, 0, 1, 2, 3, 6, 11, 20, 37, 68, 123, 210, 319, 406, 401, 256, 1

Offset: 0

Clark Kimberling

The following sequences all have the same parity: A004737, A006590, A027052, A071028, A071797, A078358, A078446. - Jeremy Gardiner, Mar 16 2003

			Triangle T(n,k) for 0 <= k <= 2n:
  1;
  1, 0, 1;
  1, 0, 1, 2, 1;
  1, 0, 1, 2, 3, 4, 1;
  1, 0, 1, 2, 3, 6, 9, 8, 1;

G. C. Greubel, Rows n = 0..50 of triangle, flattened

Cf. A001590, a tribonacci sequence.
Cf. A160999 (row sums), A005408 (row lengths).
Diagonals T(n, n+c): A027053 (c=2), A027054 (c=3), A027055 (c=4).
Diagonals T(n, 2n-c): A027056 (c=1), A027058 (c=2), A027059 (c=3), A027060 (c=4), A027061(c=5), A027062 (c=6), A027063 (c=7), A027064 (c=8), A027065 (c=9), A027066 (c=10).
Sums involving this array: A027067, A027068, A027069, A027070, A027072, A027073, A027074, A027075, A027076, A027077,A027078, A027079, A027080, A027081.
Other related sequences: A027057, A027071.
Other arrays of this type: A027023, A027082, A027113.

T:= function(n,k)
    if k=0 or k=2 or k=2*n then return 1;
    elif k=1 then return 0;
    else return Sum([1..3], j-> T(n-1, k-j) );
    fi;
  end;
Flat(List([0..10], n-> List([0..2*n], k-> T(n,k) ))); # G. C. Greubel, Nov 05 2019

T:= proc(n, k) option remember;
      if k=0 or k=2 or k=2*n then 1
    elif k=1 then 0
    else add(T(n-1, k-j), j=1..3)
      fi
    end:
seq(seq(T(n, k), k=0..2*n), n=0..10); # G. C. Greubel, Nov 05 2019

T[n_, k_]:= T[n, k]= If[k==0 || k==2 || k==2*n, 1, If[k==1, 0, Sum[T[n-1, k-j], {j, 3}]]]; Table[T[n, k], {n, 0, 12}, {k, 0, 2*n}]//Flatten (* G. C. Greubel, Nov 05 2019 *)

{T(n, k) = if(k==0 || k==2 || k==2*n, 1, if(k==1, 0, sum(j=1,3, T(n-1, k-j)) ))};
for(n=0, 10, for(k=0,2*n, print1(T(n,k), ", "))) \\ G. C. Greubel, Nov 05 2019

@CachedFunction
def T(n, k):
    if (k==0 or k==2 or k==2*n): return 1
    elif (k==1): return 0
    else: return sum(T(n-1, k-j) for j in (1..3))
[[T(n, k) for k in (0..2*n)] for n in (0..10)] # G. C. Greubel, Nov 05 2019

A001590(k+1) = T(n,k) if 0 <= k <= n. - Michael Somos, Jun 01 2014

Offset and keyword:tabl corrected by R. J. Mathar, Jun 01 2009

A004737 Concatenation of sequences (1,2,...,n-1,n,n-1,...,1) for n >= 1.

Original entry on oeis.org

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

Offset: 1

R. Muller

The following sequences all have the same parity: A004737, A006590, A027052, A071028, A071797, A078358, A078446. - Jeremy Gardiner, Mar 16 2003
The ordinal transform of a sequence b_0, b_1, b_2, ... is the sequence a_0, a_1, a_2, ... where a_n is the number of times b_n has occurred in {b_0 ... b_n}.
From Artur Jasinski, Mar 07 2010: (Start)
This sequence is the even subset of A003983 for odd p=2,4,6,8,....
For the odd subset of A003983 see A004739. (End)
From Gary W. Adamson, Mar 30 2010: (Start)
Given the triangle rows: (1; 1,2,1; 1,2,3,2,1; ...) as polcoeff with offset 0:
q = (1 + 2x + x^2), r = (1 + 2x + 3x^2 + 2x^3 +x^4), etc.; then
(1 + 2x + 3x^2 + ...) = q(x) * q(x^2) * q(x^4) * q(x^8) * ...
..................... = r(x) * r(x^3) * r(x^9) * r(x^27) * ...
..................... = s(x) * s(x^4) * s(x^16)* s(x^64) * ...
... (End)
From L. Edson Jeffery, Jan 13 2012: (Start)
Let U_1(t)=1, U_2(t)=2*t, and U_r(t)=2*t*U_(r-1)(t)-U(r-2)(t), r>2, be Chebyshev polynomials of the second kind. For q>1 an integer, let N=2*q and x_k=cos((2*k-1)*Pi/N), and define the ordered column vectors V_k=[U_k(x_1), U_k(x_2), ..., U_k(x_q)]^T, k=1,...,q, where A^T denotes the transpose of matrix A. Let E_N=[V_1, V_2, ..., V_q] be the q X q matrix formed from the ordered components of the V_k. E_N contains the joint spectra of the Danzer basis (see [Jeffery]) associated with N. Let M_N=(1/q)*[E_N]^T*E_N. For the trivial case q=1, let M_2=[1]. CONJECTURE: E_N and M_N are always integral and symmetric, with M_N having diagonal entries {1,2,...} beginning at entries 1,j (j odd) in the first row and i,1 (i odd) in the first column and with zeros elsewhere. If N is allowed to increase without bound, and assuming the conjecture is true, then triangle A004737 emerges in its entirety from the successive antidiagonals containing those entries [M_N]_(i,j) such that i+j=2*v, for each v in {1,2,...,floor((q+1)/2)}. For example, for N=18 and q=9 (omitting the zeros for clarity),
M_18=[
  (1   1   1   1   1);
  (  2   2   2   2  );
  (1   3   3   3   3);
  (  2   4   4   4  );
  (1   3   5   5   5);
  (  2   4   6   6  );
  (1   3   5   7   7);
  (  2   4   6   8  );
  (1   3   5   7   9)],
from which the first five rows of the sequence can be read off in succession. (End)
T(n,k) =  min(n,k). The order of the list T(n,k) is by sides of squares from T(1,n) to T(n,n), then from T(n,n) to T(n,1). - Boris Putievskiy, Jan 13 2013
Expanded form of T(2,k) k=0,1,...,2m for ascending m-nomial triangles. - Bob Selcoe, Feb 07 2014
Terms in the first nine rows of the triangle can be duplicated by performing (111...)^2 with <= nine ones. By way of example, (11111)^2 = 123454321. - Gary W. Adamson, Mar 27 2015

			From _Boris Putievskiy_, Jan 13 2013: (Start)
The start of the sequence as a table:
  1 1 1 1 1 1 ...
  1 2 2 2 2 2 ...
  1 2 3 3 3 3 ...
  1 2 3 4 4 4 ...
  1 2 3 4 5 5 ...
  1 2 3 4 5 6 ...
  ...
The start of the sequence as an irregular triangle array read by rows:
  1;
  1,2,1;
  1,2,3,2,1;
  1,2,3,4,3,2,1;
  1,2,3,4,5,4,3,2,1;
  1,2,3,4,5,6,5,4,3,2,1;
  ...
Row number k contains 2*k-1 numbers: 1,2,...,k-1,k,k-1,...,1. (End)
The sequence of fractions A196199/A004737 = 0/1, -1/1, 0/2, 1/1, -2/1, -1/2, 0/3, 1/2, 2/1, -3/1, -2/2, -1/3, 0/4, 1/3, 2/2, 3/1, -4/4. -3/2, ... contains every rational number (infinitely often) [Laczkovich]. - _N. J. A. Sloane_, Oct 09 2013

Miklós Laczkovich, Conjecture and Proof, TypoTex, Budapest, 1998. See Chapter 10.
F. Smarandache, "Numerical Sequences", University of Craiova, 1975.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Jerry Brown et al., Problem 4619, School Science and Mathematics, USA, Vol. 97 (4), 1997, pp. 221-222.
L. E. Jeffery, Danzer matrices (definitions)
Boris Putievskiy, Transformations [of] Integer Sequences And Pairing Functions arXiv:1212.2732 [math.CO], 2012.
F. Smarandache, Collected Papers, Vol. II, Tempus Publ. Hse., Bucharest, 1996.
F. Smarandache, Sequences of Numbers Involved in Unsolved Problems, Hexis, Phoenix, 2006.
Eric Weisstein's World of Mathematics, Smarandache Sequences.

Cf. A004738, A008967, A003983, A196199.

Cf. A242357, A000290 (row sums).

import Data.List (inits)
a004737 n = a004737_list !! (n-1)
a004737_list = concatMap f $ tail $ inits [1..]
   where f xs = xs ++ tail (reverse xs)
-- Reinhard Zumkeller, May 11 2014, Mar 26 2011

Table[Min[n - #^2, (# + 1)^2 - n + 1] &@ Floor[Sqrt[n - 1]], {n, 105}] (* or *)
Table[Floor@ # - Abs[n - Floor[#]^2 - Floor@ # - 1] + 1 &@ Sqrt[n - 1], {n, 105}] (* Michael De Vlieger, Oct 21 2016 *)
Table[Join[Range[n],Range[n-1,1,-1]],{n,20}]//Flatten (* Harvey P. Dale, Dec 27 2019 *)

a(n) = n--;my(m=sqrtint(n));m+1-abs(n-m^2-m) \\ David A. Corneth, Oct 18 2016

a(A002061(n)) = n; a(A000290(n)) = a(A002522(n)) = 1. - Reinhard Zumkeller, Mar 10 2006
a(n) = if n<3 then 1 else (if a(n-1)=1 then 1 + 0^(a(n-2)-1) else a(n-1) - 0^X + (a(n-1)-a(n-2))*(1 - 0^X)), where X = A003059(n-1)-a(n-1). - Reinhard Zumkeller, Mar 10 2006
Let b(n) = floor(sqrt(n-1)). Then a(n) = min(n - b(n)^2, (b(n)+1)^2 - n + 1). - Franklin T. Adams-Watters, Jun 09 2006
Ordinal transform of A004741. - Franklin T. Adams-Watters, Aug 28 2006
If the sequence is read as a triangular array, beginning [1]; [1,2,1]; [1,2,3,2,1]; ..., then the o.g.f. is (1+qx)/((1-x)(1-qx)(1-q^2x)) = 1 + x(1 + 2q + q^2) + x^2(1 + 2q + 3q^2 + 2q^3 +q^4) + .... The row polynomials for this triangle are (1 + q + ... + q^n)^2 =[n,2]A008967).%20-%20_Peter%20Bala">q + q[n-1,2]_q, where [n,2]_q are Gaussian polynomials (see A008967). - _Peter Bala, Sep 23 2007
a(n) = floor(sqrt(n-1)) - |n - floor(sqrt(n-1))^2 - floor(sqrt(n-1)) - 1| + 1. - Boris Putievskiy, Jan 13 2013
Read as a triangular array, then T(n,k) = n - |n-k-1|; T(n,0) = 1; T(n,n-1) = n. - Juan Pablo Herrera P., Oct 17 2016

More terms from Patrick De Geest, Jun 15 1998

A071797 Restart counting after each new odd integer (a fractal sequence).

Original entry on oeis.org

1, 1, 2, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11

Offset: 1

Antonio Esposito, Jun 06 2002

The following sequences all have the same parity: A004737, A006590, A027052, A071028, A071797, A078358, A078446.
This is also a triangle read by rows in which row n lists the first 2*n-1 positive integers, n >= 1 (see example). - Omar E. Pol, May 29 2012
a(n) mod 2 = A071028(n). - Boris Putievskiy, Jul 24 2013
The triangle in the example is the triangle used by Kircheri in 1664. See the link "Mundus Subterraneus". - Charles Kusniec, Sep 11 2022

			a(1)=1; a(9)=5; a(10)=1;
From _Omar E. Pol_, May 29 2012: (Start)
Written as a triangle the sequence begins:
  1;
  1, 2, 3;
  1, 2, 3, 4, 5;
  1, 2, 3, 4, 5, 6, 7;
  1, 2, 3, 4, 5, 6, 7, 8, 9;
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11;
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13;
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15;
Row n has length 2*n - 1 = A005408(n-1). (End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Glen Joyce C. Dulatre, Jamilah V. Alarcon, Vhenedict M. Florida, Daisy Ann A. Disu, On Fractal Sequences, DMMMSU-CAS Science Monitor (2016-2017) Vol. 15 No. 2, 109-113.
C. Kimberling, Numeration systems and fractal sequences, Acta Arithmetica 73 (1995) 103-117.
Athanasii Kircheri, Mundus Subterraneus, (1664), pg. 24.
F. Smarandache, Only Problems, Not Solutions!, Phoenix,AZ: Xiquan,1993.
Michael Somos, Sequences used for indexing triangular or square arrays

Cf. A002260, A004737, A006590, A027052, A071028, A078358, A078446.
Cf. A074294.
Row sums give positive terms of A000384.

import Data.List (inits)
a071797 n = a071797_list !! (n-1)
a071797_list = f $ tail $ inits [1..] where
   f (xs:_:xss) = xs ++ f xss
-- Reinhard Zumkeller, Apr 14 2014

A071797 := proc(n)
    n-A048760(n-1) ;
end proc: # R. J. Mathar, May 29 2016

Array[Range[2# - 1]&, 10] // Flatten (* Jean-François Alcover, Jan 30 2018 *)

PARI
```
a(n)=if(n<1,0,n-sqrtint(n-1)^2)
```

a(n) = 1 + A053186(n-1).
a(n) = n - 1 - ceiling(sqrt(n))*(ceiling(sqrt(n))-2); n > 0.
a(n) = n - floor(sqrt(n-1))^2, distance between n and the next smaller square. - Marc LeBrun, Jan 14 2004

A078358 Non-oblong numbers: Complement of A002378.

Original entry on oeis.org

1, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 73, 74

Offset: 1

Wolfdieter Lang, Nov 29 2002

The (primitive) period length k(n)=A077427(n) of the (regular) continued fraction of (sqrt(4*a(n)+1)+1)/2 determines whether or not the Diophantine equation (2*x-y)^2 - (1+4*a(n))*y^2 = +4 or -4 is solvable and the approximants of this continued fraction give all solutions. See A077057.
The following sequences all have the same parity: A004737, A006590, A027052, A071028, A071797, A078358, A078446. - Jeremy Gardiner, Mar 16 2003
Infinite series 1/A078358(n) is divergent. Proof: Harmonic series 1/A000027(n) is divergent and can be distributed on two subseries 1/A002378(k+1) and 1/A078358(m). The infinite subseries 1/A002378(k+1) is convergent to 1, so Sum_{n>=1} 1/A078358(n) is divergent. - Artur Jasinski, Sep 28 2008

O. Perron, "Die Lehre von den Kettenbruechen, Bd.I", Teubner, 1954, 1957 (Sec. 30, Satz 3.35, p. 109 and table p. 108).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Oskar Perron, Die Lehre von den Kettenbrüchen, Teubner, Leipzig, 1913.

a(n)=(A077425(n)-1)/4.

Cf. A049068 (subsequence), A144786.

a078358 n = a078358_list !! (n-1)
a078358_list = filter ((== 0) . a005369) [0..]
-- Reinhard Zumkeller, Jul 04 2014, May 08 2012

Complement[Range[930], Table[n (n + 1), {n, 0, 30}]] (* and *) Table[Ceiling[Sqrt[n]] + n - 1, {n, 900}] (* Vladimir Joseph Stephan Orlovsky, Jul 20 2011 *)

a(n)=sqrtint(n-1)+n \\ Charles R Greathouse IV, Jan 17 2013

from operator import sub
from sympy import integer_nthroot
def A078358(n): return n+sub(*integer_nthroot(n,2)) # Chai Wah Wu, Oct 01 2024

4*a(n)+1 is not a square number.
a(n) = ceiling(sqrt(n)) + n -1. - Leroy Quet, Jul 06 2007
A005369(a(n)) = 0. - Reinhard Zumkeller, Jul 05 2014

A071028 Triangle read by rows giving successive states of cellular automaton generated by "Rule 50".

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0

Offset: 0

Hans Havermann, May 26 2002

Row n has length 2n+1.
Rules #50, #58, #114, #122, #178, #179, #186, #242, #250 all give rise to this sequence.
The following sequences all have the same parity: A004737, A006590, A027052, A071028, A071797, A078358, A078446. - Jeremy Gardiner, Mar 16 2003

			Triangle begins:
1;
1, 0, 1;
1, 0, 1, 0, 1;
1, 0, 1, 0, 1, 0, 1;
1, 0, 1, 0, 1, 0, 1, 0, 1;
1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1;
1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1;
1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1;
1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1;
1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1;
1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1;
- _Philippe Deléham_, Mar 23 2014

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; Chapter 3.

Robert Price, Table of n, a(n) for n = 0..9999
C. J. Glasby, S. P. Glasby, and F. Pleijel, Worms by number, Proc. Roy. Soc. B, Proc. Biol. Sci. 275 (1647) (2008) 2071-2076.
Eric Weisstein's World of Mathematics, Rule 250
Michael Williams, Collatz conjecture: an order isomorphic recursive machine, ResearchGate (2024). See pp. 8, 13.
S. Wolfram, A New Kind of Science
Index to Elementary Cellular Automata
Index entries for sequences related to cellular automata

Cf. A071797.

rows = 10; ca = CellularAutomaton[50, {{1}, 0}, rows-1]; Flatten[ Table[ca[[k, rows-k+1 ;; rows+k-1]], {k, 1, rows}]] (* Jean-François Alcover, May 24 2012 *)

a(n) = n - 1 + floor(sqrt(n)) - 2*Sum_{k=1..n-1} a(k) for n >= 1. - Benoit Cloitre, Jan 24 2013
a(n) = A071797(n) (mod 2). - Boris Putievskiy, Jul 24 2013
a(n) = (1+(-1)^(Sum_{k=1..floor(n/2)} floor((n-k)/k)))/2. - Wesley Ivan Hurt, Dec 25 2020

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A049820 a(n) = n - d(n), where d(n) is the number of divisors of n (A000005).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Haskell

Maple

Mathematica

PARI

Scheme

Formula

Extensions

A027052 Triangular array T read by rows: T(n,0) = T(n,2n) = 1 for n >= 0, T(n,1)=0 for n >= 1, T(n,2)=1 for n >= 2 and for n >= 3, T(n,k) = T(n-1,k-3) + T(n-1, k-2) + T(n-1,k-1) for 3 <= k <= 2n-1. T(n,k)=0 for k < 0 or k > 2n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Sage

Formula

Extensions

A004737 Concatenation of sequences (1,2,...,n-1,n,n-1,...,1) for n >= 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A071797 Restart counting after each new odd integer (a fractal sequence).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI