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 00:43, 17 March 2020
, 4 years ago→{{header|JavaScript}}
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 841:
+----+------------+------------+
</pre>
=={{header|Java}}==
{{trans|C#}}
<lang java>import java.math.BigInteger;
import java.time.Duration;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Program {
static final String ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz|";
static byte base, bmo, blim, ic;
static long st0;
static BigInteger bllim, threshold;
static Set<Byte> hs = new HashSet<>();
static Set<Byte> o = new HashSet<>();
static final char[] chars = ALPHABET.toCharArray();
static List<BigInteger> limits;
static String ms;
static int indexOf(char c) {
for (int i = 0; i < chars.length; ++i) {
if (chars[i] == c) {
return i;
}
}
return -1;
}
// convert BigInteger to string using current base
static String toStr(BigInteger b) {
BigInteger bigBase = BigInteger.valueOf(base);
StringBuilder res = new StringBuilder();
while (b.compareTo(BigInteger.ZERO) > 0) {
BigInteger[] divRem = b.divideAndRemainder(bigBase);
res.append(chars[divRem[1].intValue()]);
b = divRem[0];
}
return res.toString();
}
// check for a portion of digits, bailing if uneven
static boolean allInQS(BigInteger b) {
BigInteger bigBase = BigInteger.valueOf(base);
int c = ic;
hs.clear();
hs.addAll(o);
while (b.compareTo(bllim) > 0) {
BigInteger[] divRem = b.divideAndRemainder(bigBase);
hs.add(divRem[1].byteValue());
c++;
if (c > hs.size()) {
return false;
}
b = divRem[0];
}
return true;
}
// check for a portion of digits, all the way to the end
static boolean allInS(BigInteger b) {
BigInteger bigBase = BigInteger.valueOf(base);
hs.clear();
hs.addAll(o);
while (b.compareTo(bllim) > 0) {
BigInteger[] divRem = b.divideAndRemainder(bigBase);
hs.add(divRem[1].byteValue());
b = divRem[0];
}
return hs.size() == base;
}
// check for all digits, bailing if uneven
static boolean allInQ(BigInteger b) {
BigInteger bigBase = BigInteger.valueOf(base);
int c = 0;
hs.clear();
while (b.compareTo(BigInteger.ZERO) > 0) {
BigInteger[] divRem = b.divideAndRemainder(bigBase);
hs.add(divRem[1].byteValue());
c++;
if (c > hs.size()) {
return false;
}
b = divRem[0];
}
return true;
}
// check for all digits, all the way to the end
static boolean allIn(BigInteger b) {
BigInteger bigBase = BigInteger.valueOf(base);
hs.clear();
while (b.compareTo(BigInteger.ZERO) > 0) {
BigInteger[] divRem = b.divideAndRemainder(bigBase);
hs.add(divRem[1].byteValue());
b = divRem[0];
}
return hs.size() == base;
}
// parse a string into a BigInteger, using current base
static BigInteger to10(String s) {
BigInteger bigBase = BigInteger.valueOf(base);
BigInteger res = BigInteger.ZERO;
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
int idx = indexOf(c);
BigInteger bigIdx = BigInteger.valueOf(idx);
res = res.multiply(bigBase).add(bigIdx);
}
return res;
}
// returns the minimum value string, optionally inserting extra digit
static String fixup(int n) {
String res = ALPHABET.substring(0, base);
if (n > 0) {
StringBuilder sb = new 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
static void check(BigInteger sq) {
if (sq.compareTo(threshold) > 0) {
o.remove((byte) indexOf(ms.charAt(blim)));
blim--;
ic--;
threshold = limits.get(bmo - blim - 1);
bllim = to10(ms.substring(0, blim + 1));
}
}
// performs all the calculations for the current base
static void doOne() {
limits = new ArrayList<>();
bmo = (byte) (base - 1);
byte dr = 0;
if ((base & 1) == 1) {
dr = (byte) (base >> 1);
}
o.clear();
blim = 0;
byte id = 0;
int inc = 1;
long st = System.nanoTime();
byte[] sdr = new byte[bmo];
byte rc = 0;
for (int i = 0; i < bmo; i++) {
sdr[i] = (byte) ((i * i) % bmo);
rc += sdr[i] == dr ? (byte) 1 : (byte) 0;
sdr[i] += sdr[i] == 0 ? bmo : (byte) 0;
}
long i = 0;
if (dr > 0) {
id = base;
for (i = 1; i <= dr; i++) {
if (sdr[(int) i] >= dr) {
if (id > sdr[(int) i]) {
id = sdr[(int) i];
}
}
}
id -= dr;
i = 0;
}
ms = fixup(id);
BigInteger sq = to10(ms);
BigInteger rt = BigInteger.valueOf((long) (Math.sqrt(sq.doubleValue()) + 1));
sq = rt.multiply(rt);
if (base > 9) {
for (int j = 1; j < base; j++) {
limits.add(to10(ms.substring(0, j) + String.valueOf(chars[bmo]).repeat(base - j + (rc > 0 ? 0 : 1))));
}
Collections.reverse(limits);
while (sq.compareTo(limits.get(0)) < 0) {
rt = rt.add(BigInteger.ONE);
sq = rt.multiply(rt);
}
}
BigInteger dn = rt.shiftLeft(1).add(BigInteger.ONE);
BigInteger d = BigInteger.ONE;
if (base > 3 && rc > 0) {
while (sq.remainder(BigInteger.valueOf(bmo)).compareTo(BigInteger.valueOf(dr)) != 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)).subtract(BigInteger.ONE));
d = BigInteger.valueOf(inc * inc);
}
dn = dn.add(dn).add(d);
}
d = d.shiftLeft(1);
if (base > 9) {
blim = 0;
while (sq.compareTo(limits.get(bmo - blim - 1)) < 0) {
blim++;
}
ic = (byte) (blim + 1);
threshold = limits.get(bmo - blim - 1);
if (blim > 0) {
for (byte j = 0; j <= blim; j++) {
o.add((byte) indexOf(ms.charAt(j)));
}
}
if (blim > 0) {
bllim = to10(ms.substring(0, blim + 1));
} else {
bllim = 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));
long delta1 = System.nanoTime() - st;
Duration dur1 = Duration.ofNanos(delta1);
long delta2 = System.nanoTime() - st0;
Duration dur2 = Duration.ofNanos(delta2);
System.out.printf(
"%3d %2d %2s %20s -> %-40s %10d %9s %9s\n",
base, inc, (id > 0 ? ALPHABET.substring(id, id + 1) : " "), toStr(rt), toStr(sq), i, format(dur1), format(dur2)
);
}
private static String format(Duration d) {
int minP = d.toMinutesPart();
int secP = d.toSecondsPart();
int milP = d.toMillisPart();
return String.format("%02d:%02d.%03d", minP, secP, milP);
}
public static void main(String[] args) {
System.out.println("base inc id root square test count time total");
st0 = System.nanoTime();
for (base = 2; base < 28; ++base) {
doOne();
}
}
}</lang>
{{out}}
<pre>base inc id root square test count time total
2 1 01 -> 001 0 00:00.030 00:00.030
3 1 22 -> 1012 4 00:00.000 00:00.040
4 3 33 -> 1023 2 00:00.000 00:00.042
5 1 2 342 -> 403231 14 00:00.000 00:00.044
6 5 325 -> 310254 20 00:00.000 00:00.047
7 6 1341 -> 1630542 34 00:00.000 00:00.049
8 7 4433 -> 02457631 41 00:00.000 00:00.051
9 4 24611 -> 475208631 289 00:00.002 00:00.055
10 3 34023 -> 9483576201 17 00:00.023 00:00.080
11 10 354111 -> 987635A0421 1498 00:00.009 00:00.091
12 11 9B6693 -> 906835B7A421 6883 00:00.012 00:00.109
13 1 3 3498283 -> 9B68AC37745201 8242 00:00.053 00:00.164
14 13 C7BD9A3 -> 4A3D75C8B96201 1330 00:00.001 00:00.166
15 14 758B2101 -> 4D638ECAB795201 4216 00:00.008 00:00.175
16 15 B9D9A404 -> 9DB73AEFC8465201 18457 00:00.070 00:00.247
17 1 1 9AG28F324 -> DE753BFGC98A642101 195112 00:00.415 00:00.664
18 17 DAC284B44 -> 7HC9DA4GE8F5B63201 30440 00:00.015 00:00.680
19 6 A9E55B1101 -> 5E9A6F8IC7GBHD43201 93021 00:00.116 00:00.797
20 19 G3D5HIGD94 -> G8AJF596BH3IDC7E4201 11310604 00:06.544 00:07.342
21 1 6 F72EF5EH9C4 -> FAECK6B6J8IH9GD7543201 601843 00:01.123 00:08.467
22 21 F0JG88749F4 -> 5AKL7IHC84JEDGBF963201 27804949 00:16.134 00:24.602
23 22 CM65LE3D1101 -> 657LIJBF8MH9GKDECA43201 17710217 00:09.976 00:34.579
24 23 3DH0FGDH0JL4 -> 96ALDMGINJKCEFH78B543201 4266555 00:02.115 00:36.695
25 12 MHGHF541E1101 -> 9HN7MAIL8BFG6JKCEOD543201 78092124 00:47.584 01:24.280
26 5 K99MDB35N8K25 -> ABDJNHCPF97GKMEI6OL8543201 402922566 04:37.368 06:01.649
27 26 JJBO73E11F1101 -> A6N9QC7PKGFJIBHDMOLE8543201 457555291 05:19.215 11:20.866</pre>
=={{header|JavaScript}}==
| |||