1
$\begingroup$

Let $\mathbb P^1=\{1\}\cup\mathbb P$, the set of positive non composites. I have reason to believe that it is proved that all numbers greater than $6$ is a sum of distinct primes, and hence all $n\in\mathbb N^+$ is the sum of distinct numbers in $\mathbb P^1$. But is the latter possible to prove without the use of the prime number theorem?

 1 {{1}}
 2 {{2}}
 3 {{1,2},{3}}
 4 {{1,3}}
 5 {{2,3},{5}}
 6 {{1,2,3},{1,5}}
 7 {{2,5},{7}}
 8 {{1,2,5},{3,5},{1,7}}
 9 {{1,3,5},{2,7}}
10 {{2,3,5},{1,2,7},{3,7}}
11 {{1,2,3,5},{1,3,7},{11}}
12 {{2,3,7},{5,7},{1,11}}
13 {{1,2,3,7},{1,5,7},{2,11},{13}}
14 {{2,5,7},{1,2,11},{3,11},{1,13}}
15 {{1,2,5,7},{3,5,7},{1,3,11},{2,13}}
16 {{1,3,5,7},{2,3,11},{5,11},{1,2,13},{3,13}}
17 {{2,3,5,7},{1,2,3,11},{1,5,11},{1,3,13},{17}}
18 {{1,2,3,5,7},{2,5,11},{7,11},{2,3,13},{5,13},{1,17}}
19 {{1,2,5,11},{3,5,11},{1,7,11},{1,2,3,13},{1,5,13},{2,17},{19}}
20 {{1,3,5,11},{2,7,11},{2,5,13},{7,13},{1,2,17},{3,17},{1,19}}
21 {{2,3,5,11},{1,2,7,11},{3,7,11},{1,2,5,13},{3,5,13},{1,7,13},{1,3,17},{2,19}}
22 {{1,2,3,5,11},{1,3,7,11},{1,3,5,13},{2,7,13},{2,3,17},{5,17},{1,2,19},{3,19}}
23 {{2,3,7,11},{5,7,11},{2,3,5,13},{1,2,7,13},{3,7,13},{1,2,3,17},{1,5,17},{1,3,19},{23}}
24 {{1,2,3,7,11},{1,5,7,11},{1,2,3,5,13},{1,3,7,13},{11,13},{2,5,17},{7,17},{2,3,19},{5,19},{1,23}}
25 {{2,5,7,11},{2,3,7,13},{5,7,13},{1,11,13},{1,2,5,17},{3,5,17},{1,7,17},{1,2,3,19},{1,5,19},{2,23}}
26 {{1,2,5,7,11},{3,5,7,11},{1,2,3,7,13},{1,5,7,13},{2,11,13},{1,3,5,17},{2,7,17},{2,5,19},{7,19},{1,2,23},{3,23}}
27 {{1,3,5,7,11},{2,5,7,13},{1,2,11,13},{3,11,13},{2,3,5,17},{1,2,7,17},{3,7,17},{1,2,5,19},{3,5,19},{1,7,19},{1,3,23}}
28 {{2,3,5,7,11},{1,2,5,7,13},{3,5,7,13},{1,3,11,13},{1,2,3,5,17},{1,3,7,17},{11,17},{1,3,5,19},{2,7,19},{2,3,23},{5,23}}
29 {{1,2,3,5,7,11},{1,3,5,7,13},{2,3,11,13},{5,11,13},{2,3,7,17},{5,7,17},{1,11,17},{2,3,5,19},{1,2,7,19},{3,7,19},{1,2,3,23},{1,5,23},{29}}

Forthmath

$\endgroup$
2
  • 1
    $\begingroup$ is this goldbach's conjecture? $\endgroup$
    – Agile_Eagle
    Commented Mar 18, 2017 at 12:32
  • $\begingroup$ @PrashantGokhale. No, I'm pretty sure that it's a consequence of PNT. $\endgroup$
    – Lehs
    Commented Mar 18, 2017 at 12:33

1 Answer 1

Reset to default
3
$\begingroup$

By Bertrand's Postulate, for every $n>1$, there exists a prime $p$ such that $n<p<2n$.

I will use a strong induction to prove that there exists a "prime sum" for all integers $n$. Base case is trivial.

For induction case, let's suppose that there exists a prime sum for $1$ to $k$ and prove it for $k+1$. Note that there exists a prime $q$ such that $(k+1)/2<q<k+1$. The prime sums for $k+1-q$ will not contain the prime $q$ because $k+1-q < q$. Thus, the prime sum of $k+1-q$ plus $q$ is desired prime sum for $k+1$.

$\endgroup$
2
  • $\begingroup$ Great, but Bertrand's postulate is only proved with of PNT, isn't it? $\endgroup$
    – Lehs
    Commented Mar 18, 2017 at 12:45
  • $\begingroup$ No, it is far weaker claim than PNT and can be beautifully proved using only elementary mathematics. See en.wikipedia.org/wiki/Proof_of_Bertrand%27s_postulate . $\endgroup$
    – didgogns
    Commented Mar 18, 2017 at 12:48

You must log in to answer this question.

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