Report Number: CS-TR-72-274
Institution: Stanford University, Department of Computer Science
Title: Linear combinations of sets of consecutive integers.
Author: Klarner, David A.
Author: Rado, Richard
Date: March 1972
Abstract: Let k-1,$m_1, \ldots ,m_k$ denote non-negative integers, and suppose the greatest common divisor of $m_1, \ldots ,m_k$ is 1. We show that if $S_1, \ldots ,S_k$ are sufficiently long blocks of consecutive integers, then the set $m_1 S_1 + \ldots\ m_k S_k$ contains a sizable block of consecutive integers. For example, if m and n are relatively prime natural numbers, and u, U, v, V are integers with U-u $\geq$ n-1, V-v $geq$ m-1, then the set m{u,u+1, $\ldots$,U} + n{v,v+1, $\ldots$,V} contains the set {mu + nv - $\sigma$(m,n), $\ldots$,mU + nV - $\sigma$(m,n)} where $\sigma${m,n) = (m-1)(n-1) is the largest number such that $\sigma$(m,n)-1 cannot be expressed in the form mx + ny with x and y non-negative integers.