Rare numbers: Difference between revisions
→{{header|Phix}}
Line 1,866:
75: 8,320,411,466,598,809,138
</pre>
=={{header|Kotlin}}==
{{trans|D}}
<lang scala>import java.time.Duration
import java.time.LocalDateTime
import kotlin.math.sqrt
class Term(var coeff: Long, var ix1: Byte, var ix2: Byte)
const val maxDigits = 16
fun toLong(digits: List<Byte>, reverse: Boolean): Long {
var sum: Long = 0
if (reverse) {
var i = digits.size - 1
while (i >= 0) {
sum = sum * 10 + digits[i]
i--
}
} else {
var i = 0
while (i < digits.size) {
sum = sum * 10 + digits[i]
i++
}
}
return sum
}
fun isSquare(n: Long): Boolean {
val root = sqrt(n.toDouble()).toLong()
return root * root == n
}
fun seq(from: Byte, to: Byte, step: Byte): List<Byte> {
val res = mutableListOf<Byte>()
var i = from
while (i <= to) {
res.add(i)
i = (i + step).toByte()
}
return res
}
fun commatize(n: Long): String {
var s = n.toString()
val le = s.length
var i = le - 3
while (i >= 1) {
s = s.slice(0 until i) + "," + s.substring(i)
i -= 3
}
return s
}
fun main() {
val startTime = LocalDateTime.now()
var pow = 1L
println("Aggregate timings to process all numbers up to:")
// terms of (n-r) expression for number of digits from 2 to maxDigits
val allTerms = mutableListOf<MutableList<Term>>()
for (i in 0 until maxDigits - 1) {
allTerms.add(mutableListOf())
}
for (r in 2..maxDigits) {
val terms = mutableListOf<Term>()
pow *= 10
var pow1 = pow
var pow2 = 1L
var i1: Byte = 0
var i2 = (r - 1).toByte()
while (i1 < i2) {
terms.add(Term(pow1 - pow2, i1, i2))
pow1 /= 10
pow2 *= 10
i1++
i2--
}
allTerms[r - 2] = terms
}
// map of first minus last digits for 'n' to pairs giving this value
val fml = mapOf(
0.toByte() to listOf(listOf<Byte>(2, 2), listOf<Byte>(8, 8)),
1.toByte() to listOf(listOf<Byte>(6, 5), listOf<Byte>(8, 7)),
4.toByte() to listOf(listOf<Byte>(4, 0)),
6.toByte() to listOf(listOf<Byte>(6, 0), listOf<Byte>(8, 2))
)
// map of other digit differences for 'n' to pairs giving this value
val dmd = mutableMapOf<Byte, MutableList<List<Byte>>>()
for (i in 0 until 100) {
val a = listOf((i / 10).toByte(), (i % 10).toByte())
val d = a[0] - a[1]
dmd.getOrPut(d.toByte(), { mutableListOf() }).add(a)
}
val fl = listOf<Byte>(0, 1, 4, 6)
val dl = seq(-9, 9, 1) // all differences
val zl = listOf<Byte>(0) // zero differences only
val el = seq(-8, 8, 2) // even differences only
val ol = seq(-9, 9, 2) // odd differences only
val il = seq(0, 9, 1)
val rares = mutableListOf<Long>()
val lists = mutableListOf<MutableList<List<Byte>>>()
for (i in 0 until 4) {
lists.add(mutableListOf())
}
for (i_f in fl.withIndex()) {
lists[i_f.index] = mutableListOf(listOf(i_f.value))
}
var digits = mutableListOf<Byte>()
var count = 0
// Recursive closure to generate (n+r) candidates from (n-r) candidates
// and hence find Rare numbers with a given number of digits.
fun fnpr(
cand: List<Byte>,
di: MutableList<Byte>,
dis: List<List<Byte>>,
indicies: List<List<Byte>>,
nmr: Long,
nd: Int,
level: Int
) {
if (level == dis.size) {
digits[indicies[0][0].toInt()] = fml[cand[0]]?.get(di[0].toInt())?.get(0)!!
digits[indicies[0][1].toInt()] = fml[cand[0]]?.get(di[0].toInt())?.get(1)!!
var le = di.size
if (nd % 2 == 1) {
le--
digits[nd / 2] = di[le]
}
for (i_d in di.slice(1 until le).withIndex()) {
digits[indicies[i_d.index + 1][0].toInt()] = dmd[cand[i_d.index + 1]]?.get(i_d.value.toInt())?.get(0)!!
digits[indicies[i_d.index + 1][1].toInt()] = dmd[cand[i_d.index + 1]]?.get(i_d.value.toInt())?.get(1)!!
}
val r = toLong(digits, true)
val npr = nmr + 2 * r
if (!isSquare(npr)) {
return
}
count++
print(" R/N %2d:".format(count))
val checkPoint = LocalDateTime.now()
val elapsed = Duration.between(startTime, checkPoint).toMillis()
print(" %9sms".format(elapsed))
val n = toLong(digits, false)
println(" (${commatize(n)})")
rares.add(n)
} else {
for (num in dis[level]) {
di[level] = num
fnpr(cand, di, dis, indicies, nmr, nd, level + 1)
}
}
}
// Recursive closure to generate (n-r) candidates with a given number of digits.
fun fnmr(cand: MutableList<Byte>, list: List<List<Byte>>, indicies: List<List<Byte>>, nd: Int, level: Int) {
if (level == list.size) {
var nmr = 0L
var nmr2 = 0L
for (i_t in allTerms[nd - 2].withIndex()) {
if (cand[i_t.index] >= 0) {
nmr += i_t.value.coeff * cand[i_t.index]
} else {
nmr2 += i_t.value.coeff * -cand[i_t.index]
if (nmr >= nmr2) {
nmr -= nmr2
nmr2 = 0
} else {
nmr2 -= nmr
nmr = 0
}
}
}
if (nmr2 >= nmr) {
return
}
nmr -= nmr2
if (!isSquare(nmr)) {
return
}
val dis = mutableListOf<List<Byte>>()
dis.add(seq(0, ((fml[cand[0]] ?: error("oops")).size - 1).toByte(), 1))
for (i in 1 until cand.size) {
dis.add(seq(0, (dmd[cand[i]]!!.size - 1).toByte(), 1))
}
if (nd % 2 == 1) {
dis.add(il)
}
val di = mutableListOf<Byte>()
for (i in 0 until dis.size) {
di.add(0)
}
fnpr(cand, di, dis, indicies, nmr, nd, 0)
} else {
for (num in list[level]) {
cand[level] = num
fnmr(cand, list, indicies, nd, level + 1)
}
}
}
for (nd in 2..maxDigits) {
digits = mutableListOf()
for (i in 0 until nd) {
digits.add(0)
}
if (nd == 4) {
lists[0].add(zl)
lists[1].add(ol)
lists[2].add(el)
lists[3].add(ol)
} else if (allTerms[nd - 2].size > lists[0].size) {
for (i in 0 until 4) {
lists[i].add(dl)
}
}
val indicies = mutableListOf<List<Byte>>()
for (t in allTerms[nd - 2]) {
indicies.add(listOf(t.ix1, t.ix2))
}
for (list in lists) {
val cand = mutableListOf<Byte>()
for (i in 0 until list.size) {
cand.add(0)
}
fnmr(cand, list, indicies, nd, 0)
}
val checkPoint = LocalDateTime.now()
val elapsed = Duration.between(startTime, checkPoint).toMillis()
println(" %2d digits: %9sms".format(nd, elapsed))
}
rares.sort()
println("\nThe rare numbers with up to $maxDigits digits are:")
for (i_rare in rares.withIndex()) {
println(" %2d: %25s".format(i_rare.index + 1, commatize(i_rare.value)))
}
}</lang>
{{out}}
<pre>Aggregate timings to process all numbers up to:
R/N 1: 130ms (65)
2 digits: 133ms
3 digits: 133ms
4 digits: 135ms
5 digits: 136ms
R/N 2: 155ms (621,770)
6 digits: 171ms
7 digits: 176ms
8 digits: 238ms
R/N 3: 243ms (281,089,082)
9 digits: 266ms
R/N 4: 272ms (2,022,652,202)
R/N 5: 432ms (2,042,832,002)
10 digits: 693ms
11 digits: 1037ms
R/N 6: 1690ms (872,546,974,178)
R/N 7: 1757ms (872,568,754,178)
R/N 8: 2380ms (868,591,084,757)
12 digits: 2682ms
R/N 9: 3081ms (6,979,302,951,885)
13 digits: 3612ms
R/N 10: 9091ms (20,313,693,904,202)
R/N 11: 9180ms (20,313,839,704,202)
R/N 12: 11322ms (20,331,657,922,202)
R/N 13: 11611ms (20,331,875,722,202)
R/N 14: 12477ms (20,333,875,702,202)
R/N 15: 26933ms (40,313,893,704,200)
R/N 16: 27128ms (40,351,893,720,200)
14 digits: 29696ms
R/N 17: 29759ms (200,142,385,731,002)
R/N 18: 30024ms (221,462,345,754,122)
R/N 19: 33577ms (816,984,566,129,618)
R/N 20: 35392ms (245,518,996,076,442)
R/N 21: 35662ms (204,238,494,066,002)
R/N 22: 35748ms (248,359,494,187,442)
R/N 23: 36108ms (244,062,891,224,042)
R/N 24: 42484ms (403,058,392,434,500)
R/N 25: 42760ms (441,054,594,034,340)
15 digits: 45334ms
R/N 26: 106307ms (2,133,786,945,766,212)
R/N 27: 130390ms (2,135,568,943,984,212)
R/N 28: 134315ms (8,191,154,686,620,818)
R/N 29: 137815ms (8,191,156,864,620,818)
R/N 30: 139449ms (2,135,764,587,964,212)
R/N 31: 141563ms (2,135,786,765,764,212)
R/N 32: 146705ms (8,191,376,864,400,818)
R/N 33: 163353ms (2,078,311,262,161,202)
R/N 34: 204546ms (8,052,956,026,592,517)
R/N 35: 209994ms (8,052,956,206,592,517)
R/N 36: 251686ms (8,650,327,689,541,457)
R/N 37: 254537ms (8,650,349,867,341,457)
R/N 38: 256579ms (6,157,577,986,646,405)
R/N 39: 307145ms (4,135,786,945,764,210)
R/N 40: 347119ms (6,889,765,708,183,410)
16 digits: 350388ms
The rare numbers with up to 16 digits are:
1: 65
2: 621,770
3: 281,089,082
4: 2,022,652,202
5: 2,042,832,002
6: 868,591,084,757
7: 872,546,974,178
8: 872,568,754,178
9: 6,979,302,951,885
10: 20,313,693,904,202
11: 20,313,839,704,202
12: 20,331,657,922,202
13: 20,331,875,722,202
14: 20,333,875,702,202
15: 40,313,893,704,200
16: 40,351,893,720,200
17: 200,142,385,731,002
18: 204,238,494,066,002
19: 221,462,345,754,122
20: 244,062,891,224,042
21: 245,518,996,076,442
22: 248,359,494,187,442
23: 403,058,392,434,500
24: 441,054,594,034,340
25: 816,984,566,129,618
26: 2,078,311,262,161,202
27: 2,133,786,945,766,212
28: 2,135,568,943,984,212
29: 2,135,764,587,964,212
30: 2,135,786,765,764,212
31: 4,135,786,945,764,210
32: 6,157,577,986,646,405
33: 6,889,765,708,183,410
34: 8,052,956,026,592,517
35: 8,052,956,206,592,517
36: 8,191,154,686,620,818
37: 8,191,156,864,620,818
38: 8,191,376,864,400,818
39: 8,650,327,689,541,457
40: 8,650,349,867,341,457</pre>
=={{header|Phix}}==
| |||