Go: Project Euler 40-49

problem40.go

package main

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

func pow(x, y int) int {
	return int(math.Pow(float64(x), float64(y)))
}

func d(n int) int {
	if n < 10 {
		return n
	}
	p := 0
	for {
		x := 9 * pow(10, p)
		if x*(p+1) > n {
			break
		}
		p++
		n -= x * p
	}
	q := p + 1
	n1 := pow(10, p) + n/q
	return n1 / pow(10, q-n%q) % 10
}

func problem40() (answer int) {
	answer = 1
	for n := 1; n <= 1e6; n *= 10 {
		answer *= d(n)
	}
	return
}

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

problem41.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
}

type digits []int

func (x digits) int() (answer int) {
	for _, v := range x {
		answer = 10*answer + v
	}
	return
}

func (x digits) isPrime() bool {
	return isPrime(x.int())
}

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

func (x digits) nexts() (answer []digits) {
	for i := 1; i <= 7; i++ {
		if x.member(i) {
			continue
		}
		d := make(digits, len(x)+1)
		copy(d, x)
		d[len(x)] = i
		answer = append(answer, d)
	}
	return
}

func problem41() (answer int) {
	stack := digits{}.nexts()
	for {
		last := len(stack) - 1
		top := stack[last]
		stack = stack[:last]
		if len(top) == 7 && top.isPrime() {
			answer = top.int()
			return
		}
		if len(top) < 7 {
			stack = append(stack, top.nexts()...)
		}
	}
	return
}

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

problem42.go

package main

import (
	"fmt"
	"io/ioutil"
	"math"
	"strings"
	"time"
)

type word string

func (w word) isTriangle() bool {
	n := 0
	for _, v := range w {
		n += int(v) - 'A' + 1
	}
	r := int(math.Sqrt(float64(n*2)))
	return n == r*(r+1)/2
}

func problem42() (answer int) {
	bs, _ := ioutil.ReadFile("words.txt")
	xs := strings.Split(string(bs), ",")
	for _, v := range xs {
		w := word(strings.Trim(v, "\""))
		if w.isTriangle() {
			answer++
		}
	}
	return
}

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

problem43.go

package main

import (
	"fmt"
	"time"
)

type digits []int64

func (d digits) int64() (answer int64) {
	for _, v := range d {
		answer = 10*answer + v
	}
	return
}

func (d digits) isCandidate() bool {
	switch n := len(d); {
	case n == 4:
		return d[1:].int64()%2 == 0
	case n == 5:
		return d[2:].int64()%3 == 0
	case n == 6:
		return d[3:].int64()%5 == 0
	case n == 7:
		return d[4:].int64()%7 == 0
	case n == 8:
		return d[5:].int64()%11 == 0
	case n == 9:
		return d[6:].int64()%13 == 0
	case n == 10:
		return d[7:].int64()%17 == 0
	}
	return true
}

func (d digits) member(n int64) (answer bool) {
	for _, v := range d {
		if n == v {
			return true
		}
	}
	return
}

func (d digits) nexts() (answer []digits) {
	for i := int64(0); i <= 9; i++ {
		if d.member(i) {
			continue
		}
		next := make(digits, len(d)+1)
		copy(next, d)
		next[len(d)] = i
		if next.isCandidate() {
			answer = append(answer, next)
		}
	}
	return
}

type tree struct {
	digits
	leaves []*tree
}

func newTree(d digits) *tree {
	t := &tree{digits: d}
	for _, v := range d.nexts() {
		t.leaves = append(t.leaves, newTree(v))
	}
	return t
}

func (t tree) sum() (answer int64) {
	if len(t.digits) == 10 {
		return t.digits.int64()
	}
	for _, v := range t.leaves {
		answer += v.sum()
	}
	return
}

func problem43() int64 {
	return newTree(digits{}).sum()
}

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

problem44.go

package main

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

type num int64

func (n num) pent() num {
	return n*(3*n-1)/2
}

func (n num) isPent() bool {
	x := 1 + 24*n
	y := num(math.Sqrt(float64(x)))
	return x == y*y && y%6 == 5
}

type seq []num

func (xs seq) solve() (answer num, ok bool) {
	if len(xs) < 2 {
		return
	}
	pk := xs[len(xs)-1]
	ds := xs[:len(xs)-1]
	for _,d := range ds {
		if (pk-d).isPent() && (2*pk-d).isPent() {
			return d, true
		}
	}
	return
}

