A045652 -id:A045652 - cp's OEIS frontend

A072842 Largest m such that we can partition the set {1,2,...,m} into n subsets with the property that we never have a+b=c for any distinct elements a, b, c in one subset.

2, 8, 23, 66

Offset: 1

Tor G. J. Myklebust (pi(AT)flyingteapot.bnr.usu.edu), Jul 24 2002

The fourth term is at least 66 (Ernst Munter), from { 24 26 27 28 29 30 31 32 33 36 37 38 39 41 42 44 45 46 47 48 49 } { 9 10 12 13 14 15 17 18 20 54 55 56 57 58 59 60 61 62 } { 1 2 4 8 11 16 22 25 40 43 53 66 } { 3 5 6 7 19 21 23 34 35 50 51 52 63 64 65 }
Another set of subsets can be described with this sequence of digits (among 8238): 112122213313333333232124144444144422244144441444412223333333331222 (where each digit represents a subset) The fifth term is at least 195 and can be built with the previous sequence, 515, then 66 digits 5 and finally the sequence 122133333333312224144441444222441444444441422213333133331222. I'd like to see a 196-digit sequence. [Julien de Prabere]
Actually a(5)=196 was given by Walker without proof. But Eliahou et al. give an example of such a partition, so a(5) >= 196. And Robilliard et al. give an example for n=6 with [1..574], so a(6) >= 574. - Michel Marcus, Mar 26 2013
To clarify: a(1)-a(4) are known. a(5) = 196 was claimed by Walker but no proof is known, though the value seems likely to be correct. - Charles R Greathouse IV, Jun 13 2013
The best known lower bounds for the next terms: a(6) >= 582, a(7) >= 1740, a(8) >= 5201, a(9) >= 15596. See link to Eliahou's 2017 article. - Dmitry Kamenetsky, Oct 20 2019
From Fred Rowley, Aug 29 2025: (Start)
New lower bounds a(6) >= 642, a(7) >= 2146, a(8) >= 6976 and beyond were established by Rowley in 2021 (see link). Improved lower bounds a(6) >= 646, a(9) >= 22536 and a(10) >= 71256 and beyond were established in 2022 by Ageron et al (see link).
The following coloring demonstrates that a(5) >= 207, confirming this number remains an open problem:
 1 2 1 3 1 2 1 3 1 2   1 4 1 2 1 3 3 2 1 4   1 3 3 4 4 4 4 4 4 4   4 3 4 4 4 2 3 1 5 2
 2 3 3 2 2 1 5 2 2 1   5 2 2 1 5 2 2 1 5 2   2 1 5 2 2 1 5 2 2 1   5 2 2 1 5 3 3 4 4 4
 4 4 4 4 4 4 4 4 4 1   5 5 5 1 5 3 3 1 5 5   5 1 5 5 5 1 5 5 5 1   5 5 5 1 5 5 5 1 5 5
 5 1 5 5 5 1 5 5 5 1   3 3 5 1 5 5 5 1 4 4   4 4 4 4 4 4 4 4 4 4   3 3 5 1 2 2 5 1 2 2
 5 1 2 2 5 1 2 2 5 1   2 2 5 1 2 2 5 1 2 2   5 1 2 2 3 3 2 2 5 1   3 3 4 4 4 4 4 4 4 4
 4 4 4 4 3 3 1. (End)

			a(2) = 8 because we may partition the set {1, 2, ..., 8} into {1, 2, 4, 8} and {3, 5, 6, 7} with the desired property, and this is the unique solution; attempting to add 9 to either will produce a set with the property that a+b=c for some a,b,c (1+8=9 or 3+6=9). [Corrected by Julien de Prabere, Dec 17 2009]

EFNet #math, Jul 23 2002 (can we replace this with a link? - N. J. A. Sloane)

