A005318 -id:A005318 - cp's OEIS frontend

A096858 Triangle read by rows in which row n gives the n-set obtained as the differences {b(n)-b(n-i), 0 <= i <= n-1}, where b() = A005318().

1, 1, 2, 2, 3, 4, 3, 5, 6, 7, 6, 9, 11, 12, 13, 11, 17, 20, 22, 23, 24, 20, 31, 37, 40, 42, 43, 44, 40, 60, 71, 77, 80, 82, 83, 84, 77, 117, 137, 148, 154, 157, 159, 160, 161, 148, 225, 265, 285, 296, 302, 305, 307, 308, 309, 285, 433, 510, 550, 570, 581, 587, 590, 592, 593, 594

Offset: 1

N. J. A. Sloane, Aug 18 2004

It is conjectured that the triangle has the property that all 2^n subsets of row n have distinct sums. This conjecture was proved by T. Bohman in 1996 - N. J. A. Sloane, Feb 09 2012

It is also conjectured that in some sense this triangle is optimal. See A005318 for further information and additional references.

			The triangle begins:
{1}
{1,2}
{2,3,4}
{3,5,6,7}
{6,9,11,12,13}
{11,17,20,22,23,24}
{20,31,37,40,42,43,44}
{40,60,71,77,80,82,83,84}
{77,117,137,148,154,157,159,160,161}
{148,225,265,285,296,302,305,307,308,309}
{285,433,510,550,570,581,587,590,592,593,594}
{570,855,1003,1080,1120,1140,1151,1157,1160,1162,1163,1164}
{1120,1690,1975,2123,2200,2240,2260,2271,2277,2280,2282,2283,2284}
{2200,3320,3890,4175,4323,4400,4440,4460,4471,4477,4480,4482,4483,4484}
{4323,6523,7643,8213,8498,8646,8723,8763,8783,8794,8800,8803,8805,8806,8807}

J. H. Conway and R. K. Guy, Solution of a problem of Erdős, Colloq. Math. 20 (1969), p. 307.
R. K. Guy, Sets of integers whose subsets have distinct sums, pp. 141-154 of Theory and practice of combinatorics. Ed. A. Rosa, G. Sabidussi and J. Turgeon. Annals of Discrete Mathematics, 12. North-Holland 1982.
R. K. Guy, Unsolved Problems in Number Theory, C8.

Alois P. Heinz, Rows n = 1..141, flattened
Tom Bohman, A sum packing problem of Erdős and the Conway-Guy sequence, Proc. AMS 124, (No. 12, 1996), pp. 3627-3636.

Cf. A005318, A005230 (column 1 of triangle).

b:= proc(n) option remember;
      `if`(n<2, n, 2*b(n-1) -b(n-1-floor(1/2 +sqrt(2*n-2))))
    end:
T:= n-> seq(b(n)-b(n-i), i=1..n):
seq(T(n), n=1..15);  # Alois P. Heinz, Nov 29 2011

b[n_] := b[n] = If[n < 2, n, 2*b[n-1] - b[n-1-Floor[1/2 + Sqrt[2*n-2]]]]; t[n_] := Table[b[n] - b[n-i], {i, 1, n}]; Table[t[n], {n, 1, 15}] // Flatten (* Jean-François Alcover, Jan 14 2014, after Alois P. Heinz *)

Typo in definition (limits on i were wrong) corrected and reference added to Bohman's paper. N. J. A. Sloane, Feb 09 2012

A205744 The sequence "u_{n-r}" used by Conway and Guy in the construction of A005318 and A096858.

Original entry on oeis.org

0, 0, 1, 1, 2, 4, 4, 7, 13, 24, 24, 44, 84, 161, 309, 309, 594, 1164, 2284, 4484, 8807, 8807, 17305, 34301, 68008, 134852, 267420, 530356, 530356, 1051905, 2095003, 4172701, 8311101, 16554194, 32973536, 65679652, 65679652, 130828948, 261127540, 521203175, 1040311347, 2076449993

Offset: 1

N. J. A. Sloane, Feb 09 2012

nonn

This is A005318 with the terms A005318(i) repeated iff i is a triangular number.

R. K. Guy, Sets of integers whose subsets have distinct sums, pp. 141-154 of Theory and practice of combinatorics. Ed. A. Rosa, G. Sabidussi and J. Turgeon. Annals of Discrete Mathematics, 12. North-Holland 1982. See Table 1, column (3).

