9.go

package main

import (
	"fmt"
	"log"
)

/*

Project Euler #9:

a, b, c in Natural
a < b < c
a^2 + b^2 = c^2
a + b + c = 1000

~~~~~~~~~~~~~~~~~~

Limit the range of a:

a, b, c in Natural
a < b < c
a + b + c = 1000

=>

a < 333

~~~~~~~~~~~~~~~~~~

Express c:

a + b + c = 1000

=>

c = 1000 - a - b

~~~~~~~~~~~~~~~~~~

Transform the Pythagoras equation using c expressed:

a^2 + b^2 = c^2
c = 1000 - a - b

=>

a^2 + b^2 = (1000 - a - b)^2
a^2 + b^2 = a^2 + 2ab - 2000a + b^2 - 2000b + 1_000_000
0 = 2ab - 2000a - 2000b + 1_000_000
0 = ab - 1000a - 1000b + 500_000
0 = ab / 1000 - a - b + 500

~~~~~~~~~~~~~~~~~~

Express b:

0 = ab / 1000 - a - b + 500

=>

b - ab / 1000 = 500 - a
1000b - ab = 500_000 - 1000a
b(1000 - a) = 500_000 - 1000a
b = (500_000 - 1000a) / (1000 - a)

~~~~~~~~~~~~~~~~~~

Limit the set of possible a:

0 = ab / 1000 - a - b + 500
a, b, c in Natural

=>

ab / 1000 in Natural
a % 2 == 0 && b % 5 == 0 || a % 5 == 0 && b % 2 == 0
a % 2 == 0 || a % 5 == 0

~~~~~~~~~~~~~~~~~~

Solution with linear search:

b = (500_000 - 1000a) / (1000 - a)
a < 333
a % 2 == 0 || a % 5 == 0

=>

Input range: a < 333
Exit condition: b = (500_000 - 1000a) / (1000 - a) in Natural
Steps: 2, 5

*/

func search(step, rangeTo int) (int, int, int, bool) {
	for a := step; a < rangeTo; a += step {
		bf := (500_000 - 1000*float64(a)) / (1000 - float64(a))
		if float64(int(bf)) == bf {
			return a, int(bf), 1000 - a - int(bf), true
		}
	}

	return 0, 0, 0, false
}

func main() {
	const (
		rangeTo  = 333
		divisor5 = 5
		divisor2 = 2
	)

	var (
		a, b, c int
		step    int
		found   bool
	)

	for _, step = range []int{divisor5, divisor2} {
		if a, b, c, found = search(step, rangeTo); found {
			break
		}
	}

	if !found {
		log.Fatal("No results found.")
	}

	fmt.Printf("a=%d, b=%d, c=%d\n", a, b, c)
}