Maximum consecutive multiples of coprimes

71 Views Asked by At

Given a set of coprimes, can we calculate a value or a limit for the maximum number of consecutive multiples of these values that can possibly occur?

Now, given the same set of coprimes, if each value initiates two sequences of multiples with different starting points, can we calculate the maximum in that case?

For example, if our set is {5, 7, 11, 13}, and multiples of 5 start at 5 and 6, multiples of 7 start at 7 and 8, multiples of 11 start at 11 and 12, and multiples of 13 start at 13 and 14, what's the maximum unbroken stretch of multiples that can occur?

1

There are 1 best solutions below

0
On

A simple inclusion-exclusion argument says that, for an interval of $x$ numbers, with two residue classes from each of $5,7,11,13$, there must be enough contributions to fill the interval. So, note the positive terms involve the ceiling function, and the negative terms involve the floor function: $$x\le 2(\lceil x/5\rceil+\lceil x/7 \rceil+\lceil x/11\rceil+\lceil x/13\rceil)\\ -4(\lfloor x/35\rfloor +\lfloor x/55\rfloor+\lfloor x/65\rfloor +\lfloor x/77\rfloor + \lfloor x/91\rfloor + \lfloor x/143\rfloor) \\ +8(\lceil x/385\rceil + \lceil x/455\rceil + \lceil x/715\rceil + \lceil x/1001\rceil \\ -16\lfloor x/5005\rfloor$$ If my graph is correct, that means $x\le139$ would be the widest possible interval for this set of coprime numbers $\{5,7,11,13\}$.
A simpler calculation, that uses $\lceil z\rceil \lt z+1$ and $\lfloor z\rfloor \gt z-1$, is $$x\lt\frac{3^4-1}{\frac35\frac57\frac9{11}\frac{11}{13}}=269.629...$$ However, as I hint at in comments, the actual widest possible interval covered is $24$ numbers. That involved a computer search through all possible sets of the eight residue classes $\{5k+a,5k+b,7k+c,7k+d,11k+e,11k+f,13k+g,13k+h\}$. There are $10\times21\times55\times78$ sets. My routine looks at the numbers from $1$ to $10010=2(5\times7\times11\times13)$. The pattern repeats every 5005 numbers, so two cycles will find all the intervals.