Rare numbers: Difference between revisions
Content deleted Content added
m →10 to 19 digits: 3x aka 300% not 3000%, come on ;-) Enjoy celebrations/holi-days |
|||
Line 718:
74: 8,200,756,128,308,135,597
75: 8,320,411,466,598,809,138</pre>
=={{header|D}}==
{{trans|Go}}
Scaled down from the full duration showed in the go example because I got impatient and have not spent time figuring out where the inefficeny is.
<lang d>import std.algorithm;
import std.array;
import std.conv;
import std.datetime.stopwatch;
import std.math;
import std.stdio;
struct Term {
ulong coeff;
byte ix1, ix2;
}
enum maxDigits = 16;
ulong toUlong(byte[] digits, bool reverse) {
ulong sum = 0;
if (reverse) {
for (int i = digits.length - 1; i >= 0; --i) {
sum = sum * 10 + digits[i];
}
} else {
for (size_t i = 0; i < digits.length; ++i) {
sum = sum * 10 + digits[i];
}
}
return sum;
}
bool isSquare(ulong n) {
if ((0x202021202030213 & (1 << (n & 63))) != 0) {
auto root = cast(ulong)sqrt(cast(double)n);
return root * root == n;
}
return false;
}
byte[] seq(byte from, byte to, byte step) {
byte[] res;
for (auto i = from; i <= to; i += step) {
res ~= i;
}
return res;
}
string commatize(ulong n) {
auto s = n.to!string;
auto le = s.length;
for (int i = le - 3; i >= 1; i -= 3) {
s = s[0..i] ~ "," ~ s[i..$];
}
return s;
}
void main() {
auto sw = StopWatch(AutoStart.yes);
ulong pow = 1;
writeln("Aggregate timings to process all numbers up to:");
// terms of (n-r) expression for number of digits from 2 to maxDigits
Term[][] allTerms = uninitializedArray!(Term[][])(maxDigits - 1);
for (auto r = 2; r <= maxDigits; r++) {
Term[] terms;
pow *= 10;
ulong pow1 = pow;
ulong pow2 = 1;
byte i1 = 0;
byte i2 = cast(byte)(r - 1);
while (i1 < i2) {
terms ~= Term(pow1 - pow2, i1, i2);
pow1 /= 10;
pow2 *= 10;
i1++;
i2--;
}
allTerms[r - 2] = terms;
}
// map of first minus last digits for 'n' to pairs giving this value
byte[][][byte] fml = [
0: [[2, 2], [8, 8]],
1: [[6, 5], [8, 7]],
4: [[4, 0]],
6: [[6, 0], [8, 2]]
];
// map of other digit differences for 'n' to pairs giving this value
byte[][][byte] dmd;
for (byte i = 0; i < 100; i++) {
byte[] a = [i / 10, i % 10];
auto d = a[0] - a[1];
dmd[cast(byte)d] ~= a;
}
byte[] fl = [0, 1, 4, 6];
auto dl = seq(-9, 9, 1); // all differences
byte[] zl = [0]; // zero diferences only
auto el = seq(-8, 8, 2); // even differences only
auto ol = seq(-9, 9, 2); // odd differences only
auto il = seq(0, 9, 1);
ulong[] rares;
byte[][][] lists = uninitializedArray!(byte[][][])(4);
foreach (i, f; fl) {
lists[i] = [[f]];
}
byte[] digits;
int count = 0;
// Recursive closure to generate (n+r) candidates from (n-r) candidates
// and hence find Rare numbers with a given number of digits.
void fnpr(byte[] cand, byte[] di, byte[][] dis, byte[][] indicies, ulong nmr, int nd, int level) {
if (level == dis.length) {
digits[indicies[0][0]] = fml[cand[0]][di[0]][0];
digits[indicies[0][1]] = fml[cand[0]][di[0]][1];
auto le = di.length;
if (nd % 2 == 1) {
le--;
digits[nd / 2] = di[le];
}
foreach (i, d; di[1..le]) {
digits[indicies[i + 1][0]] = dmd[cand[i + 1]][d][0];
digits[indicies[i + 1][1]] = dmd[cand[i + 1]][d][1];
}
auto r = toUlong(digits, true);
auto npr = nmr + 2 * r;
if (!isSquare(npr)) {
return;
}
count++;
writef(" R/N %2d:", count);
auto ms = sw.peek();
writef(" %9s", ms);
auto n = toUlong(digits, false);
writef(" (%s)\n", commatize(n));
rares ~= n;
} else {
foreach (num; dis[level]) {
di[level] = num;
fnpr(cand, di, dis, indicies, nmr, nd, level + 1);
}
}
}
// Recursive closure to generate (n-r) candidates with a given number of digits.
void fnmr(byte[] cand, byte[][] list, byte[][] indicies, int nd, int level) {
if (level == list.length) {
ulong nmr, nmr2;
foreach (i, t; allTerms[nd - 2]) {
if (cand[i] >= 0) {
nmr += t.coeff * cand[i];
} else {
nmr2 += t.coeff * -cast(int)(cand[i]);
if (nmr >= nmr2) {
nmr -= nmr2;
nmr2 = 0;
} else {
nmr2 -= nmr;
nmr = 0;
}
}
}
if (nmr2 >= nmr) {
return;
}
nmr -= nmr2;
if (!isSquare(nmr)) {
return;
}
byte[][] dis;
dis ~= seq(0, cast(byte)(fml[cand[0]].length - 1), 1);
for (auto i = 1; i < cand.length; i++) {
dis ~= seq(0, cast(byte)(dmd[cand[i]].length - 1), 1);
}
if (nd % 2 == 1) {
dis ~= il;
}
byte[] di = uninitializedArray!(byte[])(dis.length);
fnpr(cand, di, dis, indicies, nmr, nd, 0);
} else {
foreach (num; list[level]) {
cand[level] = num;
fnmr(cand, list, indicies, nd, level + 1);
}
}
}
for (int nd = 2; nd <= maxDigits; nd++) {
digits = uninitializedArray!(byte[])(nd);
if (nd == 4) {
lists[0] ~= zl;
lists[1] ~= ol;
lists[2] ~= el;
lists[3] ~= ol;
} else if (allTerms[nd - 2].length > lists[0].length) {
for (int i = 0; i < 4; i++) {
lists[i] ~= dl;
}
}
byte[][] indicies;
foreach (t; allTerms[nd - 2]) {
indicies ~= [t.ix1, t.ix2];
}
foreach (list; lists) {
byte[] cand = uninitializedArray!(byte[])(list.length);
fnmr(cand, list, indicies, nd, 0);
}
auto ms = sw.peek();
writefln(" %2d digits: %9s", nd, ms);
}
rares.sort;
writefln("\nThe rare numbers with up to %d digits are:", maxDigits);
foreach (i, rare; rares) {
writefln(" %2d: %25s", i + 1, commatize(rare));
}
}</lang>
{{out}}
<pre>Aggregate timings to process all numbers up to:
R/N 1: 183 ╬╝s and 2 hnsecs (65)
2 digits: 193 ╬╝s and 8 hnsecs
3 digits: 301 ╬╝s and 3 hnsecs
4 digits: 380 ╬╝s and 1 hnsec
5 digits: 447 ╬╝s
R/N 2: 732 ╬╝s and 9 hnsecs (621,770)
6 digits: 767 ╬╝s and 1 hnsec
7 digits: 1 ms, 291 ╬╝s, and 5 hnsecs
8 digits: 5 ms, 602 ╬╝s, and 2 hnsecs
R/N 3: 5 ms, 900 ╬╝s, and 2 hnsecs (281,089,082)
9 digits: 7 ms, 537 ╬╝s, and 1 hnsec
R/N 4: 7 ms, 869 ╬╝s, and 5 hnsecs (2,022,652,202)
R/N 5: 32 ms, 826 ╬╝s, and 4 hnsecs (2,042,832,002)
10 digits: 96 ms, 422 ╬╝s, and 3 hnsecs
11 digits: 161 ms, 218 ╬╝s, and 4 hnsecs
R/N 6: 468 ms, 23 ╬╝s, and 9 hnsecs (872,546,974,178)
R/N 7: 506 ms, 702 ╬╝s, and 3 hnsecs (872,568,754,178)
R/N 8: 1 sec, 39 ms, 845 ╬╝s, and 6 hnsecs (868,591,084,757)
12 digits: 1 sec, 437 ms, 602 ╬╝s, and 8 hnsecs
R/N 9: 1 sec, 835 ms, 95 ╬╝s, and 6 hnsecs (6,979,302,951,885)
13 digits: 2 secs, 487 ms, 165 ╬╝s, and 9 hnsecs
R/N 10: 7 secs, 241 ms, 437 ╬╝s, and 1 hnsec (20,313,693,904,202)
R/N 11: 7 secs, 330 ms, 171 ╬╝s, and 2 hnsecs (20,313,839,704,202)
R/N 12: 9 secs, 290 ms, 907 ╬╝s, and 3 hnsecs (20,331,657,922,202)
R/N 13: 9 secs, 582 ms, 920 ╬╝s, and 5 hnsecs (20,331,875,722,202)
R/N 14: 10 secs, 383 ms, 769 ╬╝s, and 1 hnsec (20,333,875,702,202)
R/N 15: 25 secs, 835 ms, and 933 ╬╝s (40,313,893,704,200)
R/N 16: 26 secs, 14 ms, 774 ╬╝s, and 4 hnsecs (40,351,893,720,200)
14 digits: 30 secs, 110 ms, 971 ╬╝s, and 7 hnsecs
R/N 17: 30 secs, 216 ms, 437 ╬╝s, and 3 hnsecs (200,142,385,731,002)
R/N 18: 30 secs, 489 ms, 719 ╬╝s, and 2 hnsecs (221,462,345,754,122)
R/N 19: 34 secs, 83 ms, 642 ╬╝s, and 9 hnsecs (816,984,566,129,618)
R/N 20: 35 secs, 971 ms, 413 ╬╝s, and 3 hnsecs (245,518,996,076,442)
R/N 21: 36 secs, 250 ms, 787 ╬╝s, and 8 hnsecs (204,238,494,066,002)
R/N 22: 36 secs, 332 ms, 714 ╬╝s, and 2 hnsecs (248,359,494,187,442)
R/N 23: 36 secs, 696 ms, 902 ╬╝s, and 2 hnsecs (244,062,891,224,042)
R/N 24: 44 secs, 896 ms, and 665 ╬╝s (403,058,392,434,500)
R/N 25: 45 secs, 181 ms, 141 ╬╝s, and 5 hnsecs (441,054,594,034,340)
15 digits: 49 secs, 315 ms, 407 ╬╝s, and 4 hnsecs
R/N 26: 1 minute, 55 secs, 748 ms, 43 ╬╝s, and 4 hnsecs (2,133,786,945,766,212)
R/N 27: 2 minutes, 21 secs, 484 ms, 683 ╬╝s, and 7 hnsecs (2,135,568,943,984,212)
R/N 28: 2 minutes, 25 secs, 438 ms, 771 ╬╝s, and 7 hnsecs (8,191,154,686,620,818)
R/N 29: 2 minutes, 28 secs, 883 ms, 999 ╬╝s, and 6 hnsecs (8,191,156,864,620,818)
R/N 30: 2 minutes, 30 secs, 410 ms, and 831 ╬╝s (2,135,764,587,964,212)
R/N 31: 2 minutes, 32 secs, 594 ms, 842 ╬╝s, and 1 hnsec (2,135,786,765,764,212)
R/N 32: 2 minutes, 37 secs, 880 ms, 100 ╬╝s, and 5 hnsecs (8,191,376,864,400,818)
R/N 33: 2 minutes, 55 secs, 943 ms, 190 ╬╝s, and 5 hnsecs (2,078,311,262,161,202)
R/N 34: 3 minutes, 49 secs, 750 ms, 39 ╬╝s, and 5 hnsecs (8,052,956,026,592,517)
R/N 35: 3 minutes, 55 secs, 554 ms, 720 ╬╝s, and 1 hnsec (8,052,956,206,592,517)
R/N 36: 4 minutes, 41 secs, 59 ms, 309 ╬╝s, and 4 hnsecs (8,650,327,689,541,457)
R/N 37: 4 minutes, 43 secs, 951 ms, and 206 ╬╝s (8,650,349,867,341,457)
R/N 38: 4 minutes, 46 secs, 85 ms, 249 ╬╝s, and 7 hnsecs (6,157,577,986,646,405)
R/N 39: 5 minutes, 59 secs, 80 ms, 228 ╬╝s, and 5 hnsecs (4,135,786,945,764,210)
R/N 40: 7 minutes, 10 secs, 573 ms, 592 ╬╝s, and 2 hnsecs (6,889,765,708,183,410)
16 digits: 7 minutes, 16 secs, 827 ms, 76 ╬╝s, and 4 hnsecs
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|F_Sharp|F#}}==
| |||