Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose you are given a number $n$ and told that the sum of its prime factors is $s$. I'm looking for an efficient algorithm that checks the truth of the statement.

Obviously one can simply calculate the factorization of $n$, add, then check if the result is equal to $s,$ but it seems that the problem can be easier. For example, if $s\approx n/100$ then $n$ must be contain at least one large prime which can be discovered by trial division. Can this be formalized? Are there other properties that can be used?

In my immediate case the sum is with multiplicity (so the sum of the prime factors of 1024 is 20) but I would be interested in the case where multiplicity is ignored (giving 2). Similarly, in the problem at hand I am interested in small n ($n<10^{12}$) but approaches that apply to larger numbers are welcome.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

This isn't state of the art, but for your purposes it may be sufficient. You can implement Sieve of Eratosthenes using a dynamic programming approach.

It obviates the need to do any trial division and instead gives you trade off between upfront initialization and, roughly speaking, constant time look-up.

Let $T[i]$ denote the smallest prime, $p$, factor of $i$. To find the total factoring of $i$, start at $T[i]$ and record its value. Then, go to $T[ i / T[i] ]$ and record its value. If $i = T[i]$ terminate, otherwise continue until it does.

Take a second pass over the factoring table to evaluate the sum of factors in a similar way to build a sum of factors look-up table.

This process should take 3-5 secs (depending on your hardware) to build the sum of factors for all n between two and $10^8$.

Downside to this approach is that is not easily distributed or parallelized.

For a more concrete implementation, you can read my write-up of this approach from a couple years ago: http://antimatroid.wordpress.com/2009/04/01/integer-factorization-by-dynamic-programming-with-number-theoretic-applications/

share|improve this answer

It's an interesting problem. Let's say n has hundred digits. You can easily check and remove all prime factors let's say up to 100 million and change n and s accordingly. If s is even then n could be the product of just two primes; you have n = pq and s = p+q, that gives you a quadratic equation which is easily solved.

So we end up with a large number n and at least 3 (s odd) or at least 4 (s even) prime factors adding up to s. If s is very large then it is easy: Let's say n = 100 digits, s = 70 digits. If p is the largest prime factor, then it is at least close to s, say 0.99 s. The product of the other factors is at most n / (0.99 s), with the one or two smallest factors > 10^8, which gives a limit for the largest factor. With that, we can get a much better estimate for p, which gives a much better estimate for the smaller factors, and so on. I'd say for large s this is a good starting point.

share|improve this answer

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.