273 lines
8.7 KiB
Java
273 lines
8.7 KiB
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();
|
|
}
|
|
}
|
|
}
|