# Writing numbers as sum of primes

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Dec 6th 2009, 02:41 PM
keityo
Writing numbers as sum of primes
For this problem include 1 as a prime. Prove that every positive integer can be written as a sum of one or more distinct primes.

I'm a bit stumped...
• Dec 6th 2009, 02:46 PM
VonNemo19
Quote:

Originally Posted by keityo
For this problem include 1 as a prime. Prove that every positive integer can be written as a sum of one or more distinct primes.

I'm a bit stumped...

Having 1 included is nice.

Note that the odd natural numbers can be written as

\$\displaystyle 2n+1\$

And the evens

\$\displaystyle 2n+2\$.

Taken together, the odds and evens make the naturals.

And there you have it. I'm sure that you can formalize this argument.
• Dec 6th 2009, 04:19 PM
Bruno J.
Here is a proof by induction, using relatively heavy machinery. It clearly holds for \$\displaystyle n=1\$ by assumption. Suppose you want to write \$\displaystyle n\$ as a sum of distinct primes, and that you have managed to write all numbers up to \$\displaystyle n-1\$ as a sum of distinct primes. By Bertrand's postulate, there is a prime \$\displaystyle n \geq p >n/2\$. Then \$\displaystyle n-p < n/2\$. Now write \$\displaystyle n-p\$ as a sum of distinct primes, say \$\displaystyle n-p=p_1+...+p_k\$. Clearly none of the \$\displaystyle p_j\$'s are equal to \$\displaystyle p\$ because \$\displaystyle p>n/2\$ and \$\displaystyle n-p<n/2\$. Thus \$\displaystyle n=p+p_1+...+p_k\$ is a representation of \$\displaystyle n\$ as a sum of distinct primes. \$\displaystyle \square\$
• Dec 12th 2009, 08:56 AM
chiph588@
Quote:

Originally Posted by Bruno J.
Here is a proof by induction, using relatively heavy machinery. It clearly holds for \$\displaystyle n=1\$ by assumption. Suppose you want to write \$\displaystyle n\$ as a sum of distinct primes, and that you have managed to write all numbers up to \$\displaystyle n-1\$ as a sum of distinct primes. By Bertrand's postulate, there is a prime \$\displaystyle n \geq p >n/2\$. Then \$\displaystyle n-p < n/2\$. Now write \$\displaystyle n-p\$ as a sum of distinct primes, say \$\displaystyle n-p=p_1+...+p_k\$. Clearly none of the \$\displaystyle p_j\$'s are equal to \$\displaystyle p\$ because \$\displaystyle p>n/2\$ and \$\displaystyle n-p<n/2\$. Thus \$\displaystyle n=p+p_1+...+p_k\$ is a representation of \$\displaystyle n\$ as a sum of distinct primes. \$\displaystyle \square\$

Aside from your base case, you didn't use the fact that \$\displaystyle 1 \$ was considered a prime. Therefore if we started at \$\displaystyle n=2 \$ we could have the same theorem without considering \$\displaystyle 1 \$ as a prime. But \$\displaystyle 4=3+1 \$ is the only way to write \$\displaystyle 4 \$ as a sum of distinct primes.
With that said, could you explain where else you used \$\displaystyle 1 \$ as a prime in this proof?
• Dec 12th 2009, 04:52 PM
Bruno J.
Throughout the proof I supposed 1 as prime, and the assumption is necessary when we want to write \$\displaystyle n-p\$ as a sum of distinct primes because we could very well have \$\displaystyle n-p=1\$ as you noticed.
• Dec 13th 2009, 09:56 AM
wonderboy1953
Can't be proven
"Prove that every positive integer can be written as a sum of one or more distinct primes"

Consider the even numbers. Goldbach's conjecture says that every even number can be written as the sum of primes. Problem here is that no one has yet proven Goldbach's conjecture.
• Dec 13th 2009, 10:20 AM
chiph588@
Goldbach's Conjecture doesn't consider the distinctness of the primes being summed though.
• Dec 13th 2009, 10:37 AM
Moo
Otherwise, without including 1 as a prime, you can make it as a sum of 2's (for even numbers) or a sum of 2's+3 (for odd numbers)

:P
• Dec 13th 2009, 11:41 AM
wonderboy1953
Distinctiveness
Implicitly, Goldbach's Conjecture does consider distinctiveness because, besides 2, every even number 4 or greater when divided by 2, yields only even numbers which can't be prime so the only other choice for possible prime numbers must be distinct numbers.
• Dec 13th 2009, 01:22 PM
Bruno J.
Quote:

Originally Posted by wonderboy1953
"Prove that every positive integer can be written as a sum of one or more distinct primes"

Consider the even numbers. Goldbach's conjecture says that every even number can be written as the sum of two primes. Problem here is that no one has yet proven Goldbach's conjecture.

Fixed!
• Dec 13th 2009, 01:25 PM
Bruno J.
Quote:

Originally Posted by wonderboy1953
Implicitly, Goldbach's Conjecture does consider distinctiveness because, besides 2, every even number 4 or greater when divided by 2, yields only even numbers which can't be prime so the only other choice for possible prime numbers must be distinct numbers.

Huh? Twice an odd number is even; if you divide it by 2 what do you get?
• Dec 13th 2009, 01:49 PM
chiph588@
Quote:

Originally Posted by wonderboy1953
Implicitly, Goldbach's Conjecture does consider distinctiveness because, besides 2, every even number 4 or greater when divided by 2, yields only even numbers which can't be prime so the only other choice for possible prime numbers must be distinct numbers.

\$\displaystyle 4=2+2 \$ is the only way to express \$\displaystyle 4 \$ as the sum of primes.
• Dec 13th 2009, 06:26 PM
Shanks
Bruno, is the Bertrand's postulate proved or not yet?
• Dec 13th 2009, 08:36 PM
Bruno J.
Of course! Or else I would have never used it to prove something else.
It was first proven by Chebyshev and then by Erdös in a more elementary fashion.
• Dec 16th 2009, 09:06 AM
wonderboy1953
Skip Goldbach's Conjecture
Goldbach"s Conjecture says every positive integer above 1 (counting 1 as a prime number) can be written as the sum of two prime numbers while Keityo puts forth the problem as "Prove that every positive integer can be written as a sum of one or more distinct primes." This lets out Goldbach's Conjecture as applying to this problem (I get onto the internet from my library which has a time restriction so I didn't get a chance to carefully review what I've written - sorry about that).
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last