Universal number partition problem with divisibility

Lisa Berger, Moshe Dror, James Lynch

Research output: Contribution to journalArticlepeer-review


We examine a version of the Universal Number Partition Problem with a divisibility property referred to as the Universal Shelf Packing Problem (USPP). We show that if a shelf length is a product of powers of two primes the USPP is always partitionable. In the case where the shelf length is a product of three distinct primes we propose an efficient scheme to determine when such a case is not partitionable. We also show that a shelf length that is a product of powers of four or more primes always has at least one partition failure. Our analysis uses elementary number theory, known results related to the linear Diophantine Frobenius problem, and a new result on Frobenius gaps.

Original languageEnglish (US)
Pages (from-to)1692-1698
Number of pages7
JournalDiscrete Mathematics
Issue number10
StatePublished - May 28 2012
Externally publishedYes


  • Frobenius problem
  • Integer partitions
  • Packing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Universal number partition problem with divisibility'. Together they form a unique fingerprint.

Cite this