A002024 k appears k times; a(n) = floor(sqrt(2n) + 1/2). (Formerly M0250 N0089)

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

Offset

1,2

Comments

Integer inverse function of the triangular numbers A000217. The function trinv(n) = floor((1+sqrt(1+8n))/2), n >= 0, gives the values 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, ..., that is, the same sequence with offset 0. - N. J. A. Sloane, Jun 21 2009

Array T(k,n) = n+k-1 read by antidiagonals.

Eigensequence of the triangle = A001563. - Gary W. Adamson, Dec 29 2008

Can apparently also be defined via a(n+1)=b(n) for n >= 2 where b(0)=b(1)=1 and b(n) = b(n-b(n-2))+1. Tested to be correct for all n <= 150000. - José María Grau Ribas, Jun 10 2011

For any n >= 0, a(n+1) is the least integer m such that A000217(m)=m(m+1)/2 is larger than n. This is useful when enumerating representations of n as difference of triangular numbers; see also A234813. - M. F. Hasler, Apr 19 2014

Number of binary digits of A023758, i.e., a(n) = ceiling(log_2(A023758(n+2))). - Andres Cicuttin, Apr 29 2016

a(n) and A002260(n) give respectively the x(n) and y(n) coordinates of the sorted sequence of points in the integer lattice such that x(n) > 0, 0 < y(n) <= x(n), and min(x(n), y(n)) < max(x(n+1), y(n+1)) for n > 0. - Andres Cicuttin, Dec 25 2016

Partial sums (A060432) are given by S(n) = (-a(n)^3 + a(n)*(1+6n))/6. - Daniel Cieslinski, Oct 23 2017

As an array, T(k,n) is the number of digits columns used in carryless multiplication between a k-digit number and an n-digit number. - Stefano Spezia, Sep 24 2022

a(n) is the maximum number of possible solutions to an n-statement Knights and Knaves Puzzle, where each statement is of the form "x of us are knights" for some 1 <= x <= n, knights can only tell the truth and knaves can only lie. - Taisha Charles and Brittany Ohlinger, Jul 29 2023

References

Edward S. Barbeau, Murray S. Klamkin, and William O. J. Moser, Five Hundred Mathematical Challenges, Prob. 441, pp. 41, 194. MAA 1995.

R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 97.

K. Hardy and K. S. Williams, The Green Book of Mathematical Problems, p. 59, Solution to Prob. 14, Dover NY, 1985

R. Honsberger, Mathematical Morsels, pp. 133-134, MAA 1978.

J. F. Hurley, Litton's Problematical Recreations, pp. 152; 313-4 Prob. 22, VNR Co., NY, 1971.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, p. 43.

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

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 129.

Links

Franklin T. Adams-Watters, Table of n, a(n) for n = 1..5050

Jaegug Bae and Sungjin Choi, A generalization of a subset-sum-distinct sequence, J. Korean Math. Soc. 40 (2003), no. 5, 757--768. MR1996839 (2004d:05198). See b(n).

Jonathan H. B. Deane and Guido Gentile, A diluted version of the problem of the existence of the Hofstadter sequence, arXiv:2311.13854 [math.NT], 2023. See p. 10.

Nathan Fox, Connecting Slow Solutions to Nested Recurrences with Linear Recurrent Sequences, arXiv:2203.09340 [math.CO], 2022.

H. T. Freitag and H. W. Gould, Solution to Problem 571, Math. Mag., 38 (1965), 185-187.

H. T. Freitag (Proposer) and H. W. Gould (Solver), Problem 571: An Ordering of the Rationals, Math. Mag., 38 (1965), 185-187 [Annotated scanned copy]

Mikel Garcia-de-Andoin, Álvaro Saiz, Pedro Pérez-Fernández, Lucas Lamata, Izaskun Oregi, and Mikel Sanz, Digital-Analog Quantum Computation with Arbitrary Two-Body Hamiltonians, arXiv:2307.00966 [quant-ph], 2023.

S. W. Golomb, Discrete chaos: sequences satisfying "strange" recursions, unpublished manuscript, circa 1990 [cached copy, with permission (annotated)]

Henry W. Gould, Letters to N. J. A. Sloane, Oct 1973 and Jan 1974.

