A lower bound for weak Schur numbers with a deterministic algorithm

Abstract Given a positive integer K, the weak Schur problem is to find the largest weakly sum-free K-partition of positive integers. Our goal is to increase known values of n for which the set { 1 , … , n } can be divided into sum-free sets, i.e. sets for which there are no three distinct elements x, y, z in the same set such that x + y = z . Our main contribution consists in designing a recursive deterministic algorithm which improves the results reported in the literature. It constructs a solution out of “perfect” or, at times, “perforated” series of integers using arbitrary rules. We call it the Deterministic Weak Schur Series (DWSS) algorithm. When analyzing our algorithm, we use the Gros sequence to bound from above the number of operations it executes. Consequently, we prove that its complexity is in O ( 3 3 K ) . With DWSS, we discovered larger weakly sum-free partitions, breaking the literature records for K = 8 to K = 12 . We next hybridize DWSS by stringing it together with a Monte Carlo-based method which explores the neighborhood of the solution obtained deterministically. We call it the Randomized Weak Schur Series (RWSS). As this algorithm requires more computational effort than DWSS, we are not able to compute partitions for K > 10 . We exceed our own DWSS results for K = 8 to K = 10 .

• Publication year

  2018

• Venue

  J. Discrete Algorithms

• Publication date

  2018-07-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.jda.2018.10.002
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Tower of Hanoi

  2020cited by this paper
• An Abstract Procedure to Compute Weak Schur Number Lower Bounds

  2015influential reference
• The Tower of Hanoi - Myths and Maths

  2013cited by this paper
• Investigating Monte-Carlo Methods on the Weak Schur Problem

  2013cited by this paper
• Weak Schur numbers and the search for G.W. Walker's lost partitions

  2012cited by this paper
• A Multilevel Tabu Search with Backtracking for Exploring Weak Schur Numbers

  2011cited by this paper
• On an extension of a theorem of Schur

  2002cited by this paper
• On stirling numbers of the second kind

  1969cited by this paper
• Elementary Theory of Numbers

  1964cited by this paper
• An Analytic Geometry for N Variables

  1945cited by this paper

• No citing papers are available for this paper.