Combinations with repetitions/Square digit chain: Difference between revisions
Combinations with repetitions/Square digit chain (view source)
Revision as of 15:10, 11 October 2017
, 6 years agoAdded Kotlin
(Added Kotlin) |
|||
Line 134:
//(k=17) In the range 1 to 99999999999999999
//12024696404768024 translate to 1 and 87975303595231975 translate to 89
</pre>
=={{header|Kotlin}}==
To achieve reasonable performance, the Kotlin entry for the [[Iterated digits squaring]] task used a similar approach to that required by this task for k = 8.
So the following generalizes that code to deal with values of k up to 17 (which requires 64 bit integers) and to identify numbers where the squared digits sum sequence eventually ends in 1 rather than 89, albeit the sum of both must of course be 10 ^ k - 1.
<lang scala>// version 1.1.51
fun endsWithOne(n: Int): Boolean {
var digit: Int
var sum = 0
var nn = n
while (true) {
while (nn > 0) {
digit = nn % 10
sum += digit * digit
nn /= 10
}
if (sum == 1) return true
if (sum == 89) return false
nn = sum
sum = 0
}
}
fun main(args: Array<String>) {
val ks = intArrayOf(7, 8, 11, 14, 17)
for (k in ks) {
val sums = LongArray(k * 81 + 1)
sums[0] = 1
sums[1] = 0
var s: Int
for (n in 1 .. k) {
for (i in n * 81 downTo 1) {
for (j in 1 .. 9) {
s = j * j
if (s > i) break
sums[i] += sums[i - s]
}
}
}
var count1 = 0L
for (i in 1 .. k * 81) if (endsWithOne(i)) count1 += sums[i]
val limit = Math.pow(10.0, k.toDouble()).toLong() - 1
println("For k = $k in the range 1 to $limit")
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>
| |||