Small pairs a, b, every integer up to k dividing at least one of them

Question

My question is essentially the $m=2$ case of this question.

Given a positive integer $k$, I'm interested in (small) pairs of positive integers $a,b$ such that every positive integer up to (and including) $k$ is a factor of at least one of them. For example, for $k=10$, one such pair is $a=70$, $b=72$; every integer up to 10 is a factor of at least one of these two numbers.

It's easy to see that the product of any such pair must be a multiple of the least common multiple, call it $L(k)$, of $1,2,3,\dots,k$. It's known that $L(k)$ is asymptotic to $e^k$. Moreover, it's trivial to find a pair whose product is exactly $L(k)$; just take $a=1$, $b=L(k)$. This tells me that, for this problem, the product, $ab$, is not a good measure of how small the pair $a,b$ is. Two other measures that suggest themselves are the sum, $a+b$, and the maximum. Since the product is at least $L(k)$, the sum must be at least $2\sqrt{L(k)}$, and the maximum must be at least $\sqrt{L(k)}$. My question is, how sharp are these bounds?

I did a small amount of calculation by hand during a recent committee meeting, and arrived at these figures, given without any guarantee that they are, in fact, minimal: $$\matrix{k&a&b&a+b&ab/L\cr3&2&3&5&1\cr4&3&4&7&1\cr5&5&12&17&1\cr6&5&12&17&1\cr7&12&35&47&1\cr7&28&30&58&2\cr8&24&35&59&1\cr9&35&72&107&1\cr10&70&72&142&2\cr11&77&360&437&1\cr12&77&360&437&1\cr13&360&1001&1361&1\cr}$$ Note that for $k=7$ I have given two $a,b$ pairs, one with a smaller sum, the other with a smaller maximum.

I have checked the Online Encyclopedia of Integer Sequences for $a$, $b$, and $a+b$, finding nothing.

I suppose one could ask the same question for triples $a,b,c$ such that every integer up to $k$ is a factor of one of them, or quadruples, or....

The relation to question 98330 is as follows. With the notation used here, the sets $A=\lbrace a+1,b+1\rbrace$ and $B=\lbrace 1,a+b+1\rbrace$ are indistinguishable modulo $m$ for all $m$ up to $k$.

Answer 1

Claim: Among the pairs $a$ and $b$ so that $GCD(a,b)=2$ and every integer up to $n$ divides $a$ or $b$, the minimum value of $\max(a,b)$ is $\sqrt{2 L(n)}(1+o(1))$.

This leaves open the question of when it might be better with $(a,b)=1$. As I commented, if $(a,b)=1$, then $L(n/2) \prod p$ divides the even factor, where the product is over all primes with a power between $n/2$ and $n$, including $p=2$. In some numerical tests, $L(n/2) \gt \sqrt {L(n)}$. If this happens for large $n$, then $\max(a,b)$ is minimized with $(a,b)=2$.

Also, for finitely many $n$, it could be that $\max(a,b)$ is minimized when $GCD(a,b) \gt 2$.

To find a pair with $\max(a,b)$ close to $\sqrt{2L(n)}$, we consider a large collection of pairs with $(a,b)=2$ so that $3|a$, ranging from those with $a$ much less than $b$ to those with $a$ much greater than $b$, so that the ratio between each and the next larger is $1+o(1)$.

Let $a_0 = L(n)/\prod_{n/3 \lt \text{prime}~p \le n} p = L(\lfloor n/3 \rfloor) 2^\alpha \prod p$ where the product is over odd primes $p$ so that there is a power of $p$ between $n/3$ and $n$, and $2^\alpha$ is the quotient of the greatest power of $2$ up to $n$ by the greatest power of $2$ up to $n/3$, so $2^\alpha$ is $2$ or $4$. Since $L(n) \approx \exp(n)$, $L(n/3) \approx \sqrt[3]{L(n)} \ll \sqrt{L(n)}$. Also, for large $n$, $a_0 \ll \sqrt{L(n)}$, by Stirling's formula, for example. $a_0$ has been chosen so that not only does every integer from $1$ to $n$ divide $a_0$ or $2L(n)/a_0$, but every set $S$ of primes between $n/3$ and $n$ can be "added" to $a_0$ and it will still be the case that every integer up to $n$ divides $a_S = a_0 \prod_{p \in S}p$ or $2L(n)/a_S$. We want to choose $S$ so that $a_S$ is close to $\sqrt{2L(n)}$.

