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

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

2012-06-01T00:16:02Z

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 by Gerhard Paseman for Small pairs a, b, every integer up to k dividing at least one of them

2012-06-01T02:28:06Z

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 by Aaron Meyerowitz for Small pairs a, b, every integer up to k dividing at least one of them

2012-06-01T08:50:05Z

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 by Douglas Zare for Small pairs a, b, every integer up to k dividing at least one of them

2012-06-01T22:13:04Z

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 by Will Sawin for Small pairs a, b, every integer up to k dividing at least one of them

2012-06-01T22:37:54Z

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.