Cf. A005318, A096858.

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

A206239 Subsequence A005318(t_n), where t_n is the n-th triangular number (A000217).

Original entry on oeis.org

0, 1, 4, 24, 309, 8807, 530356, 65679652, 16512273616, 8370804628178, 8525389679187197, 17408681737224080093, 71192609533782031405771, 582711051458083440858730497, 9542765396943645975520145941300, 312620974584432225019935558843189172, 20485270547000003746699189223065768145956

Offset: 1

N. J. A. Sloane, Feb 09 2012

nonn

These are the repeated terms in A205744.

R. K. Guy, Sets of integers whose subsets have distinct sums, pp. 141-154 of Theory and practice of combinatorics. Ed. A. Rosa, G. Sabidussi and J. Turgeon. Annals of Discrete Mathematics, 12. North-Holland 1982. See Table 1.

Cf. A005318, A205744, A096858.

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

Original entry on oeis.org

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

N. J. A. Sloane

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

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

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.

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

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.

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

a002024_list = [1..] >>= \n -> replicate n n

a002024 = (!!) $ [1..] >>= \n -> replicate n n
-- Sascha Mücke, May 10 2016

[Floor(Sqrt(2*n) + 1/2): n in [1..80]]; // Vincenzo Librandi, Nov 19 2014

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

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

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

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

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

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

A002024(n)=(sqrtint(n*8)+1)\2 \\ M. F. Hasler, Apr 19 2014

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

a(n)=my(k=1);while(binomial(k+1,2)+1<=n,k++);k \\ R. J. Cano, Mar 17 2014

from math import isqrt
def A002024(n): return (isqrt(8*n)+1)//2 # Chai Wah Wu, Feb 02 2022

[floor(sqrt(2*n) +1/2) for n in (1..80)] # G. C. Greubel, Dec 10 2018

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

A004137 Maximal number of edges in a graceful graph on n nodes.

Original entry on oeis.org

0, 1, 3, 6, 9, 13, 17, 23, 29, 36, 43, 50, 58, 68, 79, 90, 101, 112, 123, 138, 153, 168, 183, 198, 213, 232

Offset: 1

N. J. A. Sloane, Simon Plouffe

A graph with e edges is "graceful" if its nodes can be labeled with distinct integers in {0,1,...,e} so that, if each edge is labeled with the absolute difference between the labels of its endpoints, then the e edges have the distinct labels 1, 2, ..., e.
Equivalently, maximum m for which there's a restricted difference basis with respect to m with n elements. A "difference basis w.r.t. m" is a set of integers such that every integer from 1 to m is a difference between two elements of the set. A "restricted" difference basis is one in which the smallest element is 0 and the largest is m.
a(n) is also the length of an optimal ruler with n marks. For definitions see A103294. For example, a(6)=13 is the length of the optimal rulers with 6 marks, {[0, 1, 6, 9, 11, 13], [0, 2, 4, 7, 12, 13], [0, 1, 4, 5, 11, 13], [0, 2, 8, 9, 12, 13], [0, 1, 2, 6, 10, 13], [0, 3, 7, 11, 12, 13]}. Also n = 1 + A103298(a(n)). - Peter Luschny, Feb 28 2005
If the conjecture is true that an optimal ruler with more than 12 segments is a Wichmann ruler then the sequence continues 232, 251, 270, 289, 308, 327, ... - Peter Luschny, Oct 09 2011 [updated to take the verifications of Robison into account, Oct 01 2015]

			a(7)=17: Label the 7 nodes 0,1,8,11,13,15,17 and include all edges except those from 8 to 15, from 13 to 15, from 13 to 17 and from 15 to 17. {0,1,8,11,13,15,17} is a restricted difference basis w.r.t. 17.
a(21)=153 because there exists a complete ruler (i.e., one that can measure every distance between 1 and 153) with marks [0,1,2,3,7,14,21,28,43,58,73,88,103,118,126,134,142,150,151,152,153] and no complete ruler of greater length with the same number of marks can be found. This ruler is of the type described by B. Wichmann and it is conjectured by _Peter Luschny_ that it is impossible to improve upon Wichmann's construction for finding optimal rulers of bigger lengths.

