Go: Project Euler 1-9

problem1.go

package main

import (
	"fmt"
	"time"
)

type num int

func (x num) value() (answer num) {
	if x%3 == 0 || x%5 == 0 {
		return x
	}
	return
}

func problem1() (answer num) {
	for i := num(1); i < 1000; i++ {
		answer += i.value()
	}
	return
}

func main() {
	start := time.Now()
	fmt.Println(problem1())
	fmt.Println(time.Now().Sub(start).Seconds())
}

problem2.go

package main

import (
	"fmt"
	"time"
)

func problem2() (answer int) {
	a, b := 1, 2
	for a < 4000000 {
		if a%2 == 0 {
			answer += a
		}
		a, b = b, a+b
	}
	return
}

func main() {
	start := time.Now()
	fmt.Println(problem2())
	fmt.Println(time.Now().Sub(start).Seconds())
}

problem3.go

package main

import (
	"fmt"
	"time"
)

type num int64

type primeFactors map[num]int

func newFactors(n num) (answer primeFactors) {
	answer = make(primeFactors)
	for n%2 == 0 {
		answer[2]++
		n /= 2
	}
	for p := num(3); p*p <= n; p += 2 {
		for n%p == 0 {
			answer[p]++
			n /= p
		}
	}
	if n > 1 {
		answer[n]++
	}
	return
}

func (x primeFactors) max() (answer num) {
	for i := range x {
		if i > answer {
			answer = i
		}
	}
	return
}

func problem3() num {
	return newFactors(600851475143).max()
}

func main() {
	start := time.Now()
	fmt.Println(problem3())
	fmt.Println(time.Now().Sub(start).Seconds())
}

problem4.go

/**** Code A ****/

package main

import (
	"fmt"
	"time"
)

func palindrome(n int) bool {
	d := []int{}
	for n > 0 {
		d = append(d, n%10)
		n /= 10
	}
	for i, j := 0, len(d)-1; i < j; i, j = i+1, j-1 {
		if d[i] != d[j] {
			return false
		}
	}
	return true
}

func problem4() (answer int) {
	x := 999
	for x > 99 {
		y := x
		for {
			n := x * y
			if n <= answer || y < 100 {
				break
			}
			if palindrome(n) {
				answer = n
			}
			y--
		}
		x--
	}
	return
}

func main() {
	start := time.Now()
	fmt.Println(problem4())
	fmt.Println(time.Now().Sub(start).Seconds())
}

/**** Code B: use "container/heap" ****/

package main

import (
	"container/heap"
	"fmt"
	"time"
)

func palindrome(n int) bool {
	d := []int{}
	for n > 0 {
		d = append(d, n%10)
		n /= 10
	}
	for i, j := 0, len(d)-1; i < j; i, j = i+1, j-1 {
		if d[i] != d[j] {
			return false
		}
	}
	return true
}

type number struct {
	num int
	gt  int
	lt  int
}

func newNumber(a, b int) *number {
	if a < b {
		return newNumber(b, a)
	}
	return &number{
		num: a*b,
		gt: a,
		lt: b,
	}
}

type queue []*number

func newQueue() queue {
	return queue([]*number{})
}

func (q queue) Less(i, j int) bool {
	return q[i].num > q[j].num
}

func (q queue) Swap(i, j int) {
	q[i], q[j] = q[j], q[i]
}

func (q queue) Len() int {
	return len(q)
}

func (q *queue) Push(elem interface{}) {
	*q = append(*q, elem.(*number))
}

func (q *queue) Pop() (answer interface{}) {
	answer, *q = (*q)[len(*q)-1], (*q)[:len(*q)-1]
	return
}

func problem4() (answer int) {
	q := newQueue()
	heap.Push(&q, newNumber(999, 999))
	for {
		x := heap.Pop(&q)
		n := x.(*number)
		if palindrome(n.num) {
			answer = n.num
			break
		}
		heap.Push(&q, newNumber(n.gt, n.lt-1))
		if n.gt == n.lt {
			heap.Push(&q, newNumber(n.gt-1, n.gt-1))
		}
	}
	return
}

func main() {
	start := time.Now()
	fmt.Println(problem4())
	fmt.Println(time.Now().Sub(start).Seconds())
}

/**** Code C: use pairing heap ****/

package main

import (
	"fmt"
	"heap"
	"time"
)

func palindrome(n int) bool {
	d := []int{}
	for n > 0 {
		d = append(d, n%10)
		n /= 10
	}
	for i, j := 0, len(d)-1; i < j; i, j = i+1, j-1 {
		if d[i] != d[j] {
			return false
		}
	}
	return true
}

type number struct {
	num int
	gt  int
	lt  int
}

func newNumber(a, b int) *number {
	if a < b {
		a, b = b, a
	}
	return &number{
		num: a * b,
		gt:  a,
		lt:  b,
	}
}

func (x number) Ord(y *heap.Node) bool {
	return x.num >= y.Order.(*number).num
}

func newNode(a, b int) *heap.Node {
	return heap.New(newNumber(a, b))
}

func nextNode(x *heap.Node) (answer *heap.Node) {
	m := x.Order.(*number).gt
	n := x.Order.(*number).lt
	answer = heap.Merge(x.Pop(), newNode(m, n-1))
	if m == n {
		answer = heap.Merge(answer, newNode(m-1, m-1))
	}
	return
}

func solve(x *heap.Node) *number {
	for !palindrome(x.Order.(*number).num) {
		x = nextNode(x)
	}
	return x.Order.(*number)
}

