Problems & Puzzles: Conjectures
Conjecture 21. Rivera's
Conjectures about the representation of
every natural number as
sum of distinct
consecutive prime numbers.
For sure many prime numbers lovers have spent tons of hours around the mysterious attraction of the Goldbach conjecture. I'm not the exception. Two weeks ago I got a hit on my head when I read in the P. Ribenboim well known book this:
In that very moment I started considering:
Here are my first results:
Conjecture 1. Each Natural number N=>Nş can be expressed (at least in one way) as an
algebraic sum of distinct consecutive primes, none of them greater than N.
2. Exists an extremely simple and successful algorithm to find at least one
(the first) solution (algebraic sum of distinct consecutive primes equal
to N) for any N:
Given N, arrange all the allowed primes less than N in descending order
This algorithm always halts if N=>5 and "2" is allowed, or if
N=>15 and only ODD primes are allowed.
can obtain an "optimized
using the algorithm described in Conjecture 2, but applying the step 2) to all the
allowed primes less than N and saving the solution that uses the least quantity of
optimized solution (obtained with the reiterative use of the algorithm
described in Conjecture 2) not necessarily provides the "minimal"
example the "optimized
for N=14 is: 11+7-5+3-2 (5 primes) while the "minimal
is 13-11+7+5 (4 primes).
Other N values such that the
Other N values such that theminimal solution has less primes than the optimized solution are: 44, 51, 66, 70, 82, 110, 176, 194, 246, ... See in the Appendix I the solutions for N<=50.
1. Can you demonstrate or refute the Conjectures 1
& 2 (no matter if you use for
this purpose the undemonstrated Goldbach one)?
2. Can you produce a simpler algorithm than the described in the Conjecture 2 to produce at least one solution for any N?
3. Can you devise a simple algorithm to produce the "minimal" solutions for any N? (here, "simple" means a non exhaustive-combinatorial procedure)
4. Let's define R(N) as the quantity of distinct consecutive primes used in the minimal solution for N:
5.- Here are the least N integers for the first 7 values for R(N):
Can you continue this table ?
Last comment: Obviously that my main hope is that the mathematical concept "algebraic sum of distinct consecutive prime numbers" becomes a new & interesting object of study; if useful to tackle the old Goldbach Conjecture, the better!...
Chris Nash has total and positively proved (15/07/2000) the Conjecture 1, proving a stronger and beauty fact:
Obviously the fact discovered by Nash proves also the Conjecture 1 of this puzzle. At the same time provides a first answer to the question 4.1: R(N)<pi(N), where pi(N) is the quantity of primes less or equal to N, no matter if it seems a "weak" answer: this bound the figures...
From another point of view, I would say that the Nash's result demonstrates the validity of the Conjecture 1 because he proved the existence of the "maximal solutions", that is to say the existence of algebraic sum of all the primes less than N.
I must confess that I had not even a glimpse of that beauty kind of solutions, neither in a conjectural state... since the beginning I started seeking in the opposite direction: the minimal solutions. So I lost of my scope that diamonds in the sky...
After knowing the demonstration of the Conjecture 1 - because of the existence of these kind of (maximal) solutions- I immediately asked himself if he devised an efficient algorithm for getting them. One day after he responded with a proposal. Please see his algorithm in the Appendix III. As you can see his algorithm is a kind of extension of my algorithm & Conjecture 2, plus the basic tables prepared by Nash as part of his proof of the Conjecture 1.
Questions 3 & 5
Chris Nash has also developed an approach to get the minimal solutions (description still not available) and has produced three (3) new entries to the Table in construction of the question 5. His search for these solutions has reached up to N=65521... "It looks like it could be difficult to extend the table further, without a faster algorithm!"
Comparing his "minimal" results with the "optimized" ones obtained with my procedure & code for the same N values, it seems that the quantity of primes involved in both approaches differ by no more than 2.
So, the issue of producing an efficient algorithm for getting the minimal solutions, while is partially solved for low values of N is still needing a better solution for moderate to large N values.
Regarding the existence of Kr, Chris Nash says "I expect the Kr exists"
I want to express my admiration and gratitude to Chris Nash for his fine work on this Conjectures. In particular I find amazing the unexpected exploitation of that gem of Erdös in a subject apparently so far of the Bertrand Postulate like the Conjecture 1
Let q(n,k) be the number of ways of expressing n as an algebraic sum of ALL consecutive primes, the largest of which is p_k. Here ALL depends on which problem we are attacking, we may allow or disallow 2.We may define q(n,0) to be zero for n not equal to zero. And we may define q(0,0) to be 1. If we are disallowing 2, then q(n,1) is zero except q(0,1)=1.
Now the other relationship we need. Let's add the k'th prime to an already-existing sum that has largest prime p_(k-1). Then we have q(n,k) = q(n-p_k,k-1) + q(n+p_k,k-1) (*) since we can either add or subtract the new prime to previously- existing sums.
Now we define the following function r(k). r(k) is the largest integer r such that q(n,k) is non-zero for -r<=n<-r, and for n of the right parity - evidently all the points at which q(n,k) is not zero are either all odd, or all even. In other words, all numbers from -r(k) to r(k) can be expressed as an algebraic sum of primes, whose largest element is p_k, for precisely eeither the odd valuies or the even values depending on k.
Suppose r(k)>=p_(k+2). Then r(k+1) is at least r(k)+p_(k+1)., since any positive integer of the right parity in this range can be expressed as p_(k+1), plus another sum that ends in p_k. (Similarly any negative integer of the right parity is -p_(k+1) plus a sum listed in the r(k)).
Furthermore we have r(k+1) >= r(k)+p_(k+2) >= p_(k+1)+p_(k+2) We require this to be greater than p(k+3) for the induction step to work.
http://mathworld.wolfram.com/ChoquetTheory.html gives a clue. Erdos proved there is always at least one prime of each of the forms 4k+1, 4k+3 between n and 2n for n>6. In other words, we can strengthen Bertrand's postulate and say there are always at least * two* primes between n and 2n, for n>6.
Hence in those cases p(k+1)+p(k+2) > 2p(k+1) > p(k+3), as long as p(k+1) is greater than 6. And the induction step follows. Now we complete the proof we need.
Suppose r(k)>=p_(k+2), and p(k+1) is greater than 6. Then r(k+1)>=p_(k+ 3). And furthermore: all values of n, p_(k+1)<n<=p_(k+2), of one parity, can be expressed as an algebraic sum of primes, the largest of which is p_k, by definition of r_k, and all values of n, p_(k+1)<n<=p_(k+2), of the opposite parity, can be expressed as an algebraic sum of primes, the largest of which is p_(k+ 1), by definition of r_(k+1).
Therefore, if we can find a value of k such that p(k+1)>6 & r(k)>=p(k+2) then the conjecture is proven for all values of n greater than p_(k+1).
And we may return to test smaller values. So now we need to search whether such a value of k exists. This is easy to do, using the relationship (*) to build a table of the function q for each value of k. Perhaps surprisingly, r(k) is very quickly much much larger than p_(k+2).
If the prime 2 is allowed, we find r(6)=27>=19. The induction can begin and we have proven the conjecture for all values of N greater than 17.
We can quickly check the values 5, 7, 9, 11, 13, 15, and the conjecture is true.
If the prime 2 is not allowed, we find r(7)=36>=23. Thus we have proven the conjecture for all values of N greater than 19. We can quickly check the values 11, 13, 15, 17, 19, and again the conjecture is true.
To complete the proof, I list here the necessary tables to prove that r(6)>=19 in the first case, and r(7)>=23 in the second.
Case 1: All odd numbers up to 19 are expressible as an algebraic sum of the first six primes.
Case 2: All even numbers up to 24 are expressible as an algebraic sum of the first six ODD primes
We have actually proven a stronger result than the conjecture suggested. Not only is every integer beyond the suggested value an algebraic sum of consecutive primes, every integer beyond the values required by the induction is an algebraic sum of ALL primes less than n, or ALL primes less than n except the last!
So here is my suggestion - the first step is indeed to sum all the primes and test for odd or even, so you know the largest prime to use. From then this is the algorithm:
Set R, the remainder, to equal n.
Set k to the index of the largest prime you need for each value of k
If R is positive, write down "+p_k", and subtract p_k from R. If R is negative, write down "-p_k" and add p_k to R. then decrease k until k is small enough to use the tables I sent you in the last mail (k=6 for all primes, k=7 for odd primes)
Finally look up the final value of R in the tables and write down the sum that appears there. The proof tells us this algorithm is successful (we end up with an R value listed in the tables), provided our n value is large enough (larger than the limit of the tables). Of course this only finds ONE such solution, there may be many solutions. It's a very quick and easy algorithm
Example, sum to 50. All primes up to 47 have an even sum, so we will
start with 47
We are at the tables so need R=-1
so -1 is +2-3-5+7+11-13
and so we have