Rare numbers: Difference between revisions
→{{header|Julia}}
Langurmonkey (talk | contribs) |
|||
Line 2,706:
75 8,320,411,466,598,809,138 19: 00:12:48.590 00:15:14.316
</pre>
=={{header|Java}}==
{{trans|Kotlin}}
<lang java>import java.time.Duration;
import java.time.LocalDateTime;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
public class RareNumbers {
public interface Consumer5<A, B, C, D, E> {
void apply(A a, B b, C c, D d, E e);
}
public interface Consumer7<A, B, C, D, E, F, G> {
void apply(A a, B b, C c, D d, E e, F f, G g);
}
public interface Recursable5<A, B, C, D, E> {
void apply(A a, B b, C c, D d, E e, Recursable5<A, B, C, D, E> r);
}
public interface Recursable7<A, B, C, D, E, F, G> {
void apply(A a, B b, C c, D d, E e, F f, G g, Recursable7<A, B, C, D, E, F, G> r);
}
public static <A, B, C, D, E> Consumer5<A, B, C, D, E> recurse(Recursable5<A, B, C, D, E> r) {
return (a, b, c, d, e) -> r.apply(a, b, c, d, e, r);
}
public static <A, B, C, D, E, F, G> Consumer7<A, B, C, D, E, F, G> recurse(Recursable7<A, B, C, D, E, F, G> r) {
return (a, b, c, d, e, f, g) -> r.apply(a, b, c, d, e, f, g, r);
}
private static class Term {
long coeff;
byte ix1, ix2;
public Term(long coeff, byte ix1, byte ix2) {
this.coeff = coeff;
this.ix1 = ix1;
this.ix2 = ix2;
}
}
private static final int MAX_DIGITS = 16;
private static long toLong(List<Byte> digits, boolean reverse) {
long sum = 0;
if (reverse) {
for (int i = digits.size() - 1; i >= 0; --i) {
sum = sum * 10 + digits.get(i);
}
} else {
for (Byte digit : digits) {
sum = sum * 10 + digit;
}
}
return sum;
}
private static boolean isNotSquare(long n) {
long root = (long) Math.sqrt(n);
return root * root != n;
}
private static List<Byte> seq(byte from, byte to, byte step) {
List<Byte> res = new ArrayList<>();
for (byte i = from; i <= to; i += step) {
res.add(i);
}
return res;
}
private static String commatize(long n) {
String s = String.valueOf(n);
int le = s.length();
int i = le - 3;
while (i >= 1) {
s = s.substring(0, i) + "," + s.substring(i);
i -= 3;
}
return s;
}
public static void main(String[] args) {
final LocalDateTime startTime = LocalDateTime.now();
long pow = 1L;
System.out.println("Aggregate timings to process all numbers up to:");
// terms of (n-r) expression for number of digits from 2 to maxDigits
List<List<Term>> allTerms = new ArrayList<>();
for (int i = 0; i < MAX_DIGITS - 1; ++i) {
allTerms.add(new ArrayList<>());
}
for (int r = 2; r <= MAX_DIGITS; ++r) {
List<Term> terms = new ArrayList<>();
pow *= 10;
long pow1 = pow;
long pow2 = 1;
byte i1 = 0;
byte i2 = (byte) (r - 1);
while (i1 < i2) {
terms.add(new Term(pow1 - pow2, i1, i2));
pow1 /= 10;
pow2 *= 10;
i1++;
i2--;
}
allTerms.set(r - 2, terms);
}
// map of first minus last digits for 'n' to pairs giving this value
Map<Byte, List<List<Byte>>> fml = Map.of(
(byte) 0, List.of(List.of((byte) 2, (byte) 2), List.of((byte) 8, (byte) 8)),
(byte) 1, List.of(List.of((byte) 6, (byte) 5), List.of((byte) 8, (byte) 7)),
(byte) 4, List.of(List.of((byte) 4, (byte) 0)),
(byte) 6, List.of(List.of((byte) 6, (byte) 0), List.of((byte) 8, (byte) 2))
);
// map of other digit differences for 'n' to pairs giving this value
Map<Byte, List<List<Byte>>> dmd = new HashMap<>();
for (int i = 0; i < 100; ++i) {
List<Byte> a = List.of((byte) (i / 10), (byte) (i % 10));
int d = a.get(0) - a.get(1);
dmd.computeIfAbsent((byte) d, k -> new ArrayList<>()).add(a);
}
List<Byte> fl = List.of((byte) 0, (byte) 1, (byte) 4, (byte) 6);
List<Byte> dl = seq((byte) -9, (byte) 9, (byte) 1); // all differences
List<Byte> zl = List.of((byte) 0); // zero differences only
List<Byte> el = seq((byte) -8, (byte) 8, (byte) 2); // even differences only
List<Byte> ol = seq((byte) -9, (byte) 9, (byte) 2); // odd differences only
List<Byte> il = seq((byte) 0, (byte) 9, (byte) 1);
List<Long> rares = new ArrayList<>();
List<List<List<Byte>>> lists = new ArrayList<>();
for (int i = 0; i < 4; ++i) {
lists.add(new ArrayList<>());
}
for (int i = 0; i < fl.size(); ++i) {
List<List<Byte>> temp1 = new ArrayList<>();
List<Byte> temp2 = new ArrayList<>();
temp2.add(fl.get(i));
temp1.add(temp2);
lists.set(i, temp1);
}
final AtomicReference<List<Byte>> digits = new AtomicReference<>(new ArrayList<>());
AtomicInteger count = new AtomicInteger();
// Recursive closure to generate (n+r) candidates from (n-r) candidates
// and hence find Rare numbers with a given number of digits.
Consumer7<List<Byte>, List<Byte>, List<List<Byte>>, List<List<Byte>>, Long, Integer, Integer> fnpr = recurse((cand, di, dis, indicies, nmr, nd, level, func) -> {
if (level == dis.size()) {
digits.get().set(indicies.get(0).get(0), fml.get(cand.get(0)).get(di.get(0)).get(0));
digits.get().set(indicies.get(0).get(1), fml.get(cand.get(0)).get(di.get(0)).get(1));
int le = di.size();
if (nd % 2 == 1) {
le--;
digits.get().set(nd / 2, di.get(le));
}
for (int i = 1; i < le; ++i) {
digits.get().set(indicies.get(i).get(0), dmd.get(cand.get(i)).get(di.get(i)).get(0));
digits.get().set(indicies.get(i).get(1), dmd.get(cand.get(i)).get(di.get(i)).get(1));
}
long r = toLong(digits.get(), true);
long npr = nmr + 2 * r;
if (isNotSquare(npr)) {
return;
}
count.getAndIncrement();
System.out.printf(" R/N %2d:", count.get());
LocalDateTime checkPoint = LocalDateTime.now();
long elapsed = Duration.between(startTime, checkPoint).toMillis();
System.out.printf(" %9sms", elapsed);
long n = toLong(digits.get(), false);
System.out.printf(" (%s)\n", commatize(n));
rares.add(n);
} else {
for (Byte num : dis.get(level)) {
di.set(level, num);
func.apply(cand, di, dis, indicies, nmr, nd, level + 1, func);
}
}
});
// Recursive closure to generate (n-r) candidates with a given number of digits.
Consumer5<List<Byte>, List<List<Byte>>, List<List<Byte>>, Integer, Integer> fnmr = recurse((cand, list, indicies, nd, level, func) -> {
if (level == list.size()) {
long nmr = 0;
long nmr2 = 0;
List<Term> terms = allTerms.get(nd - 2);
for (int i = 0; i < terms.size(); ++i) {
Term t = terms.get(i);
if (cand.get(i) >= 0) {
nmr += t.coeff * cand.get(i);
} else {
nmr2 += t.coeff * -cand.get(i);
if (nmr >= nmr2) {
nmr -= nmr2;
nmr2 = 0;
} else {
nmr2 -= nmr;
nmr = 0;
}
}
}
if (nmr2 >= nmr) {
return;
}
nmr -= nmr2;
if (isNotSquare(nmr)) {
return;
}
List<List<Byte>> dis = new ArrayList<>();
dis.add(seq((byte) 0, (byte) (fml.get(cand.get(0)).size() - 1), (byte) 1));
for (int i = 1; i < cand.size(); ++i) {
dis.add(seq((byte) 0, (byte) (dmd.get(cand.get(i)).size() - 1), (byte) 1));
}
if (nd % 2 == 1) {
dis.add(il);
}
List<Byte> di = new ArrayList<>();
for (int i = 0; i < dis.size(); ++i) {
di.add((byte) 0);
}
fnpr.apply(cand, di, dis, indicies, nmr, nd, 0);
} else {
for (Byte num : list.get(level)) {
cand.set(level, num);
func.apply(cand, list, indicies, nd, level + 1, func);
}
}
});
for (int nd = 2; nd <= MAX_DIGITS; ++nd) {
digits.set(new ArrayList<>());
for (int i = 0; i < nd; ++i) {
digits.get().add((byte) 0);
}
if (nd == 4) {
lists.get(0).add(zl);
lists.get(1).add(ol);
lists.get(2).add(el);
lists.get(3).add(ol);
} else if (allTerms.get(nd - 2).size() > lists.get(0).size()) {
for (int i = 0; i < 4; ++i) {
lists.get(i).add(dl);
}
}
List<List<Byte>> indicies = new ArrayList<>();
for (Term t : allTerms.get(nd - 2)) {
indicies.add(List.of(t.ix1, t.ix2));
}
for (List<List<Byte>> list : lists) {
List<Byte> cand = new ArrayList<>();
for (int i = 0; i < list.size(); ++i) {
cand.add((byte) 0);
}
fnmr.apply(cand, list, indicies, nd, 0);
}
LocalDateTime checkPoint = LocalDateTime.now();
long elapsed = Duration.between(startTime, checkPoint).toMillis();
System.out.printf(" %2d digits: %9sms\n", nd, elapsed);
}
Collections.sort(rares);
System.out.printf("\nThe rare numbers with up to %d digits are:\n", MAX_DIGITS);
for (int i = 0; i < rares.size(); ++i) {
System.out.printf(" %2d: %25s\n", i + 1, commatize(rares.get(i)));
}
}
}</lang>
{{out}}
<pre>Aggregate timings to process all numbers up to:
R/N 1: 17ms (65)
2 digits: 19ms
3 digits: 20ms
4 digits: 21ms
5 digits: 21ms
R/N 2: 29ms (621,770)
6 digits: 55ms
7 digits: 57ms
8 digits: 72ms
R/N 3: 76ms (281,089,082)
9 digits: 85ms
R/N 4: 89ms (2,022,652,202)
R/N 5: 237ms (2,042,832,002)
10 digits: 451ms
11 digits: 503ms
R/N 6: 833ms (872,546,974,178)
R/N 7: 869ms (872,568,754,178)
R/N 8: 1324ms (868,591,084,757)
12 digits: 1582ms
R/N 9: 1888ms (6,979,302,951,885)
13 digits: 2299ms
R/N 10: 6199ms (20,313,693,904,202)
R/N 11: 6272ms (20,313,839,704,202)
R/N 12: 7831ms (20,331,657,922,202)
R/N 13: 8070ms (20,331,875,722,202)
R/N 14: 8708ms (20,333,875,702,202)
R/N 15: 19681ms (40,313,893,704,200)
R/N 16: 19823ms (40,351,893,720,200)
14 digits: 21712ms
R/N 17: 21758ms (200,142,385,731,002)
R/N 18: 21991ms (221,462,345,754,122)
R/N 19: 24990ms (816,984,566,129,618)
R/N 20: 26552ms (245,518,996,076,442)
R/N 21: 26774ms (204,238,494,066,002)
R/N 22: 26846ms (248,359,494,187,442)
R/N 23: 27158ms (244,062,891,224,042)
R/N 24: 32349ms (403,058,392,434,500)
R/N 25: 32576ms (441,054,594,034,340)
15 digits: 34465ms
R/N 26: 85843ms (2,133,786,945,766,212)
R/N 27: 105944ms (2,135,568,943,984,212)
R/N 28: 109027ms (8,191,154,686,620,818)
R/N 29: 111677ms (8,191,156,864,620,818)
R/N 30: 112849ms (2,135,764,587,964,212)
R/N 31: 114572ms (2,135,786,765,764,212)
R/N 32: 118622ms (8,191,376,864,400,818)
R/N 33: 132237ms (2,078,311,262,161,202)
R/N 34: 164708ms (8,052,956,026,592,517)
R/N 35: 169421ms (8,052,956,206,592,517)
R/N 36: 203280ms (8,650,327,689,541,457)
R/N 37: 205555ms (8,650,349,867,341,457)
R/N 38: 207237ms (6,157,577,986,646,405)
R/N 39: 246082ms (4,135,786,945,764,210)
R/N 40: 275691ms (6,889,765,708,183,410)
16 digits: 278088ms
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|Julia}}==
| |||