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.32.5 is sunny because 2+3+5=1090. Prove that there is a sunny number with at least 102002 prime factors.




I think the number 102002 has nothing special and then it's possible to prove that given a positive integer k, there is a sunny number n with ω(n)k (here ω(.) 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={p1,p2,pn} of the first n primes and let q be their sum. Notice that qnpn, so if A is not good then q=pm with $m

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...