func problem44() (answer num) {
	xs := seq{1,5}
	for {
		if d, ok := xs.solve(); ok {
			return d
		}
		xs = append(xs, num(len(xs)+1).pent())
	}
	return
}

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

problem45.go

package main

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

type hex struct {
	index uint64
	num   uint64
}

func newHex() *hex {
	return &hex{143, 40755}
}

func (p *hex) next() {
	n := (*p).index + 1
	(*p).index = n
	(*p).num = n * (2*n - 1)
}

func (p *hex) isPent() (answer bool) {
	n := (*p).num
	x := 1 + 24*n
	y := uint64(math.Sqrt(float64(x)))
	return x == y*y && y%6 == 5
}

func problem45() (answer interface{}) {
	h := newHex()
	h.next()
	for {
		h.next()
		if h.isPent() {
			return h.num
		}
	}
	return
}

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

problem46.go

package main

import (
	"fmt"
	"time"
)

type odd int

func (x odd) int() int {
	return int(x)
}

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

type primes map[int]bool

type oddComposite struct {
	odd
	primes
}

func (x oddComposite) isAnswer() bool {
	i := 1
	for {
		j := 2 * i * i
		if j >= x.int() {
			break
		}
		if x.primes[x.int()-j] {
			return false
		}
		i++
	}
	return true
}

func newOddComposite() oddComposite {
	return oddComposite{5, primes{3: true}}
}

func problem46() (answer int) {
	x := newOddComposite()
	for {
		if x.isPrime() {
			x.primes[x.int()] = true
			x.odd += 2
			continue
		}
		if x.isAnswer() {
			return x.int()
		}
		x.odd += 2
	}
	return
}

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

problem47.go

package main

import (
	"fmt"
	"time"
)

type factors []int

func (xs factors) next() (answer factors) {
	n := len(xs)
	ys := make(factors, 10000)
	answer = append(xs, ys...)
	for i := 2; i*2 < len(answer); i++ {
		if answer[i] != 0 {
			continue
		}
		for j := 2; i*j < len(answer); j++ {
			k := i * j
			if k < n {
				continue
			}
			answer[k]++
		}
	}
	return
}

func (xs factors) find(n int) (answer int, ok bool) {
	for i := n; i < len(xs); i++ {
		answer = i - 3
		res := []bool{}
		for j := answer; j <= i; j++ {
			if xs[j] != 4 {
				break
			}
			res = append(res, true)
		}
		if len(res) == 4 {
			ok = true
			return
		}
	}
	return
}

func problem47() (answer int) {
	xs := factors{-1, -1, 0}
	for {
		m := len(xs)
		xs = xs.next()
		if n, ok := xs.find(m); ok {
			return n
		}
	}
	return
}

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

problem48.go

package main

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

const d = 1e10

func powm(n int) (answer int64) {
	x := big.NewInt(int64(n))
	m := big.NewInt(d)
	return x.Exp(x, x, m).Int64()
}

func problem48() int64 {
	var n int64
	for i := 1; i <= 1000; i++ {
		n += powm(i)
	}
	return n % d
}

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

problem49.go

package main

import (
	"fmt"
	"sort"
	"time"
)

type primes []bool

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

func key(n int) string {
	xs := []int{}
	for n > 0 {
		xs = append(xs, n%10)
		n /= 10
	}
	sort.Ints(xs)
	return fmt.Sprint(xs)
}

type seq []int

func (xs seq) find() (answer seq, ok bool) {
	if len(xs) < 3 {
		return
	}
	for i := 0; i < len(xs)-2 ; i++ {
		for j := i+1; j < len(xs)-1 ; j++ {
			for k := j+1; k < len(xs); k++ {
				if xs[i] == 1487 && xs[j] == 4817 && xs[k] == 8147 {
					continue
				}
				if 2*xs[j]-xs[i] == xs[k] {
					return seq{xs[i],xs[j],xs[k]}, true
				}
			}
		}
	}
	return
}

func (xs seq) fmt() int64 {
	return 1e8*int64(xs[0]) + 1e4*int64(xs[1]) + int64(xs[2])
}

type primeSet map[string]seq

func newPrimeSet() (answer primeSet) {
	answer = make(primeSet)
	for i, ok := range newPrimes(9999) {
		if i < 1000 || !ok {
			continue
		}
		key := key(i)
		answer[key] = append(answer[key], i)
	}
	return
}

func problem49() (answer int64) {
	for _,v := range newPrimeSet() {
		if xs, ok := v.find(); ok {
			return xs.fmt()
		}
	}
	return
}

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