Small pairs a, b, every integer up to k dividing at least one of them - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T16:52:41Z http://mathoverflow.net/feeds/question/98529 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/98529/small-pairs-a-b-every-integer-up-to-k-dividing-at-least-one-of-them Small pairs a, b, every integer up to k dividing at least one of them Gerry Myerson 2012-06-01T00:16:02Z 2012-06-03T04:53:20Z <p>My question is essentially the $m=2$ case of <a href="http://mathoverflow.net/questions/98330/what-is-the-smallest-k-such-that-two-disjoint-sets-remain-unequal-when-element" rel="nofollow">this question</a>. </p> <p>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. </p> <p>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? </p> <p>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&amp;a&amp;b&amp;a+b&amp;ab/L\cr3&amp;2&amp;3&amp;5&amp;1\cr4&amp;3&amp;4&amp;7&amp;1\cr5&amp;5&amp;12&amp;17&amp;1\cr6&amp;5&amp;12&amp;17&amp;1\cr7&amp;12&amp;35&amp;47&amp;1\cr7&amp;28&amp;30&amp;58&amp;2\cr8&amp;24&amp;35&amp;59&amp;1\cr9&amp;35&amp;72&amp;107&amp;1\cr10&amp;70&amp;72&amp;142&amp;2\cr11&amp;77&amp;360&amp;437&amp;1\cr12&amp;77&amp;360&amp;437&amp;1\cr13&amp;360&amp;1001&amp;1361&amp;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. </p> <p>I have checked the Online Encyclopedia of Integer Sequences for $a$, $b$, and $a+b$, finding nothing. </p> <p>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....</p> <p>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$. </p> http://mathoverflow.net/questions/98529/small-pairs-a-b-every-integer-up-to-k-dividing-at-least-one-of-them/98533#98533 Answer by Gerhard Paseman for Small pairs a, b, every integer up to k dividing at least one of them Gerhard Paseman 2012-06-01T02:28:06Z 2012-06-01T04:14:20Z <p>Not a definitive answer, but the following pair should set the bar for finding small pairs.</p> <p>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:</p> <pre><code>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' &lt;= n then stop # p' is the largest prime less than p if (b is 1) then stop </code></pre> <p>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.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2012.05.31</p> http://mathoverflow.net/questions/98529/small-pairs-a-b-every-integer-up-to-k-dividing-at-least-one-of-them/98551#98551 Answer by Aaron Meyerowitz for Small pairs a, b, every integer up to k dividing at least one of them Aaron Meyerowitz 2012-06-01T08:50:05Z 2012-06-01T14:18:30Z <p>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)$ </p> <p>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)$</p> <p>It is hard to say what qualifies as nearly optimal. A refined version @Gerhard's method is</p> <ul> <li><p>pick a small $s$ (<strong>probably just</strong> $1$ or $2$) and let $\ell$ be the lcm of $1,2,\cdots,s$</p></li> <li><p>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}$.</p></li> <li><p>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})$</p></li> <li><p>see if you can do better with a slightly smaller or larger $s$.</p></li> </ul> <p><strong>LATER</strong> 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$.</p> <p>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$</p> <p>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$</p> <p>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$</p> <p>Of course the same $a,b$ can work for a run of $n$ values such as $113-118$</p> http://mathoverflow.net/questions/98529/small-pairs-a-b-every-integer-up-to-k-dividing-at-least-one-of-them/98608#98608 Answer by Douglas Zare for Small pairs a, b, every integer up to k dividing at least one of them Douglas Zare 2012-06-01T22:13:04Z 2012-06-03T04:53:20Z <p>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))$.</p> <p>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$.</p> <p>Also, for finitely many $n$, it could be that $\max(a,b)$ is minimized when $GCD(a,b) \gt 2$.</p> <p>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)$.</p> <p>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)}$. </p> <p>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$ <a href="http://en.wikipedia.org/wiki/Prime_gap" rel="nofollow">there is a prime between $x$ and $x+x^{2/3}$</a>. 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$. </p> http://mathoverflow.net/questions/98529/small-pairs-a-b-every-integer-up-to-k-dividing-at-least-one-of-them/98612#98612 Answer by Will Sawin for Small pairs a, b, every integer up to k dividing at least one of them Will Sawin 2012-06-01T22:37:54Z 2012-06-01T22:37:54Z <p>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)$.</p> <p>Thus, if $A(k)$ is close to $\sqrt{L(k)}$, then the bounds are sharp.</p> <p>$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$. </p> <p>$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.</p>