Monday, May 9, 2016

divisibility - 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.


Answer




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

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...