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.

About these ads


5 Responses to “Bicycling for Collatz”

  1. Very pretty.

  2. 2 lifeh2o

    Hey!! thats great work, i was thinking almost the same thing from some days, i made a script in Processing where all numbers are written in a line.
    A curve is drawn over all multiples of a number
    For example if there will be small curve on 2 to 4, 4 to 6, 6 to 8 ……
    a bigger curve will be there on 3 to 6, 6 to 9 , 9 to 12 …..

    import processing.dxf.*;

    import netscape.javascript.*;

    import ddf.minim.signals.*;
    import ddf.minim.*;
    import ddf.minim.analysis.*;
    import ddf.minim.effects.*;

    import processing.net.*;
    import processing.opengl.*;

    void setup(){
    PFont font;
    font = loadFont(“ArialMT-18.vlw”);
    textFont(font);
    size(300,800);
    Numbers n;
    n = new Numbers();
    //n.createnumbers();
    n.createarcs(2,100,radians(-90), radians(90));
    n.createarcs(3,100,radians(90), radians(-90));
    n.createarcs(4,100,radians(-90), radians(90));
    n.createarcs(5,100,radians(90), radians(-90));
    n.createarcs(6,100,radians(-90), radians(90));
    n.createarcs(7,100,radians(90), radians(-90));
    n.createarcs(8,100,radians(-90), radians(90));
    n.createarcs(9,100,radians(90), radians(-90));
    n.createarcs(10,100,radians(-90), radians(90));
    n.createarcs(11,100,radians(90), radians(-90));
    n.createarcs(12,100,radians(-90), radians(90));
    n.createarcs(13,100,radians(90), radians(-90));
    }

    class Numbers {
    int alignx=120;
    int aligny=14;

    Numbers(){

    }
    void createnumbers(){
    for (int i=1; i<=1000; i++){
    fill(100);
    text(i,alignx,i*aligny);
    }
    }
    void createarcs(int val, int limit,float astart, float aend){
    for (int i=0; i<=limit; i++){
    noFill();
    //arc(x, y, width, height, start, stop)
    arc(alignx, i*aligny*val+(aligny/2)*(3*val-1), aligny*val, aligny*val, astart, aend);
    }
    }
    }

    /*
    val
    1-14=(14/2)*(3*val-1)+14*val*i — 28,42,56
    2-35=(14/2)*(3*val-1)+14*val*i — 63,91,119
    3-56=(14/2)*(3*val-1)+14*val*i — 98,140,182
    4-77=(14/2)*(3*val-1)+14*val*i —

    aligny/2 * (3x+2ix-1)
    */

    The idea behind this was that, for each number before which there is no multiple of it is a prime, so in the graph the number from where the curve starts is a prime.

    I hope graph viz would help me doing more experiments

  3. 3 lifeh2o

    Hey!! thats great work, i was thinking almost the same thing from some days, i made a script in Processing where all numbers are written in a line.
    A curve is drawn over all multiples of a number
    For example if there will be small curve on 2 to 4, 4 to 6, 6 to 8 ……
    a bigger curve will be there on 3 to 6, 6 to 9 , 9 to 12 …..

    import processing.dxf.*;

    import netscape.javascript.*;

    import ddf.minim.signals.*;
    import ddf.minim.*;
    import ddf.minim.analysis.*;
    import ddf.minim.effects.*;

    import processing.net.*;
    import processing.opengl.*;

    void setup(){
    PFont font;
    font = loadFont(“ArialMT-18.vlw”);
    textFont(font);
    size(300,800);
    Numbers n;
    n = new Numbers();
    //n.createnumbers();
    n.createarcs(2,100,radians(-90), radians(90));
    n.createarcs(3,100,radians(90), radians(-90));
    n.createarcs(4,100,radians(-90), radians(90));
    n.createarcs(5,100,radians(90), radians(-90));
    n.createarcs(6,100,radians(-90), radians(90));
    n.createarcs(7,100,radians(90), radians(-90));
    n.createarcs(8,100,radians(-90), radians(90));
    n.createarcs(9,100,radians(90), radians(-90));
    n.createarcs(10,100,radians(-90), radians(90));
    n.createarcs(11,100,radians(90), radians(-90));
    n.createarcs(12,100,radians(-90), radians(90));
    n.createarcs(13,100,radians(90), radians(-90));
    }

    class Numbers {
    int alignx=120;
    int aligny=14;

    Numbers(){

    }
    void createnumbers(){
    for (int i=1; i<=1000; i++){
    fill(100);
    text(i,alignx,i*aligny);
    }
    }
    void createarcs(int val, int limit,float astart, float aend){
    for (int i=0; i<=limit; i++){
    noFill();
    //arc(x, y, width, height, start, stop)
    arc(alignx, i*aligny*val+(aligny/2)*(3*val-1), aligny*val, aligny*val, astart, aend);
    }
    }
    }

    /*
    val
    1-14=(14/2)*(3*val-1)+14*val*i — 28,42,56
    2-35=(14/2)*(3*val-1)+14*val*i — 63,91,119
    3-56=(14/2)*(3*val-1)+14*val*i — 98,140,182
    4-77=(14/2)*(3*val-1)+14*val*i —

    aligny/2 * (3x+2ix-1)
    */

    The idea behind this was that, for each number before which there is no multiple of it is a prime, so in the graph the number from where the curve starts is a prime.
    I hope graphviz would help me doing more experiments


  1. 1 Code//Design » Amazing Graphviz Plots
  2. 2 Tiempo finito y logarítmico » Grafos de Collatz

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: