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: | Line 718: | ||
74: 8,200,756,128,308,135,597 |
74: 8,200,756,128,308,135,597 |
||
75: 8,320,411,466,598,809,138</pre> |
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#}}== |
=={{header|F_Sharp|F#}}== |