First perfect square in base n with n unique digits: Difference between revisions
First perfect square in base n with n unique digits (view source)
Revision as of 01:14, 18 April 2020
, 4 years ago→{{header|Pascal}}
m (→Inserted nearly all optimizations found by Hout and Nigel Galloway: correct output for base = 2. Set end; in the right row .) |
|||
Line 1,352:
16 404a9d9b 1025648cfea37bd9
</pre>
=={{header|Koltin}}==
{{trans|Java}}
<lang scala>import java.math.BigInteger
import java.time.Duration
import java.util.ArrayList
import java.util.HashSet
import kotlin.math.sqrt
const val ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz|"
var base: Byte = 0
var bmo: Byte = 0
var blim: Byte = 0
var ic: Byte = 0
var st0: Long = 0
var bllim: BigInteger? = null
var threshold: BigInteger? = null
var hs: MutableSet<Byte> = HashSet()
var o: MutableSet<Byte> = HashSet()
val chars = ALPHABET.toCharArray()
var limits: MutableList<BigInteger?>? = null
var ms: String? = null
fun indexOf(c: Char): Int {
for (i in chars.indices) {
if (chars[i] == c) {
return i
}
}
return -1
}
// convert BigInteger to string using current base
fun toStr(b: BigInteger): String {
var b2 = b
val bigBase = BigInteger.valueOf(base.toLong())
val res = StringBuilder()
while (b2 > BigInteger.ZERO) {
val divRem = b2.divideAndRemainder(bigBase)
res.append(chars[divRem[1].toInt()])
b2 = divRem[0]
}
return res.toString()
}
// check for a portion of digits, bailing if uneven
fun allInQS(b: BigInteger): Boolean {
var b2 = b
val bigBase = BigInteger.valueOf(base.toLong())
var c = ic.toInt()
hs.clear()
hs.addAll(o)
while (b2 > bllim) {
val divRem = b2.divideAndRemainder(bigBase)
hs.add(divRem[1].toByte())
c++
if (c > hs.size) {
return false
}
b2 = divRem[0]
}
return true
}
// check for a portion of digits, all the way to the end
fun allInS(b: BigInteger): Boolean {
var b2 = b
val bigBase = BigInteger.valueOf(base.toLong())
hs.clear()
hs.addAll(o)
while (b2 > bllim) {
val divRem = b2.divideAndRemainder(bigBase)
hs.add(divRem[1].toByte())
b2 = divRem[0]
}
return hs.size == base.toInt()
}
// check for all digits, bailing if uneven
fun allInQ(b: BigInteger): Boolean {
var b2 = b
val bigBase = BigInteger.valueOf(base.toLong())
var c = 0
hs.clear()
while (b2 > BigInteger.ZERO) {
val divRem = b2.divideAndRemainder(bigBase)
hs.add(divRem[1].toByte())
c++
if (c > hs.size) {
return false
}
b2 = divRem[0]
}
return true
}
// check for all digits, all the way to the end
fun allIn(b: BigInteger): Boolean {
var b2 = b
val bigBase = BigInteger.valueOf(base.toLong())
hs.clear()
while (b2 > BigInteger.ZERO) {
val divRem = b2.divideAndRemainder(bigBase)
hs.add(divRem[1].toByte())
b2 = divRem[0]
}
return hs.size == base.toInt()
}
// parse a string into a BigInteger, using current base
fun to10(s: String?): BigInteger {
val bigBase = BigInteger.valueOf(base.toLong())
var res = BigInteger.ZERO
for (element in s!!) {
val idx = indexOf(element)
val bigIdx = BigInteger.valueOf(idx.toLong())
res = res.multiply(bigBase).add(bigIdx)
}
return res
}
// returns the minimum value string, optionally inserting extra digit
fun fixup(n: Int): String {
var res = ALPHABET.substring(0, base.toInt())
if (n > 0) {
val sb = StringBuilder(res)
sb.insert(n, n)
res = sb.toString()
}
return "10" + res.substring(2)
}
// checks the square against the threshold, advances various limits when needed
fun check(sq: BigInteger) {
if (sq > threshold) {
o.remove(indexOf(ms!![blim.toInt()]).toByte())
blim--
ic--
threshold = limits!![bmo - blim - 1]
bllim = to10(ms!!.substring(0, blim + 1))
}
}
// performs all the calculations for the current base
fun doOne() {
limits = ArrayList()
bmo = (base - 1).toByte()
var dr: Byte = 0
if ((base.toInt() and 1) == 1) {
dr = (base.toInt() shr 1).toByte()
}
o.clear()
blim = 0
var id: Byte = 0
var inc = 1
val st = System.nanoTime()
val sdr = ByteArray(bmo.toInt())
var rc: Byte = 0
for (i in 0 until bmo) {
sdr[i] = (i * i % bmo).toByte()
if (sdr[i] == dr) {
rc = (rc + 1).toByte()
}
if (sdr[i] == 0.toByte()) {
sdr[i] = (sdr[i] + bmo).toByte()
}
}
var i: Long = 0
if (dr > 0) {
id = base
i = 1
while (i <= dr) {
if (sdr[i.toInt()] >= dr) {
if (id > sdr[i.toInt()]) {
id = sdr[i.toInt()]
}
}
i++
}
id = (id - dr).toByte()
i = 0
}
ms = fixup(id.toInt())
var sq = to10(ms)
var rt = BigInteger.valueOf((sqrt(sq.toDouble()) + 1).toLong())
sq = rt.multiply(rt)
if (base > 9) {
for (j in 1 until base) {
limits!!.add(to10(ms!!.substring(0, j) + chars[bmo.toInt()].toString().repeat(base - j + if (rc > 0) 0 else 1)))
}
limits!!.reverse()
while (sq < limits!![0]) {
rt = rt.add(BigInteger.ONE)
sq = rt.multiply(rt)
}
}
var dn = rt.shiftLeft(1).add(BigInteger.ONE)
var d = BigInteger.ONE
if (base > 3 && rc > 0) {
while (sq.remainder(BigInteger.valueOf(bmo.toLong())).compareTo(BigInteger.valueOf(dr.toLong())) != 0) {
rt = rt.add(BigInteger.ONE)
sq = sq.add(dn)
dn = dn.add(BigInteger.TWO)
} // aligns sq to dr
inc = bmo / rc
if (inc > 1) {
dn = dn.add(rt.multiply(BigInteger.valueOf(inc - 2.toLong())).subtract(BigInteger.ONE))
d = BigInteger.valueOf(inc * inc.toLong())
}
dn = dn.add(dn).add(d)
}
d = d.shiftLeft(1)
if (base > 9) {
blim = 0
while (sq < limits!![bmo - blim - 1]) {
blim++
}
ic = (blim + 1).toByte()
threshold = limits!![bmo - blim - 1]
if (blim > 0) {
for (j in 0..blim) {
o.add(indexOf(ms!![j]).toByte())
}
}
bllim = if (blim > 0) {
to10(ms!!.substring(0, blim + 1))
} else {
BigInteger.ZERO
}
if (base > 5 && rc > 0) while (!allInQS(sq)) {
sq = sq.add(dn)
dn = dn.add(d)
i += 1
check(sq)
} else {
while (!allInS(sq)) {
sq = sq.add(dn)
dn = dn.add(d)
i += 1
check(sq)
}
}
} else {
if (base > 5 && rc > 0) {
while (!allInQ(sq)) {
sq = sq.add(dn)
dn = dn.add(d)
i += 1
}
} else {
while (!allIn(sq)) {
sq = sq.add(dn)
dn = dn.add(d)
i += 1
}
}
}
rt = rt.add(BigInteger.valueOf(i * inc))
val delta1 = System.nanoTime() - st
val dur1 = Duration.ofNanos(delta1)
val delta2 = System.nanoTime() - st0
val dur2 = Duration.ofNanos(delta2)
System.out.printf(
"%3d %2d %2s %20s -> %-40s %10d %9s %9s\n",
base, inc, if (id > 0) ALPHABET.substring(id.toInt(), id + 1) else " ", toStr(rt), toStr(sq), i, format(dur1), format(dur2)
)
}
private fun format(d: Duration): String {
val minP = d.toMinutesPart()
val secP = d.toSecondsPart()
val milP = d.toMillisPart()
return String.format("%02d:%02d.%03d", minP, secP, milP)
}
fun main() {
println("base inc id root square test count time total")
st0 = System.nanoTime()
base = 2
while (base < 28) {
doOne()
++base
}
}</lang>
{{out}}
<pre>base inc id root square test count time total
2 1 01 -> 001 0 00:00.001 00:00.002
3 1 22 -> 1012 4 00:00.000 00:00.016
4 3 33 -> 1023 2 00:00.000 00:00.018
5 1 2 342 -> 403231 14 00:00.000 00:00.021
6 5 325 -> 310254 20 00:00.000 00:00.023
7 6 1341 -> 1630542 34 00:00.000 00:00.026
8 7 4433 -> 02457631 41 00:00.000 00:00.028
9 4 24611 -> 475208631 289 00:00.002 00:00.032
10 3 34023 -> 9483576201 17 00:00.017 00:00.050
11 10 354111 -> 987635A0421 1498 00:00.011 00:00.063
12 11 9B6693 -> 906835B7A421 6883 00:00.016 00:00.083
13 1 3 3498283 -> 9B68AC37745201 8242 00:00.031 00:00.116
14 13 C7BD9A3 -> 4A3D75C8B96201 1330 00:00.002 00:00.120
15 14 758B2101 -> 4D638ECAB795201 4216 00:00.016 00:00.138
16 15 B9D9A404 -> 9DB73AEFC8465201 18457 00:00.087 00:00.226
17 1 1 9AG28F324 -> DE753BFGC98A642101 195112 00:00.435 00:00.664
18 17 DAC284B44 -> 7HC9DA4GE8F5B63201 30440 00:00.018 00:00.683
19 6 A9E55B1101 -> 5E9A6F8IC7GBHD43201 93021 00:00.061 00:00.745
20 19 G3D5HIGD94 -> G8AJF596BH3IDC7E4201 11310604 00:06.859 00:07.605
21 1 6 F72EF5EH9C4 -> FAECK6B6J8IH9GD7543201 601843 00:01.223 00:08.830
22 21 F0JG88749F4 -> 5AKL7IHC84JEDGBF963201 27804949 00:18.191 00:27.023
23 22 CM65LE3D1101 -> 657LIJBF8MH9GKDECA43201 17710217 00:11.143 00:38.167
24 23 3DH0FGDH0JL4 -> 96ALDMGINJKCEFH78B543201 4266555 00:02.381 00:40.549
25 12 MHGHF541E1101 -> 9HN7MAIL8BFG6JKCEOD543201 78092124 00:53.150 01:33.701
26 5 K99MDB35N8K25 -> ABDJNHCPF97GKMEI6OL8543201 402922566 05:15.307 06:49.008
27 26 JJBO73E11F1101 -> A6N9QC7PKGFJIBHDMOLE8543201 457555291 06:01.338 12:50.347</pre>
=={{header|Pascal}}==
| |||