Rare numbers: Difference between revisions
Content deleted Content added
Langurmonkey (talk | contribs) |
|||
Line 2,706: | Line 2,706: | ||
75 8,320,411,466,598,809,138 19: 00:12:48.590 00:15:14.316 |
75 8,320,411,466,598,809,138 19: 00:12:48.590 00:15:14.316 |
||
</pre> |
</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}}== |
=={{header|Julia}}== |