Skip to content

Instantly share code, notes, and snippets.

@DanielKeep
Created March 5, 2010 15:06
Show Gist options
  • Save DanielKeep/322783 to your computer and use it in GitHub Desktop.
Save DanielKeep/322783 to your computer and use it in GitHub Desktop.
/**
* Collatz graph generator (inspired by http://www.xkcd.com/710/)
* Written by Daniel Keep; released to the Public Domain.
*
* To use this, compile and either dump the output to a file, or feed it
* directly into GraphViz like so:
*
* -----
* collatz 100 | dot -Ocollatz_100.svg -Tsvg
* -----
*/
module collatz;
import tango.io.Stdout;
import tango.util.Convert;
int main(char[][] args)
{
if( args.length != 2 )
{
Stderr
.formatln("Usage: {} N", args[0])
.formatln("Produces directed Collatz graph of the first N positive integers.");
return 1;
}
auto n = to!(ulong)(args[1]);
bool[ulong] highmap;
Stdout
.formatln("digraph collatz_{}", n)
.formatln("{{")
.formatln(" _1[label=\"1\"];");
for( ulong i=2 ; i<=n ; ++i )
{
// Should probably refactor into a do...while loop, but can't be
// arsed.
ulong j;
if( i % 2 == 0 )
j = i / 2;
else
j = 3*i + 1;
Stdout.formatln(" _{0}[label=\"{0}\"];", i);
Stdout.formatln(" _{} -> _{};", i, j);
while( j > n )
{
if( j in highmap ) break;
ulong k;
if( j % 2 == 0 ) k = j / 2;
else k = 3*j + 1;
Stdout.formatln(" _{0}[label=\"{0}\"];", j);
Stdout.formatln(" _{} -> _{};", j, k);
highmap[j] = true;
j = k;
}
}
Stdout
.formatln("}");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment