DX. Dumb Robots

The Collatz function on the counting numbers is really quite amazing: Divide by 2 if you can, otherwise multiply by 3 and add 1. Iterating this seems always to lead to the loop … 4, 2, 1, 4, 2, 1

For example: 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → etc.

Does this always happen??

Dunno. No one does. But it is known that you will eventually loop if you start with any number up to about 5 x 10^19

(we accidentally exaggerated this in the podcast).

Try it for 27 for a daunting peek at the difficulty of this problem!

And we have a quick puzzle from Jeff Yoak, on crashing dumb robots together!

7 Comments »

  1. intchanter said,

    May 14, 2008 at 4:16 pm

    I whipped up some Python code that any of you can hack on to try out the Collatz function. By posting it here, I am releasing it into the public domain, so have fun with it.

    ————-
    #!/usr/bin/env python

    def collatz(start):
        '''
        Run through the collatz series for a given number and return the number of
        iterations and the largest number found.
        '''
        current = start
        iter = 0
        max = start
        while current != 1:
            iter += 1
            if current % 2: # odd
                current = current * 3 + 1
            else: # even
                current = current / 2
            if current > max:
                max = current
        return (iter, max)

    if __name__ == "__main__":
        target = 1000
        max_tuple = (0, 0, 0)
        iter_tuple = (0, 0, 0)
        for start in xrange(1, target + 1):
            (iter, max) = collatz(start)
            if max > max_tuple[2]:
                max_tuple = (start, iter, max)
            if iter > iter_tuple[1]:
                iter_tuple = (start, iter, max)
        print 'Largest integer hit:', max_tuple
        print 'Longest series hit:', iter_tuple
    ————-

  2. cybersekkin said,

    May 15, 2008 at 11:05 pm

    #I (being a dumb chemical robot) made an error going by hand
    #so put this together as a simple test for a single number (27))

    #!/usr/bin/perl
    #
    #
    my $num = 27;
    my $count = 0;
    my $test3 = 0;

    until( $test3 == 1 )
    {
    print “$count number is: $num\n”;

    if($num eq 1)
    {
    $test3 = 1;
    }
    #get last digit if even divide by 2
    if(!($num % 2))
    {
    $num = $num / 2;
    }
    #if not multiply by 3 and add 1
    else
    {
    $num = (($num * 3) + 1)
    }
    $count++;
    }

  3. strauss said,

    May 16, 2008 at 5:12 am

    (* Man, 27 by hand is quite a treat! Here’s the same result in Mathematica; I love the compactness of this language! *)

    Collatz[1] = 1;

    Collatz[n_] := If[EvenQ[n], n/2, 3 n + 1];

    DoCollatz[n_] := (Print[Length[#] – 1, ” steps: “, #, “\n”]) &@ FixedPointList[Collatz, n]

    (* so typing in DoCollatz[27] spits out the sequence starting at 27;

    DoCollatz /@ Range[1,200] spits out results for 1 through 200 *)

  4. cstarbi said,

    May 18, 2008 at 8:07 pm

    Something that I found interesting: Find out if this code is the fastest way to cause a collision, and, if not, what code is? (I assumed in my solution that travel time is much much longer than the time it takes to detect a parachute or perform a goto)

  5. nklein said,

    May 18, 2008 at 10:12 pm

    DUMB ROBOTS SPOILER

    The shortest algorithm I am sure of has 7 instructions.

    1. Go Left
    2. If Parachute, Skip to 6
    3. Go Left
    4. Go Right
    5. Skip to 1
    6. Go Left
    7. Skip to 6

    Thus, both progress left at one square every three moves until the one who landed on the right hits the other robot’s parachute. After that, the robot that landed on the right speeds up to one square leftward every move.

    I had assumed instruction time was negligible compared to moving time in arriving at the algorithm. If every instruction takes equal time, we can eliminate 3 and 4. Both robots move leftward one space every three ticks until the rightmost robot finds the other parachute. Then, the rightmost robot accelerates to one square leftward every two ticks.

  6. jpincott said,

    May 18, 2008 at 10:34 pm

    For the robot puzzle, if we label the commands thus:

    L = Move left one step
    R = Move right one step
    Gn = Goto instruction n
    Cn = Conditional goto – Gn iff currently standing on a parachute

    then the following program will suffice:


    1. R
    2. L
    3. R
    4. C6
    5. G1
    6. R
    7. G6

  7. Eric said,

    May 18, 2008 at 11:18 pm

    For an added challenge, it turns out you can solve the puzzle using only one direction of travel.

    Hint:
    [spoiler]
    You will need to assume that each instruction requires some amount of time, even when the robot does not travel.
    [/spoiler]

    Solution:
    [spoiler]
    1 – Go Left
    2 – If you are standing on a parachute, go to instruction 4
    3 – Go to instruction 1
    4 – Go Left
    5 – Go to instruction 4
    [/spoiler]

RSS feed for comments on this post · TrackBack URL

Leave a Comment

You must be logged in to post a comment.

The Math Factor Podcast Website


Quality Math Talk Since 2004, on the web and on KUAF 91.3 FM


A production of the University of Arkansas, Fayetteville, Ark USA


Download a great math factor poster to print and share!

Got an idea? Want to do a guest post? Tell us about it!

Heya! Do us a favor and link here from your site!