func problem4() int {
	return solve(newNode(999, 999)).num
}

func main() {
	start := time.Now()
	fmt.Println(problem4())
	fmt.Println(time.Now().Sub(start).Seconds())
}

problem5.go

package main

import (
	"fmt"
	"math/big"
	"time"
)

func lcm(x *big.Int, y *big.Int) (answer *big.Int) {
	g := new(big.Int).GCD(nil, nil, x, y)
	answer = x.Mul(x, y).Div(x, g)
	return
}

func problem5() (answer *big.Int) {
	answer = big.NewInt(1)
	for i := 2; i <= 20; i++ {
		answer = lcm(answer, big.NewInt(int64(i)))
	}
	return
}

func main() {
	start := time.Now()
	fmt.Println(problem5())
	fmt.Println(time.Now().Sub(start).Seconds())
}

problem6.go

package main

import (
	"fmt"
	"time"
)

func problem6() int {
	n := 100
	x := n * (n + 1) / 2
	y := n * (n + 1) * (2*n + 1) / 6
	return x*x - y
}

func main() {
	start := time.Now()
	fmt.Println(problem6())
	fmt.Println(time.Now().Sub(start).Seconds())
}

problem7.go

/**** Code A ****/

package main

import (
	"fmt"
	"time"
)

type num int

func (x *num) isPrime() bool {
	switch {
	case (*x) < 2:
		return false
	case (*x) == 2:
		return true
	case (*x)%2 == 0:
		return false
	}
	for p := num(3); p*p <= (*x); p += 2 {
		if (*x)%p == 0 {
			return false
		}
	}
	return true
}

func (x *num) nextPrime() {
	(*x)++
	switch {
	case *x < 2:
		*x = 2
	case !x.isPrime():
		x.nextPrime()
	}
}

func problem7() (answer num) {
	for i := 1; i <= 10001; i++ {
		answer.nextPrime()
	}
	return
}

func main() {
	start := time.Now()
	fmt.Println(problem7())
	fmt.Println(time.Now().Sub(start).Seconds())
}

/**** Code B ****/

package main

import (
	"fmt"
	"math"
	"time"
)

type primes []bool

func newPrimes(max int) (answer primes) {
	answer = make([]bool, max+1)
	answer[2] = true
	for n := 3; n <= max; n += 2 {
		answer[n] = true
	}
	for i := 3; i*i <= max; i += 2 {
		for j := i; i*j <= max; j += 2 {
			answer[i*j] = false
		}
	}
	return
}

func (xs primes) nth(n int) (answer int) {
	x := 0
	for i, ok := range xs {
		if ok {
			x++
		}
		if x == n {
			return i
		}
	}
	return
}

func problem7() int {
	n := float64(10001)
	max := n*math.Log(n) + n*math.Log(math.Log(n))
	return newPrimes(int(max)).nth(int(n))
}

func main() {
	start := time.Now()
	fmt.Println(problem7())
	fmt.Println(time.Now().Sub(start).Seconds())
}

problem8.go

package main

import (
	"fmt"
	"strconv"
	"strings"
	"time"
)

const (
	str = "73167176531330624919225119674426574742355349194934" +
		"96983520312774506326239578318016984801869478851843" +
		"85861560789112949495459501737958331952853208805511" +
		"12540698747158523863050715693290963295227443043557" +
		"66896648950445244523161731856403098711121722383113" +
		"62229893423380308135336276614282806444486645238749" +
		"30358907296290491560440772390713810515859307960866" +
		"70172427121883998797908792274921901699720888093776" +
		"65727333001053367881220235421809751254540594752243" +
		"52584907711670556013604839586446706324415722155397" +
		"53697817977846174064955149290862569321978468622482" +
		"83972241375657056057490261407972968652414535100474" +
		"82166370484403199890008895243450658541227588666881" +
		"16427171479924442928230863465674813919123162824586" +
		"17866458359124566529476545682848912883142607690042" +
		"24219022671055626321111109370544217506941658960408" +
		"07198403850962455444362981230987879927244284909188" +
		"84580156166097919133875499200524063689912560717606" +
		"05886116467109405077541002256983155200055935729725" +
		"71636269561882670428252483600823257530420752963450"
)

type digits []int

func (d digits) mul() (answer int) {
	answer = 1
	for _, v := range d {
		answer *= v
	}
	return
}

func (d digits) multi5() (answer []int) {
	for i := range d {
		if len(d[i:]) >= 5 {
			answer = append(answer, d[i:i+5].mul())
		}
	}
	return
}

func data() (answer digits) {
	s := strings.Split(str, "")
	answer = make(digits, len(s))
	for i, v := range s {
		answer[i], _ = strconv.Atoi(v)
	}
	return
}

func problem8() (answer int) {
	s := data().multi5()
	for _, v := range s {
		if v > answer {
			answer = v
		}
	}
	return
}

func main() {
	start := time.Now()
	fmt.Println(problem8())
	fmt.Println(time.Now().Sub(start).Seconds())
}

problem9.go

package main

import (
	"fmt"
	"time"
)

func problem9() (answer int) {
	for a := 1; a < 1000/3; a++ {
		for b := a + 1; b < (1000-a)/2; b++ {
			c := 1000 - a - b
			if c*c == a*a+b*b {
				return a * b * c
			}
		}
	}
	return
}

func main() {
	start := time.Now()
	fmt.Println(problem9())
	fmt.Println(time.Now().Sub(start).Seconds())
}