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.
8 comments:
Congrats, Isabel! You posts are consistently interesting and entertaining, so I'm not surprised. =)
By the way, I've just been accepted to the PhD program in CS at UPenn, and I'll be there for an open house on 2/29 and 3/1! Think you might have a few minutes to drop by and say hi?
It's a pretty simple algorithm in binary. What's going on is that you begin with an odd number (which therefore has a 1 in its least significant bit, or LSB), and a stage in the algorithm consists of multiplying the number by 3 (which will leave a 1 in the LSB), and then shifting down by enough bits to bring the next 1 to the LSB.
So one might speculate about similar algorithms in other bases. For example, use base 3 and multiply the numbers by 4, then shift down to the next non zero LS3.
Carl, that's not quite it. What you've described is the sequence you get if you use 3n-1 instead of 3n+1. When you first shift, you're dropping the LSB, which subtracts one. Then you keep dividing by 2 as you shift.
You wrote:
Let an+1 = an/2 if n is even, and an+1 = 3an+1 if n is odd., but looking at your examples, I think you mean: Let an+1 = an/2 if an is even, and an+1 = 3an+1 if an is off....
chezmax,
of course you're right.
Let this be a lesson: don't write blog posts that involve notation before drinking coffee. (This started out as just "ooh! look! I have 100,000 hits" while I waited for my coffee to brew this morning; I didn't intend to make a serious post and then somehow it happened.)
Thanks John. I figured I had the formula wrong when I couldn't get the 3n-1 thingy to work for "7" while driving.
I saw that the records were generated by computer, but I couldn't easily find an example computer algorithm. They must be using some sort of theory to speed up the search.
The reason I was curious was because I spent many years designing FPGAs which are relatively inexpensive (i.e < $100) and can typically be designed to do this sort of problem about a thousand times faster than a general purpose computer. A typical FPGA raw speed would be 100,000 adders each doing a billion 1-bit arithmetic operations per second. You lose some for input and output operations, etc., but they are fast.
Some simple generalizations of this are actually known to be false: if you consider the "5x+1" conjecture, where you replace odd n with (5n+1)/2 and even n with n/2, then you get the cycle 13, 33, 83, 208, 104, 52, 26, 13.
anonymous,
the generalizations I was thinking of were just to say that one always gets a cycle. The interesting thing to me is that the sequence never "diverges upward", i. e. to infinity.
Post a Comment