# Numbers which are divisible by the sum of their prime factors.

I was checking some old problems from olympiads that I used to practice when I was in highschool and I found a problem that I couldn't solve (and still can't).

The question is: let's call a positive integer sunny if it's divisible by the sum of its prime factors. For example, $90=2.3^2.5$ is sunny because $2+3+5=10\mid 90$. Prove that there is a sunny number with at least $10^{2002}$ prime factors.

I think the number $10^{2002}$ has nothing special and then it's possible to prove that given a positive integer $k$, there is a sunny number $n$ with $\omega(n)\ge k$ (here $\omega(.)$ means the number of prime factors), but I have no ideas about how to approach this problem. Any help will be appreciated. Thanks in advance.

• just to be clear, the sum of the prime factors of $4$ is $2$ right? – Jorge Fernández Hidalgo Dec 9 '16 at 21:48
• Yes, it's the sum without counting multiplicities. – Xam Dec 9 '16 at 22:08
• I edited the question to avoid misunderstandings. – Xam Dec 9 '16 at 22:24

We call a set of prime numbers good if the sum of its elements has no prime divisor outside of $A$.

Your problem is clearly equivalent to proving there are good sets of arbitrarily large size. We prove that for every $n$, a good set of size $n$ or $n+1$ exists:

Consider the set $A=\{p_1,p_2,\dots p_n\}$ of the first $n$ primes and let $q$ be their sum. Notice that $q\leq n p_n$, so if $A$ is not good then $q=pm$ with $m<n$ and $p$ a prime larger than $p_n$. The set $\{p_1,p_2,\dots, p_n,p\}$ is therefore good, since the sum of its elements is $p(m+1)$, and since $m+1\leq n$ clearly all of its prime factors are among $\{p_1,p_2,\dots, p_n,p\}$

• Finally I read it and thank you so much. Your solution is very simple and clear. – Xam Dec 9 '16 at 22:33
• happy to help XD – Jorge Fernández Hidalgo Dec 9 '16 at 22:33
• Just make wonder why this problem was number six. Usually the last problem is the hardest one xd – Xam Dec 9 '16 at 22:35
• Although technically, the part "equivalent to […] of arbitrarily large size" is incorrect. :P – Daniel Fischer Dec 9 '16 at 22:35
• Oh yeah! You're right :3 it should be: " of size larger than or equal to $10^{2012}$. – Jorge Fernández Hidalgo Dec 9 '16 at 22:36

Slightly probabilistically:

Start with $2$ and add $10^{2002}-2$ large primes over (say) $1000$ to this (this total is even). Then check to see if any odd prime under $1000$ can add to this to make the sum into a new huge prime number $p_M$. If not, add in two more large primes and try again, until a reachable huge prime $p_M$ is found.

Then add $p_M$ into the total also. The total of the primes is $2p_M$ which also divides the product of all the contributing primes.