Combinations with repetitions/Square digit chain: Difference between revisions
Content added Content deleted
(Added Kotlin) |
|||
Line 134: | Line 134: | ||
//(k=17) In the range 1 to 99999999999999999 |
//(k=17) In the range 1 to 99999999999999999 |
||
//12024696404768024 translate to 1 and 87975303595231975 translate to 89 |
//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> |
</pre> |
||