J.-C. Bermond, Graceful graphs, radio antennae and French windmills, pp. 18-37 of R. J. Wilson, editor, Graph Theory and Combinatorics. Pitman, London, 1978.
R. K. Guy, Modular difference sets and error correcting codes. in: Unsolved Problems in Number Theory, 3rd ed. New York: Springer-Verlag, chapter C10, (2004), 181-183.
J. C. P. Miller, Difference bases: Three problems in additive number theory, pp. 299-322 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

D. Beutner and H. Harborth, Graceful labelings of Nearly Complete Graphs, Results Math. 41 (2002) 34-39.
G. S. Bloom and S. W. Golomb, Applications of numbered undirected graphs, Proc. IEEE 65 (1977), 562-570.
G. S. Bloom and S. W. Golomb, Numbered complete graphs, unusual rulers, and assorted applications, Theory and Applications of Graphs, Lecture Notes in Math. 642, (1978), 53-65.
L. Egidi and G. Manzini, Spaced seeds design using perfect rulers, Tech. Rep. CS Department Universita del Piemonte Orientale, June 2011.
P. Erdős, A survey of problems in combinatorial number theory, Ann. Discrete Math. 6 (1980), 89-115.
P. Erdős and R. Freud, On sums of a Sidon-sequence, J. Number Theory 38 (1991), 196-205.
P. Erdős and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. Lond. Math. Soc. 16 (1941), 212-215.
J. Leech, On the representation of 1, 2, ..., n by differences, J. Lond. Math. Soc. 31 (1956), 160-169.
S. Lou and Q. Yao, A Chebyshev's type of prime number theorem in a short interval II, Hardy-Ramanujan J. 15 (1992), 1-33.
Peter Luschny, Perfect Rulers.
Peter Luschny, Wichmann Rulers.
Klaus Nagel, Evaluation of perfect rulers C program.
O. Pikhurko, Dense edge-magic graphs and thin additive bases, Discrete Math. 306 (2006), 2097-2107.
O. Pikhurko and T. Schoen, Integer Sets Having the Maximum Number of Distinct Differences, Integers: Electronic journal of combinatorial number theory 7 (2007).
I. Redéi and A. Rényi, On the representation of integers 1, 2, ..., n by differences, Mat. Sbornik 24 (1949), 385-389 (Russian).
Arch D. Robison, Parallel Computation of Sparse Rulers, Jan 14 2014.
F. Schwartau, Y. Schröder, L. Wolf and J. Schoebel, MRLA search results and source code, Nov 6 2020.
F. Schwartau, Y. Schröder, L. Wolf and J. Schoebel, Large Minimum Redundancy Linear Arrays: Systematic Search of Perfect and Optimal Rulers Exploiting Parallel Processing, IEEE Open Journal of Antennas and Propagation, 2 (2021), 79-85.
J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43 (1938), 377-85.
David Singmaster, David Fielker, N. J. A. Sloane, Correspondence, August 1979.
M. Wald & N. J. A. Sloane, Correspondence and Attachment, 1987.
Eric Weisstein's World of Mathematics, Graceful Graph.
B. Wichmann, A note on restricted difference bases, J. Lond. Math. Soc. 38 (1963), 465-466.
Al Zimmermann's Programming Contests, Graceful Graphs, September - December 2013.

Cf. A046693, A103294, A103298, A103299, A103296, A102508, A212661.
A080060 is an erroneous version of the sequence, given in Bermond's paper. Cf. A005488.
A289761 provides the conjectured continuation.

See Klaus Nagel link.
(Parallel C++) See A. Robison link.

a(n) = n*(n-1)/2 - A212661(n). - Kellen Myers, Jun 06 2016

Miller's paper gives these lower bounds for the 8 terms from a(15) to a(22): 79, 90, 101, 112, 123, 138, 153, 168.
Edited by Dean Hickerson, Jan 26 2003
Terms 79,...,123 from Peter Luschny, Feb 28 2005, with verification by an independent program written by Klaus Nagel. Using this program Hugo Pfoertner found the next term, 138.
Using this program Hugo Pfoertner found further evidence for the conjectured term a(21)=153, Feb 23 2005
Terms a(21) .. a(24) proved by exhaustive search by Arch D. Robison, Hugo Pfoertner, Nov 01 2013
Term a(25) proved by exhaustive search by Arch D. Robison, Peter Luschny, Jan 14 2014
Term a(26) proved by exhaustive search by Fabian Schwartau, Yannic Schröder, Lars Wolf, Joerg Schoebel, Feb 22 2021

A083920 Number of nontriangular numbers <= n.

Original entry on oeis.org

