1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Perhaps those voting to close could say a few words? $\endgroup$ Nov 8, 2011 at 12:28
  • $\begingroup$ @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? $\endgroup$ Nov 8, 2011 at 13:39
  • 1
    $\begingroup$ cf. mathoverflow.net/questions/79322 $\endgroup$ Nov 9, 2011 at 0:19
  • $\begingroup$ 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 $\endgroup$ Nov 16, 2011 at 18:42

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I was very pessimistic about this question; but this answer seems pretty neat. I wonder if "we" do know the prime factorisation though? $\endgroup$ Nov 8, 2011 at 11:46
  • 1
    $\begingroup$ If we don't know the prime factorization, then how do we know there are too many divisors for an exhaustive search? $\endgroup$ Nov 8, 2011 at 12:27
  • 3
    $\begingroup$ 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. $\endgroup$ Nov 8, 2011 at 14:58
  • $\begingroup$ 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 $\endgroup$ Nov 8, 2011 at 15:46
  • 1
    $\begingroup$ @G.Paseman: indeed, see mathoverflow.net/questions/79322 $\endgroup$ Nov 9, 2011 at 0:19
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$ Nov 8, 2011 at 17:49
  • $\begingroup$ 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. $\endgroup$
    – joro
    Nov 8, 2011 at 18:46
  • $\begingroup$ 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. $\endgroup$ Nov 8, 2011 at 19:19
  • $\begingroup$ 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.? $\endgroup$ Nov 8, 2011 at 21:53
  • $\begingroup$ OK, I had multiple nonsense but now I think it is correct (albeit not the nicest example of its type.) $\endgroup$ Nov 8, 2011 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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