8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ just to be clear, the sum of the prime factors of $4$ is $2$ right? $\endgroup$
    – Asinomás
    Dec 9, 2016 at 21:48
  • $\begingroup$ Yes, it's the sum without counting multiplicities. $\endgroup$
    – Xam
    Dec 9, 2016 at 22:08
  • $\begingroup$ I edited the question to avoid misunderstandings. $\endgroup$
    – Xam
    Dec 9, 2016 at 22:24

2 Answers 2

13
$\begingroup$

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\}$

$\endgroup$
5
  • 1
    $\begingroup$ Finally I read it and thank you so much. Your solution is very simple and clear. $\endgroup$
    – Xam
    Dec 9, 2016 at 22:33
  • $\begingroup$ happy to help XD $\endgroup$
    – Asinomás
    Dec 9, 2016 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, 2016 at 22:35
  • 1
    $\begingroup$ Although technically, the part "equivalent to […] of arbitrarily large size" is incorrect. :P $\endgroup$ Dec 9, 2016 at 22:35
  • $\begingroup$ Oh yeah! You're right :3 it should be: " of size larger than or equal to $10^{2012}$. $\endgroup$
    – Asinomás
    Dec 9, 2016 at 22:36
2
$\begingroup$

Slightly probabilistic:

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .