The Warwick Mathematics Society Website

User login

Upcoming events

  • No upcoming events available
Add to iCalendar
more

There are 466 members of the Warwick Mathematics Society, of which 0 are new today!
We're 93% of the way toward our target of 500 members.
You can join up on the UWSU website.

PBIG's Conjecture

Post Icon Posted: Submitted by Xedi on 18 January 2008 - 8:38pm.

Joined: 2007-10-03
Posts: 245

Hey guys,
I made a little Python code to check the first few counterexamples to PBIG's conjecture...

Here's a list of the first few counterexamples (under 1000) :

[(4,) 38, 68, 80, 98, 122, 128, 146, 158, 164, 188, 206, 212, 218, 224, 248, 278, 290, 302, 308, 326, 332, 338, 344, 368, 374, 380, 398, 410, 416, 428, 440, 458, 476, 488, 500, 518, 530, 536, 542, 548, 554, 578, 584, 608, 614, 626, 632, 638, 668, 674, 692, 698, 710, 716, 728, 734, 740, 752, 758, 770, 782, 788, 794, 806, 818, 836, 848, 854, 872, 878, 896, 902, 908, 920, 926, 938, 962, 968, 992, 998]

For example, the only prime decompositions of 38 are :
38 = 31 + 7
33 and 9 are both composite
38 = 19 + 19
21 is composite

Yet another myth is debunked.

‹ Riemann Hypothesis Plausible nonsense... ›
Post Icon Posted: 18 January 2008 - 10:01pm

Joined: 2006-11-02
Posts: 811

Big surprise... :D
Post Icon Posted: 18 January 2008 - 10:04pm

Joined: 2007-10-03
Posts: 245

