UlamSpiralGenerator.java

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.geom.Ellipse2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Arrays;

import javax.imageio.ImageIO;

public class UlamSpiralGenerator {

	private final static String DEFAULT_PATH = "ulam.png";
	
	private final static int N = 0;
	private final static int S = 1;
	private final static int E = 2;
	private final static int W = 3;

	private final static Color[] cols = new Color[256];
	static {
		for (int i = 0; i < cols.length; i++) cols[i] = new Color(i, i, i);
	}

	private final static int cacheSize = 10000;
	
	private final static int[] smallestPrimeFactors = new int[cacheSize];

	private static final int[] ps = new int[100];
	

	public static void main(String[] args) throws IOException {
		//obtain file path
		final String path;
		if (args.length == 0) {
			path = DEFAULT_PATH;
		} else {
			path = args[0];
		}
		
		//fix dimensions
		final int gap = 4;
		final int r = 200;
		final int s = 2 * r * gap + 1;
		
		//generate graphical context
		final BufferedImage image = new BufferedImage(s, s, BufferedImage.TYPE_INT_RGB);
		final Graphics2D g = image.createGraphics();
		g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
		
		final int c = (s-1)/2;
		final int m = s * s;
		//loop over number of unique prime factors
		for (int j = 3; j >= 1; j--) {
			int x = 1;
			int y = 0;
			int d = N;
			//choose radius
			final double rr;
			switch (j) {
			case 1 : rr=3; break;
			case 2 : rr=2; break;
			case 3 : rr=1; break;
			default : rr=0; break;
			}
			for (int i = 2; i < m; i++) {
				//filter
				int u = countUniquePrimeFactors(i);
				if (u == j) {
					//choose color
					int f = countPrimeFactors(i);
					int k = 256 * f / 10;
					g.setColor( cols[Math.min(k, 255)] );
					//plot
					double rrr = rr * Math.log(i)/5.0;
					g.fill( new Ellipse2D.Double(c+x*gap-rrr/2, c+y*gap-rrr/2, rrr, rrr) );
				}
				//move
				switch (d) {
				case N : y--; break;
				case S : y++; break;
				case E : x++; break;
				case W : x--; break;
				}
				//change direction
				if (y > 0 && x > 0 && y+1 == x) {
					d = N;
				} else if (Math.abs(x) == Math.abs(y)) {
					if (x > 0 && y < 0) {
						d = W;
					} else if (x < 0 && y < 0) {
						d = S;
					} else if (x < 0 && y > 0) {
						d = E;
					}
				}
			}
		}
		//write image
		ImageIO.write(image, "PNG", new File(path));
	}
	
	private static final int countPrimeFactors(int i) {
		int p = smallestPrimeFactor(i);
		return p == i ? 1 : 1 + countPrimeFactors(i/p);
	}
	
	private static final int countUniquePrimeFactors(int i) {
		return countUniquePrimeFactors(i, 0);
	}
	
	private static int countUniquePrimeFactors(int i, int c) {
		int p = smallestPrimeFactor(i);
		if (Arrays.binarySearch(ps, 0, c, p) < 0) ps[c++] = p;
		if (p == i) return c;
		return countUniquePrimeFactors(i/p, c);
	}

	private static final int smallestPrimeFactor(int i) {
		if (i < cacheSize && smallestPrimeFactors[i] != 0) return smallestPrimeFactors[i];
		if ((i & 1) == 0) return 2;
		final int s = (int) Math.sqrt(i);
		for (int f = 3; f <= s; f +=2) {
			if ((i % f) == 0) {
				if (i < cacheSize) smallestPrimeFactors[i] = f;
				return f;
			}
		}
		if (i < cacheSize) smallestPrimeFactors[i] = i;
		return i;
	}
	
}