R. Ageron, P. Casteras, T. Pellerin, Y. Portella, A. Rimmel and J. Tomasik, New lower bounds for Schur and weak Schur numbers, arXiv:2112.03175 [math.CO], 2021-2022.
P. Blanchard, F. Harary and R. Reis, Partitions into sum-free sets, Integers: electronic journal of combinatorial number theory, 6. 2006.
P. Bornsztein, An extension of a theorem of Schur, Acta Arithmetica, 101.4 (2001), pp. 395-399.
Dr. Dobb's Journal, Solutions to the "Monopoles" Problem, Dec 01 1999.
S. Eliahou, J. M. Marín, M. P. Revuelta, M. I. Sanz, Weak Schur numbers and the search for G.W. Walker’s lost partitions, Computers & Mathematics with Applications, Volume 63, Issue 1, January 2012, Pages 175-182.
Shalom Eliahou, Les extraordinaires prédictions du Révérend Walker, Images des Mathématiques, CNRS, 2017 (in French).
Gordon Hamilton, Grade 2 $1,000,000 Unsolved Problem (2011).
Robert W. Irving, An extension of Schur's theorem on sum-free partitions, Acta Arithmetica 25 (1973/74), pp. 55-64. (see p. 59ff)
Dmitry Kamenetsky, Paint numbers from 1 to 8 with two colours, Puzzling StackExchange, 2019.
Dmitry Kamenetsky, Paint numbers from 1 to 23 with three colours, Puzzling StackExchange, 2019.
MathEnJeans, Les tiroirs anti-sommes, 2010-2011 (in French).
D. Robilliard, C. Fonlupt, V. Marion-Poty, Amine Boumaza, A multilevel Tabu Search with Backtracking for Exploring Weak Schur Numbers, Artificial Evolution, Lecture Notes in Computer Science, Volume 7401, 2012, pp 109-119.
Fred Rowley, New lower bounds for weak Schur partitions, Integers, vol. 21, p. #A59, 2021.
G. W. Walker, Solution to the problem E985, American Mathematical Monthly, Vol. 59 (1952), p. 253.

The requirement that a not equal b is the only difference between these numbers and the Schur numbers A045652.

Cf. A036918, A118771, A297023.

It is known that 315^((n-1)/5) <= a(n) <= floor(n!*n*e). - Pierre Bornsztein (bornsztein(AT)voila.fr), Sep 02 2003

a(n) < A118771(n), and also a(n) <= A036918(n+1). - Michel Marcus, Mar 26 2013

Additional comments from Rob Pratt and Brendan McKay, Nov 02 2002
More terms from Pierre Bornsztein (bornsztein(AT)voila.fr), Sep 02 2003
Minor additions from Julien de Prabere (jdpbr(AT)aliceadsl.fr), Feb 25 2010
Term a(5) = 196 removed by Fred Rowley, Aug 29 2025

A030126 Schur's numbers (version 1).

Original entry on oeis.org

2, 5, 14, 45, 161

Offset: 1

Eric W. Weisstein

Smallest number such that for any n-coloring of the integers 1, ..., a(n) no color is sum-free, that is, some color contains a triple x + y = z. - Charles R Greathouse IV, Jun 11 2013
Named after the Russian mathematician Issai Schur (1875-1941). - Amiram Eldar, Jun 24 2021
a(6) >= 537, a(7) >= 1681 (see Ahmed et al. at p. 2). - Stefano Spezia, Aug 25 2023

			Baumert & Golomb find a(4) = 45 and give this example:
