Symmetry in primes
Thomas Stegen
I am a engineering student and math isn't really my strongest side
so please bear with me (and you are welcome to correct any notational
convention I might break :).
I read a post just up here saying that any even number could be
represented as the sum of two primes. I did some experimenting
to see if I could find a counter example, I couldn't but I stumbled
upon something which led to the following conjecture.
For any positive integer a > 1 a positive integer x can be chosen
such that (a + x) is prime and (a - x) is prime.
Also if true does this imply that an even number can be represented
by the sum of two primes since (b is an positive even integer):
b = (b/2 + x) + (b/2 - x)
And finally it implies that an odd number can be represented as
the sum of three primes. c is a positive odd integer, c > 2.
d is a prime, d < c and d not equal to 2
c - d = f (f is even)
=> f = (f/2 + x) + (f/2 - x)
=> c = f + d = (f/2 + x) + (f/2 - x) + d
Can someone confirm or deny this?
Regards.
--
Thomas Stegen
http://www.geocities.com/thinkoidz
David C. Ullrich
<tst...@cis.strath.ac.uk> wrote:
>Hi there.
>
>I am a engineering student and math isn't really my strongest side
>so please bear with me (and you are welcome to correct any notational
>convention I might break :).
>
>I read a post just up here saying that any even number could be
>represented as the sum of two primes.
This is a famous unsolved problem - if you see someone claiming
to be able to prove this he's either an awesome genius or a
crackpot. (In this particular case he's a crackpot - you can't
believe everything you read.) It's called the "Goldbach Conjecture".
>I did some experimenting
>to see if I could find a counter example,
People have done a _lot_ of experimenting without finding
a counterexample.
>I couldn't but I stumbled
>upon something which led to the following conjecture.
>
>For any positive integer a > 1 a positive integer x can be chosen
>such that (a + x) is prime and (a - x) is prime.
That's equivalent to the original conjecture.
>Also if true does this imply that an even number can be represented
>by the sum of two primes since (b is an positive even integer):
>
>b = (b/2 + x) + (b/2 - x)
>
>And finally it implies that an odd number can be represented as
>the sum of three primes. c is a positive odd integer, c > 2.
>d is a prime, d < c and d not equal to 2
>
>
> c - d = f (f is even)
>=> f = (f/2 + x) + (f/2 - x)
>=> c = f + d = (f/2 + x) + (f/2 - x) + d
>
>Can someone confirm or deny this?
>
>
>Regards.
>--
>Thomas Stegen
>http://www.geocities.com/thinkoidz
>
David C. Ullrich
Denis Feldmann
"Thomas Stegen" <tst...@cis.strath.ac.uk> a écrit dans le message news:
3CE95838...@cis.strath.ac.uk...
Oh, it is correct (albeit rather elementary). But it doesn't appear easier
to prove that the original conjecture.
Thomas Stegen
> "Thomas Stegen" <tst...@cis.strath.ac.uk> a écrit dans le message news:
> 3CE95838...@cis.strath.ac.uk...
>
>>Hi there.
>>
>>I am a engineering student and math isn't really my strongest side
>>so please bear with me (and you are welcome to correct any notational
>>convention I might break :).
>>
>>I read a post just up here saying that any even number could be
>>represented as the sum of two primes. I did some experimenting
>>to see if I could find a counter example, I couldn't but I stumbled
>>upon something which led to the following conjecture.
>>
>>For any positive integer a > 1 a positive integer x can be chosen
>>such that (a + x) is prime and (a - x) is prime.
>>
>>Also if true does this imply that an even number can be represented
>>by the sum of two primes since (b is an positive even integer):
>>
>>b = (b/2 + x) + (b/2 - x)
>>
>>And finally it implies that an odd number can be represented as
>>the sum of three primes. c is a positive odd integer, c > 2.
>>d is a prime, d < c and d not equal to 2
>>
>>
>> c - d = f (f is even)
>>=> f = (f/2 + x) + (f/2 - x)
>>=> c = f + d = (f/2 + x) + (f/2 - x) + d
>>
>>Can someone confirm or deny this?
>>
>
> Oh, it is correct (albeit rather elementary).
Have to start somewhere ;)
> But it doesn't appear easier
> to prove that the original conjecture.
>
While we are on the topic of conjectures. Is it possible to prove
that something is unprovable?
Thanks to both of you.
Randy Poe
>
> Hi there.
>
> I am a engineering student and math isn't really my strongest side
> so please bear with me (and you are welcome to correct any notational
> convention I might break :).
>
> I read a post just up here saying that any even number could be
> represented as the sum of two primes.
The prime pages (http://primes.utm.edu) are a good source
for facts and conjecture on prime numbers.
This was a reference to the Goldbach conjecture:
(http://primes.utm.edu/glossary/page.php/GoldbachConjecture.html)
Every even number greater than 2 can be represented as
a sum of two primes. Equivalently, every integer (odd or
even) greater than 5 can be represented as a sum of three
primes. It is still neither proven nor
disproven. It's been shown valid up to 10^14 or so.
> I did some experimenting
> to see if I could find a counter example, I couldn't but I stumbled
> upon something which led to the following conjecture.
>
> For any positive integer a > 1 a positive integer x can be chosen
> such that (a + x) is prime and (a - x) is prime.
I'll call this (*)
>
> Also if true does this imply that an even number can be represented
> by the sum of two primes since (b is an positive even integer):
>
> b = (b/2 + x) + (b/2 - x)
It is clear that (*) implies Goldbach. Given any even b,
find the x such that (b/2+x) and (b/2-x) are prime. Does Goldbach
imply (*)? Suppose Goldbach is true. Given any a, find the
decomposition of b=2a such that b=p1 + p2. Label them
so p1>=p2. Then clearly p1 can be written in the form (a + x)
then p2 = b-p1 = a-x. Therefore a+x and a-x are prime.
However, I think Goldbach allows the case p1=p2. So your
conjecture is not completely equivalent to Goldbach. It's
a little stronger, and would imply that there's always
a Goldbach decomposition into two *distinct* primes.
> And finally it implies that an odd number can be represented as
> the sum of three primes. c is a positive odd integer, c > 2.
> d is a prime, d < c and d not equal to 2
Yes, this is equivalent to Goldbach (but again the primes need
not be distinct, I think).
- Randy
Denis Feldmann
Sure:-) Look at "Lobatchewski" or "Riemann" for the 5th Euclid postulate, at
"Gödel" for the proof of the consistency of arithmetic, at "Turing" for the
halting problem, at "Matijasevic" for polynomials not having integer
solutions, at "Chaitin" for values of digits of a certain constant...
Virgil
Thomas Stegen <tst...@cis.strath.ac.uk> wrote:
> While we are on the topic of conjectures. Is it possible to prove
> that something is unprovable?
>
>
> Thanks to both of you.
If you can prove it is false, you have proved it unprovable.
There are statements which can be shown unprovable and whose
negations can also be shown unprovable within some fixed system or
logical structure. However, it may be possible to expand the system
or logical structure just enough to make one and only one of them
provable.
Of course, if you have a system in which any statement and its
negation are both provable, then every statement is both provable
and disprovable, and the system is of little use.
Mark Wraith
> find the x such that (b/2+x) and (b/2-x) are prime. Does Goldbach
> imply (*)? Suppose Goldbach is true. Given any a, find the
> decomposition of b=2a such that b=p1 + p2. Label them
> so p1>=p2. Then clearly p1 can be written in the form (a + x)
> then p2 = b-p1 = a-x. Therefore a+x and a-x are prime.
> However, I think Goldbach allows the case p1=p2. So your
> conjecture is not completely equivalent to Goldbach. It's
> a little stronger, and would imply that there's always
> a Goldbach decomposition into two *distinct* primes.
Having been paying much attention, but this corresponds to the case
x=0, I think. In any case it isn't possible to write any even>2 as the
sum of two distinct primes. Neither four nor 6 can be written in this
way. Are there any others??
> > And finally it implies that an odd number can be represented as
> > the sum of three primes. c is a positive odd integer, c > 2.
> > d is a prime, d < c and d not equal to 2
My Math is bad, but isn't this weaker than Goldbach's conjecture? I
see how Goldbach's conjecture implies this trivially, but how does
this conjecture imply Goldbach?
Mark W
Jan Kristian Haugland
Thomas Stegen wrote:
> Hi there.
>
> I am a engineering student and math isn't really my strongest side
> so please bear with me (and you are welcome to correct any notational
> convention I might break :).
>
> I read a post just up here saying that any even number could be
> represented as the sum of two primes. I did some experimenting
> to see if I could find a counter example, I couldn't but I stumbled
> upon something which led to the following conjecture.
This is one of the most famous unsolved problems in
mathematics, so it would probably take a while for
you to catch up with the range that has already been
tested.
> For any positive integer a > 1 a positive integer x can be chosen
> such that (a + x) is prime and (a - x) is prime.
It is false for a = 2 (1 is normally not considered prime).
> Also if true does this imply that an even number can be represented
> by the sum of two primes since (b is an positive even integer):
>
> b = (b/2 + x) + (b/2 - x)
Yes, the two conjectures (after modification) are
obviously equivalent.
> And finally it implies that an odd number can be represented as
> the sum of three primes. c is a positive odd integer, c > 2.
> d is a prime, d < c and d not equal to 2
This has been proved to be true for all sufficiently
large odd integers. It is also trivially true if we
assume Goldbach's conjecture (add the term 3).
> c - d = f (f is even)
> => f = (f/2 + x) + (f/2 - x)
> => c = f + d = (f/2 + x) + (f/2 - x) + d
>
> Can someone confirm or deny this?
>
> Regards.
> --
> Thomas Stegen
> http://www.geocities.com/thinkoidz
--
J K Haugland
http://hjem.sol.no/neutreeko
Timothy E. Vaughan
"Thomas Stegen" <tst...@cis.strath.ac.uk> wrote in message
news:3CE95838...@cis.strath.ac.uk...
> For any positive integer a > 1 a positive integer x can be chosen
> such that (a + x) is prime and (a - x) is prime.
a = 3 is a counterexample.
Rupert
So is 2.
Russell Easterly
For every prime number written in binary,
there is another prime number that differs
from the first in only one bit position.
2 and 3 differ by just one bit in binary.
Russell
- the universe is one dimensional
>Rupert" <rupertm...@yahoo.com> wrote in message
news:d6af759.02052...@posting.google.com...
Robert Israel
>For every prime number written in binary,
>there is another prime number that differs
>from the first in only one bit position.
Interesting conjecture. The first counterexample is 127
and there are lots after that (109 of the first 1000 primes).
Given a large odd number n, there are approximately log_2(n) odd
numbers differing from n by one bit position, and the
probability of a randomly chosen number of this size being
prime is approximately 2/ln(n). Therefore we would expect
an average of approximately 2/ln(2) = 2.885... of these numbers
to be prime. Assuming a Poisson distribution (which isn't really
justified, but might not be too far wrong), the probability that
at least one is prime should be approximately 1 - exp(-2/ln(2))
= 0.944...
Robert Israel isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
Fred Galvin
> In article <uP%G8.84518$UV4.146802@rwcrnsc54>,
> Russell Easterly <logi...@attbi.com> wrote:
> >Here is a fun conjecture.
>
> >For every prime number written in binary,
> >there is another prime number that differs
> >from the first in only one bit position.
>
> Interesting conjecture. The first counterexample is 127
> and there are lots after that (109 of the first 1000 primes).
> Given a large odd number n, there are approximately log_2(n) odd
> numbers differing from n by one bit position, and the
I guess I misunderstood the question: I would have thought there were
infinitely many numbers differing from 127 in one bit position, one
such number being 383, a prime number.
Phil Carmody
The Sierpinski problem provides us with an infinite number of values which can never become prime no matter what power of two is added to them. So all we need to do is find one of these values which also fails for the flipping (to zero) of its set bits, and we're home and dry.
I'd assert false, but don't have the counter-example to prove it yet.
Phil
Phil Carmody
Not sure of minimality, but 14088643 looks like a candidate.
Having said that, I've not even double-checked it, so it might even be garbage!
Phil
Phil Carmody
And it was. One single character (digit) wrong in my script!
I beg your forgiveness, and hope that I can atone for this by providing the real solution!
I think it's the minimal answer, this time I'll show my working, so it can be verified :-|
2131099
Method:
Note - I ran the program with only 6 sierpinski families to get the value 2131099, and then I added all the other sierpinski families which can have members below that value. None of the newly added sierpinski values were able to find a smaller example.
The sierpinski numbers are stored in @sns, and the bases (products of the covering set of primes) are in @bs, I simply iterate over all of them, over each member in the keller-transform loop (k->(2k+p)%p), and for all numbers equivalent to that modulo the corresponding base. I abort the inner loop as soon as I'm over the largest known solution. For each number I test I ensure that it's prime and that every number with one bit toggled is composite. Prime tests are via trial-division to the square root, using an on-the-fly list of small primes. Speed was not considered an issue (it only takes half a second on a 50MHz machine anyway!).
#!/usr/bin/perl -w
my @sp=(2,3,5,7,11,13,17,19,23,29);
my $spl=30;
sub isprimehelp
{
my $cand=$_[0];
for(@sp)
{
if(!($cand%$_)) { return 0; }
if($_*$_>=$cand) { return 1; }
}
return -1;
}
sub isprime
{
my $cand=$_[0];
#print("isprime($cand)\n");
my $stab=isprimehelp($cand);
return $stab if($stab!=-1);
# undecided
while(($spl*$spl<$cand) && ($stab==-1))
{
my @newp=();
for(1,7,11,13,17,19,23,29)
{
if(isprimehelp($spl+$_))
{
if(!($cand%($spl+$_))) { $stab=0; }
push @newp, ($spl+$_);
}
}
#print("adding ", join(",", @newp), " to prime list\n");
push @sp, @newp;
$spl+=30;
}
return -$stab; # -1 -> +1, 0 stays composite
}
my $abortat=100000000;
my @sns=(271129, 271577, 78557, 2510177, 8184977, 12756019,
322523,327739,934909,1290677,1777613); # added after 2131099 was found
my @bs=(5592405,5592405,70050435,70050435,70050435,70050435,
401868285,578477445,206364795,104595855,20808921315); # ditto
my $i;
for($i=0; $i<=$#sns; ++$i)
{
my $sn0=$sns[$i]; my $b=$bs[$i];
print("Sequences based on $sn0 mod $b\n");
my $sn=$sn0;
while(1)
{
my $gotnp=0;
my $a=$sn;
#print("Sequence at $a\n");
while(!$gotnp && $a<$abortat)
{
my $bit;
my $gotprime=0;
if(isprime($a))
{
for($bit=2; $bit<=$a; $bit<<=1)
{
if(isprime($a^$bit))
{
$gotprime=1;
last;
}
}
if(!$gotprime)
{
print("$a had no primes\n");
$gotnp=1;
$abortat=$a;
}
else
{
#print("$a prime at ", $a^$bit, "\n");
}
}
$a+=$b*2; # only odds please
}
$sn = ($sn*2+$b)%(2*$b);
if($sn==$sn0) { last; }
}
}
Phil
Jack Brennen
> > > In article <uP%G8.84518$UV4.146802@rwcrnsc54>,
> > > Russell Easterly <logi...@attbi.com> wrote:
> > > >Here is a fun conjecture.
> > >
> > > >For every prime number written in binary,
> > > >there is another prime number that differs
> > > >from the first in only one bit position.
>
> Having said that, I've not even double-checked it, so it might
> even be garbage!
Someone spent a lot of effort putting together a really good
web site about this:
http://www.csm.astate.edu/~wpaulsen/primemaze/pmaze.html
There are an infinite number of counterexamples to the "conjecture",
and one is given there -- 2131099 -- which is smaller than Phil's.
Phil Carmody
> Phil Carmody wrote:
> > > > In article <uP%G8.84518$UV4.146802@rwcrnsc54>,
> > > > Russell Easterly <logi...@attbi.com> wrote:
> > > > >Here is a fun conjecture.
> > > >
> > > > >For every prime number written in binary,
> > > > >there is another prime number that differs
> > > > >from the first in only one bit position.
> >
> > Not sure of minimality, but 14088643 looks like a candidate.
> > Having said that, I've not even double-checked it, so it might
> > even be garbage!
Bletch.
> Someone spent a lot of effort putting together a really good
> web site about this:
>
> http://www.csm.astate.edu/~wpaulsen/primemaze/pmaze.html
>
> There are an infinite number of counterexamples to the "conjecture",
> and one is given there -- 2131099 -- which is smaller than Phil's.
Hello Jack, fancy meeting you here! :-)
More importantly, it's also a correct answer, which will teach me to google for tables on one machine and write the code on the other machine, relying on bad eyesight and/or flawed touch-typing instead of just using one machine and copy/paste.
Amusingly, if 14088643 had been a correct answer, it would have provided the maths world with a simple proof of both the GRH and the Twin Prime conjecture simultaniously. (Sod it, I can afford another Euro to charity, even if it was only a tangential reference, my tally since march is only 4 Euros!)
Phil
Robert Israel
Maybe I misunderstood it. I took it to mean differing in one of the
bits used to write the original number, not including leading 0's.
I think it's an interesting question either way.
Russell Easterly
"Jack Brennen" <John.B...@marconi.com> wrote in message
news:3CED0178...@marconi.com...
Thanks. This is a cool site.
My "conjecture" was based on a reduced Boolean function I derived for
primes less than 512. Most of the "min-terms" had only one
reduced variable. This suggested that primes came in pairs
that differ by a power of 2.
I find it interesting that there is such a number.
Hopefully, I can crank up my Boolean function finding program
to handle all the primes up to 2^24.
(Somebody will probably have to prove P=NP first.)
Russell
- 2 many 2 count
Chas F Brown
>
<snip>
> Speed was not considered an issue (it only takes half a second on a 50MHz machine anyway!).
Good lord! Where do you find a 50MHz processor these days? :)
Cheers - Chas
---------------------------------------------------
C Brown Systems Designs
Multimedia Environments for Museums and Theme Parks
---------------------------------------------------
Lynn Killingbeck
I still have mine, 'though it's not used too much any more. Does nicely
for "really, really DOS, zilcho Windoze" programs of old. Also, some
older games. [Still have my Atari 400 and 800, too.) So, to answer your
direct question, "I find it just down the hall!"
Lynn Killingbeck
Phil Carmody
> Phil Carmody wrote:
>
> Good lord! Where do you find a 50MHz processor these days? :)
>
> Cheers - Chas
Same place as the other 29 other people currently logged into it, using it to host their X Sessions, and read their mail, etc. Nice machines, these old HPPA HP-UX boxes.
Phil
Bill Taylor
|> The Sierpinski problem provides us with an infinite number of values
which can never become prime no matter what power of two is added to them.
Can you expand on this Sierpinski thing please? Sounds fun.
_..._ _..._
.~ `~. .~` ~.
,_ / } { \ _,
,_\'--, \ _.'`~~/ \~~`'._ / ,--'/_,
\'--,_`{_,} -( )- {,_}`_,--'/
'.`-.`\;--,___.'_ _'.___,--;/`.-`.'
'._`/ |_ _{@} {@}_ _| \`_.'
/ ` |-';/ _ \;'-| ` \
/ \ / | _ {@}_ | \ / \
/ '--;_ _ {@} _Y{@} _;--' \
_\ `\ {@}\Y/ {@} Y/ /` /_
/ |`-.___. / \Y/\|{@}Y/\|// \ .___,-'| \
^^^^^^^^^`--`------'`--`^^^^^^^^^^^^^^^^^^^^^^^^^^^`--`'------`--`^^^^^^^
TIA
------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
------------------------------------------------------------------------------
sig-file construction kit now guaranteed free of buggs
------------------------------------------------------------------------------
Phil Carmody
>
> Phil Carmody <firstnam...@nokia.com> writes:
>
> |> The Sierpinski problem provides us with an infinite number of values
> which can never become prime no matter what power of two is added to them.
>
> Can you expand on this Sierpinski thing please? Sounds fun.
It's actually a dual to the original Sierpinski problem, as managed by Ray Ballinger and Wilfrid Keller
http://www.prothsearch.net/sierp.html
In summary There are some k such that k.2^n+1 is never prime - what's the smallest such value?
It may well be k=78557, which generates provably composite values, but there are 17 other values that noone's found a prime for yet.
Payam Samidoost, who is working on 4847 (follow the '4847' link), has started a dual project (follow his 'dual' link).
Divisors of k.2^n+1 for some n are also divisors of 2^m+k for some m.
Therefore the smallest proven sierpinski number, k=78557, also yields provably composite values for 2^n+k.
Payam and others are searching for the smallest k value that yields no primes. There are only 11 remaining possible candidates for this dual project.
If you have any spare CPU power, you might want to grab a range, tell Payam I sent you ;-)
Phil