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.



6 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

  4. Good respond in return of this question with firm arguments and describing the whole thing
    concerning that.


  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: