Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

share|improve this question
    
My guess is for n=2k, one will have (2lcm(1,...,k),P_pi(n)/P_pi(k)) as a near optimal pair, where the last term is my way of writing the product of primes at most n and more than k. Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2012.05.31 –  Gerhard Paseman Jun 1 '12 at 1:01
    
I may need to replace 2 by P_pi(sqrt(n)), but hopefully the idea comes across. Gerhard "Still Packing Circles In Circles" Paseman, 2012.05.31 –  Gerhard Paseman Jun 1 '12 at 1:05
    
@Gerhard, you may need to involve the prime powers between $k$ and $n$. E.g., for $k=7$, neither $2L(7)=840$ nor $(11)(13)=143$ is a multiple of 9. –  Gerry Myerson Jun 1 '12 at 2:01
    
Yes, but between k and 2k lcm(1...k) should be short at most one occurence of each small prime factor up to sqrt(2k), thus my tweak regarding P_pi(sqrt(n)). Gerhard "Ask Me About System Design" Paseman, 2012.05.31 –  Gerhard Paseman Jun 1 '12 at 2:13
2  
Small quibble: $L(k)$ is not really asymptotic to $e^k$. However, $L(k) = e^{(1 + o(1))k}$ is true. –  Woett Jun 1 '12 at 8:23

4 Answers 4

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$.

share|improve this answer

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$

share|improve this answer
    
For small values, one has to take care in choosing Q so as to satisfy the divisibility property (hopefully s takes care of that, but it is wise to put limits on such Q). If one is willing to do small values by hand and use your tweak for all large values, I agree with the feeling that s does not need to be more than 2, but there will be more choices for Q as n grows. Gerhard "Ask Me About System Design" Paseman, 2012.06.01 –  Gerhard Paseman Jun 1 '12 at 15:35
    
As I defined it $Q$ can be any divisor of $P$. Here $P$ is exactly the product of the primes $p$ such that $p,2p,\cdots,sp$ are all the multiples we need. What $s$ takes care of is not $Q$, it is (the prime divisors of) $P/Q.$ –  Aaron Meyerowitz Jun 1 '12 at 22:00

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

share|improve this answer
    
Indeed, there is a certain "balancing of prime products" which reminds me of computing the order of the largest element in the group S_n, the symmetric group on n letters. Note in the example above I could choose 11 and 22 instead of 13 and 26. Gerhard "Ask Me About System Design" Paseman, 2012.05.31 –  Gerhard Paseman Jun 1 '12 at 2:36
    
This algorithm always gives $ab=L$. That is, I'm sure, suboptimal for $k=10$; maybe it's suboptimal for infinitely many $k$; maybe it's "badly" suboptimal for large $k$. I don't have any strong intuitions on this. But what's worse is that (depending on how one defines "happy") it doesn't guarantee $a,b$ have the property. Take $n=10$, start with 1 and 2520, go to 7 and 360, then 35 and 72, and neither is divisible by 10. –  Gerry Myerson Jun 1 '12 at 3:36
    
Good catch. I shall change it to 2*p <= n, which should guarantee the divisibility property. For small n, this algorithm does not give optimal results for sure. For large n also the results are suboptimal, but I imagine they are not very far from the desired results. I like having ab=L, but you are welcome to provide an alternative that gives ab=cL for some appropriate small positive integer c. Gerhard "Ask Me About System Design" Paseman, 2012.05.31 –  Gerhard Paseman Jun 1 '12 at 4:04
    
Thanks. You might be right, this might not be far from optimal, but, again, I don't have a good intuition about it. For $n=28$ I believe the new stopping rule gives you 10810800 and 7429, which looks pretty bad. –  Gerry Myerson Jun 1 '12 at 6:09
1  
The product of the primes between $n/2$ and $n$ is of magnitude $e^{(1/2+o(1))k}$. So this gives $a+b=e^{(1/2+o(1))k}$, right? Or am I misunderstanding the algorithm? –  Woett Jun 1 '12 at 8:40

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.

share|improve this answer
    
One can improve the bounds greatly by letting $A$ be the product of all primes between $y$ and $k$, where $y$ is a parameter that can be chosen more precisely. Imagine starting $y$ at $k/2$ and then moving it up or down to more equally balance $A$ with $L/A$. Since moving $y$ past a prime changes $A$ and $L/A$ by only about $k/2$, this procedure should allow $A$ to be chosen so that the maximum is less than $\sqrt{L(k)k/2}$. Still not quite as sharp as the OP wanted, but further micro-optimization games are surely possible (switch one large prime with two small primes, etc.) –  Greg Martin Jun 3 '12 at 20:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.