A002024 - OEIS

%I M0250 N0089 #293 Jan 05 2025 19:51:32

%S 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,

%T 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,

%U 11,11,11,11,11,11,12,12,12,12,12,12,12,12,12,12,12,12,13,13,13,13,13,13

%N k appears k times; a(n) = floor(sqrt(2n) + 1/2).

%C 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

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

%C Eigensequence of the triangle = A001563. - _Gary W. Adamson_, Dec 29 2008

%C 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

%C 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

%C Number of binary digits of A023758, i.e., a(n) = ceiling(log_2(A023758(n+2))). - _Andres Cicuttin_, Apr 29 2016

%C 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

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

%C 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

%C 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

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

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

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

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

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

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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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

%H Franklin T. Adams-Watters, <a href="/A002024/b002024.txt">Table of n, a(n) for n = 1..5050</a>

%H Jaegug Bae and Sungjin Choi, <a href="https://doi.org/10.4134/JKMS.2003.40.5.757">A generalization of a subset-sum-distinct sequence</a>, J. Korean Math. Soc. 40 (2003), no. 5, 757--768. MR1996839 (2004d:05198). See b(n).

%H Jonathan H. B. Deane and Guido Gentile, <a href="https://arxiv.org/abs/2311.13854">A diluted version of the problem of the existence of the Hofstadter sequence</a>, arXiv:2311.13854 [math.NT], 2023. See p. 10.

%H Nathan Fox, <a href="https://arxiv.org/abs/2203.09340">Connecting Slow Solutions to Nested Recurrences with Linear Recurrent Sequences</a>, arXiv:2203.09340 [math.CO], 2022.

%H H. T. Freitag and H. W. Gould, <a href="http://www.jstor.org/stable/2688796">Solution to Problem 571</a>, Math. Mag., 38 (1965), 185-187.

%H H. T. Freitag (Proposer) and H. W. Gould (Solver), <a href="/A002024/a002024_1.pdf">Problem 571: An Ordering of the Rationals</a>, Math. Mag., 38 (1965), 185-187 [Annotated scanned copy]

%H Mikel Garcia-de-Andoin, Álvaro Saiz, Pedro Pérez-Fernández, Lucas Lamata, Izaskun Oregi, and Mikel Sanz, <a href="https://arxiv.org/abs/2307.00966">Digital-Analog Quantum Computation with Arbitrary Two-Body Hamiltonians</a>, arXiv:2307.00966 [quant-ph], 2023.

%H S. W. Golomb, <a href="/A005185/a005185_1.pdf">Discrete chaos: sequences satisfying "strange" recursions</a>, unpublished manuscript, circa 1990 [cached copy, with permission (annotated)]

%H Henry W. Gould, <a href="/A003099/a003099.pdf">Letters to N. J. A. Sloane, Oct 1973 and Jan 1974</a>.

%H Abraham Isgur, Vitaly Kuznetsov, and Stephen Tanny, <a href="http://arxiv.org/abs/1202.0276">A combinatorial approach for solving certain nested recursions with non-slow solutions</a>, arXiv:1202.0276 [math.CO], 2012.

%H Stanley Wu-Wei Liu, <a href="/A002024/a002024_3.pdf">Closed form expressions for A002024(n)</a>.

%H M. A. Nyblom, <a href="http://www.jstor.org/stable/2695446">Some curious sequences involving floor and ceiling functions</a>, Am. Math. Monthly 109 (#6, 200), 559-564.

%H Boris Putievskiy, <a href="http://arxiv.org/abs/1212.2732">Transformations [Of] Integer Sequences And Pairing Functions</a>, arXiv:1212.2732 [math.CO], 2012.

%H Raphael Schumacher, <a href="https://arxiv.org/abs/1605.09204">Extension of Summation Formulas involving Stirling series</a>, arXiv:1605.09204 [math.NT], 2016.

%H Raphael Schumacher, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/55-2/Schumacher12132016.pdf">The self-counting identity</a>, Fib. Quart., 55 (No. 2 2017), 157-167.

%H Raphael Schumacher, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/60-5/schumacher.pdf">The Self-Counting Flow</a>, Fibonacci Quart. 60 (2022), no. 5, 324-343.

%H N. J. A. Sloane, <a href="/A001149/a001149.pdf">Handwritten notes on Self-Generating Sequences, 1970</a>. (note that A1148 has now become A005282)

%H Michael Somos, <a href="/A073189/a073189.txt">Sequences used for indexing triangular or square arrays</a>.

%H L. J. Upton, <a href="/A002024/a002024.pdf">Letter to N. J. A. Sloane, May 22 1991</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Self-CountingSequence.html">Self-Counting Sequence</a>.

%H <a href="/index/Ho#Hofstadter">Index entries for Hofstadter-type sequences</a>

%F 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]

