I just came back from my Number Theory course, and during the lecture there was mention of the Collatz Conjecture.
I'm sure that everyone here is familiar with it; it describes an operation on a natural number – $n/2$ if it is even, $3n+1$ if it is odd.
The conjecture states that if this operation is repeated, all numbers will eventually wind up at $1$ (or rather, in an infinite loop of $1-4-2-1-4-2-1$).
I fired up Python and ran a quick test on this for all numbers up to $5.76 \times 10^{18}$ (using the powers of cloud computing and dynamic programming magic). Which is millions of millions of millions. And all of them eventually ended up at $1$.
Surely I am close to testing every natural number? How many natural numbers could there be? Surely not much more than millions of millions of millions. (I kid.)
I explained this to my friend, who told me, "Why would numbers suddenly get different at a certain point? Wouldn't they all be expected to behave the same?"
To which I said, "No, you are wrong! In fact, I am sure there are many conjectures which have been disproved by counterexamples that are extremely large!"
And he said, "It is my conjecture that there are none! (and if any, they are rare)".
Please help me, smart math people. Can you provide a counterexample to his conjecture? Perhaps, more convincingly, several? I've only managed to find one! (Polya's conjecture). One, out of the many thousands (I presume) of conjectures. It's also one that is hard to explain the finer points to the layman. Are there any more famous or accessible examples?
Best Answer
Another example: Euler's sum of powers conjecture, a generalization of Fermat's Last Theorem. It states:
If the equation $\sum_{i=1}^kx_i^n=z^n$ has a solution in positive integers, then $n \leq k$ (unless $k=1$). Fermat's Last Theorem is the $k=2$ case of this conjecture.
A counterexample for $n=5$ was found in 1966: it's
$$ 61917364224=27^5+84^5+110^5+133^5=144^5 $$ The smallest counterexample for $n=4$ was found in 1988:
$$ 31858749840007945920321 = 95800^4+217519^4+414560^4=422481^4 $$ This example used to be even more useful in the days before FLT was proved, as an answer to the question "Why do we need to prove FLT if it has been verified for thousands of numbers?" :-)