Go: Project Euler 20-29

problem20.go

package main

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

func problem20() (answer int) {
	str := new(big.Int).MulRange(1, 100).String()
	for _, v := range strings.Split(str, "") {
		var n int
		fmt.Sscanf(v, "%d", &n)
		answer += n
	}
	return
}

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

problem21.go

package main

import (
	"fmt"
	"time"
)

func problem21() (answer int) {
	max := 9999
	sums := make([]int, max+1)
	for i := 1; i*2 <= max; i++ {
		for j := 2; i*j <= max; j++ {
			sums[i*j] += i
		}
	}
	for i, v := range sums {
		if i > v && sums[v] == i {
			answer += i + v
		}
	}
	return
}

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

problem22.go

package main

import (
	"fmt"
	"io/ioutil"
	"os"
	"sort"
	"strings"
	"time"
)

type name string

func (n name) value() (answer int) {
	for i := range n {
		answer += int(n[i]) - 64
	}
	return
}

type names []name

func (names names) totalScore() (answer int) {
	for i := range names {
		answer += names[i].value() * (i + 1)
	}
	return
}

func readNames() (answer names) {
	f, _ := os.Open("names.txt")
	defer f.Close()
	bs, _ := ioutil.ReadAll(f)
	xs := strings.Split(string(bs), ",")
	sort.Strings(xs)
	answer = make(names, len(xs))
	for i := range xs {
		answer[i] = name(strings.Trim(xs[i], "\""))
	}
	return
}

func problem22() int {
	return readNames().totalScore()
}

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

problem23.go

package main

import (
	"fmt"
	"time"
)

const MAX = 28123

func abundants() (answer []int) {
	sums := make([]int, MAX+1)
	for i := 1; i*2 <= MAX; i++ {
		for j := 2; i*j <= MAX; j++ {
			sums[i*j] += i
		}
	}
	for i, v := range sums {
		if i < v {
			answer = append(answer, i)
		}
	}
	return
}

func problem23() (answer int) {
	xs := abundants()
	nums := make([]bool, MAX+1)
	for i, v := range xs {
		if 2*v > MAX {
			break
		}
		j := i
		for {
			k := v + xs[j]
			if k > MAX {
				break
			}
			nums[k] = true
			j++
		}
	}
	for i, ok := range nums {
		if !ok {
			answer += i
		}
	}
	return
}

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

problem24.go

package main

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

type indices []int

func newIndices(n int) (answer indices) {
	for i := 9; i >= 0; i-- {
		fact := int(math.Gamma(float64(i)+1))
		x := (n - 1) / fact
		answer = append(answer, x)
		n -= fact * x
	}
	return
}

func (x indices) int64() (answer int64) {
	digits := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	for i := range x {
		answer = 10*answer + int64(digits[x[i]])
		digits = append(digits[:x[i]], digits[x[i]+1:]...)
	}
	return
}

func problem24() int64 {
	return newIndices(1e6).int64()
}

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

problem25.go

package main

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

type fib struct {
	num  *big.Int
	next *big.Int
}

func newFib(a, b int) *fib {
	return &fib{num: big.NewInt(int64(a)), next: big.NewInt(int64(b))}
}

func (f *fib) incr() {
	f.next.Add(f.next, f.num)
	f.num.Sub(f.next, f.num)
}

func problem25() (answer int) {
	answer = 1
	fib := newFib(1, 1)
	x := new(big.Int).Exp(big.NewInt(10), big.NewInt(999), nil)
	for fib.num.Cmp(x) < 0 {
		answer++
		fib.incr()
	}
	return
}

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

problem26.go

package main

import (
	"fmt"
	"time"
)

type nums []int

func (xs nums) member(n int) bool {
	for _, v := range xs {
		if n == v {
			return true
		}
	}
	return false
}

func cycle(n int) (answer int) {
	xs := nums{}
	for x := 10 % n; !xs.member(x); x = 10 * x % n {
		xs = append(xs, x)
	}
	answer = len(xs)
	return
}

func problem26() (answer int) {
	max := 0
	for i := 2; i < 1000; i++ {
		if x := cycle(i); x > max {
			answer, max = i, x
		}
	}
	return
}

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

problem27.go

package main

import (
	"fmt"
	"time"
)

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

func primeLength(a, b int) (answer int) {
	for n := 0; isPrime(n*n + a*n + b); n++ {
		answer++
	}
	return
}

func problem27() (answer int) {
	max := 0
	for a := -999; a < 1000; a += 2 {
		for b := 3; b < 1000; b += 2 {
			if x := primeLength(a, b); x > max {
				answer, max = a*b, x
			}
		}
	}
	return
}

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

problem28.go

package main

import (
	"fmt"
	"time"
)

type layer int

func (x layer) sum() int {
	n := int(x)
	a := n * n
	b := n - 1
	return a + (a - b) + (a - 2*b) + (a - 3*b)
}

func problem28() (answer int) {
	answer++
	for n := layer(3); n <= 1001; n += 2 {
		answer += n.sum()
	}
	return
}

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

problem29.go

package main

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

func problem29() int {
	m := map[string]bool{}
	for a := 2; a <= 100; a++ {
		for b := 2; b <= 100; b++ {
			x := big.NewInt(int64(a))
			x.Exp(x, big.NewInt(int64(b)), nil)
			m[x.String()] = true
		}
	}
	return len(m)
}

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