When I was in high school my AP Computer Science professor presented our class of eleven students with a very interesting algorithm. He called it 3n+1 (it is really the Collatz Conjecture). He claimed that given any positive, non-zero integer when the following steps are applied, the result will always be 1.
n := <any postive non-zero integer>
while (n != 1) do
if (n is even) then
n := n / 2
else
n := 3 * n + 1
end if
end while
To a class of nine seniors and two juniors, Mr. Ball gave this algorithm and told us to play with it and see what happened. Did I mention Mr. Ball was a great teacher?
Naturally we went to our respective, half-functioning 386s and 486s loaded with pirated copies of Turbo Pascal 7 and went to work. The faster typers noticed "a problem."
Student: Mr. Ball? I entered ten thousand to test the function and the printout "went negative."
Mr. Ball: So what does that mean?
Student: Well, we've hit MAXINT when calculating 3n+1.
Mr. Ball: mmmhmmm. So what number makes the function overflow?
I did not realize it at the time but he taught us a valuable lesson: Learn what values will cause an overflow. After some Pascal voodoo the class decided that the number was 4471. I've remembered that number since 1998 as a "stand out" number. (The 47 society is expecting my dues any day.)
Like I said, this is an interesting algorithm and it has been suggested2 that this is unprovable. I don't know about that, I'm a programmer, not a mathematician. Maybe some number theory buffs will stop in and clear this whole mess up.
1: For the curious the sequence for 447 goes:
447:1342:671:2014:1007:3022:1511:4534:2267:6802:3401:
10204:5102:2551:7654:3827:11482:5741:17224:8612:4306:
2153:6460:1615:4846:2423:7270:3635:10906:5453:16360:
8180:4090:2045:6136:3068:1534:767:2302:1151:3454:1727:
5182:2591:7774:3887:11662:5831:17494:8747:26424:13121:
39364:19682:9841:29524:14762:7381:22144:11072:5536:2768:
1384:692:346:173:520:260:130:65:196:98:49:148:74:37:112:
56:28:14:7:22:11:34:17:52:26:13:40:20:10:5:16:8:4:2:1 - qed
2: http://arxiv.org/abs/math.GM/0312309 contains a paper which claims "In this paper, we show that any proof of the Collatz $3n+1$ (sic) Conjecture must have an infinite number of lines. Therefore, no formal proof is possible. We also discuss whether the proof strategy in this paper has any promise for proving that the Riemann Hypothesis is also unprovable." -- And it appears that this has been cleared up: cakedamber writes:
"Ok. There's a few reasons that guy is wrong. I'm assuming you read the paper? (It's rather short and the key bit is just a paragraph long.) The problem with his proof is on several counts. First, and simplest, is that you don't need to talk about every last value of a function in order to prove something about that function. If you did, you could never prove anything about ANY infinite-domained function. The second problem is that you don't necessarily need as many words/letters as there are values anyhow. In fact, it's possible to talk about infinite sets using only a finite number of words. On top of that, there are some really deep philosophical paradoxes that pop up if you assume that there's a simple mathematical mapping from functions to natural-language definitions. Those last two are really just the icing on the cake, though -- the first one is more than enough to show that the paper's hogwash."