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.

  • $\begingroup$ just to be clear, the sum of the prime factors of $4$ is $2$ right? $\endgroup$ – Onir Dec 9 '16 at 21:48
  • $\begingroup$ Yes, it's the sum without counting multiplicities. $\endgroup$ – Xam Dec 9 '16 at 22:08
  • $\begingroup$ I edited the question to avoid misunderstandings. $\endgroup$ – 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\}$

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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