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

Offset

1,1

Comments

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

References

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

Links

Table of n, a(n) for n=1..5.

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.

G. W. Walker, Solution to the problem E985, American Mathematical Monthly, Vol. 59 (1952), p. 253.

Formula

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

Example

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]

Crossrefs

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

Cf. A118771, A297023.

Sequence in context: A290926 A018042 A304304 * A303861 A138387 A354176

Adjacent sequences: A072839 A072840 A072841 * A072843 A072844 A072845

Keyword

nonn,more,nice,hard

Author

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

Extensions

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

Status

approved