0, 0, 1, 1, 2, 3, 3, 4, 5, 6, 6, 7, 8, 9, 10, 10, 11, 12, 13, 14, 15, 15, 16, 17, 18, 19, 20, 21, 21, 22, 23, 24, 25, 26, 27, 28, 28, 29, 30, 31, 32, 33, 34, 35, 36, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 55, 56, 57, 58, 59, 60, 61, 62

Offset: 0

Clark Kimberling, May 08 2003

nonn

An alternative description: the sequence of nonnegative integers with the triangular numbers repeated.

a(t(n)) = t(n+1), where t(n)=A000217(n)=n(n+1)/2, the n-th triangular number. For n>=1, a(n)=a(n-1) if and only if n is a triangular number; otherwise, a(n)=1+a(n-1).

			a(7)=4 counts the nontriangular numbers, 2,4,5,7, that are <=7.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
R. K. Guy, Sets of integers whose subsets have distinct sums, pp. 141-154 of Theory and practice of combinatorics. Ed. A. Rosa, G. Sabidussi and J. Turgeon. Annals of Discrete Mathematics, 12. North-Holland 1982. See Table 1, column (4).

Cf. A000217, A002024, A003056, A005318, A205744.
Essentially partial sums of A023532.
Number of nonzero terms in row n+1 of A342557.

a083920 n = a083920_list !! n
a083920_list = scanl1 (+) $ map (1 -) a010054_list
-- Reinhard Zumkeller, Feb 12 2012

[n-Floor((Sqrt(8*n+1)-1)/2):n in [1..75]]; // Marius A. Burtea, Jun 19 2019

f[n_] := n - Floor[(Sqrt[8n + 1] - 1)/2]; Table[ f[n], {n, 0, 73}] (* Robert G. Wilson v, Oct 22 2005 *)
Accumulate[Table[If[OddQ[Sqrt[8n+1]],0,1],{n,0,120}]] (* Harvey P. Dale, Oct 14 2014 *)

a(n)=n-(sqrtint(8*n+1)-1)\2 \\ Charles R Greathouse IV, Sep 02 2015

from math import isqrt
def A083920(n): return n-(k:=isqrt(m:=n+1<<1))+((m>=k*(k+1)+1)^1) # Chai Wah Wu, Jun 07 2025

a(n) = n-floor((x-1)/2) = n-A003056(n), where x = sqrt(8*n+1).
A005318(n+1) = 2*A005318(n)-A205744(n), A205744(n) = A005318(a(n)), a(n) = n - A002024(n). - N. J. A. Sloane, Feb 11 2012
G.f.: 1/(1 - x)^2 - (1/(1 - x))*Product_{k>=1} (1 - x^(2*k))/(1 - x^(2*k-1)). - Ilya Gutkovskiy, May 30 2017
a(n) = n - floor(sqrt(2*n + 1) - 1/2). - Ridouane Oudra, Jun 19 2019

Added alternative definition and Guy reference. - N. J. A. Sloane, Feb 09 2012

A005230 Stern's sequence: a(1) = 1, a(n+1) is the sum of the m preceding terms, where m(m-1)/2 < n <= m(m+1)/2 or equivalently m = ceiling((sqrt(8*n+1)-1)/2) = A002024(n).

Original entry on oeis.org

1, 1, 2, 3, 6, 11, 20, 40, 77, 148, 285, 570, 1120, 2200, 4323, 8498, 16996, 33707, 66844, 132568, 262936, 521549, 1043098, 2077698, 4138400, 8243093, 16419342, 32706116, 65149296, 130298592, 260075635, 519108172, 1036138646, 2068138892, 4128034691

Offset: 1

N. J. A. Sloane, Simon Plouffe

A002487 is THE Stern's sequence!

Limit_{n->oo} a(n)/2^n = 0.11756264240558743281779408719593950494049225979176... - Jon E. Schoenfield, Dec 17 2016

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

Harvey P. Dale, Table of n, a(n) for n = 1..1000 [extending prior submission by T. D. Noe]
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 d_1(n).
G. Kreweras, Sur quelques problèmes relatifs au vote pondéré, [Some problems of weighted voting], Math. Sci. Humaines No. 84 (1983), 45-63.
M. A. Stern, Aufgaben, J. Reine Angew. Math., 18 (1838), 100.
Index entries for sequences related to Stern's sequences
Index entries for "core" sequences

Cf. A002487.