We need some mild density results on the primes between $n/3$ and $n$. (Edit: I had a weaker density condition earlier but I think that was insufficient.) It's enough to say that for sufficiently large $x$ there is a prime between $x$ and $x+x^{2/3}$. Using this, construct sets of primes $U$ and $V$ of equal size so that every ratio $u/v$ between a prime in $U$ and a prime in $V$ is between $1$ and $1+f(n)$, where $f(n)$ is $o(1)$, the product of all primes in $U$ divided by the product of all primes in $V$ is greater than $n$, and $a_V \lt \sqrt{2L(n)}$. The point is that if we start with all elements of $V$ in $S$, and no element of $U$ in $S$, we can increase $a_S$ by a factor of less than $1+f(n)$ by adding an element of $U$ to $S$ and removing an element of $V$ from $S$, and repeat to increase the magnitude by more than a factor of $n$. Then we can add a prime to $S$ which is not in $U$ or $V$, remove all elements of $U$ and put back all elements of $V$, which decreases the magnitude to at most $n$ times the original. In turn, we add each prime between $n/3$ and $n$ outside $V$ and $U$, and this gives us a sequence of magnitudes of $a_{S(i)}$ which starts below $\sqrt{2L(n)}$ and ends up above it without taking an upward step of a factor larger than $1+f(n)$, so there is some set of primes $T$ so that $a=a_T$ is between $\sqrt{2L(n)}$ and $\sqrt{2L(n)}(1+f(n))$, and $b = 2L(n)/a \lt a$.

Answer 2

For $n=27$ or $n=28$ one has the possible case $(a,b)=(10810800,7429)=(16\cdot27\cdot25\cdot7\cdot11\cdot13,17\cdot19\cdot23)$ That seems like the best one could do with $ab=L.$ Throwing a $2$ on the right allows $(831600,193154)=(16\cdot27\cdot25\cdot7\cdot11,2\cdot13\cdot17\cdot19\cdot23)$

A greedy approach for $n=29$ with $ab=2L$ gives $(a,b)=(831600,5601466)=(16\cdot27\cdot25\cdot7\cdot11,2\cdot13\cdot17\cdot19\cdot23\cdot29)$ However even better is $(2192400,2124694)=(16\cdot27\cdot25\cdot7\cdot29,2\cdot13\cdot17\cdot19\cdot23\cdot11)$

It is hard to say what qualifies as nearly optimal. A refined version @Gerhard's method is

• pick a small $s$ (probably just $1$ or $2$) and let $\ell$ be the lcm of $1,2,\cdots,s$

• start with $b=\ell P$ with $P$ the product of all primes $\frac{n}{s+1} \lt p \le n$ and $a$ the lcm of all $p^i \le n$ with $p \le \frac{n}{s+1}$.

• if $a \ge b$ then you can't do better with that $s$ (I think this always happens when $s=1$, I stopped checking after a while.) . Otherwise find a divisor $Q$ of $P$ which is as close as possible to $\sqrt{\frac{b}{a}}$ and use $(aQ,\frac{b}{Q})$

• see if you can do better with a slightly smaller or larger $s$.

LATER I am pretty sure that we only ever see $s=1$ and $s=2$. For $s=2$ and $n$ not too small it is possible to get $\frac{b}{a}$ very close to $1$.

If my program and reasoning is correct then up to $7 \le n \le 129$ it is best to have $s=1$ when $n=8-12, 17, 18, 22-26, 31-34, 43-46, 53-58, 61, 62, 71, 72, 81, 82, 119, 120$

it is best to have $s=1$ for $a+b$ but better to have $s=2$ for $\max(a,b)$ when $n=7, 13, 14, 75-80, 103-106$

For the other $76$ cases $n=15, 16, 19-21, 27-30, 35-42, 47-52, 59, 60$$63-70, 73, 74, 83-102, 107-118, 121-129$ it is best to have $s=2$

Of course the same $a,b$ can work for a run of $n$ values such as $113-118$

Answer 3

Not a definitive answer, but the following pair should set the bar for finding small pairs.

I tried in the comments above to define a pair in terms of products of primes (primorials $P_k$) and lcm, but it is actually simpler to do the following:

Set a = 1 and b = L = lcm(1,...,n)
While p is the largest prime dividing b do
   a = a*p
   b = b/p
   if (one is happy with the pair (a,b)) then stop
   if 2*p' <= n then stop # p' is the largest prime less than p
   if (b is 1) then stop

Of course, for large n one ends up with (L/q, q) where q is a product of enough primes, all of them larger than n/2. I imagine q is close to sqrt(L), but I do not have the asymptotics at hand. Letting n=30, one has q=215441 and L/q = 10810800, so one asks whether to divide one number by 13 and multiply the smaller by 26. I would be surprised if one could show q was asymptotically bad for the task, as opposed to just asymptotically suboptimal.

Gerhard "Ask Me About System Design" Paseman, 2012.05.31

Answer 4

Here is a quick asymptotic. Let $A(k)$ be the product of all $k/2>p\leq k$. Then $(L(k)/A(k),A(k))$ form a pair, as pointed out in different notation by Gerhard Paseman in the comments. This is because every $i\leq k$ is either a prime dividing $A(k)$ or coprime to $A(k)$.

Thus, if $A(k)$ is close to $\sqrt{L(k)}$, then the bounds are sharp.

$A(k)$ is easy to calculate with the prime number theorem. $\ln A(k)$ is a sum over the primes between $k/2$ and $k$ of the log of that prime, which is approximately $k-k/2=k/2$.

$L(k)=e^{(1+o(1))k}$. $A(k)=e^{(1/2+o(1))k}$. Thus the max of $a$ and $b$ is no more than $e^{(1/2+o(1))k}$, and the sum is no more than $2e^{(1/2+o(1))k}$. Getting the bounds tighter than that seems hard.