A = {1, 3, 5, 15, 17, 19, 26, 28, 40, 42, 44}
B = {2, 7, 8, 18, 21, 24, 27, 37, 38, 43}
C = {4, 6, 13, 20, 22, 23, 25, 30, 32, 39, 41}
D = {9, 10, 11, 12, 14, 16, 29, 31, 33, 34, 35, 36}
which demonstrates that a(4) > 44. Note that the union of these sets is {1, ..., 44} and none of the sets contains three numbers (perhaps not all distinct) such that one is the sum of the other two. - _Charles R Greathouse IV_, Jun 11 2013
From _Marijn Heule_, Dec 12 2017: (Start)
Exoo computed the first certificate showing that a(5) > 160:
A = {1, 6, 10, 18, 21, 23, 26, 30, 34, 38, 43, 45, 50, 54, 65, 74, 87, 96, 107, 111, 116, 118, 123, 127, 131, 135, 138, 140, 143, 151, 155, 160}
B = {2, 3, 8, 14, 19, 20, 24, 25, 36, 46, 47, 51, 62, 73, 88, 99, 110, 114, 115, 125, 136, 137, 141, 142, 147, 153, 158, 159}
C = {4, 5, 15, 16, 22, 28, 29, 39, 40, 41, 42, 48, 49, 59, 102, 112, 113, 119, 120, 121, 122, 132, 133, 139, 145, 146, 156, 157}
D = {7, 9, 11, 12, 13, 17, 27, 31, 32, 33, 35, 37, 53, 56, 57, 61, 79, 82, 100, 104, 105, 108, 124, 126, 128, 129, 130, 134, 144, 148, 149, 150, 152, 154}
E = {44, 52, 55, 58, 60, 63, 64, 66, 67, 68, 69, 70, 71, 72, 75, 76, 77, 78, 80, 81, 83, 84, 85, 86, 89, 90, 91, 92, 93, 94, 95, 97, 98, 101, 103, 106, 109, 117} (End)

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Sections E11 and E12, pp. 323-326.
I. Schur, Über die Kongruenz x^m+y^m=z^m (mod p), Jahresber. Deutsche Math.-Verein., Vol. 25 (1916), pp. 114-116.

T. Ahmed, L. Boza, M. P. Revuelta, and M. I. Sanz, Exact values and lower bounds on the n-color weak Schur numbers for n=2,3. Ramanujan J (2023). See Table 1 at p. 2.
Leonard D. Baumert and Solomon W. Golomb, Backtrack Programming, Journal of the ACM, Vol. 12, No. 4 (1965), pp. 516-524.
Marijn J. H. Heule, Schur number five, Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 32, No. 1 (2018), pp. 6598-6606; arXiv preprint, arXiv:1711.08076 [cs.LO], 2017.
Eric Weisstein's World of Mathematics, Schur Number.

Cf. A045652.

a(5) from Marijn Heule, Nov 26 2017

Example corrected by Eckard Specht, Jul 06 2021

A003323 Multicolor Ramsey numbers R(3,3,...,3), where there are n 3's.

Original entry on oeis.org

2, 3, 6, 17

Offset: 0

N. J. A. Sloane

Definition: if the edges of a complete graph with at least a(n) nodes are colored with n colors then there is always a monochromatic triangle, and a(n) is the smallest number with this property.
Has it been proved that a(4)=62, or is it just an upper bound? - N. J. A. Sloane, Jun 12 2016
62 is an upper bound. It is probably not the correct value, which is likely closer to the lower bound of 51. - Jeremy F. Alm, Jun 12 2016
From Pontus von Brömssen, Jul 23 2021 (updated Mar 13 2025): (Start)
According to the survey by Radziszowski, the following are the best known bounds:
    51 <= a(4) <=    62,
   162 <= a(5) <=   307,
   538 <= a(6) <=  1838,
  1698 <= a(7) <= 12861.
(End)
In general, if a(n)=r then a(n+1) <= n*(r-1) + r + 1 = (n+1)*(r-1) + 2. - Roderick MacPhee, Mar 03 2023

			a(2)=6 since in a party with at least 6 people, there are three people mutually acquainted or three people mutually unacquainted.

G. Berman and K. D. Fryer, Introduction to Combinatorics. Academic Press, NY, 1972, p. 175.
S. Fettes, R. Kramer, S. Radziszowski, An upper bound of 62 on the classical Ramsey number R(3,3,3,3), Ars Combin. 72 (2004), 41-63.
H. W. Gould, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Thomas Bloom, Problem 183, Erdős Problems.
Shalom Eliahou, An adaptive upper bound on the Ramsey numbers R(3,...,3), Integers 20 (2020), Paper No. A54, 7 pp; arXiv:1912.05353 [math.CO], 2019.
Henry W. Gould, Letters to N. J. A. Sloane, 1974
R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math., 7 (1955), 1-7.
Stanisław Radziszowski, Small Ramsey numbers, The Electronic Journal of Combinatorics, Dynamic Surveys, DS1 (ver. 17, 2024).
Terence Tao, Erdős problem database, see no. 183.

