Combinations with repetitions/Square digit chain: Difference between revisions
Combinations with repetitions/Square digit chain (view source)
Revision as of 12:57, 5 September 2018
, 5 years agoAdded Go
m (→{{header|Kotlin}}: Minor changes to wording of preamble.) |
(Added Go) |
||
Line 134:
//(k=17) In the range 1 to 99999999999999999
//12024696404768024 translate to 1 and 87975303595231975 translate to 89
</pre>
=={{header|Go}}==
{{trans|Kotlin}}
<lang go>package main
import (
"fmt"
"math"
)
func endsWithOne(n int) bool {
sum := 0
for {
for n > 0 {
digit := n % 10
sum += digit * digit
n /= 10
}
if sum == 1 {
return true
}
if sum == 89 {
return false
}
n = sum
sum = 0
}
}
func main() {
ks := [...]int{7, 8, 11, 14, 17}
for _, k := range ks {
sums := make([]int64, k*81+1)
sums[0] = 1
sums[1] = 0
for n := 1; n <= k; n++ {
for i := n * 81; i > 0; i-- {
for j := 1; j < 10; j++ {
s := j * j
if s > i {
break
}
sums[i] += sums[i-s]
}
}
}
count1 := int64(0)
for i := 1; i <= k*81; i++ {
if endsWithOne(i) {
count1 += sums[i]
}
}
limit := int64(math.Pow10(k)) - 1
fmt.Println("For k =", k, "in the range 1 to", limit)
fmt.Println(count1, "numbers produce 1 and", limit-count1, "numbers produce 89\n")
}
}</lang>
{{out}}
<pre>
For k = 7 in the range 1 to 9999999
1418853 numbers produce 1 and 8581146 numbers produce 89
For k = 8 in the range 1 to 99999999
14255666 numbers produce 1 and 85744333 numbers produce 89
For k = 11 in the range 1 to 99999999999
15091199356 numbers produce 1 and 84908800643 numbers produce 89
For k = 14 in the range 1 to 99999999999999
13770853279684 numbers produce 1 and 86229146720315 numbers produce 89
For k = 17 in the range 1 to 99999999999999999
12024696404768024 numbers produce 1 and 87975303595231975 numbers produce 89
</pre>
| |||