69 lines
1.9 KiB
Plaintext
69 lines
1.9 KiB
Plaintext
// version 1.1.2
|
|
|
|
const val LIMIT = 1_000_000
|
|
|
|
val sb = StringBuilder()
|
|
|
|
fun selfRefSeq(s: String): String {
|
|
sb.setLength(0) // faster than using a local StringBuilder object
|
|
for (d in '9' downTo '0') {
|
|
if (d !in s) continue
|
|
val count = s.count { it == d }
|
|
sb.append("$count$d")
|
|
}
|
|
return sb.toString()
|
|
}
|
|
|
|
fun permute(input: List<Char>): List<List<Char>> {
|
|
if (input.size == 1) return listOf(input)
|
|
val perms = mutableListOf<List<Char>>()
|
|
val toInsert = input[0]
|
|
for (perm in permute(input.drop(1))) {
|
|
for (i in 0..perm.size) {
|
|
val newPerm = perm.toMutableList()
|
|
newPerm.add(i, toInsert)
|
|
perms.add(newPerm)
|
|
}
|
|
}
|
|
return perms
|
|
}
|
|
|
|
fun main(args: Array<String>) {
|
|
val sieve = IntArray(LIMIT) // all zero by default
|
|
val elements = mutableListOf<String>()
|
|
for (n in 1 until LIMIT) {
|
|
if (sieve[n] > 0) continue
|
|
elements.clear()
|
|
var next = n.toString()
|
|
elements.add(next)
|
|
while (true) {
|
|
next = selfRefSeq(next)
|
|
if (next in elements) {
|
|
val size = elements.size
|
|
sieve[n] = size
|
|
if (n > 9) {
|
|
val perms = permute(n.toString().toList()).distinct()
|
|
for (perm in perms) {
|
|
if (perm[0] == '0') continue
|
|
val k = perm.joinToString("").toInt()
|
|
sieve[k] = size
|
|
}
|
|
}
|
|
break
|
|
}
|
|
elements.add(next)
|
|
}
|
|
}
|
|
val maxIterations = sieve.max()!!
|
|
for (n in 1 until LIMIT) {
|
|
if (sieve[n] < maxIterations) continue
|
|
println("$n -> Iterations = $maxIterations")
|
|
var next = n.toString()
|
|
for (i in 1..maxIterations) {
|
|
println(next)
|
|
next = selfRefSeq(next)
|
|
}
|
|
println()
|
|
}
|
|
}
|