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

Given 2 positive integers $n, l$ with $ l \leq n$, I am looking for a way to find the largest divisor $d$ of $n$, such as $d \leq l$.
Assume $n$ has too many divisors for an exhaustive search.
Thanks in advance


I have finally found the right algorithm for this problem
(Meet in the middle algorithm
http://community.topcoder.com/tc?module=Static&d1=hs&d2=match_editorials&d3=tchs07Semi)

Thank you for all the answers.

Here is a brief description.

BTW, the factorization of $n$ is known.
I factorize $n$ in 2 parts $n=n1 \times n2$ where $n1$ and $n2$ have roughly the same number of divisors.
I generate $d1$ = the divisors of $n1$ and $d2$ = the divisors of $n2$.
The number of divisors of $n1$ and $n2$ is roughly $\sqrt {} $ number of divisors of $n $

Then I use the aformentioned algorithm using lists $d1$ and $d2$

For example: Largest divisor of $16! \le 10^{13} = 6974263296000$

public static long ClosestDivisor(long n1, long n2, long target)
{
List<long> a = Divisors(n1);
a.Sort();
List<long> b = Divisors(n2);
b.Sort();

int i1 = 0;
int i2 = b.Count - 1;
long M = long.Zero;
while (i1 < a.Count && i2 >= 0)
{
    long P = a[i1] * b[i2];
    if (P > target)
        i2--;
    else
    {
        if (P > M)
            M = P;
        i1++;
    }
}
return M;
}

Philippe

share|improve this question
    
Perhaps those voting to close could say a few words? –  Gerry Myerson Nov 8 '11 at 12:28
    
@Gerry: I was probably too hasty-- your answer has convinced me of that. But I still don't quite understand what the question wants. For example, it would be great to have the questioner comment on whether your answer is a good answer for them? –  Matthew Daws Nov 8 '11 at 13:39
1  
cf. mathoverflow.net/questions/79322 –  Noam D. Elkies Nov 9 '11 at 0:19
    
The given algorithm is good at finding an approximate answer. When one has a candidate P less than target, one can then try exchanging a factor of P for a slightly larger factor of N/P. Gerhard "Ask Me About System Design" Paseman, 2011.11.16 –  Gerhard Paseman Nov 16 '11 at 18:42

2 Answers 2

Let's also assume that $l$ is too large for us to want to try $l,l-1,l-2,\dots$ until we find a divisor.

Let's also assume that we know the prime factorization of $n$, $n=\prod_1^mp_i^{r_i}$.

Then we want to maximize $\sum a_i\log p_i$, subject to $0\le a_i\le r_i$ and $\sum a_i\log p_i\le\log d$. Looks like a problem in integer programming, a topic on which there is a considerable literature available.

share|improve this answer
    
I was very pessimistic about this question; but this answer seems pretty neat. I wonder if "we" do know the prime factorisation though? –  Matthew Daws Nov 8 '11 at 11:46
1  
If we don't know the prime factorization, then how do we know there are too many divisors for an exhaustive search? –  Gerry Myerson Nov 8 '11 at 12:27
3  
Using binary search, it is easy to see that one can compute the smallest prime factor of $n$ in polynomial time with an oracle for the problem in question, and then we can divide it out and recurse. Thus, the problem is at least as hard as factorization under polynomial-time Turing reductions. –  Emil Jeřábek Nov 8 '11 at 14:58
    
A comment elsewhere by Noam Elkies likened this problem to integer knapsack, if I recall correctly. Gerhard "Ask Me About System Design" Paseman, 2011.11.08 –  Gerhard Paseman Nov 8 '11 at 15:46
1  
@G.Paseman: indeed, see mathoverflow.net/questions/79322 –  Noam D. Elkies Nov 9 '11 at 0:19

after a major correction: Now that the context has been described, Gerry's answer is just right. On the other hand: is $N!+1$ prime? Find the largest factor of $n=(N!)!$ which is less than or equal to $l=N!+1.$ If $N!+1$ is composite then that largest factor is $N!+1$ otherwise it is $N!$ That might not be a fair example but I had to put it in.

share|improve this answer
    
1. I don't know about fair, but it is not very illustrative. If you mean the smallest factor greater than N! + 2, that is more challenging. Gerhard "Ask Me About System Design" Paseman, 2011.11.08 –  Gerhard Paseman Nov 8 '11 at 17:49
    
I had to check simple properties of divisors and it was quite time consuming. The factorization was known, yet the number of divisors was big. –  joro Nov 8 '11 at 18:46
    
Ok now we know the context. For $M=N!$ or any other integer, the largest divisor of $M^2$ which is less than $M+2$ is $M+1$ if that number is composite and $M$ when $M+1$ is prime. –  Aaron Meyerowitz Nov 8 '11 at 19:19
    
Not following you. Let $M=7$, so $M+1$ is composite. The largest divisor of 49, less than 9, is 8? $M+1$ never divides $M^2$ for $M\gt0$. And in your answer, the smallest factor of $(N!)^2$, less than $N!+2$, is always 1. Did you mean, greatest factor of $(N!)^2$ etc., etc.? –  Gerry Myerson Nov 8 '11 at 21:53
    
OK, I had multiple nonsense but now I think it is correct (albeit not the nicest example of its type.) –  Aaron Meyerowitz Nov 8 '11 at 23:24

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.