# [Golang] Distinct powers - Problem 29 - Project Euler

**Problem**: [1]

Consider all integer combinations of *a*^{b} for 2 ≤ *a* ≤ 5 and 2 ≤ *b* ≤ 5:

2^{2}=4, 2^{3}=8, 2^{4}=16, 2^{5}=32

3^{2}=9, 3^{3}=27, 3^{4}=81, 3^{5}=243

4^{2}=16, 4^{3}=64, 4^{4}=256, 4^{5}=1024

5^{2}=25, 5^{3}=125, 5^{4}=625, 5^{5}=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 *a*^{b} for 2 ≤ *a* ≤ 100 and 2 ≤ *b* ≤ 100?

**Solution**:

9183

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 | 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:

[1] | Distinct powers - Problem 29 - Project Euler |

[2] | [Golang] Large Positive Integer Multiplication |

[3] | Go maps in action - The Go Blog |