5

[Golang] Distinct powers - Problem 29 - Project Euler

 3 years ago
source link: http://siongui.github.io/2018/10/29/go-distinct-powers-problem-29-project-euler/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

[Golang] Distinct powers - Problem 29 - Project Euler

October 29, 2018

Problem: [1]

Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

Solution:

Use big-number arithmetic [2] for power operations and Go built-in map [3] to count distinct items. It may takes several minutes to run the following code.

29.go | repository | view raw 

package main

import (
	"fmt"
	"strconv"
)

const MaxDigits = 201
const BASE = 10

func MakePositiveInt(s string) (n [MaxDigits]int) {
	// make n zero
	for i := 0; i < MaxDigits; i++ {
		n[i] = 0
	}

	for index, digit := range s {
		i := len(s) - index - 1
		switch digit {
		case '0':
			n[i] = 0
		case '1':
			n[i] = 1
		case '2':
			n[i] = 2
		case '3':
			n[i] = 3
		case '4':
			n[i] = 4
		case '5':
			n[i] = 5
		case '6':
			n[i] = 6
		case '7':
			n[i] = 7
		case '8':
			n[i] = 8
		case '9':
			n[i] = 9
		default:
			panic("invalid digit in number string")
		}
	}

	return
}

func AddPositiveInt(a, b [MaxDigits]int) (c [MaxDigits]int) {
	var carry, sum = 0, 0

	// make c zero
	for i := 0; i < MaxDigits; i++ {
		c[i] = 0
	}

	for i := 0; i < MaxDigits; i++ {
		sum = a[i] + b[i] + carry

		if sum >= BASE {
			carry = 1
			sum -= BASE
		} else {
			carry = 0
		}

		c[i] = sum
	}

	if carry != 0 {
		panic("overflow in addition")
	}

	return
}

func MultiplyOneDigit(a [MaxDigits]int, n int) (b [MaxDigits]int) {
	var carry = 0

	// make b zero
	for i := 0; i < MaxDigits; i++ {
		b[i] = 0
	}

	for i := 0; i < MaxDigits; i++ {
		b[i] = n * a[i]

		b[i] += carry

		if b[i] >= BASE {
			carry = b[i] / BASE
			b[i] %= BASE
		} else {
			carry = 0
		}
	}

	if carry != 0 {
		panic("overflow in multiplication")
	}

	return
}

func ShiftLeft(a [MaxDigits]int, n int) [MaxDigits]int {
	var i int

	for i = MaxDigits - 1; i >= n; i-- {
		a[i] = a[i-n]
	}
	for i >= 0 {
		a[i] = 0
		i -= 1
	}

	return a
}

func MultiplyPositiveInt(a, b [MaxDigits]int) (c [MaxDigits]int) {
	// make c zero
	for i := 0; i < MaxDigits; i++ {
		c[i] = 0
	}

	for i := 0; i < MaxDigits; i++ {
		tmp := MultiplyOneDigit(b, a[i])
		tmp = ShiftLeft(tmp, i)
		c = AddPositiveInt(c, tmp)
	}

	return
}

// a^b, b is integer and b>=2
func Power(a [MaxDigits]int, b int) (c [MaxDigits]int) {
	c = MultiplyPositiveInt(a, a)
	for i := 2; i < b; i++ {
		c = MultiplyPositiveInt(c, a)
	}
	return
}

func PositiveIntToString(a [MaxDigits]int) (s string) {
	isLeadingZero := true
	for i := MaxDigits - 1; i >= 0; i-- {
		if isLeadingZero && a[i] == 0 {
			continue
		} else {
			isLeadingZero = false
			s += strconv.Itoa(a[i])
		}
	}
	return
}

func main() {
	distinctNum := make(map[string]bool)
	for i := 2; i <= 100; i++ {
		a := MakePositiveInt(strconv.Itoa(i))
		for b := 2; b <= 100; b++ {
			c := Power(a, b)
			distinctNum[PositiveIntToString(c)] = true
		}
	}

	fmt.Println(len(distinctNum))
}

Test on:

  • Ubuntu 18.04, Go 1.11.1

References:


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK