4

Let's say I have two natural numbers $n$ and $m$, both of which are exceeding large, and I want to determine which is smaller. Thankfully, I happen to know both of their prime factorizations, but they're composed of many terms to high powers, so it's infeasible for me to just multiply it out and determine which is smaller that way. Hence my question is: Is there any way to compare the magnitude of two numbers, knowing only their prime factors?

As a perhaps somewhat artificial example, take: $$n=67\times24977\times8598615939$$ $$m=2^5\times3^2\times5^5\times7^4\times13\times23^3\times421$$ Is there anyway to know $m>n$ from just those factorizarions apart from multiplying them out and comparing digits?

InsertCreativityHere
  • 83
  • 1
    why you want to know that – Tsemo Aristide Jun 11 '17 at 01:13
  • You could multiply subsets of the factors together and hope that you could get comparisons that work, for example: $2^4 \cdot 3 > 67$ – Zubin Mukerjee Jun 11 '17 at 01:15
  • Realistically, it will take you far longer to find the prime factorization than to compare the numbers. – infinitylord Jun 11 '17 at 01:16
  • 3
    You could take logarithms, and compute the (faster) sums instead of the product. – B. Mehta Jun 11 '17 at 01:16
  • 1
    @infinitylord I think the idea is that you already know the prime factorization, but not the full number. – Zubin Mukerjee Jun 11 '17 at 01:17
  • @B.Mehta Good idea, but I think just multiplying the numbers together must be faster than computing logarithms, no ? – Zubin Mukerjee Jun 11 '17 at 01:18
  • 1
    @ZubinMukerjee: I understand that, but I've never seen a problem where you know the prime factorization but not the number itself. This honestly just seems very arbitrary to me. – infinitylord Jun 11 '17 at 01:19
  • @ZubinMukerjee Potentially, but the logarithms may be more memory-efficient to store computationally and compare – B. Mehta Jun 11 '17 at 01:19
  • agreed, it does seem like there would be no situation in which this question would have a useful answer – Zubin Mukerjee Jun 11 '17 at 01:20
  • @TsemoAristide I'm working with primes over some various operations, and for some of those I've found ways to construct them using certain sets of the standard prime numbers. But I'm at a loss on how to go about ordering them all, or figuring out how many there are up to certain values. – InsertCreativityHere Jun 11 '17 at 01:26
  • 2
    @B.Mehta That would also certainly be using in dealing with all the powers, plus it shouldn't be too horrible to just make a table of logs of primes and store that... Good idea! – InsertCreativityHere Jun 11 '17 at 01:29
  • I think you'd have to take it on a case-by-case basis and there probably is no general algorithm that's always faster than multiplying – Gregory Grant Jun 11 '17 at 01:51

0 Answers0