Bicycling for Collatz

22Feb07

Q: How many people with ADD does it take to change a lightbulb?
A: HEY! Let’s ride bikes!


module Bikes where


Graphviz is fun. Graphviz is fair. You may already have one. You may already be there:


data Arr a = a :-> a


Graphviz plots graphs from .DOT files consisting of remarkably simple syntax:


instance (Show a) => Show (Arr a) where show (x:->y) = show x ++ " -> " ++ show y
class (Show a) => (Dot a) where
dot :: [a] -> String
dot = (++"}") . ("digraph untitled {"++) . unlines . map ((++";") . show)
instance (Show a) => Dot (Arr a)


One fun thing we can do with it is plotting graphs of integer-valued functions:


arr f = (\x-> x :-> f x)
rra f = (\x-> f x :-> x)


Let’s see what a simple invertible function looks like:


t2 = dot $ map (arr (*2)) [0..40]


Clearly there’s one and only one way to connect any given two nodes — which is what invertibility means. But let’s look at something fun now; say, the co-totient function. There’s a closed-form equation for this, but why not go full ape declarative?


totient x = x - (length $ [n | n<-[1..x], coprimes n x]) where coprimes a b = (gcd a b) == 1
t3 = dot $ map (arr totient) [1..100]


(Click to see full-size picture)

The first hierarchy line contains the prime numbers; their co-totient is always 1. These numbers are connected to numbers whose co-totient they are; from that graph you can find the co-totient of any number by looking at which number it’s connected to. At first glance it looks pretty tree-like, but it suffices to chase the series of powers of two to see it isn’t.

Now, being that the totient is the quantity of numbers “strange” to a number (in the sense their only common divisor is 1) and the co-totient is precisely a number minus its totient, higher co-totients seem to indicate a more “composite” structure. That’s not clearly represented by graph hierarchy, of course. So we try a different representation of compositeness in integers:


t4 = dot $ filter (\(x:->y) -> y /=1 && x/=y ) $ concat $ map (\y->(map (arr (gcd y)) [2..32])) [2..32]


This will connect all numbers that divide each other by as many arrows as there are ways to divide it:

Click here to see full image

That makes for a smashing bedroom poster.

Finally, as hopelessly amateur mathematicians we are, we just can’t resist poking the Collatz function!


t = dot $ map (rra (\x->if (odd x) then 3*x+1 else x `div` 2)) [1..384]


I’ve plotted Collatz graphs as far as 15000. But let’s keep it to manageable sizes; you can later experiment at home and see trust me that larger graphs keep the structure contained in this graph — there are relatively very few ways to get into the “main Collatz stream” down to 4-2-1 and most numbers are stuck in two-house citadels of their own, with a few managing to form their own substreams that sometimes even manage to join the main Collatz “stream”:

Abandon all hope ye who enter here

Yes, I know, I should be working in PFP and all, but when a boy’s mind is overcome with newfound love, he must clutch at any tiny window of intellectual focus he occasionally comes across by as his brain walks through the shadows of love.

Filed under: Uncategorized   |  6 Comments