First perfect square in base n with n unique digits: Difference between revisions
Content added Content deleted
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: | Line 1,352: | ||
16 404a9d9b 1025648cfea37bd9 |
16 404a9d9b 1025648cfea37bd9 |
||
</pre> |
</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}}== |
=={{header|Pascal}}== |