Cf. A045652, A343607.

A073591(n) is an upper bound on a(n).

The limit of a(n)^(1/n) exists and is at least 3.28 (possibly infinite). (See the survey by Radziszowski.) - Pontus von Brömssen, Jul 23 2021 (updated Mar 13 2025)
a(n) = min {k >= 0; A343607(k) > n}. - Pontus von Brömssen, Aug 01 2021
For n >= 4, a(n) <= n!*(e-1/6) + 1. - Elijah Beregovsky, Mar 22 2023

Upper bound and additional comments from D. G. Rogers, Aug 27 2006
Better definition from Max Alekseyev, Jan 12 2008
Comment corrected by Brian Kell, Feb 14 2010
Changed a(4) to 62, following Fettes et al. - Jeremy F. Alm, Jun 08 2016
Entry revised by N. J. A. Sloane, Jun 12 2016
a(4) and a(5) deleted (since they are not known), a(0) prepended by Pontus von Brömssen, Aug 01 2021

A225231 Schur numbers S(3,n).

Original entry on oeis.org

9, 16, 23, 37, 53, 71, 93, 119, 147, 177, 211, 249, 289, 331, 377, 427, 479, 533, 591, 653, 717, 783, 853, 927, 1003, 1081, 1163, 1249, 1337, 1427, 1521, 1619, 1719, 1821, 1927, 2037, 2149, 2263, 2381, 2503, 2627, 2753, 2883, 3017, 3153, 3291, 3433

Offset: 3

Eric M. Schmidt, May 03 2013

a(n) is, by definition, the least positive m such that if {1,...,m} is written as a disjoint union of sets A and B, then either A contains 3 distinct numbers, one the sum of the other two, or B contains n distinct numbers, one the sum of the other n - 1.

Eric M. Schmidt, Table of n, a(n) for n = 3..1000
Tanbir Ahmed, Michael G. Eldredge, Jonathan J. Marler, and Hunter S. Snevily, Strict Schur Numbers, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 13, Paper A22, 2013.
Index entries for linear recurrences with constant coefficients, signature (3,-4,4,-3,1).

Cf. A030126, A045652, A072842.

Join[{9,16},LinearRecurrence[{3,-4,4,-3,1},{23,37,53,71,93},45]] (* Ray Chandler, Feb 13 2014 *)

def A225231(n) : return 9 if n == 3 else 16 if n == 4 else (3*n^2 - 7*n)//2 + [3,3,4,4][n%4]

For n >= 5, a(n) = 3n^2/2 - 7n/2 + c, where c = 3 if n == 0,1 (mod 4), else c = 4.

G.f.: x^3*(3*x^6-7*x^5+3*x^4+4*x^3-11*x^2+11*x-9) / ((x-1)^3*(x^2+1)). - Colin Barker, May 16 2013

cp's OEIS Frontend

A072842 Largest m such that we can partition the set {1,2,...,m} into n subsets with the property that we never have a+b=c for any distinct elements a, b, c in one subset.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A030126 Schur's numbers (version 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A003323 Multicolor Ramsey numbers R(3,3,...,3), where there are n 3's.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A225231 Schur numbers S(3,n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Sage

Formula

A011080 Decimal expansion of 4th root of 89.

Views

Author

Keywords

Comments

Links

Programs

PARI

A365190 The weak Schur numbers for 2-coloring.

Views

Author

Keywords

Comments

Links

Crossrefs

A365191 The weak Schur numbers for 3-coloring.

Views

Author

Keywords

Comments

Links

Crossrefs