Yeah I thought he was revolutionizing the whole world of mathematics. :(
Oh well, that'll be for the next one !
Post Icon Posted: 20 January 2008 - 1:55am

Joined: 2006-10-05
Posts: 534

I think it would be a revolution if pbig made mathematics wrong or not work anymore!
Post Icon Posted: 20 January 2008 - 4:49pm

Joined: 2006-11-02
Posts: 811

The real revolution would be PBiG making his own mathematics work. Hmm, in fact, it does work (at times) if we exchange normal logic by PBiG logic, a strange system where:

  • If $ A \Rightarrow B $, then $ B \Rightarrow A $.
  • If $ A \Leftrightarrow B $ then both $ A $ and $ B $ are true.
  • Every proof assumes it's conclusion (circular logic is not only allowed but necessary).
  • If $ A $ is a problem expressable in simple arithmetic terms then $ A $ is easily provable by induction.
  • etc.
Post Icon Posted: 20 January 2008 - 11:25pm

Joined: 2006-08-31
Posts: 676

PBIG's conjecture

huh?
Post Icon Posted: 21 January 2008 - 2:32am

Joined: 2006-11-02
Posts: 811

He was trying to solve Goldbach by induction so he conjectured (in less clear terms and adding a couple of dubious assumptions about logic :p) that if you can write a number $ 2k $ as a sum of two odd primes there's at least one pair of primes $ p $ and $ q $ such that $ p + q = n $ and at least one of $ p+2 $ or $ q+2 $ is prime.
Post Icon Posted: 21 January 2008 - 9:22pm

Joined: 2006-08-31
Posts: 676

uh huh. Okay.
Post Icon Posted: 28 January 2008 - 8:30pm

Joined: 2007-10-08
Posts: 12

what happens if 1 is included
ie 38=1+37, so 40=3+37
etc
Post Icon Posted: 29 January 2008 - 2:27am

Joined: 2007-10-03
Posts: 245

Ok let me dig out my code, I'll have a look !
Post Icon Posted: 29 January 2008 - 2:36am

Joined: 2007-10-03
Posts: 245

Here are the first counterexamples for this modified conjecture :
[122, 146, 188, 206, 218, 248, 290, 302, 326, 344, 416, 428, 476, 518, 530, 536, 554, 584, 626, 638, 668, 698, 716, 782, 794, 806, 818, 836, 848, 872, 896, 902, 926, 962]

Notice 122 is the first one in the list as the first ones in the first list all had n-1 prime, whereas 122 - 1 = 121 = 11².

122 = 13 + 109
Neither 13 + 2 or 109 + 2 are primes
122 = 19 + 103
Neither 19 + 2 or 103 + 2 are primes
122 = 43 + 79
Neither 43 + 2 or 79 + 2 are primes
122 = 61 + 61
61 + 2 isn't prime
Post Icon Posted: 29 January 2008 - 3:08am

Joined: 2006-10-01
Posts: 370

Genius.

Just genius.
Post Icon Posted: 29 January 2008 - 3:44am

Joined: 2006-11-02
Posts: 811

What happens if 1,2,3,4,5,6,7,8,9,10,11,... are allowed?
Furthermore, what happens if 0 is allowed?
Post Icon Posted: 29 January 2008 - 11:28am

Joined: 2007-10-03
Posts: 245

Try 19694 ! (Counterexample when you're using 0,1,2,3...100 (surely more) :p)

An actual list up to 100 000 of those :
[19694, 23522, 24314, 24884, 24914, 27392, 27404, 28094, 30668, 34016, 35264, 35708, 35714, 35720, 35726, 38102, 38132, 38144, 38858, 43256, 47030, 54230, 54242, 58586, 59876, 59912, 61316, 61904, 61946, 68084, 68384, 70742, 72416, 72830, 73256, 73496, 75008, 75146, 75974, 77066, 78134, 78296, 78686, 79556, 81476, 81494, 81506, 84626, 88112, 88142, 88154, 88202, 88784, 91916, 91934, 97766, 97784, 99494, 99686]

Now no more silly questions :p
Post Icon Posted: 29 January 2008 - 6:05pm

Joined: 2006-11-02
Posts: 811

Still, the 0 case is actually the most awesome conjecture ever.
Post Icon Posted: 29 January 2008 - 6:10pm

Joined: 2007-10-03
Posts: 245

Obviously so.
Post Icon Posted: 29 January 2008 - 6:18pm

Joined: 2006-10-01
Posts: 370

I would like to conjecture that every counterexample to pBig's conjecture is of the form 38+6n
Post Icon Posted: 29 January 2008 - 6:23pm

Joined: 2007-10-03
Posts: 245

Hmm, interesting, can't seem to find any counterexamples for the moment (except 4 but let's dismiss that one)... Though to be honest, the algorithm does run very slowly for big numbers... (Only checked up to 10 000 which is a ridiculously small number, and it took about one minute...)

Have you got an explanation for this ?
Post Icon Posted: 30 January 2008 - 12:10am

Joined: 2007-10-04
Posts: 186

Perhaps it would run quicker if you used something other than python. Also I'm not surprised it runs slowly. as the number grows it has to check more primes beneath the number. Does your algorithm check all pairs beneath a numer or does it add up primes to generate numbers. Depending on how you do it it could take quite a while.

Adding together primes and assingning each pair to a number would be quickest I'd imagine, I hope that's how you've done it. This algorithm would still be quite slow for larger numbers though. As the prime start to thin out, this algorithm could be pretty quick I imagine.

Edit: In fact better still, you could just add to primes which are the lower half of a twin ie 37+3,37+5,37+7,37+11,37+13,37+17,37+19 etc. and anything which doesn't get assigned a number is a counter-exaxmple. I'll bet this is how you did it since it's the easiest to implement
Post Icon Posted: 30 January 2008 - 2:15am

Joined: 2007-10-03
Posts: 245

All right, let this devolve into algorithmic optimization talk...
Initially I did actually check all pairs as I was going for a counterexample to Goldbach's conjecture :p

So I redid the program, and here are the timings for up to 4000 (times in seconds) :

Creating a list of primes up to 4000 : 0.0192750056221
Creating a list of twins up to 4000 : 0.0072136263127
Generating all the numbers twin + prime : 6.13388922335 (Managed to cut that down to 4.26102912521 at the moment)
Checking about the conjectures : 0.398316266453

And this method is really not faster than the one I had before, it's about the same...
I'll see if I can optimise the generation any further...

Edit : But in case I was unclear, the explanation I asked for was for that of Tom's conjecture, not why my code is slow :p
Post Icon Posted: 30 January 2008 - 2:55am

Joined: 2007-10-03
Posts: 245

All right, done so much better than generating the even numbers : check them to see if even - twin = prime directly. No generation.

Here's what I got for 4000 :
Creating primes list : 0.0253458889326
Creating twins list : 0.000454038152839
Checking the numbers : 0.198874717317

Quite an improvement !

Even up to 10 000 :
Primes : 0.0916439798913
Twins : 0.00147483828252
Check : 1.08542573148

30 000:
Primes : 0.480264321303
Twins : 0.00750262952414
Check : 9.89879893953

100 000 (and still no counterexample):
Primes : 3.60436633706
Twins : 0.0473146028336
Check : 175.612905341

Seems my algorithm is about $ \mathcal{O}(n^2) $ (latest estimate would give $ \mathcal{O}(n^{2.2}) $ but maybe it just isn't polynomial...)

Now I'm ready to check this conjecture up to $ \varepsilon_0 $ :D
Post Icon Posted: 30 January 2008 - 3:46am

Joined: 2006-11-02
Posts: 811

That's quite interesting actually. Primes larger than 3 must be either congruent to 1 or -1 mod 6. 38 + 6k means it's congruent to 2 mod 6 and thus either the sum of two primes of the form 6k+1 (and obviously these primes can't be the first twin prime in a pair because 6k+1+2 is always composite) or the sum of a prime of the form 6k+5 and 3. Thus, if n-3 is not prime (which is why this doesn't work for numbers congruent to 2 less than 38, for instance), n will necessarily be a counterexample to PBiG's conjecture. I find it somewhat more puzzling that in the other cases (where one of the primes is of the form 6k+5) we can apparently always find one which will be the first of a pair of twin primes (another way of stating Tom's conjecture). I'll think about this a bit more in the morning.
Post Icon Posted: 30 January 2008 - 1:47pm

Joined: 2006-10-09
Posts: 318

So, about 8 hours to do 1 million...

Beyond that, we're going to have to get started on distributed computing.

I have to say, this is a really odd one, it gives us some real insight into the distribution of twin primes if it is true... Crazy shit.

Jamie

PS. I still maintain that this can't be true. It's insane. Totally nuts. Seriously? I mean... Ugh, I don't know.
Post Icon Posted: 30 January 2008 - 8:19pm

Joined: 2007-10-04
Posts: 186

That seems a little surprising. Does your list contain every number and mark them as prime or not prime? Otherwise the search functions must be pretty damn good.
Post Icon Posted: 30 January 2008 - 9:20pm

Joined: 2006-10-10
Posts: 391

I didn't even understand the original conjecture, but I do have the sheet of paper pinned on my wall. If this line of reasoning bears fruit, I want a namecheck on the journal article :P
Post Icon Posted: 31 January 2008 - 12:43am

Joined: 2007-10-04
Posts: 186

It'll look damn weird putting mauhbc on the article.
Post Icon Posted: 1 February 2008 - 11:03am

Joined: 2006-10-09
Posts: 318

Right, so I think it's about time we formalise the Boardman-PBIG Conjecture:

\newtheorem{conj}{Conjecture} \newtheorem{cor}[conj]{Corollary} \begin{conj}[The Boardman-PBIG Conjecture] If $\mathbb{P}$ is the set of prime numbers and $n\in 2\mathbb{Z}$ then either: \begin{enumerate} \item $\exists p,q\in\mathbb{P}$ such that $p+q=n$ and either $p+2\in\mathbb{P}$ or $q+2\in\mathbb{P}$. Otherwise, \item $n\equiv 2 (\mathrm{mod}\, 3)$ \end{enumerate} \end{thm} \begin{cor}[The DG Corollary] If $\exists a\in 2\mathbb{Z}$ such that $\nexists p,q\in\mathbb{P}$ such that $a=p+q$ then $a\equiv 2(\mathrm{mod}\, 3)$ \end{cor}

Everyone happy with these atm?

Jamie
Post Icon Posted: 1 February 2008 - 6:58pm

Joined: 2006-10-09
Posts: 318

Right, just to keep everyone up to date, I'm running Sam's python script at the moment up to 1,000,000, it's got to 250,000 at the moment, should be done by morning. Elsewhere, I'm starting to write the C program which we're going to be running on Samir Siksek's machine, looking up info on how to get it working on multi-core machines etc etc.

I haven't noticed any counterexamples to the Boardman-PBIG conjecture as yet, but there is a huge chance that I've missed one if there has been so far.

Fingers crossed!

Jamie
Post Icon Posted: 1 February 2008 - 7:04pm

Joined: 2006-10-01
Posts: 370

Latest update:

The Boardman-Pbig conjecture has been taken to Samir and he likes it. Much. We now have access to his computer to run a checking algorithm with the prospect of a publish, possibly even if we find a counter-example.

When Jamie and I approached him he asked us quite seriously what we were doing for a PhD. We're talking instant number theory cred for anyone involved (-he reckons we're even likely to get into a book of number theory unsolved problems!). Consequently, it seems like a no-brainer that anyone with a desire to go into that area (ie. Cosmin) should get on board and quickly.