%F a((k-1)*k/2 + i) = k for k > 0 and 0 < i <= k. - _Reinhard Zumkeller_, Aug 30 2001

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

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

%F T(n,k) = A003602(A118413(n,k)); = T(n,k) = A001511(A118416(n,k)). - _Reinhard Zumkeller_, Apr 27 2006

%F G.f.: (x/(1-x))*Product_{k>0} (1-x^(2*k))/(1-x^(2*k-1)). - _Vladeta Jovovic_, Oct 06 2003

%F Equals A127899 * A004736. - _Gary W. Adamson_, Feb 09 2007

%F 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

%F a(n) + n = A014132(n). - _Vincenzo Librandi_, Jul 08 2010

%F a(n) = ceiling(-1/2 + sqrt(2n)). - _Branko Curgus_, May 12 2009

%F a(A169581(n)) = A038567(n). - _Reinhard Zumkeller_, Dec 02 2009

%F 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

%F 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

%F Expansion of psi(x) * x / (1 - x) in powers of x where psi() is a Ramanujan theta function. - _Michael Somos_, Mar 19 2014

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

%F 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

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

%F a(n) = floor((A000196(8*n)+1)/2). - _Pontus von Brömssen_, Dec 10 2018

%F Sum_{n>=1} (-1)^(n+1)/a(n) = Pi/4 (A003881). - _Amiram Eldar_, Oct 01 2022

%F G.f. as array: (x^2*(1 - y)^2 + y^2 + x*y*(1 - 2*y))/((1 - x)^2*(1 - y)^2). - _Stefano Spezia_, Apr 22 2024

%e From _Clark Kimberling_, Sep 16 2008: (Start)

%e As a rectangular array, a northwest corner:

%e   1 2 3 4 5 6

%e   2 3 4 5 6 7

%e   3 4 5 6 7 8

%e   4 5 6 7 8 9

%e This is the weight array (cf. A144112) of A107985 (formatted as a rectangular array). (End)

%e 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 + ...

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

%t a[1] = 1; a[n_] := a[n] = a[n - a[n - 1]] + 1 (* _Branko Curgus_, May 12 2009 *)

%t Table[n, {n, 13}, {n}] // Flatten (* _Robert G. Wilson v_, May 11 2010 *)

%t Table[PadRight[{},n,n],{n,15}]//Flatten (* _Harvey P. Dale_, Jan 13 2019 *)

%o /* 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)).

%o * 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)).

%o * 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)).

%o - _Michael Somos_, Aug 23, 2002 */

%o (PARI) t1(n)=floor(1/2+sqrt(2*n)) /* A002024 = this sequence */

%o (PARI) t2(n)=n-binomial(floor(1/2+sqrt(2*n)),2) /* A002260(n-1) */

%o (PARI) t3(n)=binomial(floor(3/2+sqrt(2*n)),2)-n+1 /* A004736 */

%o (PARI) t4(n)=n-1-binomial(floor(1/2+sqrt(2*n)),2) /* A002260(n-1)-1 */

%o (PARI) A002024(n)=(sqrtint(n*8)+1)\2 \\ _M. F. Hasler_, Apr 19 2014

%o (PARI) a(n)=(sqrtint(8*n-7)+1)\2

%o (PARI) a(n)=my(k=1);while(binomial(k+1,2)+1<=n,k++);k \\ _R. J. Cano_, Mar 17 2014

%o (Haskell)

%o a002024 n k = a002024_tabl !! (n-1) !! (k-1)

%o a002024_row n = a002024_tabl !! (n-1)

%o a002024_tabl = iterate (\xs@(x:_) -> map (+ 1) (x : xs)) [1]

%o a002024_list = concat a002024_tabl

%o a002024' = round . sqrt . (* 2) . fromIntegral

%o -- _Reinhard Zumkeller_, Jul 05 2015, Feb 12 2012, Mar 18 2011

%o (Haskell) a002024_list = [1..] >>= \n -> replicate n n

%o (Haskell) a002024 = (!!) $ [1..] >>= \n -> replicate n n

%o -- _Sascha Mücke_, May 10 2016

%o (Magma) [Floor(Sqrt(2*n) + 1/2): n in [1..80]]; // _Vincenzo Librandi_, Nov 19 2014

%o (Sage) [floor(sqrt(2*n) +1/2) for n in (1..80)] # _G. C. Greubel_, Dec 10 2018

%o (Python)

%o from math import isqrt

%o def A002024(n): return (isqrt(8*n)+1)//2 # _Chai Wah Wu_, Feb 02 2022

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

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

%Y A123578 is an essentially identical sequence.

%K nonn,easy,nice,tabl,changed

%O 1,2

%A _N. J. A. Sloane_