sum of distinct primes


by chhitiz
Tags: distinct, primes
chhitiz
chhitiz is offline
#1
Mar29-09, 12:47 PM
P: 221
i observed that every composite no. with exception of 4 and 6 can be expressed as sum of distinct prime no.s. eg: 200=103+97 100=53+47 25=13+7+5
is this true? is there any theorem stating as such?
Phys.Org News Partner Science news on Phys.org
NASA's space station Robonaut finally getting legs
Free the seed: OSSI nurtures growing plants without patent barriers
Going nuts? Turkey looks to pistachios to heat new eco-city
AUMathTutor
AUMathTutor is offline
#2
Mar29-09, 10:41 PM
P: 490
Interesting question!

It seems true. Maybe you could prove it using induction?

The base cases could be integers from 1 to 20, say, by just showing the sums.

Then you could assume that it works for all composite numbers up to a composite number k.

Then does it work for the next composite number? Well, look at the largest prime number less than it. If composite - prime is not 1 or 4 or 6, then the sum can certainly be expressed as prime + (sum for the difference composite - prime, which can definitely be done... if the difference is prime, just take the prime, otherwise, the inductive hypothesis covers it). If the difference is 1 or 4 or 6, try the next prime number below the one you just tried. If this isn't 4 or 6, do the same thing. If it is, try the next lower prime number. And etc.

21 = composite, 19 = prime, diff = 2, done with sum = 19 + 2.

22 = composite, 19 = prime, diff = 3, done with sum = 19 + 3.

24 = composite, 23 = prime, diff = 1. Try 19 = prime, then diff = 5 and done with 19 + 5.

25 = composite, 23 = prime, diff = 2, done with 23 + 2.

26 = composite, 23 = prime, diff = 3, done with 23 + 3.

27 = composite, 23 = prime, diff = 4, try 19 = prime, diff = 9, done with 19 + psum(9) = 19 + 7 + 2.

etc.

This is just a sketch, but I think it should work. Does anybody have any comments?
CRGreathouse
CRGreathouse is offline
#3
Mar29-09, 11:19 PM
Sci Advisor
HW Helper
P: 3,680
You can prove this with Bertrand's postulate.

mathmate
mathmate is offline
#4
Apr4-09, 04:43 PM
P: 366

sum of distinct primes


Yes, indeed.
It also follows from Bertrand's postulate that the number of such distinct primes does not exceed log2(N), where N is the original number to be decomposed.
Am I correct?
epenguin
epenguin is offline
#5
Apr4-09, 05:43 PM
HW Helper
epenguin's Avatar
P: 1,932
This is almost identical to 'Goldbach's conjecture' which is more than two and a half centuries old, famous, and has never been proved, so you are unlikely to.
mathmate
mathmate is offline
#6
Apr4-09, 07:08 PM
P: 366
This one is 'easier' in the sense that there is no limit on the number of primes that make the sum, just that they are distinct, whilw Goldback's conjecture restricts to two primes. It seems to me that Bertrand's postulate is sufficient for the proof.


Register to reply

Related Discussions
factors of product of n distinct primes Linear & Abstract Algebra 7
Distinct Eigenvalues Precalculus Mathematics Homework 4
Let A be A set of n Distinct Elements. Calculus & Beyond Homework 2
distinct primes Calculus & Beyond Homework 1
(distinct eigenvalues) help! Calculus & Beyond Homework 12