Next meeting with Siksek (probably some time next week), come along and we will make you a star!
Post Icon Posted: 1 February 2008 - 7:16pm

Joined: 2006-10-09
Posts: 318

6:14pm - Just hit 300,000 and counting...
6:30pm - 330,000
6:49pm - 360,000
7:17pm - 400,000
8:35pm - 507,000
9:58pm - 590,000
10:51pm - 634,700 (really starting to slow down now...)
11:28pm - 663,000
12:26am - 704,000
12:31am - 713,000 (which is itself an anti-PBIG number)
01:38am - 750,000 (and bed time!)
Post Icon Posted: 1 February 2008 - 7:56pm

Joined: 2006-11-02
Posts: 811

Awesome. :D

One thing though, I'm not 100% happy with the formalised version. It should actually be something more like:
If $ \exists p,q \in \mathbb{P} $ such that $ p + q = n $ then we can either find $ p_0, q_0 \in \mathbb{P} $ such that $ p_0 + q_0 = n $ and at least one of $ p_0+2 $ or $ q_0 + 2 $ is prime or $ n\equiv 2 \pmod 6 $.

As you've written it now, 1. is Goldbach and the twin prime thing combined (which makes the corollary trivial and uninteresting: you're basically conjecturing from the start something much, much stronger). The other version is weaker since it doesn't assume that the number can be represented by Goldbach, which is what PBiG initially needed for his proof by induction (since he was trying to prove Goldbach). So, in fact, we don't actually have any interesting corollaries for the moment.