A005230[1] := 1: n := 50: for k from 1 to n-1 do: A005230[k+1] := sum('A005230[j]','j'=k+1-(ceil((sqrt(8*k+1)-1)/2))..k): od: [seq(A005230[k],k=1..n)]; # UlrSchimke(AT)aol.com, Mar 16 2002

Module[{lst={1,1},n=2},While[n<40,AppendTo[lst,Total[ Take[lst, -Ceiling[ (Sqrt[8n+1]-1)/2]]]];n++];lst] (* Harvey P. Dale, Apr 02 2012 *)

a(n)=if(n==1,1,sum(k=1,ceil((sqrt(8*n-7)-1)/2),a(n-k))) \\ Paul D. Hanna, Aug 28 2006

v=vector(10^3);v[1]=v[2]=1;v[3]=2;v[4]=3;u=vector(#v,i,if(i>4,0,sum(j=1,i,v[j])));for(i=5,#v,m=ceil((sqrt(8*i-7)-1)/2);v[i]=u[i-1]-u[i-m-1];u[i]=u[i-1]+v[i]);u=0;v \\ Charles R Greathouse IV, Sep 19 2011

from itertools import count, islice
from math import isqrt
def A005230_gen(): # generator of terms
    blist = [1]
    for n in count(1):
        yield blist[-1]
        blist.append(sum(blist[-i] for i in range(1,(isqrt(8*n)+3)//2)))
A005230_list = list(islice(A005230_gen(),30)) # Chai Wah Wu, Feb 02 2022

Partial sums give Conway-Guy sequence A005318. Cf. A066777.

2*a(n*(n+1)/2 + 1) = a(n*(n+1)/2 + 2) for n>=1; lim_{n->oo} a(n+1)/a(n) = 2. - Paul D. Hanna, Aug 28 2006

Name corrected by Mario Szegedy, Sep 15 1996

Name revised by Ulrich Schimke (ulrschimke(AT)aol.com), Mar 16 2002

A005255 Atkinson-Negro-Santoro sequence: a(n+1) = 2*a(n) - a(n-floor(n/2+1)).

Original entry on oeis.org

0, 1, 2, 4, 7, 13, 24, 46, 88, 172, 337, 667, 1321, 2629, 5234, 10444, 20842, 41638, 83188, 166288, 332404, 664636, 1328935, 2657533, 5314399, 10628131, 21254941, 42508561, 85014493, 170026357, 340047480, 680089726, 1360169008, 2720327572

Offset: 0

N. J. A. Sloane, Simon Plouffe

For each n, the n-term sequence (b(k) = a(n) - a(n-k), 1 <= k <= n), has the property that all 2^n sums of subsets of the terms are distinct.

a(n) = A062178(n+1) - 1; see also A002083. - Reinhard Zumkeller, Nov 18 2012

			For n = 4, the sequence b is 7-4,7-2,7-1,7-0 = 3,5,6,7, which has subset sums (grouped by number of terms) 0, 3,5,6,7, 8,9,10,11,12,13, 14,15,16,18, 21.

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.28.
T. V. Narayana, Recent progress and unsolved problems in dominance theory, pp. 68-78 of Combinatorial mathematics (Canberra 1977), Lect. Notes Math. Vol. 686, 1978.
T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, pp. 100-101.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=0..300
M. D. Atkinson et al., Sums of lexicographically ordered sets, Discrete Math., 80 (1990), 115-122.
W. F. Lunnon, Integer sets with distinct subset-sums, Math. Comp. 50 (1988), 297-320.
B. E. Wynne & N. J. A. Sloane, Correspondence, 1976-84
B. E. Wynne & T. V. Narayana, Tournament configuration, weighted voting, and partitioned catalans, Preprint.
Bayard Edmund Wynne, and T. V. Narayana, Tournament configuration and weighted voting, Cahiers du bureau universitaire de recherche opérationnelle, 36 (1981): 75-78.

Cf. A002083, A005318, A062178.

a005255 n = a005255_list !! (n-1)
a005255_list = scanl (+) 0 $ tail a002083_list
-- Reinhard Zumkeller, Nov 18 2012

a[ 0 ] := 0; a[ 1 ] := 1; a[ n_ ] := 2*a[ n - 1 ] - a[(n - 1) - Floor[ (n - 1)/2 + 1 ] ]; For[ n = 1, n <= 100, n++, Print[ a[ n ] ] ];

More terms from Winston C. Yang (winston(AT)cs.wisc.edu), Aug 26 2000

Edited by Franklin T. Adams-Watters, Apr 11 2009

A276661 Least k such that there is a set S in {1, 2, ..., k} with n elements and the property that each of its subsets has a distinct sum.

Original entry on oeis.org

0, 1, 2, 4, 7, 13, 24, 44, 84, 161

Offset: 0

Charles R Greathouse IV and J. P. Grossman, Sep 11 2016

This sequence is the main entry for the distinct subset sums problem. See also A201052, A005318, A005255.
The Conway-Guy sequence A005318 is an upper bound. Lunnon showed that a(67) < 34808838084768972989 = A005318(67), and Bohman improved the bound to a(67) <= 34808712605260918463.
Lunnon found a(0)-a(8) and J. P. Grossman found a(9).
a(10) > 220, with A201052. - Fausto A. C. Cariboni, Apr 06 2021

			a(0) = 0: {}
a(1) = 1: {1}
a(2) = 2: {1, 2}
a(3) = 4: {1, 2, 4}
a(4) = 7: {3, 5, 6, 7}
a(5) = 13: {3, 6, 11, 12, 13}
a(6) = 24: {11, 17, 20, 22, 23, 24}
a(7) = 44: {20, 31, 37, 40, 42, 43, 44}
a(8) = 84: {40, 60, 71, 77, 80, 82, 83, 84}
a(9) = 161: {77, 117, 137, 148, 154, 157, 159, 160, 161}

Iskander Aliev, Siegel’s lemma and sum-distinct sets, Discrete Comput. Geom. 39 (2008), 59-66.
J. H. Conway and R. K. Guy, Solution of a problem of Erdos, Colloq. Math. 20 (1969), p. 307.
Dubroff, Q., Fox, J., & Xu, M. W. (2021). A note on the Erdos distinct subset sums problem. SIAM Journal on Discrete Mathematics, 35(1), 322-324.
R. K. Guy, Unsolved Problems in Number Theory, Section C8.
Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, Karol Węgrzycki, Equal-Subset-Sum Faster Than the Meet-in-the-Middle, arXiv:1905.02424
Stefan Steinerberger, Some remarks on the Erdős Distinct subset sums problem, International Journal of Number Theory, 2023 , #19:08, 1783-1800 (arXiv:2208.12182).

Tom Bohman, A sum packing problem of Erdős and the Conway-Guy sequence, Proc. AMS 124:12 (1996), pp. 3627-3636.
J. H. Conway & R. K. Guy, Sets of natural numbers with distinct sums, Manuscript.
R. K. Guy, Letter to N. J. A. Sloane, Apr 1975
R. K. Guy, Sets of integers whose subsets have distinct sums, pp. 141-154 of Theory and practice of combinatorics. Ed. A. Rosa, G. Sabidussi and J. Turgeon. Annals of Discrete Mathematics, 12. North-Holland 1982.
R. K. Guy, Sets of integers whose subsets have distinct sums, pp. 141-154 of Theory and practice of combinatorics. Ed. A. Rosa, G. Sabidussi and J. Turgeon. Annals of Discrete Mathematics, 12. North-Holland 1982. (Annotated scanned copy)
W. F. Lunnon, Integer sets with distinct subset-sums, Math. Comp. 50 (1988), pp. 297-320.
Arun J. Manattu and Aparna Lakshmanan S., Erdős Conjecture and AR-Labeling, arXiv:2502.19182 [math.CO], 2025. See p. 3.

Cf. A005255, A005318, A201052.

cp's OEIS Frontend

A096858 Triangle read by rows in which row n gives the n-set obtained as the differences {b(n)-b(n-i), 0 <= i <= n-1}, where b() = A005318().

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A205744 The sequence "u_{n-r}" used by Conway and Guy in the construction of A005318 and A096858.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A206239 Subsequence A005318(t_n), where t_n is the n-th triangular number (A000217).

Views

Author

Keywords

Comments

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Haskell

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

PARI

PARI

Python

Sage

Formula

A004137 Maximal number of edges in a graceful graph on n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

C

Formula

Extensions

A083920 Number of nontriangular numbers <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

A005230 Stern's sequence: a(1) = 1, a(n+1) is the sum of the m preceding terms, where m(m-1)/2 < n <= m(m+1)/2 or equivalently m = ceiling((sqrt(8*n+1)-1)/2) = A002024(n).