3
$\begingroup$

Suppose we would like to compute an approximate prime factorization of a large integer x in the sense that the difference between x and its approximation is minimized. A naive way to state the problem in Mathematica is as follows.

n = 50;
x = RandomInteger[10^100];
vars = Map[z[#] &, Range[n]];
f = Abs[Times@@Map[Prime[#]^z[#] &, Range[n]] - x];
cons = Map[# >= 0 &, vars];
NMinimize[{f, cons}, vars \[Element] Integers]

The result is not very convincing and simply increasing n does not help. Do you have a better way to solve the problem?

Update: To account for the criticism presented by @yarchik, let me define the problem more precisely by demanding that the largest prime $p$ usable in the factorization must satisfy $10^p \leq x$. The naive Mathematica formulation above can be adapted as follows (being still naive but more precise).

x = RandomInteger[10^100];
p = {2};
While[NextPrime@Last@p <= Floor@Log[10, x], AppendTo[p, NextPrime@Last@p]];
n = Length[p];
vars = Map[z[#] &, Range[n]];
f = Abs[Times@@Map[#[[1]]^#[[2]] &, Thread[{p, vars}]] - x];
cons = Map[# >= 0 &, vars];
NMinimize[{f, cons}, vars \[Element] Integers]

Besides a better method to address this problem, I am also interested in lower and upper bounds of the solution for a given x.

Update 2: @DanielLichtblau suggested an encoding as knapsack problem which indeed improves the result obtained by NMinimize. One way to compute the resulting vars rules is as follows.

Thread[vars -> KnapsackSolve[Thread[{Log[p], Log[p]}], Log[x]]]
Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Not directly connected to you question, using indexed variables such as z[1], z[2] would enhanced the readability of your code. Another point is that there is an obvious limit to your function f that you try to minimize. Take the factors to be 2 and [x/2]. The error is at most 1. In other words, you need a better target function. $\endgroup$ Commented Jul 18, 2021 at 21:00
  • $\begingroup$ @yarchik: Thanks, I updated the formulation to increase readability. I would like the factors to be small compared to x. Are you aware of an upper/lower bound to the optimization problem given x and n (or a list of factors alternatively)? $\endgroup$ Commented Jul 18, 2021 at 21:25
  • 2
    $\begingroup$ Maybe set it up as a knapsack problem, using nonnegative integer sums of logs of small primes to approximate the log of the target integer. $\endgroup$ Commented Jul 19, 2021 at 4:38
  • $\begingroup$ @DanielLichtblau: Thank you, great suggestion that improves the result and is even optimal if KnapsackSolve is optimal. If you like to write an answer, I will accept it. In the meantime, I mention your solution in the question. $\endgroup$ Commented Jul 19, 2021 at 20:18
  • $\begingroup$ Good to see it works. I cannot write it up as a real answer because I am away from Mathematica for another week. Since you worked out the details, it would be fine for you to write as a response. Certainly I would not be offended. $\endgroup$ Commented Jul 19, 2021 at 21:43

0

Reset to default

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.