Solution:
package main
func main() {
i, sum := 0, 0
for i < 1000 {
if i%3 == 0 || i%5 == 0 {
sum += i
}
i++
}
println(sum)
}
Result: 233168
Time: 0m0.003s
Wednesday, July 13, 2011
Problem #1
Problem link
Solution:
Result: 233168
Time: 0m0.003s
Solution:
Result: 233168
Time: 0m0.003s
Problem #2
Problem link
Solution:
Result: 4613732
Time: 0m0.003s
Solution:
package main
func main() {
a, b, sum := 1, 2, 0
for b < 4000000 {
if b%2 == 0 {
sum += b
}
a, b = b, a+b
}
println(sum)
}
Result: 4613732
Time: 0m0.003s
Problem #3
Problem link
Solution:
Result: 6857
Time: 0m0.003s
Solution:
package main
func main() {
target := int64(600851475143)
arr := make([]bool, 10000)
prime := 3
var k int
for {
for k = 2 * prime; k < len(arr); k += prime {
arr[k] = true
}
for k = prime + 2; k < len(arr) && arr[k]; k += 2 {
}
if k < len(arr) {
prime = k
if target%int64(k) == 0 {
target = target / int64(k)
if target == 1 {
println(k)
return
}
}
} else {
break
//prevent infinite loop in case the answer
//is not less than 10000
}
}
}
Result: 6857
Time: 0m0.003s
Problem #4
Problem link
Solution:
Result: 906609
Time: 0m0.304s
Solution:
package main
import (
"strconv"
)
func isPalindrome(input string) bool {
for i := 0; i < len(input)/2; i++ {
if input[i] != input[len(input)-1-i] {
return false
}
}
return true
}
func main() {
max, mul := 0, 0
for i := 100; i < 1000; i++ {
for j := i; j < 1000; j++ {
mul = i * j
if isPalindrome(strconv.Itoa(mul)) && mul > max {
max = mul
}
}
}
println(max)
}
Result: 906609
Time: 0m0.304s
Problem #5
Problem link
Solution:
Result: 232792560
Time: 0m0.003s
Solution:
package main
func main() {
primes := []int{2, 3, 5, 7, 11, 13, 17, 19}
result := 1
var divisor int
for i := range primes {
divisor = primes[i]
for divisor <= 20 {
divisor *= primes[i]
}
divisor /= primes[i]
result *= divisor
}
println(result)
}
Result: 232792560
Time: 0m0.003s
Problem #6
Problem link
Solution:
Result: 25164150
Time: 0m0.003s
Solution:
package main
func main() {
result := ((100*101)/2)*((100*101)/2) - ((100 * 101 * 201) / 6)
println(result)
}
Result: 25164150
Time: 0m0.003s
Problem #7
Problem link
Solution:
After learning that the result is 104743, size of the boolean array is dropped down to 105000
Result: 104743
Time: 0m0.006s
Solution:
package main
func main() {
arr := make([]bool, 105000)
arr[0], arr[1] = true, true
count, prime := 2, 3
var k int
for {
for k = 2 * prime; k < len(arr); k += prime {
arr[k] = true
}
for k = prime + 2; k < len(arr) && arr[k]; k += 2 {
}
if k < len(arr) {
prime = k
count++
if count == 10001 {
println(prime)
break
}
} else {
break
}
}
}
After learning that the result is 104743, size of the boolean array is dropped down to 105000
Result: 104743
Time: 0m0.006s
Problem #8
Problem link
Solution:
Result: 40824
Time: 0m0.008s
Solution:
package main
import "strconv"
func main() {
number := "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
largestPro := 0
for i := 0; i < len(number)-5; i++ {
localPro := 1
for j := i; j < i+5; j++ {
num, _ := strconv.Atoi(string(number[j]))
localPro *= num
}
if localPro > largestPro {
largestPro = localPro
}
}
println(largestPro)
}
Result: 40824
Time: 0m0.008s
Problem #9
Problem link
Solution:
Result: 31875000
Time: 0m0.016s
Solution:
package main
import "math"
func isSquare(num int) (bool, int) {
sqrt := int(math.Sqrt(float64(num)))
if sqrt*sqrt == num {
return true, sqrt
}
return false, -1
}
func main() {
loop:
for a := 1; a < 500; a++ {
for b := a; b < 500; b++ {
result, c := isSquare(a*a + b*b)
if result && a+b+c == 1000 {
println(a * b * c)
break loop
}
}
}
}
Result: 31875000
Time: 0m0.016s
Problem #10
Problem link
Solution:
Result: 142913828922
Time: 0m0.055s
Solution:
package main
func main() {
arr := make([]bool, 2000000)
arr[0], arr[1] = true, true
sum, prime := int64(5), 3
var k int
for {
for k = 2 * prime; k < len(arr); k += prime {
arr[k] = true
}
for k = prime + 2; k < len(arr) && arr[k]; k += 2 {
}
if k < len(arr) {
prime = k
sum += int64(k)
} else {
break
}
}
println(sum)
}
Result: 142913828922
Time: 0m0.055s
Problem #11
Problem link
Solution:
Input file is renamed as 011_input.txt.
Result: 70600674
Time: 0m0.005s
Solution:
package main
import (
"strconv"
"io/ioutil"
"strings"
)
func main() {
fileBuf, err := ioutil.ReadFile("011_input.txt")
if err != nil {
panic(err.String())
}
fileStr := string(fileBuf)
lines := strings.Split(fileStr, "\n", 20)
arr := make([][]uint, 20)
var strArr []string
for i := range lines {
arr[i] = make([]uint, 20)
strArr = strings.Split(lines[i], " ", 20)
for j := range arr[i] {
intvalue, _ := strconv.Atoi(strArr[j])
arr[i][j] = uint(intvalue)
}
}
max := uint(0)
//left to right
for i := range arr {
for j := 0; j < 17; j++ {
mul := arr[i][j] * arr[i][j+1] * arr[i][j+2] * arr[i][j+3]
if mul > max {
max = mul
}
}
}
//up to down
for i := 0; i < 17; i++ {
for j := range arr[i] {
mul := arr[i][j] * arr[i+1][j] * arr[i+2][j] * arr[i+3][j]
if mul > max {
max = mul
}
}
}
//first diagonal
for i := 0; i < 17; i++ {
for j := 0; j < 17; j++ {
mul := arr[i][j] * arr[i+1][j+1] * arr[i+2][j+2] * arr[i+3][j+3]
if mul > max {
max = mul
}
}
}
//second diagonal
for i := 3; i < 20; i++ {
for j := 0; j < 17; j++ {
mul := arr[i][j] * arr[i-1][j+1] * arr[i-2][j+2] * arr[i-3][j+3]
if mul > max {
max = mul
}
}
}
println(max)
}
Input file is renamed as 011_input.txt.
Result: 70600674
Time: 0m0.005s
Problem #12
Problem link
Solution:
Result: 76576500
Time: 0m1.010s
Solution:
package main
import (
"math"
)
func main() {
divisors := 1
triangleN := uint64(1)
for i := 2; divisors < 500; i++ {
triangleN += uint64(i)
divisors = noOfDivisors(triangleN)
}
println(triangleN)
}
func noOfDivisors(number uint64) int {
counter := 0
limit := uint64(math.Sqrt(float64(number)))
for i := 1; uint64(i) <= limit; i++ {
if number%uint64(i) == 0 {
counter += 2
}
}
return counter
}
Result: 76576500
Time: 0m1.010s
Problem #13
Problem link
Solution:
Result: 5537376230
Time: 0m0.010s
Solution:
package main
import (
"io/ioutil"
"strconv"
"strings"
)
func main() {
fileBuf, err := ioutil.ReadFile("013_input.txt")
if err != nil {
panic(err.String())
}
fileStr := string(fileBuf)
lines := strings.Split(fileStr, "\n", 100)
result := ""
carryout, digit := 0, 0
for i := 49; i >= 0; i-- {
sum := carryout
for j := range lines {
num, _ := strconv.Atoi(string(lines[j][i]))
sum += num
}
digit = sum % 10
carryout = sum / 10
result = strconv.Itoa(digit) + result
}
result = strconv.Itoa(carryout) + result
println(result[0:10])
}
Result: 5537376230
Time: 0m0.010s
Problem #14
Problem link
Solution:
Result: 837799
Time: 0m0.271s
Solution:
package main
func main() {
//allocate 4 MB of space at once
arr := make([]int, 1000000)
max, maxLoc, notFound, cur, steps := 0, 0, true, uint64(0), 0
for i := 1; i < 1000000; i++ {
notFound = true
cur = uint64(i)
steps = 0
for notFound {
if cur == 1 {
notFound = false
arr[i] = steps
if steps > max {
max = steps
maxLoc = i
}
} else if cur < uint64(i) {
notFound = false
steps = steps + arr[cur]
arr[i] = steps
if steps > max {
max = steps
maxLoc = i
}
} else {
if cur%2 == 0 {
cur /= 2
} else {
cur = 3*cur + 1
}
}
steps++
}
}
println(max, maxLoc)
}
Result: 837799
Time: 0m0.271s
Problem #15
Problem link
Solution:
Result: 137846528820
Time: 0m0.003s
Solution:
package main
var arr [][]uint64
func main() {
arr = make([][]uint64, 21)
for i := range arr {
arr[i] = make([]uint64, 21)
for j := range arr[i] {
arr[i][j] = uint64(0)
}
}
arr[20][20] = uint64(1)
println(noOfRoutes(0, 0))
}
func noOfRoutes(i, j int) uint64 {
if arr[i][j] != uint64(0) {
return arr[i][j]
}
var result uint64
if i < 20 && j < 20 {
result = noOfRoutes(i+1, j) + noOfRoutes(i, j+1)
} else if i < 20 && j == 20 {
result = noOfRoutes(i+1, j)
} else {
result = noOfRoutes(i, j+1)
}
arr[i][j] = result
return result
}
Result: 137846528820
Time: 0m0.003s
Problem #16
Problem link
Solution:
Result: 1366
Time: 0m0.228s
Solution:
package main
import (
"strconv"
)
func main() {
input := "2"
for i := 0; i < 999; i++ {
input = multipyByTwo(input)
}
println(sumUpDigits(input))
}
func sumUpDigits(input string) int {
result, digit := 0, 0
for i := range input {
digit, _ = strconv.Atoi(string(input[i]))
result += digit
}
return result
}
func multipyByTwo(input string) string {
result, carryout, digit := "", 0, 0
for i := len(input) - 1; i >= 0; i-- {
digit, _ = strconv.Atoi(string(input[i]))
digit = digit*2 + carryout
carryout = digit / 10
digit = digit % 10
result = strconv.Itoa(digit) + result
}
if carryout > 0 {
result = strconv.Itoa(carryout) + result
}
return result
}
Result: 1366
Time: 0m0.228s
Problem #17
Problem link
Solution:
Result: 21124
Time: 0m0.003s
Solution:
package main
func main() {
sum := 0
for i := 0; i < 1000; i++ {
sum += lengthNumber(i)
}
println(sum + len("onethousand"))
}
func lengthNumber(number int) int {
switch number {
case 0:
return 0
case 1:
return 3 //one
case 2:
return 3 //two
case 3:
return 5 //three
case 4:
return 4 //four
case 5:
return 4 //five
case 6:
return 3 //six
case 7:
return 5 //seven
case 8:
return 5 //eight
case 9:
return 4 //nine
case 10:
return 3 //ten
case 11:
return 6 //eleven
case 12:
return 6 //twelve
case 13:
return 8 //thirteen
case 14:
return 8 //fourteen
case 15:
return 7 //fifteen
case 16:
return 7 //sixteen
case 17:
return 9 //seventeen
case 18:
return 8 //eighteen
case 19:
return 8 //nineteen
case 20:
return 6 //twenty
case 30:
return 6 //thirty
case 40:
return 5 //forty
case 50:
return 5 //fifty
case 60:
return 5 //sixty
case 70:
return 7 //seventy
case 80:
return 6 //eighty
case 90:
return 6 //ninety
}
if number < 100 {
return lengthNumber(number-(number%10)) + lengthNumber(number%10)
}
if number%100 == 0 {
return lengthNumber(number/100) + 7
}
return lengthNumber(number/100) + 10 + lengthNumber(number%100)
}
Result: 21124
Time: 0m0.003s
Problem #18
Problem link
Solution:
Tree is read from a file named as 018_input.txt and also memoization is used for this problem.
Result: 1074
Time: 0m0.005s
Solution:
package main
import (
"io/ioutil"
"strconv"
"strings"
)
var arr [][]int
var bests [][]int
func main() {
fileBuf, err := ioutil.ReadFile("018_input.txt")
if err != nil {
panic(err.String())
}
fileStr := strings.Trim(string(fileBuf), "")
oneDArrStr := strings.Split(fileStr, "\n", -1)
var line []string
arr = make([][]int, 15)
bests = make([][]int, len(arr))
for i := range arr {
line = strings.Split(oneDArrStr[i], " ", -1)
arr[i] = make([]int, len(line))
bests[i] = make([]int, len(arr[i]))
for j := range line {
arr[i][j], _ = strconv.Atoi(line[j])
bests[i][j] = -1
}
}
println(bestSum(0, 0))
}
func bestSum(i, j int) int {
var result int
if bests[i][j] != -1 {
result = bests[i][j]
} else if i == len(arr)-1 {
result = arr[i][j]
return arr[i][j]
} else {
sumLeft, sumRight := bestSum(i+1, j), bestSum(i+1, j+1)
if sumLeft > sumRight {
result = arr[i][j] + sumLeft
} else {
result = arr[i][j] + sumRight
}
}
bests[i][j] = result
return result
}
Tree is read from a file named as 018_input.txt and also memoization is used for this problem.
Result: 1074
Time: 0m0.005s
Problem #19
Problem link
Solution:
Result: 171
Time: 0m0.003s
Solution:
package main
var months []int
var count int
func main() {
months = make([]int, 12)
//calculate first days of the months in 1900
daysInMonths := []int{31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30}
months[0] = 0
for i := range daysInMonths {
months[i+1] = (months[i] + daysInMonths[i]) % 7
}
count = 0
for year := 1900; year < 2000; year++ {
for i := range months {
if (year%4 == 0 && i <= 1) || ((year+1)%4 == 0 && i > 1) {
months[i] = (months[i] + 366) % 7
} else {
months[i] = (months[i] + 365) % 7
}
if months[i] == 6 {
count++
}
}
}
println(count)
}
Result: 171
Time: 0m0.003s
Problem #20
Problem link
Solution:
Result: 648
Time: 0m0.023s
Solution:
package main
import (
"big"
"strconv"
)
func main() {
mul := big.NewInt(1)
for i := 2; i <= 100; i++ {
mul.Mul(mul, big.NewInt(int64(i)))
}
result, digit := 0, 0
for i := range mul.String() {
digit, _ = strconv.Atoi(string(mul.String()[i]))
result += digit
}
println(result)
}
Result: 648
Time: 0m0.023s
Problem #21
Problem link
Solution:
Result: 31626
Time: 0m0.023s
Solution:
package main
import (
"math"
)
func main() {
sum, j := 0, 0
for i := 1; i < 10000; i++ {
j = sumOfProperDivisors(i)
if i == sumOfProperDivisors(j) && i != j {
sum += i
}
}
println(sum)
}
func sumOfProperDivisors(input int) int {
//checking until the square root is enough
//since a divisor less than the square root corresponds
//the other divisor greater than the square root
limit, sum := int(math.Sqrt(float64(input))), 0
for i := 1; i <= limit; i++ {
if input%i == 0 {
if i == input/i {
sum += i
} else {
sum += i + (input / i)
}
}
}
return sum - input
}
Result: 31626
Time: 0m0.023s
Problem #22
Problem link
Solution:
Result: 871198282
Time: 0m0.035s
Solution:
package main
import (
"io/ioutil"
"strings"
"sort"
)
func main() {
fileBuf, err := ioutil.ReadFile("022_input.txt")
if err != nil {
panic(err.String())
}
fileStr := string(fileBuf)
arr := strings.Split(fileStr, ",", -1)
for i := range arr {
arr[i] = strings.Split(arr[i], "\"", -1)[1]
}
sort.SortStrings(arr)
result := uint64(0)
for i := range arr {
result += uint64(i+1) * uint64(alphabeticValue(arr[i]))
}
println(result)
}
func alphabeticValue(in string) int {
sum := 0
for i := range in {
sum += int(in[i]) - int('A') + 1
}
return sum
}
Result: 871198282
Time: 0m0.035s
Problem #23
Problem link
Solution:
Result: 4179871
Time: 0m1.406s
Solution:
package main
import (
"math"
"container/list"
)
var writable []bool
var limit int
var abunList *list.List
func main() {
abunList = list.New()
limit = 28124
writable = make([]bool, limit)
for i := 1; i < limit; i++ {
writable[i] = false
if i < sumOfProperDivisors(i) {
abunList.PushBack(i)
}
}
checkWritables()
sum := 0
for i := 1; i < limit; i++ {
if !writable[i] {
sum += i
}
}
println(sum)
}
func checkWritables() {
for i := abunList.Front(); i != nil; i = i.Next() {
for j := i; j != nil; j = j.Next() {
if sum := i.Value.(int) + j.Value.(int); sum < limit {
writable[sum] = true
}
}
}
}
func sumOfProperDivisors(input int) int {
//checking until the square root is enough
//since a divisor less than the square root corresponds
//the other divisor greater than the square root
limit, sum := int(math.Sqrt(float64(input))), 0
for i := 1; i <= limit; i++ {
if input%i == 0 {
if i == input/i {
sum += i
} else {
sum += i + (input / i)
}
}
}
return sum - input
}
Result: 4179871
Time: 0m1.406s
Problem #24
Problem link
Solution:
Result: 2783915460
Time: 0m0.003s
Solution:
package main
var used []bool
func main() {
used = make([]bool, 10)
for i := range used {
used[i] = false
}
remaining := 999999
perm := 1
index := 0
for i := 9; i > 0; i-- {
perm = 1
for j := i; j > 0; j-- {
perm *= j
}
index = remaining / perm
remaining = remaining % perm
j := 0
for j = 0; j < index || used[j]; j++ {
if used[j] {
index++
}
}
used[j] = true
print(j)
}
println(remaining)
}
Result: 2783915460
Time: 0m0.003s
Problem #25
Problem link
Solution:
Result: 4782
Time: 0m2.108s
Solution:
package main
import (
"big"
)
func main() {
a, b, c, counter := big.NewInt(int64(1)), big.NewInt(int64(2)), big.NewInt(int64(0)), 2
for len(a.String()) < 1000 {
c.Neg(a) //c is a temp variable
a.Add(a, b)
b.Neg(c)
counter++
}
println(counter)
}
Result: 4782
Time: 0m2.108s
Problem #26
Problem link
Solution:
Result: 983
Time: 0m0.041s
Solution:
package main
import (
"big"
)
//using Fermat's little theorem we need to find the largest prime less than 1000
//see details: http://en.wikipedia.org/wiki/Repeating_decimal#Fractions_with_prime_denominators
func main() {
//find primes
arr := make([]bool, 1000)
arr[0], arr[1] = true, true
prime := 3
var k int
for {
for k = prime * 2; k < len(arr); k += prime {
arr[k] = true
}
for k = prime + 2; k < len(arr) && arr[k]; k += 2 {
}
if k < len(arr) {
prime = k
} else {
break
}
}
//iterate over primes in reverse direction
b := big.NewInt(0)
var i int
for k = prime; k > 0; k -= 2 {
if !arr[k] && k%2 != 0 {
inner:
for i = 1; i < k; i++ {
if b.Mod(b.Sub(b.Exp(big.NewInt(10), big.NewInt(int64(i)), nil), big.NewInt(1)), big.NewInt(int64(k))).Int64() == 0 {
break inner
}
}
if k-i == 1 {
println(k)
return
}
}
}
}
Result: 983
Time: 0m0.041s
Problem #27
Problem link
Solution:
Result: -59231
Time: 0m0.802s
Solution:
package main
import (
"math"
)
func main() {
var maxCounter, aInMax, bInMax int
maxCounter = 0
for a := -999; a < 1000; a++ {
for b := -999; b < 1000; b++ {
inner:
for n := 0; ; n++ {
if !isPrime(n*n + a*n + b) {
if n > maxCounter {
maxCounter, aInMax, bInMax = n, a, b
}
break inner
}
}
}
}
println(aInMax * bInMax)
}
func isPrime(in int) bool {
limit := int(math.Sqrt(float64(in)))
if in < 2 || in%2 == 0 {
return false
} else {
for i := 2; i < limit; i++ {
if in%i == 0 {
return false
}
}
}
return true
}
Result: -59231
Time: 0m0.802s
Problem #28
Problem link
Solution:
Result: 669171001
Time: 0m0.005s
Solution:
package main
func main() {
sum, number, skip := 1, 1, 0
for i := 0; i < 2000; i++ {
if i%4 == 0 {
skip += 2
}
for j := 0; j < skip; j++ {
number++
}
sum += number
}
println(sum)
}
Result: 669171001
Time: 0m0.005s
Problem #29
Problem link
Solution:
Result: 9183
Time: 0m0.300s
Solution:
package main
import (
"big"
)
func main() {
strMap := make(map[string]int)
for a := 2; a < 101; a++ {
for b := 2; b < 101; b++ {
bigA := big.NewInt(int64(a))
bigB := big.NewInt(int64(b))
bigA.Exp(bigA, bigB, nil)
strMap[bigA.String()] = 0
}
}
println(len(strMap))
}
Result: 9183
Time: 0m0.300s
Problem #30
Problem link
Solution:
Result: 443839
Time: 0m0.038s
Solution:
package main
func main() {
limit := 9 * 9 * 9 * 9 * 9 * (5 - 1)
sum := 0
for i := 22; i < limit; i++ {
if i == sumOfFifthPowers(i) {
sum += i
}
}
println(sum)
}
func sumOfFifthPowers(in int) int {
sum := 0
for in > 0 {
sum += fifthPower(in % 10)
in /= 10
}
return sum
}
func fifthPower(in int) int {
return in * in * in * in * in
}
Result: 443839
Time: 0m0.038s
Problem #31
Problem link
Solution:
Result: 73682
Time: 0m0.094s
Solution:
package main
var total int
var coins []int
func main() {
total, coins = 200, []int{1, 2, 5, 10, 20, 50, 100, 200}
println(count(total, len(coins)))
}
func count(n, m int) int {
if n == 0 {
return 1
} else if n < 0 {
return 0
} else if m <= 0 && n >= 1 {
return 0
}
return count(n, m-1) + count(n-coins[m-1], m)
}
Result: 73682
Time: 0m0.094s
Problem #32
Problem link
Solution:
Result: 45228
Time: 0m2.405s
Solution:
package main
import (
"strconv"
"strings"
)
func main() {
mp := map[int]int{}
for i := 1; i < 200; i++ {
for j := 1; j < 5000; j++ {
if isPandigital(i, j, i*j) {
mp[i*j] = 1
}
}
}
sum := 0
for key, _ := range mp {
sum += key
}
println(sum)
}
func isPandigital(mul1, mul2, result int) bool {
str := strconv.Itoa(mul1) + strconv.Itoa(mul2) + strconv.Itoa(result)
if len(str) != 9 {
return false
}
for i := 1; i < 10; i++ {
if !strings.Contains(str, strconv.Itoa(i)) {
return false
}
}
return true
}
Result: 45228
Time: 0m2.405s
Problem #33
Problem link
Solution:
Result: 100
Time: 0m0.003s
Solution:
package main
func main() {
var i, j, k, ki, ij int
result := 1.0
for i = 1; i < 10; i++ {
for j = 1; j < i; j++ {
for k = 1; k < j; k++ {
ki = 10*k + i
ij = 10*i + j
if ki*j == ij*k {
result *= float64(ij) / float64(ki)
}
}
}
}
println(int(result))
}
Result: 100
Time: 0m0.003s
Problem #34
Problem link
Solution:
Result: 40730
Time: 0m8.565s
Solution:
package main
func main() {
factorials := make([]int, 10)
factorials[0] = 1
for i := 1; i <= 9; i++ {
factorials[i] = factorials[i-1] * i
}
//find limit
powerOfTen := 10
limit := factorials[9]
for limit > powerOfTen {
limit *= 2
powerOfTen *= 10
}
sum := 0
var localSum, j int
for i := 10; i < limit; i++ {
localSum, j = 0, i
for j > 9 {
localSum += factorials[j%10]
j /= 10
}
localSum += factorials[j]
if i == localSum {
sum += i
}
}
println(sum)
}
Result: 40730
Time: 0m8.565s
Problem #35
Problem link
Solution:
Result: 55
Time: 0m0.135s
Solution:
package main
import (
"strconv"
)
func main() {
arr := make([]bool, 1000000)
arr[1] = true
prime := 3
count := 13
var k, tmp, localCount int
var str string
primeloop:
for {
for k = prime * 2; k < len(arr); k += prime {
arr[k] = true
}
for k = prime + 2; k < len(arr) && arr[k]; k += 2 {
}
if k < len(arr) {
prime = k
str = strconv.Itoa(prime)
if prime > 100 {
localCount = 1
for i := 0; i < len(str)-1; i++ {
str = str[1:] + str[0:1]
tmp, _ = strconv.Atoi(str)
if tmp > prime {
continue primeloop
} else if !arr[tmp] && tmp%2 != 0 {
localCount++
} else {
continue primeloop
}
}
count += localCount
}
} else {
break
}
}
println(count)
}
Result: 55
Time: 0m0.135s
Problem #36
Problem link
Solution:
Result: 872187
Time: 0m0.801s
Solution:
package main
import (
"strconv"
)
func main() {
sum := 0
for i := 0; i < 1000000; i++ {
if isPalindrome(strconv.Itoa(i)) {
if isPalindrome(strconv.Itob(i, 2)) {
sum += i
}
}
}
println(sum)
}
func isPalindrome(in string) bool {
for i := 0; i < len(in); i++ {
if in[i] != in[len(in)-i-1] {
return false
}
}
return true
}
Result: 872187
Time: 0m0.801s
Problem #37
Problem link
Solution:
Result: 748317
Time: 0m0.083s
Solution:
package main
import (
"strconv"
)
func main() {
arr := make([]bool, 1000000)
left := make([]bool, 1000000)
right := make([]bool, 1000000)
//manuel setting for the values less than 10
left[2], left[3], left[5], left[7] = true, true, true, true
right[2], right[3], right[5], right[7] = true, true, true, true
arr[0], arr[1], arr[6], arr[9] = true, true, true, true
a := []int{3, 5, 7}
for i := range a {
for k := a[i] * 2; k < len(arr); k += a[i] {
arr[k] = true
}
}
//calculate other primes and check the condition.
var k, tmp int
prime, counter, sum := 11, 0, 0
for {
if right[prime/10] {
right[prime] = true
}
tmp, _ = strconv.Atoi(strconv.Itoa(prime)[1:])
if left[tmp] {
left[prime] = true
if right[prime] {
sum += prime
counter++
if counter == 11 {
println(sum)
return
}
}
}
for k = prime * 2; k < len(arr); k += prime {
arr[k] = true
}
for k = prime + 2; k < len(arr) && arr[k]; k += 2 {
}
if k < len(arr) {
prime = k
} else {
break
}
}
}
Result: 748317
Time: 0m0.083s
Problem #38
Problem link
Solution:
Result: 932718654
Time: 0m0.049s
Solution:
package main
import (
"strconv"
"strings"
)
func main() {
max := 0
var tmp int
for i := 1; i < 10000; i++ {
str := ""
for j := 1; j < 9 && len(str) < 9; j++ {
str += strconv.Itoa(i * j)
}
if len(str) == 9 && isPandigital(str) {
tmp, _ = strconv.Atoi(str)
if tmp > max {
max = tmp
}
}
}
println(max)
}
func isPandigital(str string) bool {
if len(str) != 9 {
return false
}
for i := 1; i < 10; i++ {
if !strings.Contains(str, strconv.Itoa(i)) {
return false
}
}
return true
}
Result: 932718654
Time: 0m0.049s
Problem #39
Problem link
Solution:
Result: 840
Time: 0m1.245s
Solution:
package main
func main() {
answer := 0
max := 0
var solutions int
for p := 5; p <= 1000; p++ {
solutions = 0
for c := p; c > p/3; c-- {
for b := 1; b < c; b++ {
a := p - c - b
if isPythagoras(a, b, c) {
solutions++
}
}
}
if solutions > max {
max, answer = solutions, p
}
}
println(answer)
}
func isPythagoras(a, b, c int) bool {
if a*a+b*b == c*c {
return true
}
return false
}
Result: 840
Time: 0m1.245s
Problem #40
Problem link
Solution:
Result: 210
Time: 0m0.153s
Solution:
package main
import (
"strconv"
)
func main() {
i, count, limit, mul := 1, 0, 10, 1
var tmp int
for limit < 1000001 {
str := strconv.Itoa(i)
count += len(str)
if count >= limit {
tmp, _ = strconv.Atoi(str[len(str)-(count-limit)-1 : len(str)-(count-limit)])
mul *= tmp
limit *= 10
}
i++
}
println(mul)
}
Result: 210
Time: 0m0.153s
Problem #41
Problem link
Solution:
Result: 7652413
Time: 0m15.596s
Solution:
package main
import (
"strconv"
"strings"
)
func main() {
a := make([]bool, 87654322)
a[0], a[1] = true, true
prime := 3
var k int
finished := false
for !finished {
for k = 2 * prime; k < len(a); k += prime {
a[k] = true
}
for k = prime + 2; k < len(a) && a[k]; k += 2 {
}
if k < len(a) {
prime = k
} else {
finished = true
}
}
//a now has false values for the primes and multiples of 2
//but we skip even numbers in our iteration.
for i := int64(87654321); i > 0; i -= 2 {
if !a[i] && isPandigital(i) {
println(i)
return
}
}
}
func isPandigital(in int64) bool {
str := strconv.Itoa64(in)
n := len(str)
for i := 1; i <= n; i++ {
if !strings.Contains(str, strconv.Itoa(i)) {
return false
}
}
return true
}
Result: 7652413
Time: 0m15.596s
Problem #42
Problem link
Solution:
Result: 162
Time: 0m0.009s
Solution:
package main
import (
"io/ioutil"
"strings"
)
var triangles []int
func main() {
//read names
fileBuf, err := ioutil.ReadFile("042_input.txt")
if err != nil {
panic(err.String())
}
fileStr := string(fileBuf)
arr := strings.Split(fileStr, ",", -1)
for i := range arr {
arr[i] = strings.Split(arr[i], "\"", -1)[1]
}
//create an array of triangle numbers
triangles = make([]int, 20)
for i := range triangles {
triangles[i] = (i * (i + 1)) / 2
}
//iterate over names to check
result := 0
for i := range arr {
if isTriangle(alphabeticValue(arr[i])) {
result++
}
}
println(result)
}
func isTriangle(in int) bool {
for i := range triangles {
if triangles[i] == in {
return true
}
}
return false
}
func alphabeticValue(in string) int {
sum := 0
for i := range in {
sum += int(in[i]) - int('A') + 1
}
return sum
}
Result: 162
Time: 0m0.009s
Problem #43
Problem link
Solution:
Result: 16695334890
Time: 0m6.223s
Solution:
package main
import (
"strconv"
)
var result int64
var divisors []int
var tmp int
var tmp64 int64
func main() {
result = int64(0)
divisors = []int{2, 3, 5, 7, 11, 13, 17}
allPerms("", "0123456789")
println(result)
}
func allPerms(pre, s string) {
if len(s) == 0 {
checkTheProperty(pre)
} else {
for i := 0; i < len(s); i++ {
allPerms(pre+s[i:i+1], s[0:i]+s[i+1:len(s)])
}
}
}
func checkTheProperty(s string) {
if s[0] == '0' {
return
} else {
for i := 1; i < 8; i++ {
if tmp, _ = strconv.Atoi(s[i : i+3]); tmp%divisors[i-1] != 0 {
return
}
}
}
tmp64, _ = strconv.Atoi64(s)
result += tmp64
}
Result: 16695334890
Time: 0m6.223s
Problem #44
Problem link
Solution:
Result: 5482660
Time: 0m0.961s
Solution:
package main
var arr []int
func main() {
//2500 is learned after experiment. The array includes the result
arr = make([]int, 2500)
for i := range arr {
arr[i] = (i * (3*i - 1)) / 2
}
min := int(^uint(0) >> 1)
for i := 1; i < len(arr); i++ {
for j := i + 1; j < len(arr); j++ {
if isPentagonal(arr[j]-arr[i]) && isPentagonal(arr[j]+arr[i]) && arr[j]-arr[i] < min {
min = arr[j] - arr[i]
}
}
}
println(min)
}
func isPentagonal(in int) bool {
return search(in, 0, len(arr)-1)
}
func search(value, low, high int) bool {
if high < low {
return false
}
mid := low + (high-low)/2
if arr[mid] > value {
return search(value, low, mid-1)
} else if arr[mid] < value {
return search(value, mid+1, high)
}
return true
}
Result: 5482660
Time: 0m0.961s
Problem #45
Problem link
Solution:
Result: 1533776805
Time: 0m0.035s
Solution:
package main
var arr []int64 //pentagonals
func main() {
arr = make([]int64, 80000)
for i := 1; i < len(arr); i++ {
arr[i] = int64(i) * (3*int64(i) - 1) / 2
}
var tmp int64
i := 144
loop:
for {
tmp = int64(i) * int64(2*i-1)
if isPentagonal(tmp) { //every hexagonal is also triangle
println(tmp)
break loop
}
i++
}
}
func isPentagonal(in int64) bool {
return search(in, 1, len(arr)-1)
}
func search(value int64, low, high int) bool {
if high < low {
return false
}
mid := low + (high-low)/2
if arr[mid] > value {
return search(value, low, mid-1)
} else if arr[mid] < value {
return search(value, mid+1, high)
}
return true
}
Result: 1533776805
Time: 0m0.035s
Problem #46
Problem link
Solution:
Result: 5777
Time: 0m0.043s
Solution:
package main
import (
"math"
)
func main() {
arr := make([]bool, 1000000)
arr[0], arr[1], arr[2] = false, false, true
i := 3
var composite, found bool
var tmp, tmp2 int
loop:
for {
composite = false
inner:
for j := 2; j < i; j++ {
if arr[j] && i%j == 0 {
composite = true
break inner
}
}
if composite {
found = false
inner2:
for j := 2; j < i; j++ {
if arr[j] {
tmp = (i - j)
if tmp2 = int(math.Sqrt(float64(tmp / 2))); tmp%2 == 0 && tmp2*tmp2 == tmp/2 {
found = true
break inner2
}
}
}
if !found {
println(i)
break loop
}
} else { //prime
arr[i] = true
}
i += 2
}
}
Result: 5777
Time: 0m0.043s
Problem #47
Problem link
Solution:
Result: 134043
Time: 0m1.323s
Solution:
package main
func main() {
arr := make([]bool, 1000000)
arr[0], arr[1] = true, true
count, prime := 2, 3
var k int
for {
for k = 2 * prime; k < len(arr); k += prime {
arr[k] = true
}
for k = prime + 2; k < len(arr) && arr[k]; k += 2 {
}
if k < len(arr) {
prime = k
count++
} else {
break
}
}
primes := make([]int, count)
primes[0] = 2
index := 1
for i := 3; i < len(arr); i += 2 {
if !arr[i] {
primes[index] = i
index++
}
}
var consecutiveCount, divisorCount, tmp int
outer:
for i := 646; i < 1000000; i++ {
consecutiveCount = 0
inner:
for j := i; j < i+4; j++ {
divisorCount = 0
//find divisors of j
if !arr[j] && j%2 != 0 {
//a quick check: if j is prime
continue outer
} else {
tmp = j
for k := 0; k < len(primes); k++ {
if (!arr[tmp] && tmp%2 != 0) || tmp%primes[k] == 0 {
divisorCount++
if divisorCount == 4 {
consecutiveCount++
if consecutiveCount == 4 {
println(i)
return
}
continue inner
} else if !arr[tmp] && tmp%2 != 0 {
//another quick check for prime tmp
continue outer
}
for tmp%primes[k] == 0 {
tmp /= primes[k]
}
}
}
}
}
}
}
Result: 134043
Time: 0m1.323s
Problem #48
Problem link
Solution:
Result: 9110846700
Time: 0m0.090s
Solution:
package main
import (
"big"
)
func main() {
result := big.NewInt(0)
power := big.NewInt(0)
var number *big.Int
for i := 1; i < 1001; i++ {
number = big.NewInt(int64(i))
power.Exp(number, number, nil)
result.Add(result, power)
}
str := result.String()
println(str[len(str)-10 : len(str)])
}
Result: 9110846700
Time: 0m0.090s
Problem #49
Problem link
Solution:
Result: 296962999629
Time: 0m0.420s
Solution:
package main
import (
"strings"
"strconv"
)
func main() {
arr := make([]bool, 10000)
prime := 2
finished := false
var i int
for !finished {
for i = 2 * prime; i < 10000; i += prime {
arr[i] = true
}
//next prime
for i = prime + 1; i < 10000 && arr[i]; i++ {
}
if i < 10000 {
prime = i
} else {
finished = true
}
}
outer:
for i := 1000; i < len(arr); i++ {
for j := i + 1; j < len(arr); j++ {
if i != 1487 && !arr[i] && !arr[j] && isPerm(i, j) && 2*j-i < 10000 && !arr[2*j-i] && isPerm(i, 2*j-i) {
print(i)
print(j)
print(2*j - i)
break outer
}
}
}
println()
}
func isPerm(i1, i2 int) bool {
s1, s2 := strconv.Itoa(i1), strconv.Itoa(i2)
for i := 0; i < len(s1); i++ {
//we need a cross check for repetition of numbers like in 1049 1499 comparison
if !strings.Contains(s1, s2[i:i+1]) || !strings.Contains(s2, s1[i:i+1]) {
return false
}
}
return true
}
Result: 296962999629
Time: 0m0.420s
Problem #50
Problem link
Solution:
Result: 997651
Time: 0m0.057s
Solution:
package main
var primes []int
func main() {
arr := make([]bool, 1000000)
arr[0], arr[1] = true, true
count := 2
prime := 3
var k int
finished := false
for !finished {
for k = 2 * prime; k < len(arr); k += prime {
arr[k] = true
}
for k = prime + 2; k < len(arr) && arr[k]; k += 2 {
}
if k < len(arr) {
prime = k
count++
} else {
finished = true
}
}
primes = make([]int, count)
index := 1
primes[0] = 2
for i := 0; i < len(arr); i++ {
if !arr[i] && i%2 != 0 {
primes[index] = i
index++
}
}
answer := 0
maxCount := 0
var tmp int
for i := range primes {
tmp = primes[i]
count = 0
inner2:
for j := i + 1; j < len(primes); j++ {
tmp += primes[j]
count++
if tmp > len(arr)-1 {
break inner2
}
if tmp%2 != 0 && !arr[tmp] && count > maxCount { //is prime and better result
maxCount = count
answer = tmp
}
}
}
println(answer)
}
Result: 997651
Time: 0m0.057s
Subscribe to:
Posts (Atom)