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.
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
G.f.: (x/(1-x))*Product_{k>0} (1-x^(2*k))/(1-x^(2*k-1)). - Vladeta Jovovic, Oct 06 2003
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(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
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
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
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 + ...
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
KEYWORD
AUTHOR
STATUS
approved