### 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

• ## Dr. Syntaxfree

Dr. Syntaxfree has no PhD and shouldn't call himself a "doctor", but does so for amusement value anyway. An unemployed (ok, graduate student) econopundit by day, he's been progressively obsessed about Haskell to the point he often can't fathom not working on it. A jack-of-many-trades, he has an unusual CS background in that he knows no imperative programming at all, he hopes to be both helpful to those less knowledgeable than him and illustrative to the really smart people trying to understand the mentality of a common man trying to tackle functional programming.
• ## Licenses

All rights reserved for textual content. A specific exception is granted to wikis hosted in the haskell.org domain; any text or code can be freely copied to such pages. All code is otherwise released under the LGPL.