The lucky winner, who receives eiπ+1 dollars, is someone from Atlanta, Georgia, who looked at this post from December about a Putnam problem; they came there from a google search on "3K+1 probability problem". The post in question probably didn't help them; it was just a post that involved the notation "3k+1" and talked about probability at one point or another. (A lot of my Google search strings seem to be like that -- people looking for pointers on homework with somewhat misguided search strings. It's not surprising they're misguided, since they don't know the subject that well! I'm sure I've committed the same offense at one point or another.)
I'm assuming that this person was looking for something about the Collatz conjecture. This conjecture is as follows -- let a0 be a positive integer. Let an+1 = an/2 if an is even, and an+1 = 3an+1 if an is odd. Then it appears that the sequence eventually reaches the number 1, at which point it repeats 1, 4, 2, 1, 4, 2, 1, ... forever. For example, if a0 = 22 we get
22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
This statement has been checked up to some ridiculously high number. The Wikipedia article is interesting. It seems like this theorem should be true for the following reason: let {bn} be the subsequence of odd numbers obtained when running the Collatz recursion; so in the above example we have
11, 17, 13, 5, 1.
Note that we get from 11 to 17 by multiplying by 3, adding 1, and dividing by 2. We get from 17 to 13 by multiply by 3, adding 1, and dividing by 2 twice. In general, bn+1 i s the largest odd factor of 3bn + 1. Half the time, 3bn + 1 only has one factor of 2 in its prime factorization; then bn+1 is about 3bn/2. One fourth of the time, there are two factors of , and bn+1 is about 3bn/4. In general, the "geometric expectation" of bn+1/bn (that is, the expectation of the mean of its logarithm, which is what's relevant here since the effects we care about are multiplicative) is
(Yes, it's exactly 3/4. Don't believe it? Well, the product can clearly be rewritten as
and the exponents in the numerator add to 1; the exponents in the denominator add to 2.
So "on average" bn+1 = 3bn/4. Thus the sequences shouldn't diverge. If I could make that "on average" made sufficiently rigorous my name would be trumpeted from the rooftops, or so I'd like to think. Perhaps the eventual proof will not be of this particular conjecture but of some more general conjecture which would consider other recursions where an+1 = kan + l, where k and l are rational constants depending on the residue class of an modulo some integer and are chosen so that an+1 will always be an integer. For example, we could take an+1 = an/5 when that's an integer, and an+1 the nearest integer to 7an/5 otherwise; the analogue to 3/4 is around 0.6537... here. (I think. I may have miscalculated it.) I have no idea how that behaves -- I just made it up. But on the other hand the eventual proof could hinge on peculiar properties of, say, binary expansions, in which case it would be specific to the original problem of Collatz.
This may or may not help the person who gave me the hundred thousandth hit. I'm surprised I'd never actually talked about the Collatz conjecture here before; I thought I had, but in retrospect it seems that I just thought about it on the way to school one morning and never wrote down what I was thinking.