Abraham Isgur, Vitaly Kuznetsov, and Stephen Tanny, A combinatorial approach for solving certain nested recursions with non-slow solutions, arXiv:1202.0276 [math.CO], 2012.

Stanley Wu-Wei Liu, Closed form expressions for A002024(n).

M. A. Nyblom, Some curious sequences involving floor and ceiling functions, Am. Math. Monthly 109 (#6, 200), 559-564.

Boris Putievskiy, Transformations [Of] Integer Sequences And Pairing Functions, arXiv:1212.2732 [math.CO], 2012.

Raphael Schumacher, Extension of Summation Formulas involving Stirling series, arXiv:1605.09204 [math.NT], 2016.

Raphael Schumacher, The self-counting identity, Fib. Quart., 55 (No. 2 2017), 157-167.

Raphael Schumacher, The Self-Counting Flow, Fibonacci Quart. 60 (2022), no. 5, 324-343.

N. J. A. Sloane, Handwritten notes on Self-Generating Sequences, 1970. (note that A1148 has now become A005282)

Michael Somos, Sequences used for indexing triangular or square arrays.

L. J. Upton, Letter to N. J. A. Sloane, May 22 1991.

Eric Weisstein's World of Mathematics, Self-Counting Sequence.

Index entries for Hofstadter-type sequences

Formula

a(n) = floor(1/2 + sqrt(2n)). Also a(n) = ceiling((sqrt(1+8n)-1)/2). [See the Liu link for a large collection of explicit formulas. - N. J. A. Sloane, Oct 30 2019]

a((k-1)*k/2 + i) = k for k > 0 and 0 < i <= k. - Reinhard Zumkeller, Aug 30 2001

a(n) = a(n - a(n-1)) + 1, with a(1)=1. - Ian M. Levitt (ilevitt(AT)duke.poly.edu), Aug 18 2002

a(n) = round(sqrt(2n)). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Nov 01 2002

T(n,k) = A003602(A118413(n,k)); = T(n,k) = A001511(A118416(n,k)). - Reinhard Zumkeller, Apr 27 2006

G.f.: (x/(1-x))*Product_{k>0} (1-x^(2*k))/(1-x^(2*k-1)). - Vladeta Jovovic, Oct 06 2003

Equals A127899 * A004736. - Gary W. Adamson, Feb 09 2007

Sum_{i=1..n} Sum_{j=i..n+i-1} T(j,i) = A000578(n); Sum_{i=1..n} T(n,i) = A000290(n). - Reinhard Zumkeller, Jun 24 2007

a(n) + n = A014132(n). - Vincenzo Librandi, Jul 08 2010

a(n) = ceiling(-1/2 + sqrt(2n)). - Branko Curgus, May 12 2009

a(A169581(n)) = A038567(n). - Reinhard Zumkeller, Dec 02 2009

a(n) = round(sqrt(2*n)) = round(sqrt(2*n-1)); there exist a and b greater than zero such that 2*n = 2+(a+b)^2 -(a+3*b) and a(n)=(a+b-1). - Fabio Civolani (civox(AT)tiscali.it), Feb 23 2010

A005318(n+1) = 2*A005318(n) - A205744(n), A205744(n) = A005318(A083920(n)), A083920(n) = n - a(n). - N. J. A. Sloane, Feb 11 2012

Expansion of psi(x) * x / (1 - x) in powers of x where psi() is a Ramanujan theta function. - Michael Somos, Mar 19 2014

G.f.: (x/(1-x)) * Product_{n>=1} (1 + x^n) * (1 - x^(2*n)). - Paul D. Hanna, Feb 27 2016

a(n) = 1 + Sum_{i=1..n/2} ceiling(floor(2(n-1)/(i^2+i))/(2n)). - José de Jesús Camacho Medina, Jan 07 2017

a(n) = floor((sqrt(8*n-7)+1)/2). - Néstor Jofré, Apr 24 2017

a(n) = floor((A000196(8*n)+1)/2). - Pontus von Brömssen, Dec 10 2018

Sum_{n>=1} (-1)^(n+1)/a(n) = Pi/4 (A003881). - Amiram Eldar, Oct 01 2022

Example

From Clark Kimberling, Sep 16 2008: (Start)
As a rectangular array, a northwest corner:
  1 2 3 4 5 6
  2 3 4 5 6 7
  3 4 5 6 7 8
  4 5 6 7 8 9
This is the weight array (cf. A144112) of A107985 (formatted as a rectangular array). (End)
G.f. = x + 2*x^2 + 2*x^3 + 3*x^4 + 3*x^5 + 3*x^6 + 4*x^7 + 4*x^9 + 4*x^9 + 4*x^10 + ...

Maple

A002024 := n-> ceil((sqrt(1+8*n)-1)/2); seq(A002024(n), n=1..100);

Mathematica

a[1] = 1; a[n_] := a[n] = a[n - a[n - 1]] + 1 (* Branko Curgus, May 12 2009 *)
Table[n, {n, 13}, {n}] // Flatten (* Robert G. Wilson v, May 11 2010 *)
Table[PadRight[{}, n, n], {n, 15}]//Flatten (* Harvey P. Dale, Jan 13 2019 *)

Prog

/* The PARI functions t1, t2 can be used to read a triangular array T(n, k) (n >= 1, 1 <= k <= n) by rows from left to right: n -> T(t1(n), t2(n)).
* The PARI functions t1, t3 can be used to read a triangular array T(n, k) (n >= 1, 1 <= k <= n) by rows from right to left: n -> T(t1(n), t3(n)).
* The PARI functions t1, t4 can be used to read a triangular array T(n, k) (n >= 1, 0 <= k <= n-1) by rows from left to right: n -> T(t1(n), t4(n)).
- Michael Somos, Aug 23, 2002 */
(PARI) t1(n)=floor(1/2+sqrt(2*n)) /* A002024 = this sequence */
(PARI) t2(n)=n-binomial(floor(1/2+sqrt(2*n)), 2) /* A002260(n-1) */
(PARI) t3(n)=binomial(floor(3/2+sqrt(2*n)), 2)-n+1 /* A004736 */
(PARI) t4(n)=n-1-binomial(floor(1/2+sqrt(2*n)), 2) /* A002260(n-1)-1 */
(PARI) A002024(n)=(sqrtint(n*8)+1)\2 \\ M. F. Hasler, Apr 19 2014
(PARI) a(n)=(sqrtint(8*n-7)+1)\2
(PARI) a(n)=my(k=1); while(binomial(k+1, 2)+1<=n, k++); k \\ R. J. Cano, Mar 17 2014
(Haskell)
a002024 n k = a002024_tabl !! (n-1) !! (k-1)
a002024_row n = a002024_tabl !! (n-1)
a002024_tabl = iterate (\xs@(x:_) -> map (+ 1) (x : xs)) [1]
a002024_list = concat a002024_tabl
a002024' = round . sqrt . (* 2) . fromIntegral
-- Reinhard Zumkeller, Jul 05 2015, Feb 12 2012, Mar 18 2011
(Haskell) a002024_list = [1..] >>= \n -> replicate n n
(Haskell) a002024 = (!!) $ [1..] >>= \n -> replicate n n
-- Sascha Mücke, May 10 2016
(Magma) [Floor(Sqrt(2*n) + 1/2): n in [1..80]]; // Vincenzo Librandi, Nov 19 2014
(Sage) [floor(sqrt(2*n) +1/2) for n in (1..80)] # G. C. Greubel, Dec 10 2018
(Python)
from math import isqrt
def A002024(n): return (isqrt(8*n)+1)//2 # Chai Wah Wu, Feb 02 2022

Crossrefs

a(n+1) = 1+A003056(n), A022846(n)=a(n^2), a(n+1)=A002260(n)+A025581(n).

Cf. A001462, A002262, A003881, A004736, A127899, A107985, A001563, A014132, A000194, A005145, A131507, A093995, A060432 (partial sums).

A123578 is an essentially identical sequence.

Sequence in context: A274093 A087847 A107436 * A123578 A087836 A087845

Adjacent sequences: A002021 A002022 A002023 * A002025 A002026 A002027

Keyword

nonn,easy,nice,tabl

Author

N. J. A. Sloane

Status

approved