P.S. If you want to write a C program for it, you might find PARI interesting since it has great functions for like primality testing (pretty much the fastest available algorithms) and such (and you can use it directly as a C library). It also has über-awesome servo-motors. Thank you.
Post Icon Posted: 1 February 2008 - 8:31pm

Joined: 2007-10-03
Posts: 245

Great news indeed :p

(And I laughed to no end at the end of your post Cosmin, totally unexpected :D)
Post Icon Posted: 2 February 2008 - 12:03am

Joined: 2006-10-09
Posts: 318

Right, this sh*t is getting heavy right here.

I'm getting stack overflow errors thanks to my line which translates to: "long primesarray[10000000]" - time to start breaking this up into multidimensional arrays, and in so doing having to make functions to get and put elements from and to the array (so it acts like a long list...).

/me cries.

Jamie
Post Icon Posted: 2 February 2008 - 12:06am

Joined: 2007-10-03
Posts: 245

Good luck ! :p
Post Icon Posted: 2 February 2008 - 12:12am

Joined: 2006-11-02
Posts: 811

This is why C++ and the standard template library rule. vector for the win.
Post Icon Posted: 2 February 2008 - 12:30am

Joined: 2006-10-09
Posts: 318

Have to say, was talking with my flatmate Linh who's a Computer Scientist and my immediate idea was "ooh, I could create an objec... Ah, never mind." Stupid C. C being faster vs. C++ being, well, just all round nicer, I know what I'd pick (if the problem wasn't computationally hard anyway)...

I will keep updating the above post, we're getting close to 665,000 at the moment.

Jamie

PS. Just for reference, my code manages to store in 2 different kinds of array and print all the primes below 100,000 in around 0.4 seconds (bear in mind that's timed with the stopwatch on my phone, so is liable to be +-0.2s)
Post Icon Posted: 2 February 2008 - 12:49am

Joined: 2006-11-02
Posts: 811

I don't really buy the C being significantly faster than C++ thing too much though, it depends on the algorithm and implementation a lot more and I believe you can even have faster implementations of some algorithms in C++ than in C (I recall reading some study about that some time ago anyway). In the end you have lots more flexiblility with C++ because you could just as well write a C program inside C++ with virtually no loss of performance (more or less) and if you ever feel like it bring in some of the useful C++ features at any moment.
Post Icon Posted: 2 February 2008 - 1:07am

Joined: 2006-10-09
Posts: 318

Just stuck a timer on my code, bear in mind this is running on one core of a dual core 1.86GHz o/ced to 2.25GHz, and it came out with an amazing 0.046s to create 2 different arrays representing all prime numbers below 100,000 (the printing obviously took a large chunk of time - edit: just checked, with printing every prime as we go along, time goes up to 0.312s (not too far off the 0.4 i guessed)).

This puts the C code potentially 100x faster than the python code, making 10 or 100 million a ready possibility.

Jamie
Post Icon Posted: 2 February 2008 - 1:08am

Joined: 2007-10-03
Posts: 245

Wow, that's a massive increase in performance !
Post Icon Posted: 2 February 2008 - 1:11am

Joined: 2006-10-09
Posts: 318

Yeah, you're not kidding, have to say it's not an identical rip of your code by any stretch of the imagination - your code was checking if each number was prime by checking it against each and every number between 2 and sqrt(number), whether odd or even (never mind prime or not), wheras mine only checks against already established primes in that same range - makes quite a big saving all-in-all.

Jamie
Post Icon Posted: 2 February 2008 - 1:17am

Joined: 2007-10-03
Posts: 245

Oh yeah, why I didn't do that in the first place is beyond me.

Edit : But anyway generating the list of primes really wasn't what took the most time in my code, it was (much) less than 1/10th of the total time...

Edit : Ok the speed increase doesn't seem that unreasonable after all, see http://furryland.org/~mikec/bench/
Still quite surprising though.
Post Icon Posted: 2 February 2008 - 1:31am

Joined: 2006-10-09
Posts: 318

Yeah, seems about 30x quicker according to those stats, so I'd guess that my algorithm speeds stuff up by 3x compared to yours?

Jamie
Post Icon Posted: 2 February 2008 - 1:42am

Joined: 2007-10-03
Posts: 245

Well depends what you're doing...
For the "native" test :
Python - 33.97
C++ - 0.09

C++ is 380 times faster.
Therefore my code is 3.8 times better than yours (or not)

But yes, what you say seems about right.
Post Icon Posted: 2 February 2008 - 9:59am

Joined: 2006-08-31
Posts: 676

Jamie if you're serious about this you should run it on the csc's machines, pop it in the queue, add some parallelism to your code (I'm guessing it's fairly parallelisble) and it'll go like stink.

If the whole Siksek thing is true (couldn't work out if it was a joke) then you might be able to talk your way onto the new IBM cluster.
Post Icon Posted: 2 February 2008 - 12:56pm

Joined: 2006-10-09
Posts: 318

Right, the python code has finished as of this morning, and (thankfully) no counterexamples!

Steven, we're serious about the Siksek thing, and I had the same thought as you with the CSC machine. However, according to Siksek we'd be better off using his machine as the "CSC machine is always broken"... Regardless, I'm going to see how quick my code runs on my machine and then Siksek's machine, then if needs be get into the CSC queue.

Jamie
Post Icon Posted: 2 February 2008 - 1:04pm

Joined: 2006-10-10
Posts: 391

It would be really good to get it going on a cluster

What is a good number to test to? 5 mil? 10 mil? 100 mil? 0.0
Post Icon Posted: 2 February 2008 - 1:29pm

Joined: 2006-10-09
Posts: 318

Given the speed increases I'm getting so far from just using C and algorithm improvements, I would suspect we'll end up 100x faster, so should be able to get to 10mil in a similar time to getting to 1mil (overnight). Dependent on quite how much faster my algorithm is, we may get further still.

edit: and i'm only referring to using a single machine at the moment, cluster we can hit 100mil i'm sure.

edit2: been doing some research and for the parallelism i'm going to need to use OpenMP which unfortunately isn't supported in MS Visual Studio 2008 Express, only the non-free versions. However, gcc does support this apparently, so I need to test this out by SSHing into a linux computer (or reinstalling linux I guess... :) )

edit3: banging head against brick wall

edit4: WHY WON'T YOU WORK!?!?!?!?

edit5: oh, i see. me=idiot.
Post Icon Posted: 2 February 2008 - 7:43pm

Joined: 2006-10-09
Posts: 318

I'm replying just so there's a new post and people check if they're interested.

I had a bit of a stall in the fact that I'm still getting stack overflow errors when using 1000×1000 arrays as opposed to 1000000×1 arrays (which also caused stack overflow). To remedy this, I'm using a linked list in place of the array, which actually makes a number of my calculations easier still. Hopefully, the speed improvements through algorithm improvements over the python script will be extreme.

Jamie
Post Icon Posted: 2 February 2008 - 7:59pm

Joined: 2007-10-03
Posts: 245

Sounds like fun.
Good work anyway, keep us informed up to where you check the conjecture ! :D
Post Icon Posted: 3 February 2008 - 10:17pm

Joined: 2006-10-09
Posts: 318

Right, set up my linked list properly, got it to calculate the primes from 1-10,000,000 in 10.968s, which is pretty nice :)

Next up is to get the twin primes in a sensible format.

Jamie
Post Icon Posted: 4 February 2008 - 2:23pm

Joined: 2006-10-09
Posts: 318

Right, after some edits, time for prime list is up to 14.468s, and time to make twin primes list (which is in a very odd format) is 0.188s. Interestingly, my final checking algorithm is very much like the 2nd of these times 2000 for 10million, so about 7 mins or so apparently... I mean, it should be order of an hour or so.

Jamie
Post Icon Posted: 4 February 2008 - 3:26pm

Joined: 2007-10-08
Posts: 12

what happnes if the caes of the counterexamples
if p(0) and q(0) exist st
p(0)+2 and q(0)+2 are not prime, and p(0) and/or q(0) are the largest of a twin prime pair (eg 19, in 17 and 19) then p(0)-2 and q(0)+4 are prime or q(0)-2 and
p(0)+4 are prime
eg 38= 19+19
40= 17+23
etc
Post Icon Posted: 4 February 2008 - 3:40pm

Joined: 2006-10-01
Posts: 370

Eh?
Post Icon Posted: 4 February 2008 - 4:49pm

Joined: 2006-11-02
Posts: 811

What he means is you'll be able to find a Goldbach representation of $ n $ with primes $ p_0 $ and $ q_0 $ such that $ p_0 - 2 $ and $ q_0+4 $ are both prime. He's basically trying to eliminate the counterexamples since this can only work for $ n \equiv 2 \pmod 6 $ (for the same reasons as above). It might actually be true (though I think it's unlikely because of the fact that, unlike the other conjecture, you need both of the primes in a pair of twins/cousins whereas before it was just one), but what's the point? Constantly refining a misguided approach has never helped anyone, you should try to find some other way of attacking the problem if you want to make any progress. Chances are this conjecture isn't going to be any easier than Goldbach itself.

Edit: Also, Jamie or Sam, could one of you post the pairs of primes that fail in the counterexamples as well? It could be interesting to see what they look like from a statistical point of view.
Post Icon Posted: 4 February 2008 - 5:44pm

Joined: 2006-10-05
Posts: 534

Can I point out that what you are saying is false. The only thing that makes an approach misguided is wether it works or not. Also a misguided approach can always be refined into somthing that does work (just in PBIG's case the refinement bears little relation the the original misguided approach).

That said, i agree with you about finding another way of attacking the problem.
Post Icon Posted: 4 February 2008 - 6:30pm

Joined: 2006-11-02
Posts: 811

Definetly NOT.

False and misguided have two very different connotations: false means the approach has no chance of working, misguided only means that it is improbable, that the heuristic reasons seem insufficient (or point the other way entirely) and so forth. Case in point: I can quite easily say that trying to prove the Riemann Hypothesis by proving P=NP is a misguided approach: the two problems have little in common, it's generally thought that P=NP is highly unlikely, etc. I can't, however, say it's false because for all I know someone might later prove that P=NP actually implies RH and that P=NP is true.

Furthermore, saying that a misguided approach can always be refined into one that works contradicts your definition of misguided, since you can't refine a false proof into a valid one. It also makes no sense according to mine since, by definition, a refinement of a misguided approach still keeps the same angle of attack on the problem and thus remains misguided. One of the first indications that a purported proof or method is invalid is that one has to keep refining it to avoid the counterexamples or inconsistencies that others find in it. It happens all the time with alleged proofs of famous theorems that you see from time to time, even those of serious mathematicians. Lastly, PBiG's refinement does bear relation to the original misguided approach since he's trying to find a way to eliminate the counterexamples. His last proposition will in fact only work for counterexamples to the original conjecture (while still using it in the cases where we can find no counterexamples).

Thank you.
Post Icon Posted: 4 February 2008 - 6:42pm

Joined: 2007-10-03
Posts: 245

To Cosmin :
Here's a graph of the counterexamples : on the x axis, the points that are counterexamples, and on the y axis, the pairs of primes that add up to that counterexample without any being the first of the twin prime.

Is that what you had in mind or would you want a list or something ?
Post Icon Posted: 4 February 2008 - 6:45pm

Joined: 2006-10-09
Posts: 318

Right, interesting development, Samir and I have come up with a reformulation of the conjecture which looks like this:

If $ n\in 2\mathbb{N} $, $ n>4 $ then $ \exists p,q\in\mathbb{P} $ such that $ p+q=n $ and either $ p+2\in\mathbb{P} $ or $ p-2\in\mathbb{P} $

That is to say that there is a decomposition into prime sum such that one of the primes is a member of a prime pair.

That is insane.

.......

....

......

...

Thank you.
Post Icon Posted: 4 February 2008 - 6:46pm

Joined: 2006-11-02
Posts: 811

Yes, it is, thanks. I take it the y axis represents the biggest of the 2 primes which add up to it or something like that?
Post Icon Posted: 4 February 2008 - 6:49pm

Joined: 2006-10-09
Posts: 318

I think the y-axis represents the twin prime in the list, which is why you get horizontal gaps...
Post Icon Posted: 4 February 2008 - 6:51pm

Joined: 2007-10-03
Posts: 245

On the y axis are all the possible combinations of primes that add up for that particular counterexample.

Even bigger version here : http://img515.imageshack.us/img515/8590/boardmanpbig2bz3.png

(And I must say I love how PBIG tries to hack together something that works :D)
Post Icon Posted: 4 February 2008 - 7:12pm

Joined: 2006-11-02
Posts: 811

Oh, ok, that's even better. I'll take a better look at it later, I need to finish preparing my DG. :P
Post Icon Posted: 6 February 2008 - 10:51am

Joined: 2006-10-09
Posts: 318

Just a little update, I'm off to Bristol today for a Complexity Science open day, so I'm not going to be getting terribly far today. However, yesterday I got a program running yesterday which overall worked, but I made a slight cock-up with which list I subtracted from :S Anyway, it ran to 10 million in about 25-30 seconds, and when the program is doing the correct thing, it should be a very similar speed :D Quite an improvement on 1 million in 8-10 hours...

Jamie
Post Icon Posted: 7 February 2008 - 12:50pm

Joined: 2007-10-04
Posts: 186

A lot of people have heard about this now, though people do seem a little vague as to what the conjecture is precisely. I just tell them to look at the forums.
Post Icon Posted: 8 February 2008 - 2:31pm

Joined: 2006-10-09
Posts: 318

Hrm, got the program working, took about 2.4s to do 100,000, which is nice. The problem i'm having now is i've got it running to 10,000,000 and task manager tells me it's using 1GiB of RAM... Memory may be more of an issue than I first thought... Although I've thought of a couple of ways of cutting it down (for example I don't free any memory anywhere at the moment...)

Jamie
Post Icon Posted: 8 February 2008 - 3:06pm

Joined: 2006-10-09
Posts: 318

Hrm, not as massively fast as I'd hoped based on the old speeds. I think I need to rewrite a chunk of it. It takes about 2.5-3 minutes to run up to 1 million, but unfortunately 10 million will take about 5 hours by the looks of it (although perhaps less now i'm running it on samir's machine, we'll see.

The biggest problem is memory, but to be honest I still think that time taken will be of the sort of length such that by the time we run out of memory the time taken will be in the days.

Jamie
Post Icon Posted: 8 February 2008 - 5:31pm

Joined: 2006-10-09
Posts: 318

Aha, not as bad as I suspected: 10 million results:

jamie@host-57-71:~/Documents> ./BPBIG
Time to complete prime list: 12.140000
Time to complete initial Boardman Array: 0.840000
Time to complete prime pair pointer list: 0.250000
Time to complete final Boardman Array: 7587.080000
4 is a counterexample to the Boardman-PBIG Conjecture!

Just over 2 hours to complete the 10 million attempt, and with 0 counterexamples! Hooray!

20 million should be about 7 hours, might try that next!

Jamie

edit: ah, screw it, 50 million is up and running.
Post Icon Posted: 8 February 2008 - 7:17pm

Joined: 2006-11-02
Posts: 811
4 is a counterexample to the Boardman-PBIG Conjecture!
:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O:O
Post Icon Posted: 8 February 2008 - 9:55pm

Joined: 2007-10-08
Posts: 12

if u read the conditions of the conjecture u will find that 4 is NOT a counterexample as it clearly states for all n>4 NOT n>=4
Post Icon Posted: 8 February 2008 - 11:28pm

Joined: 2006-10-09
Posts: 318

Yeah, we all know that, it's just useful to have 4 come up as a counterexample to show that the algorithm is working correctly! :D

Jamie
Post Icon Posted: 8 February 2008 - 11:38pm

Joined: 2006-11-02
Posts: 811
if u read the conditions of the conjecture u will find that 4 is NOT a counterexample as it clearly states for all n>4 NOT n>=4
I agree, disagree and "neutral" with you ad infinitum.
Post Icon Posted: 8 February 2008 - 11:39pm

Joined: 2006-08-31
Posts: 676

cosmin, please stop that.
Post Icon Posted: 8 February 2008 - 11:47pm

Joined: 2006-11-02
Posts: 811

The blockquote? You do it all the time, don't you? :p
Post Icon Posted: 8 February 2008 - 11:52pm

Joined: 2006-08-31
Posts: 676

The :O's I saw them. I see most things.
Post Icon Posted: 9 February 2008 - 12:08am

Joined: 2006-11-02
Posts: 811

Well, the fact that I changed my post shows I had already stopped. :p
Post Icon Posted: 9 February 2008 - 12:18am

Joined: 2006-08-31
Posts: 676

You changed them after I posted, I knew giving exec any power on the website was a mistake.
Post Icon Posted: 9 February 2008 - 3:12am

Joined: 2006-11-02
Posts: 811

Hmm, ok. Still, I edited it before I saw your post.
Post Icon Posted: 9 February 2008 - 2:42pm

Joined: 2007-10-08
Posts: 12

the other thing about -2, =4 was not a modification but an extension
so conjecture goes like this
A n in 2N, n>4 E p,q in P st if p+q=n either p+2 in P OR p-2 and q+4 in P
Post Icon Posted: 9 February 2008 - 5:37pm

Joined: 2006-11-02
Posts: 811

An extension is a modification...
Post Icon Posted: 10 February 2008 - 3:24am

Joined: 2006-10-10
Posts: 391

It is?? :O :O :O
Post Icon Posted: 10 February 2008 - 4:55am

Joined: 2006-11-02
Posts: 811

Well, not if you extend by $ \varnothing $...

:$ \varnothing $ :$ \varnothing $ :$ \varnothing $
Post Icon Posted: 10 February 2008 - 7:31pm

Joined: 2006-10-09
Posts: 318

The running to 50 million has worked with no counterexamples, total time taken was 39 hours, so less than 2 days!

Woohoo!

Jamie

data:

jamie@host-57-71:~/Documents> ./BPBIG
Time to complete prime list: 104.500000
Time to complete initial Boardman Array: 4.050000
Time to complete prime pair pointer list: 1.070000
Time to complete final Boardman Array: 142887.390000
4 is a counterexample to the Boardman-PBIG Conjecture!
Post Icon Posted: 11 February 2008 - 3:55am

Joined: 2006-10-09
Posts: 318

Right, Samir's said we need to get to 1,000,000,000 so I'm rewriting this stuff.

First, my creating primes thing is now working better thanks to use of Fermat's Little Theorem, have checked whether each number below 1,000,000,000 is prime in 85.375 seconds, now I just need to take that data, put it into some bitfields and I'm away!

Jamie
Post Icon Posted: 11 February 2008 - 9:52am

Joined: 2007-10-04
Posts: 186

Well you sure are working hard, 2:55am!
Post Icon Posted: 11 February 2008 - 11:53am

Joined: 2006-11-02
Posts: 811

Fermat's little theorem? Are you using a pseudoprime test?
Post Icon Posted: 13 February 2008 - 12:00pm

Joined: 2006-10-05
Posts: 534

That broke something.

Don't have to be exec to have power.
Post Icon Posted: 13 February 2008 - 2:31pm

Joined: 2007-03-03
Posts: 122