euler12

euler12.md

Project Euler #12

https://projecteuler.net/problem=12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Getting the number of divisors

This is the actual hard part.

After attempting to bruteforce this and speeding it up by doing work in goroutines, it was still too slow (approx 5min on 2016 MBP).

As I was not sure how to cache the intermediate results, and thinking this must be doable quicker, I did a bit of searching. Turns out if we create a prime factorization of a number, the number of divisors is a multiplication of count of individual factors, plus one.

https://www.math.upenn.edu/~deturck/m170/wk2/numdivisors.html

(Another approach: A friend has been talking about searching for coprimes. https://blog.stjepan.io/project-euler-problem-12/)

Whether a number is prime can be cached.

The rest is easy.

Having moved to this method, turns out that it's sufficiently fast that the overhead of communication over channels and of locking the primeness cache is sufficiently high that even two workers are actually slowing down finding of the result. (Probably the actual cause are locks on the map.)

The solution still seems inelegant, but it's good enough for me.

main.go

package main

import (
	"flag"
	"fmt"
	"math"
	"runtime"
	"sync"
)

var (
	primeCache = map[int]bool{}
	primeLock  sync.Mutex

	quitFlag bool
	maxSeen  int
	maxLock  sync.Mutex

	workerCount = flag.Int("worker_count", runtime.NumCPU(), "number of goroutines to spawn to calculate number of divisors")
)

type TriBr struct {
	i, triBr int
}

func isPrime(n int) bool {
	primeLock.Lock()
	if is, ok := primeCache[n]; ok {
		primeLock.Unlock()
		return is
	}
	primeLock.Unlock()
	for i := 2; i < int(math.Sqrt(float64(n))); i++ {
		if n%i == 0 {
			primeLock.Lock()
			primeCache[n] = false
			primeLock.Unlock()
			return false
		}
	}
	primeLock.Lock()
	primeCache[n] = true
	primeLock.Unlock()
	return true
}

func primeFactors(n int) (factors []int) {
	if isPrime(n) {
		factors = []int{n}
		return
	}
	max := n / 2
	for i := 2; i < max; i++ {
		if isPrime(i) {
			for n%i == 0 {
				factors = append(factors, i)
				n /= i
			}
			if n == 1 {
				break
			}
		}
	}
	return
}

func divisorsCountFromPrimeFactors(primes []int) (cnt int) {
	var currPrime int
	var currPrimeCount int
	cnt = 1
	for _, prime := range primes {
		if currPrime != prime {
			if currPrimeCount != 0 {
				cnt *= currPrimeCount + 1
			}
			currPrime = prime
			currPrimeCount = 0
		}
		currPrimeCount++
	}
	if currPrimeCount != 0 {
		cnt *= currPrimeCount + 1
	}
	return
}

func divisorsCount(n int) (cnt int) {
	return divisorsCountFromPrimeFactors(primeFactors(n))
}

func worker(id int, inStream chan TriBr, quit chan struct{}, done chan struct{}) {
	fmt.Printf("starting worker %d\n", id)
	defer func() { done <- struct{}{} }()
loop:
	for {
		select {
		case job := <-inStream:
			divs := divisorsCount(job.triBr)
			if job.i%500 == 0 {
				fmt.Printf("#%d: %d (%d)\n", job.i, job.triBr, divs)
			}
			if divs >= 500 {
				fmt.Printf("SOLUTION #%d: %d (%d)\n", job.i, job.triBr, divs)
				quitFlag = true
			}
			maxLock.Lock()
			if divs > maxSeen {
				fmt.Printf("#%d: %d (%d) MAX\n", job.i, job.triBr, divs)
				maxSeen = divs
			}
			maxLock.Unlock()
		case <-quit:
			break loop
		}
	}
}

func main() {
	var triBr int

	flag.Parse()

	workerCnt := *workerCount

	/*
		if workerCnt == 1 {
			for i := 1; true; i++ {
				triBr += i
				divs := divisorsCount(triBr)
				if divs > 500 {
					fmt.Printf("%d\n", triBr)
					return
				}
			}
		}
	*/

	jobQueue := make(chan TriBr, workerCnt-1)

	workerQuit := make([]chan struct{}, workerCnt)
	workerDone := make([]chan struct{}, workerCnt)
	for idx := range workerQuit {
		workerQuit[idx] = make(chan struct{})
		workerDone[idx] = make(chan struct{})
	}
	for idx, ch := range workerQuit {
		go worker(idx, jobQueue, ch, workerDone[idx])
	}

	for i := 1; true; i++ {
		triBr += i
		jobQueue <- TriBr{i: i, triBr: triBr}
		if quitFlag {
			break
		}
	}
	for _, ch := range workerQuit {
		ch <- struct{}{}
	}
	fmt.Printf("pending.")
	for _, ch := range workerDone {
		fmt.Printf(".")
		<-ch
	}
	fmt.Printf(" [done]\n")
}