Rare numbers: Difference between revisions
Content added Content deleted
Line 576: | Line 576: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
===Calculate L and H independently=== |
|||
<lang cpp> |
<lang cpp> |
||
// Rare Numbers : Nigel Galloway - December 20th., 2019; |
// Rare Numbers : Nigel Galloway - December 20th., 2019; |
||
// Nigel Galloway/Enter your username - January 4th., 2021 (see discussion page. |
|||
#include <functional> |
#include <functional> |
||
#include <bitset> |
#include <bitset> |
||
#include <cmath> |
#include <cmath> |
||
⚫ | |||
using namespace std; |
using namespace std; |
||
⚫ | |||
using namespace chrono; |
|||
⚫ | |||
using Z1 = function<Z2()>; |
|||
⚫ | |||
using VS = vector<string>; |
|||
// powers of 10 array |
// powers of 10 array |
||
constexpr auto pow10 = [] { array <long long, 19> n {1}; for (int j{0}, i{1}; i < 19; j = i++) n[i] = n[j] * 10; return n; } (); |
constexpr auto pow10 = [] { array <long long, 19> n {1}; for (int j{0}, i{1}; i < 19; j = i++) n[i] = n[j] * 10; return n; } (); |
||
Line 606: | Line 603: | ||
const double fac = 3.94; |
const double fac = 3.94; |
||
const int mbs = (int)sqrt(fac * pow10[9]), mbt = (int)sqrt(fac * fac * pow10[9]) >> 3; |
const int mbs = (int)sqrt(fac * pow10[9]), mbt = (int)sqrt(fac * fac * pow10[9]) >> 3; |
||
const bitset<100000>bs {[]{bitset<100000>n{false}; for(int g{3};g<mbs; |
const bitset<100000>bs {[]{bitset<100000>n{false}; for(int g{3};g<mbs;++g) n[(g*g)%100000]=true; return n;}()}; |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
constexpr array<const int, 7>li{1,3,0,0,1,1,1},lin{0,-7,0,0,-8,-3,-9},lig{0,9,0,0,8,7,9},lil{0,2,0,0,2,10,2}; |
constexpr array<const int, 7>li{1,3,0,0,1,1,1},lin{0,-7,0,0,-8,-3,-9},lig{0,9,0,0,8,7,9},lil{0,2,0,0,2,10,2}; |
||
const nLH makeL(const int n){ |
const nLH makeL(const int n){ |
||
Line 626: | Line 613: | ||
return q ? nLH(g,w,0) : nLH(g,{0},0); |
return q ? nLH(g,w,0) : nLH(g,{0},0); |
||
} |
} |
||
const bitset<100000>bt {[]{bitset<100000>n{false}; for(int g{11};g<mbt;++g) n[(g*g)%100000]=true; return n;}()}; |
|||
constexpr array<const int, 17>lu{0,0,0,0,2,0,4,0,0,0,1,4,0,0,0,1,1},lun{0,0,0,0,0,0,1,0,0,0,9,1,0,0,0,1,0},lug{0,0,0,0,18,0,17,0,0,0,9,17,0,0,0,11,18},lul{0,0,0,0,2,0,2,0,0,0,0,2,0,0,0,10,2}; |
constexpr array<const int, 17>lu{0,0,0,0,2,0,4,0,0,0,1,4,0,0,0,1,1},lun{0,0,0,0,0,0,1,0,0,0,9,1,0,0,0,1,0},lug{0,0,0,0,18,0,17,0,0,0,9,17,0,0,0,11,18},lul{0,0,0,0,2,0,2,0,0,0,0,2,0,0,0,10,2}; |
||
const nLH makeH(const int n){ |
const nLH makeH(const int n){ |
||
Line 632: | Line 620: | ||
if (n & 1){l=pow10[n>>1]<<1; g=fG(g,0,9,0,l,acc+=l);} |
if (n & 1){l=pow10[n>>1]<<1; g=fG(g,0,9,0,l,acc+=l);} |
||
if(q){long long g0{4}, g1{0}, g2{0}, g3{0}, g4{0},l3{pow10[n-5]}; while (g0<17){const long long g{g4*10000+g3*1000+g2*100+g1*10+g0}; |
if(q){long long g0{4}, g1{0}, g2{0}, g3{0}, g4{0},l3{pow10[n-5]}; while (g0<17){const long long g{g4*10000+g3*1000+g2*100+g1*10+g0}; |
||
if ( |
if (bt[g%100000]) w.push_back(l3*(g4+g3*10+g2*100+g1*1000+g0*10000)+g); |
||
if (g4<18) ++g4; else{g4=0; if(g3<18) ++g3; else{g3=0; if(g2<18) ++g2; else{g2=0; if(g1<lug[g0]) g1+=lul[g0]; else{g0+=lu[g0];g1=lun[g0];}}}}}} |
if (g4<18) ++g4; else{g4=0; if(g3<18) ++g3; else{g3=0; if(g2<18) ++g2; else{g2=0; if(g1<lug[g0]) g1+=lul[g0]; else{g0+=lu[g0];g1=lun[g0];}}}}}} |
||
return q ? nLH(g,w,0) : nLH(g,{0},pow10[n-1]<<2); |
return q ? nLH(g,w,0) : nLH(g,{0},pow10[n-1]<<2); |
||
} |
} |
||
⚫ | |||
⚫ | |||
template <typename T> // concatenates vectors |
template <typename T> // concatenates vectors |
||
vector<T>& operator +=(vector<T>& v, const vector<T>& w) { v.insert(v.end(), w.begin(), w.end()); return v; } |
vector<T>& operator +=(vector<T>& v, const vector<T>& w) { v.insert(v.end(), w.begin(), w.end()); return v; } |
||
int |
int c{0}; // solution counter |
||
auto st |
auto st{steady_clock::now()}, st0{st}, tmp{st}; // for determining elasped time |
||
int c{0},sc{0}; // solution counter |
|||
// formats elasped time |
// formats elasped time |
||
string dFmt(duration<double> et, int digs) { |
string dFmt(duration<double> et, int digs) { |
||
string res |
string res{""}; double dt{et.count()}; |
||
if (dt > 60.0) { int m = (int)(dt / 60.0); dt -= m * 60.0; res = to_string(m) + "m"; } |
if (dt > 60.0) { int m = (int)(dt / 60.0); dt -= m * 60.0; res = to_string(m) + "m"; } |
||
res += to_string(dt); return res.substr(0, digs - 1) + 's'; |
res += to_string(dt); return res.substr(0, digs - 1) + 's'; |
||
Line 655: | Line 644: | ||
char buf[99]; sprintf(buf, "%20llu %11lu %10lu", z, (long long)sqrt(h), (long long)sqrt(l)); |
char buf[99]; sprintf(buf, "%20llu %11lu %10lu", z, (long long)sqrt(h), (long long)sqrt(l)); |
||
res.push_back(buf); } } return res; |
res.push_back(buf); } } return res; |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
} |
||
void Rare(int n) { doOne(n, makeL(n), makeH(n)); } |
void Rare(int n) { doOne(n, makeL(n), makeH(n)); } |
||
int main(int argc, char *argv[]) { |
int main(int argc, char *argv[]) { |
||
int max |
int max{argc > 1 ? stoi(argv[1]) : 19}; if (max < 2) max = 2; if (max > 19 ) max = 19; |
||
printf("%4s %19s %11s %10s %5s %11s %9s\n", "nth", "forward", "rt.sum", "rt.diff", "digs", "block.et", "total.et"); |
printf("%4s %19s %11s %10s %5s %11s %9s\n", "nth", "forward", "rt.sum", "rt.diff", "digs", "block.et", "total.et"); |
||
for (int nd |
for (int nd{2}; nd <= max; ++nd) Rare(nd); |
||
} |
} |
||
</lang> |
</lang> |
||
Line 667: | Line 666: | ||
<pre> |
<pre> |
||
nth forward rt.sum rt.diff digs block.et total.et |
nth forward rt.sum rt.diff digs block.et total.et |
||
1 65 11 3 2: 0. |
1 65 11 3 2: 0.00003s 0.00003s |
||
3: 0. |
3: 0.00002s 0.00006s |
||
4: 0.00001s 0. |
4: 0.00001s 0.00008s |
||
5: 0. |
5: 0.00003s 0.00011s |
||
2 621770 836 738 6: 0. |
2 621770 836 738 6: 0.00007s 0.00018s |
||
7: 0. |
7: 0.00035s 0.00054s |
||
8: 0. |
8: 0.00110s 0.00164s |
||
3 281089082 23708 330 9: 0. |
3 281089082 23708 330 9: 0.00657s 0.00821s |
||
4 2022652202 63602 300 |
4 2022652202 63602 300 |
||
5 2042832002 63602 6360 10: 0. |
5 2042832002 63602 6360 10: 0.02246s 0.03068s |
||
11: 0. |
11: 0.11082s 0.14151s |
||
6 868591084757 1275175 333333 |
6 868591084757 1275175 333333 |
||
7 872546974178 1320616 32670 |
7 872546974178 1320616 32670 |
||
8 872568754178 1320616 33330 12: 0. |
8 872568754178 1320616 33330 12: 0.00868s 0.15019s |
||
9 6979302951885 3586209 1047717 13: 0. |
9 6979302951885 3586209 1047717 13: 0.03915s 0.18935s |
||
10 20313693904202 6368252 269730 |
10 20313693904202 6368252 269730 |
||
11 20313839704202 6368252 270270 |
11 20313839704202 6368252 270270 |
||
Line 688: | Line 687: | ||
14 20333875702202 6368252 336330 |
14 20333875702202 6368252 336330 |
||
15 40313893704200 6368252 6330336 |
15 40313893704200 6368252 6330336 |
||
16 40351893720200 6368252 6336336 14: 0. |
16 40351893720200 6368252 6336336 14: 0.11688s 0.30624s |
||
17 200142385731002 20006998 69300 |
17 200142385731002 20006998 69300 |
||
18 204238494066002 20122102 1891560 |
18 204238494066002 20122102 1891560 |
||
Line 697: | Line 696: | ||
23 403058392434500 20211202 19940514 |
23 403058392434500 20211202 19940514 |
||
24 441054594034340 22011022 19940514 |
24 441054594034340 22011022 19940514 |
||
25 816984566129618 40421606 250800 15: 0. |
25 816984566129618 40421606 250800 15: 0.69490s 1.00114s |
||
26 2078311262161202 64030648 7529850 |
26 2078311262161202 64030648 7529850 |
||
27 2133786945766212 65272218 2666730 |
27 2133786945766212 65272218 2666730 |
||
Line 712: | Line 711: | ||
38 8191376864400818 127950856 3366330 |
38 8191376864400818 127950856 3366330 |
||
39 8650327689541457 127246955 33299667 |
39 8650327689541457 127246955 33299667 |
||
40 8650349867341457 127246955 33300333 16: 2. |
40 8650349867341457 127246955 33300333 16: 2.18232s 3.18347s |
||
41 22542040692914522 212329862 333300 |
41 22542040692914522 212329862 333300 |
||
42 67725910561765640 269040196 251135808 |
42 67725910561765640 269040196 251135808 |
||
43 86965750494756968 417050956 33000 17: 13. |
43 86965750494756968 417050956 33000 17: 13.1765s 16.3599s |
||
44 225342456863243522 671330638 297000 |
44 225342456863243522 671330638 297000 |
||
45 225342458663243522 671330638 303000 |
45 225342458663243522 671330638 303000 |
||
Line 735: | Line 734: | ||
61 865721270017296468 1315452006 32071170 |
61 865721270017296468 1315452006 32071170 |
||
62 871975098681469178 1320582934 3303300 |
62 871975098681469178 1320582934 3303300 |
||
63 898907259301737498 1339270086 64576740 18: |
63 898907259301737498 1339270086 64576740 18: 41.6983s 58.0583s |
||
64 2042401829204402402 2021001202 18915600 |
64 2042401829204402402 2021001202 18915600 |
||
65 2060303819041450202 2020110202 199405140 |
65 2060303819041450202 2020110202 199405140 |
||
Line 747: | Line 746: | ||
73 8197906905009010818 4046976144 133408770 |
73 8197906905009010818 4046976144 133408770 |
||
74 8200756128308135597 4019461925 495417087 |
74 8200756128308135597 4019461925 495417087 |
||
75 8320411466598809138 4079154376 36366330 19: |
75 8320411466598809138 4079154376 36366330 19: 5m1.342s 5m59.40s |
||
</pre> |
</pre> |
||
===20+ digits=== |
===20+ digits=== |