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!
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
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
————-
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++;
}
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 *)
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)
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.
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
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]