ulam.go

package main

import (
	"image"
	"image/color"
	"image/draw"
	"image/png"
	"math"
	"os"
)

func main() {
	const (
		W  = 1000
		H  = 1000
		PM = W * H
	)
	ps := SieveErasthostenes(PM + 1)
	img := image.NewRGBA(image.Rect(0, 0, W, H))
	draw.Draw(img, img.Rect, &image.Uniform{color.White}, image.ZP, draw.Src)
	path := map[Vector]bool{}
	path[Vector{0, 0}] = true
	pv := Vector{1, 0}
	d := DirectionRight
	for i := 1; i < PM; i++ {
		p := i + 1
		if ps[p] {
			img.Set(W/2+pv.X, H/2+pv.Y, color.Black)
		}
		path[pv] = true
		nd := d.Left()
		np := pv.Add(nd)
		if _, visited := path[np]; !visited {
			d = nd
		}
		pv = pv.Add(d)
	}
	fd, err := os.OpenFile("ulam.png", os.O_WRONLY|os.O_CREATE, 0750)
	if err != nil {
		panic(err)
	}
	defer fd.Close()
	png.Encode(fd, img)
}

type Vector struct {
	X int
	Y int
}

func (v *Vector) Add(o Vector) Vector {
	return Vector{v.X + o.X, v.Y + o.Y}
}

type Direction = Vector

var (
	DirectionUp    Direction = Vector{0, -1}
	DirectionDown  Direction = Vector{0, 1}
	DirectionLeft  Direction = Vector{-1, 0}
	DirectionRight Direction = Vector{1, 0}
)

func (d Direction) Left() Direction {
	switch d {
	case DirectionUp:
		return DirectionLeft
	case DirectionDown:
		return DirectionRight
	case DirectionLeft:
		return DirectionDown
	case DirectionRight:
		return DirectionUp
	}
	panic("should not reach")
}

func SieveErasthostenes(max int) []bool {
	ps := make([]bool, max)
	for i := 2; i < max; i++ {
		ps[i] = true
	}
	sq := int(math.Sqrt(float64(max)))
	for i := 2; i < sq; i++ {
		for e := i + i; e < max; e += i {
			ps[e] = false
		}
	}
	return ps
}