3n+1: A Simple Number Game With Complex Behavior

3n+1
Here is a dirt simple game that requires only 4th grade arithmetic, yet leads to a hard puzzle.

Pick a number, say 5. It's odd, so let's multiply it by 3 and add one. We get 16. That one is even so we will divide by 2. We get 8. It's even again so divide by 2. We get 4. Then we get 2. Then we get 1. Oh, that's an odd number, so multiply by 3 and add one. We get 4. Then we get 2. Hey wait a minute, we just did that! so this little game ends up looping around! Ok, let's try starting with another number.

Remember the rules:
If the number you get is even, divide it by 2.
If the number you get is odd, multiply it by 3 and then add one.

How about 7? what happens?

It ends up in that 4,2,1, loop again, right?

This is called a mathematical dynamical system. you have a set of rules that you repeatedly operate on a given number with. The sequence of numbers you get is called an orbit. the loop 4,2,1 is called a closed orbit.

Try some more numbers, and see where they end up. Try 19. Hmm... that one is interesting, but it still ends up in our closed 4,2,1 orbit.

Do they all? Did you try 27? Oops, you will need a calculator! Even with a calculator It's too much work. Let's write a computer program to do it for us.

def iterate[n]
if int(n/2)=n/2 then 'if the integer portion of n/2 =n/2 then there is no remainder, so even
  n=n/2
else
  n=3*n+1
endif
return


simple program:

input n
while n<>1
    iterate[n]
    print n
wend
print "we've reached the loop"


program to calculate an orbit for each n:

for start_n = 1 to largest_n
    print start_n; print ": ";
    n=start_n
    while n<>1
        iterate[n]
        print n; print ", ";
    wend
    print
next start_n




here's all the orbits for numbers less than 27:

1 4 2 1
2 / (i write a slash if we hit a number we've already tried)
3 10 5 16 8 4 2 1
4 /
5 /
6 3 /
7 22 11 34 17 52 26 13 40 20 10 /

Note here that if n is odd, 3n+1 is even so you always divide by 2 after 3n+1ing, however SOMETIMES you can divide by 2 TWICE, and as with 5, you can divide by 2 THREE times. So in general it's a little crazy. we can't tell on average how many times we mult by 3 vs divide by 2. So no trends.

8 /
9 28 14 7 /
10/
11/
12 even numbers are boring we already hit them all!

13 /
15 36 18 9 /
17 /
19 58 29 88 44 22 11/
21 64 32 16 8 /

(as an aside, is there an odd number n such that for each m, 3n+1=2^m? say 2^7.. so what is 2^m mod 3?
1 1
2 2
4 1
8 2
16 1
32 2
64 1
128 2

ah. half of them)

23 70 35 106 53 160 80 40 20 10 5 /

but note that 3*53+1 does =32*5, hmm..

25 76 38 19 /

Here is 27:

27 82 41 124 62 31 94 47 142 71 214 107 322
(odd, why ending in 1s and 7s? well, 3*1+1=4 and half 4 is either ending in 7 or 2 and half 2 ends in 1! 3*7+1 ends in 2 and half that ends in 1. how would the pattern break? half 2 is sometimes ending in 6! oh, so this IS odd!)
161 484 242 121 364 182 91 274 137 412 206
(see the pattern breaks finally)
103 310 155 466 233 700 350 175 526 263
(woah! whats going on here, this one is different than all the other's we've done so far, it keeps growing!)
790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1,

WOW! That's a complicated pattern for such a simple set of rules to produce. in fact we can do something curious here's the program i wrote to produce that list of numbers:


n=27
while n<>1
n=iterate(n)
print n;", ";
wend

wait

function iterate(n)
if int(n/2)=n/2 then
iterate=n/2
else
iterate=3*n+1
end if
end function

here's the entire orbit it produces
82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1,

the program produced a sequence of characters longer and more complicated than the sequence of characters in the original program. or is it more complicated? or is it random? These are difficult concepts to pin down. One of the major themes to this complexity lab is to ask what does it mean to ask whether a simple system can produce complex behavior. It is difficult to pin down what we mean by 'complex'.

Remember, ultimately we are motivated by the question "can a simple set of laws of chemistry and physics produce a complicated living organism from scratch?"



Here's orbits for more numbers:

29 88 44 22 11/
31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 (oh, 310 is in the orbit starting with 27, so we already know what happens)
33 100 50 25 /
35 /
etc... We need to keep a list of nums we've already found, so that we don't keep calculating orbits we've already spent time calculating!

we can write a program to do that too.

Now what is going on here? notice that most of the numbers lead to short sequences that end up in the repeating loop 4, 2, 1. But 27 goes wild. It looks like it never will settle into that loop, but it eventually does! Notice the seemingly chaotic nature of the alternation of odd even here. (and we will have to come up with a careful definition of what we mean by chaotic) very chancy.

Now if you want, you can try to delve into the nature of the numbers. All the factors of 2 and 3, are there any patterns going on? Can you estimate on average how often we multiply by 3 or divide by 2 and try to guess whether the sequence can grow without end? Or is there any rhyme or reason why we might not hit a number with a large power of 2 as a factor and that sends the sequence all the way back down to a small number again...

So now we have some questions.

Is there any order to this game or is it totally chaotic?

Is there any sequence that keeps growing forever and never settles down to 4,2,1?

Are there any other loops like 4,2,1 that a sequence might settle down to?

If all sequences settle down to 4,2,1 or some other loop, how far can they go before settling down?

If there are other loops how long can they be?

It is not hard to write a computer program to play this game and even keep track of all the old numbers and detect when you've reached a loop.

Guess what? After x years of study, mathematicians do not know the answers to ANY of these questions. Though we've calculated sequences out to the gazillions and SO FAR, they seem to all settle to 4,2,1, but no one knows how to prove that that ALWAYS happens.

Curious, eh?

There are more games like this in the complexity lab manual.