Follow Slashdot blog updates by subscribing to our blog RSS feed

 


Forgot your password?
Close
typodupeerror
×
Science

Grok Goldbach, Grab Gold 249

Posted by timothy from the proof-is-worth-a-million-dollars dept.
Caseman writes, "Are you a closet mathematician who wants to come out? British publisher Tony Faber is offering a cool million bucks to the first would-be math head to prove the infamous Goldbach conjecture. Yeah, the one about every even number being the sum of two primes. Impossible, you say? Remember Fermat's Last Theorem? It stood unproven for 350 years until a recent effort yielded a proof. Read The London Times article about the challenge. "
This discussion has been archived. No new comments can be posted.

Grok Goldbach, Grab Gold More

Grok Goldbach, Grab Gold

Comments Filter:

  • a question (Score:1)

    by Anonymous Coward
    Doesn't somebody (or five people, or six) make this exact same joke any time proofs are mentioned?

    Maybe I've been hallucinating, but I don't think so. Really, is anyone else still amused by this? I'm not.
  • So you can just take your proof and suck it.

    But really, what keeps n+2=q+r from being true (where q+r are prime), and n+4=s+t, and n+6=u+v, etc.?
  • > Lots of work has been done that could be useful
    > to the GC, just the same was as done for FLT.
    > The winnings will go not to the person who does
    > the most work towards it, but whoever supplies
    > the piece of the puzzle that happens to be last.

    But in mathematics it can be just as difficult (if not more so) to realise that there is some connection between two hitherto unrelated pieces of mathematics as it is to think up something original. Everybody recognises Wiles(*) as the guy who proved FLT, and everybody recognises that WIles' work couldn't have been done without earlier work of Ribet, Frey, Serre, ...

    ((*) Actually, the proof of FLT is more correctly attributed to Wiles and Taylor. Wiles uses a property of Hecke algebras that is proved in a companion paper to Wiles' `Modular forms, elliptic curves and Fermat's Last Theorem' that is contained in a supplementary paper by Taylor and WIles.)

    > This might encourage work on the GC, but it
    > also might discourage publication of such work,
    > because the mathematicians haven't quite
    > finished the proof.

    Unlikely. GC is sufficiently important to be independent of some monetary prize being given away as a marketing gimmick. It will give amateur mathematicians and cranks something to do for the next few months though...

    As for discouraging publication, this certainly wouldn't happen in the UK. Our universities are publicly funded and every 4 years have to go through the `Research Assessment Exercise' (RAE). Essentially, each university and each department within each university is graded according to how good the research output from the academic staff is. The grade each department gets determines how much money the government is willing to give in grant income. Doing well in the RAE is far more important (in terms of prestige for the university and promotion prospects for the staff involved) than deliberately witholding papers from publication because of some prize (no matter how large!). Any substantial progress towards GC would be of value when it comes to the RAE.

    Going back to the article, the time-frame seems unrealistic. A paper must be submitted to a journal with 2 years - the only way this is likely to happen is if somebody is almost all the way to proving GC already and has just not announced it yet. But to ask for publication within 4 years is pushing it. GC is sufficiently important to attract a lot of attention and interest and the journal to which it is submitted will want to make sure the proof is correct. Hence the refereeing process is likely to be lengthy. Then there's the fact that most journals have large backlogues meaning that it can sometimes take 3 years for a paper that has been accepted for publication to actually appear. Maybe GC is sufficiently important to be `fast-tracked' though...

    The most interesting thing about the article is that the prize is a 6 figure sum but the insurance premium is a 5 figure sum. So, roughly speaking, the insurance company thinks there is a 1 in 10 chance of somebody actually proving GC and getting it in print within 4 years! These insurers sound like they know something the mathematical community doesn't - maybe we should hire them for the next RAE ;-)
  • Here's a little something I worked out a few years back. If you have a number, n, which is the product of two primes, you can extract the primes with this formula:

    GCD(n, fact(floor(sqrt(n))))

    where GCD is the greatest common divisor function (easily calculated using Euclidean math), fact is a factorial function (which can be calculated using the gamma function), and the rest should be obvious. This will return the smaller of the two factors. The other can be found simply by dividing the answer into n. Understand, though, that this is only guaranteed to work if n is the product of two primes -- other numbers may or may not work (24 is a good example of one that won't work).

    But before you run off and celebrate that you have a quick way of breaking encryption codes, realize that most encryption uses extrememly large numbers, and calculating the factorial of such large numbers is rather futile.


    --
  • certainly not rocket science but since we're on the topic I thought folks might enjoy it

    #include <stdio.h>
    #include <limits.h>
    #include <math.h>

    static int isPrime(int x)
    {
    int result = 1;

    if(x > 1)
    {
    int middle = sqrt((double)x);
    int i = 0;

    for(i = 2; result && i < middle; i ++)
    if(x % i == 0)
    result = 0;
    }
    else
    result = 0;

    return(result);
    }

    int main(int argc, char **argv)
    {
    int i = 0;

    for(i = 4; i < INT_MAX; i += 2)
    {
    int j = 0;
    int found = 0;

    for(j = 2; !found && j < i; j ++)
    if(isPrime(j) && isPrime(i - j))
    found = 1;

    if(found)
    printf("%d = %d + %d\n", i, j, i - j);

    else
    printf("Goldbach Conjecture FALSE for: [%d]\n", i);
    }

    return(0);
    }
  • Eek! Mea Culpa - you are correct, I typed that program in in about 2 minutes compiled it, ran it and didn't bother to examine the output too carefully - oh well, that's what one gets for hubris ;-). This story's a bit old now but if you still care drop me a line and I'll send you the corrected version ... sorry about that ;-).

  • For a proof by induction, you express what you're trying to prove as a statement with a parameter n - call it P(n). Then you show that it is true for P(1) (or some other n), and that if P(n) is true (for any n) then it implies that P(n+1) is true.

    Then, for example, P(378) must be true because it is implied by P(377), which is implied by P(376), and so on down to P(2), which is implied by P(1), which you have shown is true separately.

    If you've proved that P(n) implies P(n+1) for any n, without assuming any special cases such as that n is prime, then it must be true for all n >= 1.

    Proving induction: the proof I've seen is a proof by contradiction based on the principle that the natural numbers are well-ordered. This means that any non-empty set of natural numbers must contain a lowest element.

    Now suppose you have a statement, P, that P(1) is true, and that P(n) implies P(n+1). To prove that this is sufficient to show that P(n) is true for all n, first assume it isn't - ie there are some values, k, for which P(n) is not true.

    Now let S be the set of all of these values, ie S = {k : P(k) is false}. As we have assumed that P(n) is not true for every n, S cannot be empty, so it must have a least element, x, by well-ordering. x cannot be 1 since we have shown P(1) is true separately.

    Therefore we have that P(x) is false, but P(x-1) is true since x is the least element of S. But x-1 is a natural number because x is, so by the inductive step P(x-1) must imply P(x). Therefore P(x) must be true, but by definition it is false. This is a contradiction, and as all the logical reasoning since the assumption was sound, the assumption must be wrong - ie P(n) is true for all natural numbers n, so S is empty and x doesn't exist.

    Andy

  • Link in your math library. Try adding -lm to your link line, but this is compiler-dependent of course.

    --j

  • This is picky, but his proof appeared when he was 19, not 20. His proof is a thing of beauty.

    --j

  • Some people are suggesting brute-force attacks, but this is laughable to anyone with even a passing interest in mathematics. Automatic Theorem Proving has been suggested here as well, but ATP has a lot of practical problems, especially in a more complicated domain such as mathematics or more specifically, number theory.

    Maybe in XEmacs 22?
  • Haven't you ever heard of the Prime Number Theorem? Primes have a relatively logarithmic distribution.

    See Mathworld [wolfram.com] on the issue.

  • Similarly, if we assume:
    1. 2 = 3
    we can multiply through by 0 to get:
    2. 0 = 0

    So (1) must be true. ;-)

  • But seriously, though, even numbers can be made by adding two odd numbers together. Any prime bigger than 2 is going to be an odd number, otherwise it would have at least 3 factors, now I'm starting to confuse myself, anybody know what sort of pattern a graph of primes makes?
  • Okay, where I was going with this is that you can generate even numbers by adding a positive odd number and a negative odd number, but I just realised that any negative odd number has at least 3 factors, +1, -1, and itself, so now I remember why I didn't major in math (other than that pesky having to get up and go to class thing).
  • Is 1 not a prime number (even though it is divisible only by 1 and itself) just because whoever wrote the rule said it wasn't or does making 1 a prime screw up something else (like letting division by zero be defined)?
  • Maybe if I'm lucky all the moderators are sleeping in this morning.
  • I am all too familiar with that nice feeling.
  • Actually, the incorrect operation is division by zero. Multiplication by zero is fine.

    ebw
  • Remember Fermat's Last Thereom was proven by someone who work alone and had very little help if any.
    This will encourage those lonely mathematician to do something come out of their shell. Anyways competion always help make things more interesting.


    http://theotherside.com/dvd/ [theotherside.com]

  • I wonder (Score:1)

    by jjr ( 6873 )
    I am curious what the math department at my school are going to say about this.
    Being one of 20 math majors at school I wonder if this is a challenge the other math majors
    (And maybe some CS people ) are willing to partake in. I guess I need to read up on my Number Theory
    I think that is one of my next classes to take :)


    http://theotherside.com/dvd/ [theotherside.com]
  • The comments about not allowing 1 as a prime so as not to mess up unique factorization have already been made (and pretty much all the number theory of primes would get messed up with it), but there is also a neat(ish) way of not allowing 1 as a prime number (this is a paraphrase of the definition that I remember being taught):

    "A prime number is a positive integer having _two_ unique positive integer factors, 1 and itself"

    1 is therefore let off the hook, because 1 only has one factor - itself, not the two required by this definition.
  • ehh... something bugs me about mathematical induction. How do you know that n+1 is going to work for all numbers without testing? Suppose there is a number somewhere along the way that behaves differently. Primes, for example, aren't evenly distributed in the integers. How do we know that "if p(k) AND p(k+1) then for every n, p(n)"? Do you have to use induction to prove induction? How does this work in math? My proof skills are a bit weak.
  • Thanks for the reference!

    I figured it was probably possible - my previous message was just politely trying to find out whether the first poster knew what he was talking about.

  • It has already been proven that no formula can generate the Nth digit of PI

    I'd be interested to see that proof, since a formula for calculating the nth digit of pi [mathsoft.com] does exist. The only catch is, the formula calculates the nth digit of pi in hexadecimal.

    If there really is a proof that it's impossible, then presumably that's for base 10 numbers? Do you have a reference?

  • Poked around with this thing for an hour or so. Seems like if you just start enumerating all the pairs of prime numbers and sum them up you construct all the even numbers. That won't float by itself though, cause the primes logarithmically taper out as you go...

    I asked the google miester [google.com] whether it had any ideas, and it came up with this site's proof. [mathematical.com]

    It's only 8 pages, and it seems pretty decent. I followed it till about page 4, and then I saw those capital pi product symbols and decided to run away.

    -Snoot

  • normality.
  • The book Satan, Cantor and Infinity by Raymond Smullyan has a good description of this problem and a proposed solution. (as well as lots of nifty truth-telling puzzles). Basically, the problem stems from the "Unlimited Abstraction Principle", which is that for any property description you can make a set of all things having that property. This is usually (Zermelo-Frankel set theory) replaced with the "Limited Abstraction Principle), which is that for a given set, a property divides that set into elements with that property and without. This allows all of Cantor's niftiness without the messy paradox.

    Other sources of good, understandable infinity:

    Mind Tools and Inifinity and the Mind by Rudy Rucker

    The Book of Numbers by John H. Conway and Guy (don't know his first name, offhand.

  • Are you saying that Landau essentially said that this is one conjecture that cannot be proved? If so is it possible to prove that it cannot be proved?
    Cantor's Continuum Hypothesis states that the "cardinality" (roughly count) of the real numbers is 2^(cardinality of integers). This is usually written using the Hebrew alpha, but I can't find this on my keyboard. See any of the references I gave in an earlier comment for more details.


    Anyway, it has been proven that this hypothesis cannot be proven or disproven with current set theory. I won't pretend to understand either proof at all, but they are generally well accepted.

  • Wrong, what you have shown is that for any center, there must be primes equidistant from it. This is not the same as saying that by knowing one point and centre, we can deduce another point. That "one point" has to be one with a specific property. If we know the center and the proper point to use, well then were really back at the beginning, except using:
    • 2*N-prime = prime
    for your equation.
  • Comment removed based on user account deletion
  • You can also use an approach called "Proof by induction", which works as follows:
    1. Show empirically that the conjecture is true for some specific value o
    2. Find a logical argument that shows that anytime the conjecture is true for any value n, it must also be true for n+1
    3. If 1 & 2 are true, then the conjecture must be true every value greater than o.
    Of course for this particular conjecture you would use n+2 in step two, since you are only interested in every second number.
  • 2.5) We all know that 1 != 0
    2.75) Combining steps 2 and 2.5, it must be the case that For all N, N=4
    --
  • this may futher your point of "anyone interested in Slashdot should still be for [gore]."

    this is made by one of those "people with relatively weak intellectual immune systems."

    The following quote comes at the end of a recent email from Bush to Gore.

    "Thank you for your email. This Internet of yours is a wonderful invention"

    take it as you will, i wanted McCain.
  • I can just see some old grandma coming out of the wood work announcing that she has a proof. she then goes on to show it using lemon drops and apple pie, therebye stunning the mathematics community.

  • For some reason this post brings up an interesting question. suppose within two years i create a sufficiently(sp?) capable ai, that then goes on to create a proof for GC.

    do i still get the prize money?
  • And more than that, Wiles' proof, IIRC, uses plenty of number theory and other unrelated disciplines which didn't even exist, and where far from suspected in Fermatt's time... so, if Fermatt had a proof using the number theory in his time, it has to be very inteligent and/or full of ingenuity.

    Fermatt was a genius. And he was a joker. So, in a way, Fermatt's Last Theorem is *still* unresolved. Wiles' proof is NOT the proof Fermatt had, if he had one. :)
  • Taken from a lecture this winter by Carl Pomerance of Bell Labs/Lucent:

    - The conjecture is true for numbers less than 10^14

    - All sufficiently large even numbers are the sum of a prime and (the product of 2 primes). Note that this product is thus composite, but not very!! So this fact is kinda close to the GC.

    - All sufficiently large odd numbers are the sum of 3 primes.

    - If the generalized Riemann Hypothesis is true, all odd numbers bigger than 5 are the sum of 3 primes.

    - There will generally be multiple representations of a given number as the sum of two primes. The count of these representations is large, and is suspected to go as n/( log(n)*log(n) )

    This is probably too late to reach many people, but oh, well.

    - Brian
  • My friend Jon wrote a C program the other day that made a list of prime numbers. He's currently past 1,000,000. I'm sure that his program could be modified in some way as to test these numbers. However, I don't think he'd enjoy using his CPU for that.

    Hah, your frend must be a pretty crappy programmer then, I've written a program that searches all the primes in prettymuch linear time, 10,000,000 takes about 3 or so seconds (on a p200, when I last ran it, btw)
  • Actualy, I belive that you only have to prove for n > 4...

  • Disproof. (Score:2)

    by Anonymous Coward
    What if you disprove the theorem? Then what, huh? No money?
  • Let's say I want to prove this about the sum of all the positive odd numbers up to some number n:

    1 + 3 + ... + n = (n + 1)^2 / 4

    We know that, for n = 5, 1 + 3 + 5 = (5 + 1)^2 / 4 = 9, and so the formula is true for n = 5. Now assume that the formula is correct for all n. What happens if we work it for n + 2?

    1 + 3 + ... + n + (n + 2) = ((n + 2) + 1)^2 / 4 - substitute n+2 for n in the formulas
    (n + 1)^2 / 4 + (n + 2) = ((n + 2) + 1)^2 / 4 - substitute the assumed true value in for 1 + 3 ... + n
    (n + 1)^2 / 4 + (n + 2) = (n + 3)^2 / 4 - add n + 2 and 1
    (n + 1)^2 + 4(n + 2) = (n + 3)^2 - Multiply through by 4
    (n^2 + 2n + 1) + (4n + 8) = n^2 + 6n + 9 - multiply everything out
    n^2 + 6n + 9 = n^2 + 6n + 9 - add everything up. This is true for all n.

    What all that means is that if the formula holds for n, then it must hold for n + 2. And since it holds for n + 2, it must hold for n + 2 + 2, and so on into infinity. I came up with one n (5) for which the formula works, so it must work for all odd numbers larger than five. I don't have to test all the odd numbers into infinity - the infinitely recursive nature of induction does that for me in something that can be expressed in a noninfinite amount of data (and a good thing, too - I don't have enough bandwidth to post an infinite-length comment to /.)

  • To say that every even number >2 is the sum of two primes is to say that every integer >=1 is the mean of two primes.

    This, in turn, means that for every integer I, there is a circle, such that the centre is at I and the intersection of the circle with the positive natural numbers will occur at two prime numbers.

    Now, how does this make things any easier? Simple. If the distribution of primes is =totally= random, this statement HAS to be false. Randomness means that by knowing any number of points, you cannot deduce an unknown point. Here, we have shown that by knowing one point and a centre, we can deduce another point. This implies an inherent relationship between the prime numbers.

    Thus, IF AND ONLY IF the prime numbers are non-random, Goldbach's Theorum is correct. If, however, they ARE random, it would be impossible to define a geometric relationship, which (as shown) does exist.

  • Primes are definitely not random. In fact it can be proven that they have a distribution such that the number of primes less than x is about
    x/log(x). Read more at http://www.utm.edu/research/ primes/howmany.shtml [utm.edu]
    --
  • You are holding waaay too much in memory. If you have 7000 primes, and you consider all pair of them, that is 49,000,000 numbers. If you were slightly smart about it you could cut that in half.

    As you noticed, this is pretty inefficient.

    A much better way to slice this problem is to look at the numbers as an array of bits. For instance the first 800,000 numbers is a 100 K string. Start off with a block of 0's. Generate a vector of primes. Shift the vector by 2. OR it with your first vector. Shift by 1 more. OR it with your first vector. Shift it by 2 more. OR it again. Shift it by 2 again, then 4, then 2... (We are walking through cumulative shifts equivalent to the number of primes.)

    You can make it faster still by having your bitmap being only the even numbers. You will have to do a bit of thinking. But you should find that this approach is significantly faster and cuts down tremendously on the memory. You will also find that after a few shifts you will have covered most of the territory. At some point it becomes more efficient to track down each one you have not tracked down and search for primes that add up to that one...

    Cheers,
    Ben

  • In fact (Score:2)

    by tilly ( 7530 )
    With the probability reasoning it is trivial that there are (100% probability) only a finite number of exceptions. The odds of there being any after you have verified the first 100,000 cases is pretty small. But it gives you no idea how to prove it.

    Likewise the probability result strongly suggests that the Riemann conjecture is true. But again, it gives no insight into the real problem.

    However when you compute statistics, perfect match with the probability prediction. :-/

    Cheers,
    Ben
  • That's definitely not the only way to prove stuff like this. It goes back to the fact that you can use a generalized definition to talk about all those numbers up to infinity, and then prove based on the definition instead of on real numbers.

    For example, prove that every single possible even number is the sum of two odd numbers. Instead of looking at all the examples, we'll go by definition.

    Definition of even number: 2x, where x is an integer.

    Definition of odd number: 2y-1, where y is an integer.

    So if the even number is 2x, that is the same as 2x-1 + 1, which is two odd numbers added together.

    That was a really simply example, but hopefully you get the idea. No matter what even number you choose, it fits that definition. 993928302390 fits the definition, and plugging it into the equation, the two odd numbers are 993928302389 and 1. I just didn't have to do as much work to get there as you will :)

    --John
  • Mathematics is a great cooperative venture. It wouldn't be easy to identify one mathematician who did the largest share of the work
    Probably the money would go to the person who completed the proof, that is, did the last few steps, essentially dismissing any work done previously by others. As you point out, this isn't a terribly fair method of compensation. The uniqueness of the winner's status would be a disincentive to anybody who had a lot to contribute, but was reasonably unsure he'd accomplish the last few steps of the proof.

    An interesting counter-proposal to address this dilemma is proposed by a New Zealand economist named Ronnie Horesh, at http://www.geocities.com/WallStreet/9856/ [geocities.com], albeit in a different context. Horesh's idea is a social policy bond issued by a government or somebody else with deep pockets and a social agenda. The bond is redeemable for a large fixed sum when the goal is achieved. Until then, the bond is a good that can be bought and sold like a share of stock. Like a share of stock, its price will rise as the goal moves closer to being accomplished. The purpose of inventing these bonds is to delegate the implementation of social goals to free market forces.

    If a mathematician felt confident that he had made an important contribution, but didn't feel confident that he'd complete the proof himself, he could buy bonds cheaply as soon as they were issued, and hold onto them until the proof was complete. When the proof was made public, each bond would become redeemable for a large fixed sum, and the guy who bought early would make big bucks.

  • Erg. Sorry, wrong answer.

    Mathematics is replete with proofs about infinite sets of numbers. My personal favorite (mostly because I actually understand it) is Cantor's hypothesis:

    Cantor wanted to prove that even though there's an infinite number of integers, and an infinite number of "real" numbers, there are clearly more real numbers than integers. So he devised this infinitely large list. You take every real number (even ones of infinite length) and write them down on a convenient piece of infinitely large graph paper, one digit per square. Finally, you number each one in the left hand column with a counting number (positive integer).

    Now, since you've used graph paper, you can show that there's a real number not on the list. You start at the first real number, take the digit in the first column, and change it to something else. Go to the second number, take the digit in the second column, and change it. And so on, and so forth, blah blah, nth digit from nth number, etc. In the end, you have a new real number which can't be duplicated anywhere on the list, because it's sure to vary from every other number by at least one digit. Furthermore, even if you add the new number to the bottom of the list, you haven't solved the problem: you can make a brand new number which still doesn't appear anywhere on the list just by repeating the process. This kind of proof utilizes what's called a "diagonalization method", since the number you wind up constructing can be viewed by drawing a diagonal line across the list of reals you made up.

    Anyway, this is getting way too long. The upshot: there are plenty of examples in mathematics of people making proofs about infinite sets of numbers, and they don't have to sit down with calculators for an infinite length of time to write them. More to the point, since no one actually can enumerate all of the primes (because there are infinitely many of them, see), no computer program is going to be solving this one any time soon.
  • Well, you can just e-mail that to me and I'll be sure to pass it along to Rob Malda so he can post it elsewhere on the page :) ...just take out the TINLC part, there is no lumber cartel.... :)

  • That is - an extremely small probability!!!

    Yeah, but close only counts in horseshoes, hand grenades, and Inter-Continental Ballistic Missiles..... :)

  • An odd number is some integer (n*2)+1. There is no integer that will satisify 0 = (n*2)+1. Therefore, zero is not odd (it's even).

    A prime number is some integer that is divisble only by 1 and itself. Since a denominator of zero is undefined, zero cannot divided itself. Therefore, zero is not prime.

  • Andrew Wiles' proof of FLT runs into the hundreds of pages and makes use of vast tracts of number theory, some dating back hundreds of years. It can probably only be understood in full by a handful of top mathematicians.

    Now that FLT has been proven, what about Fermat's comment about his "great proof"? Do modern mathematicians believe he was joking? Or did he have some different, simpler proof? That he would have the same lengthy page proof seems unlikely, but it would definitely fit the description of "too large for the margin of this book"! ;-)


  • try compiling with -lm.
  • What do you mean "such as this"? The whole point of a proof is that it is deeper than a whole list of numbers with checkmarks beside them. "Yep, 5 is sum of two primes. Yep, 7 is the sum of two primes." is just a demonstration, not a proof.


    --
  • "Who Wants To Be A Millionaire" is the American version of a British show. Only... nobody there ever won the big prize (the insurance company that pays the prizes is rather upset).
  • If we find a counterexample, thereby proving the conjecture false, do we also collect the million?

    Time to get a cluster searching, eh?
  • As someone else noted, many people think Fermat stumbled on one of the elegant but incorrect proofs of his theorem that other people produced over the years. In fact, although the marginal note was made toward the end of Fermat's life, it's not like it's the last thing he ever wrote; he did write letters afterward, and he didn't mention the theorem in any of them, so it seems plausible that he himself realized his proof was incorrect, and so he dropped the matter.


    -rpl

  • Not in ISO C in doesn't; it's undefined. In "pidgin C" it does [...] Specifically, operators lik ^= do not define sequence points, so there's no assurance that the inner assignment will happen before the outer one.

    Well I don't have a copy of the standard, but my fragment compiles without warnings on gcc 2.95.2 using the -pedantic option. Since that's meant to make gcc complain about non-ANSI (i.e. ISO) extensions, does that mean this is a bug in gcc? Are you sure it hasn't been added to the standard since the version you've seen?


    Hmm the standard says that ^= and -= are right-associative and have the same precedence. The associativity should force the expression to be evaluated as I claim.


    Of course, my version hasn't been carefully analyzed, but I wouldn't make it my .sig. ;-)

    Would you care to provide a reference saying where in the ISO standard I should look to see what you're saying?
  • operators like ^= do not define sequence points, so there's no assurance that the inner assignment to b will happen before the outer one.

    But = also does not define a sequence point, so by that argument "a=b=c=d=2" is also undefined. What am I missing here?
  • where does 0 fit in

    Ok, I lied slightly, it is more normal to say "any *natural* number" rather than "any number". A natural number means 1, 2, 3, ... . So yes, 0 is excluded from this theorem.
    What about the primes themselves if 1 is not a prime [...]? What are the prime factors of 5?

    Again, the definitions are tailored specially so that things are neat to state. To a mathematician, "a product" doesn't neccessarily mean two or more numbers. Just "5" by itself gets counted as a product. And the empty product, the product of 0 numbers, is arbitrarily defined as being "1". So the prime factorisation of 5 is "5", and the prime factorisation of 1 is "".

    You're probably thinking that the "empty product equals 1" thing is a bit bizzare. It's worth comparing with addition. What do you get if you add zero numbers together? Answer: 0. 0 is the number that makes no difference when you add it to things. Similarly, 1 is the number that makes no difference when you multiply things by it. Hmmm, I'm not sure if that makes it any clearer, but hey.

  • _Why_ is the prime factorization theorem so fundamental to arithmetic? [...] Nobody ever explained why [factoring] is useful to anyone outside of number theory.

    Factorising isn't exactly very "useful". It's more that it's kind of the underlying thing that causes the numbers to work like they do. Without the Fundamental Theorem, mathematicians couldn't have any sort of a grip on what the hell multiplication "is". With the Fundamental Theorem, we know that multiplication has this nice, orderly property which allows us to understand it well enough to prove more difficult stuff.


    So you're right, to an engineer, or a scientist, factorization isn't very useful, because these people just "use" arithmetic, as a sort of contraption that works. The Fundamental Theorem is only Fundamental to a mathematician, who is interested in studying the contraption itself.


    what's the piece of code in your .sig supposed to do?

    If a and b are two non-zero integers, it replaces a with the highest common factor of a and b (clobbering b in the process).
  • I just looked it up so I'll correct myself. The conjecture was Bertrand's, and it was first proved by Chebyshev. Erdös found a shorter, neater proof when he was 20, causing some witty soul to come up with the following rhyme:
    Chebyshev said it, and I say it again,

    There is always a prime between n and 2n.

    Who says mathematicians can't write poetry? Hmmm.

  • "Words have their meanings to help you understand", as Lauren Savoy would have it. The word "prime" is defined in the way which makes the word most useful. The central fact about primes is that "any number can be expressed uniquely as a product of prime factors" (ignoring the order in which you write the factors). This is regarded as so fundamental that it's called "The Fundamental Theorem of Arithmetic".


    If we were to accept 1 as a prime, there'd be lots of ways to prime-factor a number, e.g. 9 = 3*3 = 3*3*1 = 3*3*1*1*1*1. So to keep the Fundamental Theorem true, we'd have to say "except 1" in it. There's also lots of other theorems where you'd need to say "except 1" for similar reasons, so it works out as more convenient to exclude 1 when defining the word "prime".


    For this reason also, we exclude negative numbers from being prime. Otherwise, 9 = 3*3 = -3*-3 etc.

  • You have to be able to prove that there MUST be a prime P between any 2X > 4 and X.

    This is true; IIRC it was proved by Ramanujan.


    Another useful fact: (number of primes less than N) tends to N / log(N) as N tends to infinity. This is called the prime number theorem.

  • they count as integers :)

    but I dont think so
  • you need a generalised proof.. something like induction.. betchya wished you'd paid attention in math class now!
  • what I did first was to figure out the number of primes that sum to the first 20 or so evens.. obviously it's been done before (hey, I was hoping for a fibonachi sequence or something groovy like that).. anyways

    http://www.research .att.com/~njas/sequences/Sindx_G.html#Goldbach [att.com]
  • The k p (calc-prime-test) command checks if the integer on the top of the stack is prime. For integers less than eight million, the answer is always exact and reasonably fast. For larger integers, a probabilistic method is used (see Knuth vol. II, section 4.5.4, algorithm P). The number is first checked against small prime factors (up to 13). Then, any number of iterations of the algorithm are performed. Each step either discovers that the number is non-prime, or substantially increases the certainty that the number is prime. After a few steps, the chance that a number was mistakenly described as prime will be less than one percent. (Indeed, this is a worst-case estimate of the probability; in practice even a single iteration is quite reliable.) After the k p command, the number will be reported as definitely prime or non-prime if possible, or otherwise "probably" prime with a certain probability of error.

  • Faber has stipulated that the proof must be submitted to a respectable mathematical journal within two years of the book's publication next week, and published within four years. A panel of world-renowned mathematicians will be appointed to decide whether the proof is valid (Faber is refusing to disclose the panel's names, for fear that they will be flooded with letters from amateurs).

    I have a serious question here, and I hope that someone might be able to answer it.

    From the tone of the article, it sounds like they are expecting somebody in the mathematical community to submit it, if anybody does. How would say, me, your average slashdot reader, go about claiming such a prize? I have no idea how one would go about publishing something in a mathematical journal, and with such a prize at stake how would one prevent one's proof from being stolen by someone else (like a person you find to "help" you get it published)?

  • This might encourage work on the GC, but it also might discourage publication of such work, because the mathematicians haven't quite finished the proof.

    It does make sense to have lots of people offering lots of little prizes all over the place.

    As I've pointed out in The Bowery Prize for Amateur Rocketry [geocities.com]:

    The Internet provides a unique opportunity to promote space technology via prize awards. Individuals can post a public pledge of money as a prize award for any technical objective they see fit, to be disbursed at their sole discretion. With enough diversity of people and technical objectives, there would be a "fuzzy" gradient of incentive created for ever higher performance amateur rockets, not dependent on the credibility of any one organization's political structure for "fairness" or good technical judgement. A periodic posting of all such prize award offers in this, and related, newsgroups, would serve as an ongoing challenge to technical excellence and as an inspiration for young people.

    This sort of approach to what should be called "Contest Philanthropy" will address the concern that people will hold off publishing important but obscure work.

    Here's how:

    If a bunch of mathematicians believe a particular popular conjecture is critically dependent on some obscure, but hard, math getting done, then all they need to do is post a prize award that promises they will give half their winnings for the popular conjecture to the mathematician who does the obscure work. If enough credible mathematicians target a particular obscure piece of work, then the philanthropists can start providing direct prize awards for that support work.

  • Unfortunately, that does nothing to make finding prime numbers any easier. IE, knowing the approximate shape of the graph (and the graph isn't perfect) still doesn't give you any information for calculating the next prime number. You have to pick a number (ending in 1,3,7, or 9), brute force it to test its primitude (I just made up a word!) by dividing it by all previous primes = the square root of the number you're testing.
  • For those banging their heads against the monitor. He multiplies by zero at one point. Then, all bets are off.
  • But your assumption is wrong. How about:
    1) Assume 1 == 1
    2) Either 1 == 1 or N = 4 for all N
    3) 4 is the sum of two primes
    4) by 2 and 3, for all N, N is the sum of two primes
    5) Since all numbers are the sum of two primes, all odd numbers are the sum of two primes (QED)
  • If it turns out that the conjecture is not true, then you would only have to produce a single even number, and the primes beneath it.

    Finding that number is left as an exercise for the reader. Heh.

    Best regards,

    SEAL

  • An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself.

    Thus, negative numbers are not prime.

    Best regards,

    SEAL
  • Maybe.. maybe not. Think Fermat's last theorem. This would be the obvious approach for that too except that a proof was found differently(elliptic curves and all that cool stuff). Primes are a little more trickier to deal with than regular integers, though. Besides, according to the article someone has already proven that all odd integers starting from some sufficiently large number are the sum of three primes. Now just reduce the number to 5, add even numbers and collect million bucks.. think I'll try it tonight on my lunch break.. not.
  • People should try to get the full story on Gore before dismissing the one candidate who actually knows something about technology. Gore's comment was that he "took the initiative in creating the Internet," and he said it in the context of trying to differentiate himself from Bradley and other challengers. A charitable reading (and what Gore should have said) is "among the candidates for President, I am the only one who showed significant government leadership in helping to foster the Internet."

    Slashdotter's should consider reading "Brill's Content" magazine for its recent story on the media's incompetent handling of the "Gore invented Love Canal" story. Then they should ask themselves if a guy as smart as Gore, who actually does have well-reported techno-wonk credentials, would really have claimed to have "invented the Internet."

    Gore was one of the leading proponents of the "information superhighway." Now, if he wants to talk more about it, he runs the risk of a bunch of know-it-nothings laughing at him and hurling once-funny cheap shots.

    This "Gore says he invented the Internet (har-har)" stuff is a silly mental virus propagated by people with relatively weak intellectual immune systems, IMHO. That's not to say they are stupid, just susceptible. Gore fouled up his line, true. But anyone interested in Slashdot should still be for him.

  • Ah, but you can't say that a formal proof is the correct method unless you have proved that a proof exists.

    In which case, you have proved the conjecture and should be collecting your prize rather than posting to slashdot.....

    If on the other hand the above proof does not exist, then there must exist a counterexample. Therefore searching by brute force may be a perfectly valid approach.
  • I think that if you came up with a valid proof, people would take you seriously very quickly and you would have no problem getting published.

    Having said that, I somehow doubt that anyone who isn't already a fairly academic mathematician will be able to prove this one. It's a famous problem, and you can bet that virtually every simple route to a proof will have been tried already.

    Of course, I would be extremely amused if someone with no mathematical background whatsoever were to prove it :-)
  • Hmmmm.... you can't actually *prove* Goldbach's conjecture by direct computation because the number of combinations you would have to try is infinite. It's the same reason why you couldn't prove Fermat's Last Theorem this way.

    You could of course *disprove* the conjecture by finding a counter-example, i.e. by finding a positive even number X>2 such that X is not the sum of two primes.

    It would certainly be fun if you were to find such a beastie, but I think you might be in for a long search :-)

  • First, IANAM

    you wrote The word "prime" is defined in the way which makes the word most useful. The central fact about primes is that "any number can be expressed uniquely as a product of prime factors" (ignoring the order in which you write the factors). This is regarded as so fundamental that it's called "The Fundamental Theorem of Arithmetic".

    This fundamental theorem seems to me to be wrong in principle, it requires 1 not to be a prime, where does 0 fit in (or is it not a number). What about the primes themselves if 1 is not a prime, or have you just mis-stated the theorem?

    What are the prime factors of 5?

  • yes, it is possible. The point is made in the article that simply showing that it is true for a large number of candidates is NOT a proof, as you will, by definition, never make it to infinity.

    The trick is to use an abstract and generalised proof, for example:

    by contradiction: you say that the conjecture is untrue, then extrapolate some fact from this which is patently untrue. Hence the initial conjecture must be true.

    by induction: you show that for some instance n the conjecture is true. You then show that for the general step n+1 the conjecture must also be true through the use of some logical argument, rather than just testing it. Hence the conjecture must be true for all instances.

    abstraction: find some analogous system and proove it for that. For example, when doing analysis of AC curcuits the common technique is to consider the current and voltage as phasors (ie. V*e^i*theta)and manipulate the phasors which is much simpler. When the manipulation is complete you can simply take the real/imaginary part of the result, and you have your answer. This makes use of the identity that e^i*theta = cos theta +i*sin theta. (I shall leave the proof as an excercise for the student [grin])

  • 1 isn't a prime number, as this would cause the natural numbers not to be a unique factorization domain.
  • at least in the UK you seem to value education and things such as this. Here in the states we prefer to have people win a million dollars by either picking 7 random numbers and watching ping pong balls or answering 10 questions or so from Regis.
  • Before too many intelligent minds fall to the task of disproving Goldbach's conjecture, let me suggest the likely purpose to the proposed contest:

    Goldbach's conjecture is very probably true; mathematicians and number theorists don't need to be reminded of that and likewise don't need to be bothered by "amateurs" (really, lay-people without formal education in number theory) who suggest that the conjecture is false. In all matters of fact, while I am sure that Faber and his erudite associates would be happy to be presented with a valid counter-example, said mathematicians probably aren't losing any sleep over the possibility. What Tony Faber is looking for and what's worth $1m to him is not the labors of the unitiated towards a hopeless cause but is instead the establishment of the conjecture's logical truth by means of established principles of number theory -- he wants to know how this elegantly simple and ostensibly true statement may be derived from postulates and previous proofs, not, regrettably, whether or not it is true.

    There has been some grumbling over the apparent fact that Faber is trying to keep the proof of Goldbach's conjecture within the mathematical community. If the conjecture is proved, it will be through the collaborative efforts of the professional mathematic community -- I simply can't see someone without extensive background in number theory really having a chance of winning the contest. Remember that the proof of Fermat's theorem was by no stretch of the imagination simple and elegant. If there were an elegant proof to Goldbach's conjecture, it would almost certainly have already been realized by mathematicians who are just as intelligent and, if anything, better-versed in matters of number theory than folks like you and me, and if there is a proof, I suggest that its development will not be a feat accomplishable by anyone who doesn't make their living in mathematics.

    And before anyone tries to make this proof a black&white, true/false issue (too late?), let us remember the work of mathematician Kurt Gödel:

    Gödel's most famous contribution was the proof that some statements about natural numbers are true but unprovable.... [his] proof demonstrated that the axioms of number theory are incomplete. That is, there are true statements about the natural numbers that cannot be proved by those axioms. (J. W. Dawson, Jr., Scientific American - June 1999)

    Do I underrate the ingenuity of the human mind? I hope so; however, I would like to think I am merely being realistic. It seems to me that blind beginner's luck has been drastically overrated in response to the proposed contest.

    To those of you interested by the prospect of testing every reasonably-large even number to find a counter-example and thus disprove the conjecture, and especially to those of you who have suggested that the resources of distributed.net be used in so doing, please refer back to sela, 3/19. I'm afraid you'll be wasting your time.

  • Re:Disproof. (Score:3)

    by Anonymous Coward on Sunday March 19, 2000 @04:19AM (#1192766)
    What if you disprove the theorem? Then what, huh? No money?

    If you disprove the theorem then you pay them $1 million.

  • I know! I know! ...uh, nevermind. (Score:3)

    by unitron ( 5733 ) on Sunday March 19, 2000 @03:50AM (#1192767) Homepage Journal
    Do negative numbers count as primes?

  • Al's got the proof! (Score:3)

    by semis ( 14252 ) on Sunday March 19, 2000 @06:22AM (#1192768) Homepage
    Honest,

    Al Gore told me he's got the proof to this theory - he did it while he was inventing the Internet, and Open Source and all that.

  • My Proof (Score:3)

    by FascDot Killed My Pr ( 24021 ) on Sunday March 19, 2000 @04:17AM (#1192769)
    1) Assume 1 == 0.
    2) Then clearly this follows Either 1 == 0 OR N = 4 for all N
    3) Obviously 4 is the sum of two primes (2+2)
    4) Combining steps 2 and 3 we get For all N, N is the sum of two primes
    5) Step 4 states that all numbers are the sum of two primes, therefore all odd numbers are the sum of two primes.
    QED
    --

  • Suggested reading (Score:3)

    by David A. Madore ( 30444 ) on Monday March 20, 2000 @02:44AM (#1192770) Homepage

    The first step any Goldbach-conjecture-prover-wannabee should take is to read the book ``Additive Number Theory: the Classical Bases'' by Melvyn B. Nathanson, in Springer's Graduate Texts in Mathematics (number 164). It contains a description of the sieve methods and the Hardy-Littlewood-Ramanujan circle methods used to prove that sort of results in additive number theory. It gives a proof of the closes results known to Goldbach's conjecture: Vinogradov's theorem that every sufficiently large odd integer is the sum of three primes, and Chen's theorem that every even integer is the sum of a prime and a number which is at most product of two primes.

    If you think it must be interesting reading, you're dead wrong. I have read many boring proofs in my life, but none of them came even close to the total lack of interest, the absolute and utter dullness of the analytic estimations of additive number theory, as found in the book in question. Even the (much easier) proof of Waring's problem (every integer is the sum of a bounded number of k-th powers, where the bound depends only on k) is unconceivably dull, and it is nothing compared to the more subtle results in the second part of the book.

    Now why couldn't they offer a million dollars for proving the Riemann hypothesis. At least that's a worthwile result (nobody cares in the least about Goldbach's conjecture, but the Riemann hypothesis has many fascinating consequences).

  • Fermat's last theorem (Score:3)

    by Captain Zion ( 33522 ) on Sunday March 19, 2000 @05:47AM (#1192771)
    Are mathematicians finally satisfied with Andrew Wiles's proof of Fermat's Last Theorem? Scientific American [sciam.com] Ask the Experts section has comments about that and why has this theorem been so difficult to prove [sciam.com]. Here's an excerpt:
    "Yes, mathematicians are satisfied that Fermat's Last Theorem has been proved. Andrew Wiles's proof of the 'semistable modularity conjecture'--the key part of his proof--has been carefully checked and even simplified. It was already known before Wiles's proof that Fermat's Last Theorem would be a consequence of the modularity conjecture, combining it with another big theorem due to Ken Ribet and using key ideas from Gerhard Frey and Jean-Pierre Serre.

  • Some code.... (Score:3)

    by chazR ( 41002 ) on Sunday March 19, 2000 @04:38AM (#1192772) Homepage
    // usage: goldbach
    // Lists all pairs of primes that sum to
    // Copyright Chaz Randles 2000
    // Licence: GPL

    #include
    #include

    using std::cout;
    using std::endl;
    using std::vector;

    vector * get_primes(int maxPrime) {

    vector* result = new vector();
    vector::iterator it;

    bool isPrime;

    result->push_back(2); // 2 is prime

    for (int candidate = 3; candidate begin(); it!=result->end(); ++it) {
    if (!(candidate % *it)) {
    isPrime=false;
    }
    }
    if (isPrime) result->push_back(candidate);
    }
    return result;
    }

    bool find(vector* vec, int data) {

    vector::iterator it;

    bool found=false;
    for (it=vec->begin(); it!=vec->end(); ++it) {
    if (*it==data) {
    found=true;
    break;
    }
    }

    return found;

    }

    int main(int argc, char** argv) {

    if (argc!=2) {
    cout " * primes=get_primes(num);
    vector::iterator it;

    for (it=primes->begin(); it!=primes->end(); ++it) {
    if(find(primes, num - (*it))) {
    cout num '\t'*it'\t'num - (*it)endl;
    }
    }

    delete primes;

    return 0;
    }

    // Apologies for poor quality code - done in 10 mins

  • I notice the other guy didn't actually answer your question, so maybe this would help. If you should actually come up with a proof, the Journal of the American Mathematical Society [ams.org] would be a good place to start. On their website they have a link with submission instructions. I didn't look at their particular instructions, but it's pretty safe to assume that they expect the manuscript to be in LaTeX using the AMSTeX macro package. Send it wherever the instructions say to send it. That's pretty much it. From there the scientific editor will probably hand it off to a referee, and you will get back status reports as things progress. I guess if you are really paranoid about someone trying to claim your idea you could take a hardcopy, date it, and take it to a notary or something, but really it shouldn't be a problem.


    Having said all that, the other poster was right; if this were easy someone would have done it already. At the very least you will need enough mathematical background to write with the correct terminology and symbols. Really you shouldn't seriously attempt this sort of research without first becoming familliar with what other people have tried and why it didn't work. Please don't annoy the journal editors with bogus submissions (not that I think you were planning to, but it bears repeating nonetheless).


    -rpl

  • With a conjecture such as this, isn't it impossible to find a proof without trying every even number bigger than 4, up to infinity?

    No, you can do tricks like "proof by contradiction". That works as follows:
    1. You pretend the claim isn't true. In that case there must be some number x which isn't the sum of two primes.
    2. This is the clever bit: you find a logical argument which shows that if such an x existed then, consequentially, something impossible would happen. So you might find a logical argument that says if you have such an x then 1=0.
    3. You conclude that, therefore, there can't possibly be any such x. Hence you've proved the conjecture.

  • Doesn't quite work ... (Score:3)

    by divec ( 48748 ) on Sunday March 19, 2000 @05:47AM (#1192775) Homepage
    I'm assuming you're not trolling, or I'm replying for anyone else who's wondering.
    every Even number can be written as the sum of not more than 300,000 primes

    That means that "there is some way to get to any even number by adding together less than 300,000 primes". It doesn't mean "no number can be obtained by adding more than 300,000 primes". The second statement is clearly false. e.g. if
    a = 2 + 3 + 5 + 7 + 11 + ... + (300,001th prime)

    then a is the sum of 300,001 primes.
  • Lots of work has been done that could be useful to the GC, just the same was as done for FLT. The winnings will go not to the person who does the most work towards it, but whoever supplies the piece of the puzzle that happens to be last.

    Mathematics is a great cooperative venture. It wouldn't be easy to identify one mathematician who did the largest share of the work even if they tried to do it that way, and if they did it would probably be Gauss or Poincare or some other dead heavyweight genius.

    This might encourage work on the GC, but it also might discourage publication of such work, because the mathematicians haven't quite finished the proof.
    --

  • I know the proof. (Score:5)

    by Masem ( 1171 ) on Sunday March 19, 2000 @04:18AM (#1192777)
    I have to proof to the Goldbach conjections.

    Unfortunately, the slashdot comment submission box is too small to post the whole proof. I shall leave the proof to the reader.

  • Not to discourage anyone but.. (Score:5)

    by mav[LAG] ( 31387 ) on Sunday March 19, 2000 @04:28AM (#1192778)
    ..saying that a "recent effort yielded a proof to Fermat's Last Theorem" is a bit of an understatement. Andrew Wiles' proof of FLT runs into the hundreds of pages and makes use of vast tracts of number theory, some dating back hundreds of years. It can probably only be understood in full by a handful of top mathematicians. It took him something like seven years of concentrated work with no guarantee of success and included one horrible non-proof which he was able to fix to produce the Real Thing some months later.

    Yes, it is possible that the Goldbach conjecture may be proved or disproved by a lay person but it's far more likely to be solved by someone with a sound grasp of lots of number theory who is already studying the properties of numbers for a living.

    BTW I have a truly marvellous proof of the Goldbach conjecture but there is no margin on the submit form to write it in :)

  • Probability ... (Score:5)

    by sela ( 32566 ) on Sunday March 19, 2000 @07:44AM (#1192779) Homepage
    Disclaimer: long boring math stuff with a conclusion that may be interesting for some at the end ...

    An interesting question is: assuming prime numbers are "randomly" distributed, what is the probability that an even number won't be the sum of two odd numbers?

    If the probability is rather high, yet we did not find any such even number, it can be an indication there may be some "meat" in goldbach theorem. On the other hand, if such probability is exremely low, than the verification of goldbach's theorem up to 4e+15 means nothing ...

    Well, according to Gauss' estimate for prime number density around sufficiently large n, the density is 1/log(n). To find pi(n), which is the number of prime numbers up to n, we need to integrate this, but pi(n)=n/log(n), so we can make life simpler and over-estimate the probability by taking the smaller number.

    Now, given the number of prime numbers up to n, pi(n), if we choose x to be a prime number smaller than n, than the probability its pair: (n-x) is a prime number is: 2*pi(n)/n. (I multiplied by 2 since itcannot be possibly an even number, so no need to consider them).
    The probability that it is not a prime number is therefore (1-2*pi(n)/n).

    Since there are pi(n) different prime numbers to choose from, the probability that an even number is not the sum of two prime numbers is:
    (1-2*pi(n)/n)^pi(n).

    So what is the probability for numbers around 1e+15? If we use the estimate for pi(n), we get:
    pi(n)=2e+13
    (1-2*pi(n)/n) = 0.959

    Taking the last number by the power of pi(n), the result is that the probability is around:
    10^-(4e11)

    That is - an extremely small probability!!!

    Conclusion:
    ----------

    If Goldbach's theorem is false, the probability that an even number won't be the sum of two prime numbers is so small that we may need to check around 10^(10^11) numbers to find a counter example. This number is so big no computer could possibly handle it now or any time soon ...

    In other words: Don't bother to find a counter-example.

    Sela

  • Didn't anyone take a college math course? (Score:5)

    by Junks Jerzey ( 54586 ) on Sunday March 19, 2000 @09:05AM (#1192780)
    It's stunning how many people want to approach this as a programming problem; i.e. a fast way of checking lots of numbers. We're talking about a *proof*. Guessing and checking is missing the point.

Slashdot Top Deals

Hackers are just a migratory lifeform with a tropism for computers.

Close