Rare numbers: Difference between revisions
Content added Content deleted
Line 576: | Line 576: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
===The task=== |
|||
The following is a simple implementation that demonstrates the principle of [[Talk:Rare_numbers#A_few_more_mins.]]. Interestingly it compile with both g++ and clang++, but g++ produces incorrect output. It is sufficient to meet the unambitious requirements of this task. |
|||
<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 <iostream> |
|||
#include <functional> |
#include <functional> |
||
#include <bitset> |
|||
#include <cmath> |
#include <cmath> |
||
#include < |
#include <chrono> |
||
using namespace std; |
|||
constexpr std::array<const long,18> pow10{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000}; |
|||
using namespace chrono; |
|||
constexpr auto r1=([]{std::array<bool,10>n{}; for(auto g:{0,1,4,5,6,9}) n[g]=true; return n;})(); |
|||
using Z2 = optional<long long>; |
|||
constexpr bool izRev( int n, long i, long g){return (i/pow10[n-1]!=g%10)? false : (n<2)? true : izRev(n-1,i%pow10[n-1],g/10);} |
|||
using Z1 = function<Z2()>; |
|||
struct nLH{ |
|||
using VU = vector<unsigned long long>; |
|||
using VS = vector<string>; |
|||
// powers of 10 array |
|||
nLH(std::function<std::optional<long>()> g){while (auto n=g()){if (([n]{long g=sqrt(*n); return (g*g==n);})()) (*n%2==0)? even.push_back(*n) : odd.push_back(*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; } (); |
|||
}; |
|||
long long acc, l; |
|||
template<int z>void Rare(){ |
|||
bool izRev(int n, unsigned long long i, unsigned long long g) { |
|||
auto L=nLH(([n=std::array<int,z/2>{},p=([]{int g{z/2}; std::array<long,z/2>n{}; for(auto& n:n){n=pow10[z-g]-pow10[g-1]; --g;} return n;})()]() mutable{ |
|||
return (i / pow10[n - 1] != g % 10) ? false : n < 2 ? true : izRev(n - 1, i % pow10[n - 1], g / 10); |
|||
for (auto g=n.begin();g<(n.end());++g) if (*g<9){*g+=1; while(!r1[(n[z/2-1]*9)%10]) *g+=1; return std::optional{std::inner_product(n.begin(),n.end(),p.begin(),0L)};} else *g=-9; |
|||
return std::optional<long>{};})); |
|||
auto H=nLH(([n=([]{std::array<int,(z+1)/2>n{}; *(n.end()-1)=1; *n.begin()-=1; return n;})(), |
|||
p=([]{int g{z/2}; std::array<long,(z+1)/2>n{}; for(auto& i:n) if (z%2==1&n[0]==0) i=2*pow10[z/2]; else {i=pow10[z-g]+pow10[g-1]; --g;} return n;})()]() mutable{ |
|||
for (auto g=n.begin();g<(n.end());++g) if (*g<19&(z%2==0|n[0]<10)){ |
|||
*g+=1; while(!r1[n[(z+1)/2-1]%10]) *g+=1; return std::optional{std::inner_product(n.begin(),n.end(),p.begin(),0L)};} else *g=0; |
|||
return std::optional<long>{};})); |
|||
std::cout<<"Rare numbers of length "<<z<<std::endl; |
|||
for(auto l:L.even) for(auto h:H.even){long r=(h-l)/2; if(izRev(z,r,h-r)) std::cout<<"n="<<h-r<<" r="<<r<<" n-r="<<l<<" n+r="<<h<<std::endl;} |
|||
for(auto l:L.odd) for(auto h:H.odd) {long r=(h-l)/2; if(izRev(z,r,h-r)) std::cout<<"n="<<h-r<<" r="<<r<<" n-r="<<l<<" n+r="<<h<<std::endl;} |
|||
} |
} |
||
const Z1 fG(Z1 n, int start, int end, int reset, const long long step, long long &l) { |
|||
int main(){ |
|||
return [n, i{step * start}, g{step * end}, e{step * reset}, &l, step] () mutable { |
|||
Rare<2>(); |
|||
while (i<g){i+=step; return Z2(l+=step);} |
|||
Rare<3>(); |
|||
l-=g-(i=e); return n();}; |
|||
Rare<4>(); |
|||
Rare<5>(); |
|||
Rare<6>(); |
|||
Rare<7>(); |
|||
Rare<8>(); |
|||
Rare<9>(); |
|||
Rare<10>(); |
|||
Rare<11>(); |
|||
Rare<12>(); |
|||
Rare<13>(); |
|||
Rare<14>(); |
|||
Rare<15>(); |
|||
Rare<16>(); |
|||
} |
} |
||
struct nLH { |
|||
</lang> |
|||
vector<unsigned long long>even{}, odd{}; |
|||
{{out}} |
|||
nLH(const Z1 a, const vector<long long> b, long long llim){while (auto i = a()) for (auto ng : b) |
|||
<pre> |
|||
if(ng>0 | *i>llim){unsigned long long sq{ng+ *i}, r{sqrt(sq)}; if (r*r == sq) ng&1 ? odd.push_back(sq) : even.push_back(sq);}} |
|||
Rare numbers of length 2 |
|||
n=65 r=56 n-r=9 n+r=121 |
|||
Rare numbers of length 3 |
|||
Rare numbers of length 4 |
|||
Rare numbers of length 5 |
|||
Rare numbers of length 6 |
|||
n=621770 r=77126 n-r=544644 n+r=698896 |
|||
Rare numbers of length 7 |
|||
Rare numbers of length 8 |
|||
Rare numbers of length 9 |
|||
n=281089082 r=280980182 n-r=108900 n+r=562069264 |
|||
Rare numbers of length 10 |
|||
n=2022652202 r=2022562202 n-r=90000 n+r=4045214404 |
|||
n=2042832002 r=2002382402 n-r=40449600 n+r=4045214404 |
|||
Rare numbers of length 11 |
|||
Rare numbers of length 12 |
|||
n=872546974178 r=871479645278 n-r=1067328900 n+r=1744026619456 |
|||
n=872568754178 r=871457865278 n-r=1110888900 n+r=1744026619456 |
|||
n=868591084757 r=757480195868 n-r=111110888889 n+r=1626071280625 |
|||
Rare numbers of length 13 |
|||
n=6979302951885 r=5881592039796 n-r=1097710912089 n+r=12860894991681 |
|||
Rare numbers of length 14 |
|||
n=20313693904202 r=20240939631302 n-r=72754272900 n+r=40554633535504 |
|||
n=20313839704202 r=20240793831302 n-r=73045872900 n+r=40554633535504 |
|||
n=20331657922202 r=20222975613302 n-r=108682308900 n+r=40554633535504 |
|||
n=20331875722202 r=20222757813302 n-r=109117908900 n+r=40554633535504 |
|||
n=20333875702202 r=20220757833302 n-r=113117868900 n+r=40554633535504 |
|||
n=40313893704200 r=240739831304 n-r=40073153872896 n+r=40554633535504 |
|||
n=40351893720200 r=202739815304 n-r=40149153904896 n+r=40554633535504 |
|||
Rare numbers of length 15 |
|||
n=200142385731002 r=200137583241002 n-r=4802490000 n+r=400279968972004 |
|||
n=221462345754122 r=221457543264122 n-r=4802490000 n+r=442919889018244 |
|||
n=816984566129618 r=816921665489618 n-r=62900640000 n+r=1633906231619236 |
|||
n=245518996076442 r=244670699815542 n-r=848296260900 n+r=490189695891984 |
|||
n=204238494066002 r=200660494832402 n-r=3577999233600 n+r=404898988898404 |
|||
n=248359494187442 r=244781494953842 n-r=3577999233600 n+r=493140989141284 |
|||
n=244062891224042 r=240422198260442 n-r=3640692963600 n+r=484485089484484 |
|||
n=403058392434500 r=5434293850304 n-r=397624098584196 n+r=408492686284804 |
|||
n=441054594034340 r=43430495450144 n-r=397624098584196 n+r=484485089484484 |
|||
Rare numbers of length 16 |
|||
n=2133786945766212 r=2126675496873312 n-r=7111448892900 n+r=4260462442639524 |
|||
n=2135568943984212 r=2124893498655312 n-r=10675445328900 n+r=4260462442639524 |
|||
n=8191154686620818 r=8180266864511918 n-r=10887822108900 n+r=16371421551132736 |
|||
n=8191156864620818 r=8180264686511918 n-r=10892178108900 n+r=16371421551132736 |
|||
n=2135764587964212 r=2124697854675312 n-r=11066733288900 n+r=4260462442639524 |
|||
n=2135786765764212 r=2124675676875312 n-r=11111088888900 n+r=4260462442639524 |
|||
n=8191376864400818 r=8180044686731918 n-r=11332177668900 n+r=16371421551132736 |
|||
n=2078311262161202 r=2021612621138702 n-r=56698641022500 n+r=4099923883299904 |
|||
n=4135786945764210 r=124675496875314 n-r=4011111448888896 n+r=4260462442639524 |
|||
n=6889765708183410 r=143818075679886 n-r=6745947632503524 n+r=7033583783863296 |
|||
n=8052956026592517 r=7152956206592508 n-r=899999820000009 n+r=15205912233185025 |
|||
n=8052956206592517 r=7152956026592508 n-r=900000180000009 n+r=15205912233185025 |
|||
n=8650327689541457 r=7541459867230568 n-r=1108867822310889 n+r=16191787556772025 |
|||
n=8650349867341457 r=7541437689430568 n-r=1108912177910889 n+r=16191787556772025 |
|||
n=6157577986646405 r=5046466897757516 n-r=1111111088888889 n+r=11204044884403921 |
|||
Rare numbers of length 17 |
|||
n=86965750494756968 r=86965749405756968 n-r=1089000000 n+r=173931499900513936 |
|||
n=22542040692914522 r=22541929604024522 n-r=111088890000 n+r=45083970296939044 |
|||
n=67725910561765640 r=4656716501952776 n-r=63069194059812864 n+r=72382627063718416 |
|||
</pre> |
|||
===10 to 19 digits=== |
|||
The following is a faster implementation of the algorithm. It compiles with both g++ and clang++, both produce the correct output. It will not work for lengths less than 10 or greater than 19. The timings are using Mingw running on a Core I5 1035G1. |
|||
<lang cpp> |
|||
// Rare Numbers : Nigel Galloway - December 20th., 2019 |
|||
#include <iostream> |
|||
#include <functional> |
|||
#include <bitset> |
|||
#include <cmath> |
|||
using Z2=std::optional<long>; using Z1=std::function<Z2()>; |
|||
constexpr std::array<const long,19> pow10{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000}; |
|||
constexpr bool izRev(int n,unsigned long i,unsigned long g){return (i/pow10[n-1]!=g%10)? false : (n<2)? true : izRev(n-1,i%pow10[n-1],g/10);} |
|||
const Z1 fG(Z1 n,int start, int end,int reset,const long step,long &l){return ([n,i{step*start},g{step*end},e{step*reset},&l,step]()mutable{ |
|||
while(i<g){l+=step; i+=step; return Z2(l);} i=e; l-=(g-e); return n();});} |
|||
struct nLH{ |
|||
std::vector<unsigned long>even{}; |
|||
std::vector<unsigned long>odd{}; |
|||
nLH(std::pair<Z1,std::vector<std::pair<long,long>>> e){auto [n,g]=e; while (auto i=n()){for(auto [ng,gg]:g){ if((ng>0)|(*i>0)){ |
|||
unsigned long w=ng*pow10[4]+gg+*i; unsigned long g=sqrt(w); if(g*g==w) (w%2==0)? even.push_back(w) : odd.push_back(w);}}}} |
|||
}; |
|||
class Rare{ |
|||
long acc{0}; |
|||
const std::bitset<10000>bs; |
|||
const std::pair<Z1,std::vector<std::pair<long,long>>> makeL(const int n){ |
|||
Z1 g[n/2-3]; g[0]=([]{return Z2{};}); |
|||
for(int i{1};i<n/2-3;++i){int s{(i==n/2-4)? -10:-9}; long l=pow10[n-i-4]-pow10[i+3]; acc+=l*s; g[i]=fG(g[i-1],s,9,-9,l,acc);} |
|||
return {g[n/2-4],([g0{0},g1{0},g2{0},g3{0},l3{pow10[n-8]},l2{pow10[n-7]},l1{pow10[n-6]},l0{pow10[n-5]},this]()mutable{std::vector<std::pair<long,long>>w{}; while (g0<10){ |
|||
long n{g3*l3+g2*l2+g1*l1+g0*l0}; long g{-1000*g3-100*g2-10*g1-g0}; if(g3<9) ++g3; else{g3=-9; if(g2<9) ++g2; else{g2=-9; if(g1<9) ++g1; else{g1=-9; ++g0;}}} |
|||
if (bs[(pow10[10]+g)%10000]) w.push_back({n,g});} return w;})()};} |
|||
const std::pair<Z1,std::vector<std::pair<long,long>>> makeH(const int n){ acc=-(pow10[n/2]+pow10[(n-1)/2]); |
|||
Z1 g[(n+1)/2-3]; g[0]=([]{return Z2{};}); |
|||
for(int i{1};i<n/2-3;++i) g[i]=fG(g[i-1],(i==(n+1)/2-3)? -1:0,18,0,pow10[n-i-4]+pow10[i+3],acc); |
|||
if(n%2==1) g[(n+1)/2-4]=fG(g[n/2-4],-1,9,0,2*pow10[n/2],acc); |
|||
return {g[(n+1)/2-4],([g0{1},g1{0},g2{0},g3{0},l3{pow10[n-8]},l2{pow10[n-7]},l1{pow10[n-6]},l0{pow10[n-5]},this]()mutable{std::vector<std::pair<long,long>>w{}; while (g0<17){ |
|||
long n{g3*l3+g2*l2+g1*l1+g0*l0}; long g{g3*1000+g2*100+g1*10+g0}; if(g3<18) ++g3; else{g3=0; if(g2<18) ++g2; else{g2=0; if(g1<18) ++g1; else{g1=0; ++g0;}}} |
|||
if (bs[g%10000]) w.push_back({n,g});} return w;})()};} |
|||
const nLH L,H; |
|||
public: Rare(int n):L{makeL(n)},H{makeH(n)},bs{([]{std::bitset<10000>n{false}; for(int g{0};g<10000;++g) n[(g*g)%10000]=true; return n;})()}{ |
|||
std::cout<<"Rare "<<n<<std::endl; |
|||
for(auto l:L.even) for(auto h:H.even){unsigned long r{(h-l)/2},z{(h-r)}; if(izRev(n,r,z)) std::cout<<"n="<<z<<" r="<<r<<" n-r="<<l<<" n+r="<<h<<std::endl;} |
|||
for(auto l:L.odd) for(auto h:H.odd) {unsigned long r{(h-l)/2},z{(h-r)}; if(izRev(n,r,z)) std::cout<<"n="<<z<<" r="<<r<<" n-r="<<l<<" n+r="<<h<<std::endl;} |
|||
} |
|||
}; |
}; |
||
const double fac = 3.94; |
|||
int main(){ |
|||
const int mbs = (int)sqrt(fac * pow10[9]), mbt = (int)sqrt(fac * fac * pow10[9]) >> 3; |
|||
Rare(19); |
|||
const bitset<100000>bs {[]{bitset<100000>n{false}; for(int g{3};g<mbs;g+=3) n[(g*g)%100000]=true; for(int g{11};g<mbt;g++) n[(g*g)%100000]=true; return n;}()}; |
|||
// reports one block of digits |
|||
void doOne(int n, nLH L, nLH H) { |
|||
VS lines = dump(n, L.even, H.even); lines += dump(n, L.odd , H.odd); sort(lines.begin(), lines.end()); |
|||
duration<double> tet = (tmp = steady_clock::now()) - st; int ls = lines.size(); |
|||
if (ls-- > 0) |
|||
for (int i = 0; i <= ls; ++i) |
|||
printf("%3d %s%s", ++c, lines[i].c_str(), i == ls ? "" : "\n"); |
|||
else printf("%s", string(47, ' ').c_str()); |
|||
printf(" %2d: %s %s\n", n, dFmt(tmp - st0, 8).c_str(), dFmt(tet, 8).c_str()); st0 = tmp; |
|||
} |
|||
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){ |
|||
constexpr int r{9}; acc=0; Z1 g{[]{return Z2{};}}; int s{-r}, q{(n>11)*5}; vector<long long> w{}; |
|||
for (int i{1};i<n/2-q+1;++i){l=pow10[n-i-q]-pow10[i+q-1]; s-=i==n/2-q; g=fG(g,s,r,-r,l,acc+=l*s);} |
|||
if(q){long long g0{0}, g1{0}, g2{0}, g3{0}, g4{0}, l3{pow10[n-5]}; while (g0<7){const long long g{-10000*g4-1000*g3-100*g2-10*g1-g0}; |
|||
if (bs[(g+1000000000000LL)%100000]) w.push_back(l3*(g4+g3*10+g2*100+g1*1000+g0*10000)+g); |
|||
if(g4<r) ++g4; else{g4= -r; if(g3<r) ++g3; else{g3= -r; if(g2<r) ++g2; else{g2= -r; if(g1<lig[g0]) g1+=lil[g0]; else {g0+=li[g0];g1=lin[g0];}}}}}} |
|||
return q ? nLH(g,w,0) : nLH(g,{0},0); |
|||
} |
|||
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){ |
|||
acc= -pow10[n>>1]-pow10[(n-1)>>1]; Z1 g{[]{ return Z2{};}}; int q{(n>11)*5}; vector<long long> w {}; |
|||
for (int i{1}; i<(n>>1)-q+1; ++i) g = fG(g,0,18,0,pow10[n-i-q]+pow10[i+q-1], acc); |
|||
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 (bs[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];}}}}}} |
|||
return q ? nLH(g,w,0) : nLH(g,{0},pow10[n-1]<<2); |
|||
} |
|||
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; } |
|||
int sc = 0; // solution counter |
|||
auto st = steady_clock::now(), st0 = st, tmp = st; double dir = 0; // for determining elasped time |
|||
int c{0},sc{0}; // solution counter |
|||
// formats elasped time |
|||
string dFmt(duration<double> et, int digs) { |
|||
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"; } |
|||
res += to_string(dt); return res.substr(0, digs - 1) + 's'; |
|||
} |
|||
// combines list of square differences with list of square sums, reports compatible results |
|||
VS dump(int nd, VU lo, VU hi) { |
|||
VS res {}; |
|||
for (auto l : lo) for (auto h : hi) { |
|||
auto r { (h - l) >> 1 }, z { h - r }; |
|||
if (izRev(nd, r, z)) { |
|||
char buf[99]; sprintf(buf, "%20llu %11lu %10lu", z, (long long)sqrt(h), (long long)sqrt(l)); |
|||
res.push_back(buf); } } return res; |
|||
} |
|||
void Rare(int n) { doOne(n, makeL(n), makeH(n)); } |
|||
int main(int argc, char *argv[]) { |
|||
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"); |
|||
for (int nd = 2; nd <= max; ++nd) Rare(nd); |
|||
} |
} |
||
</lang> |
</lang> |
||
{{out}} |
{{out}} |
||
Processor Intel(R) Core(TM) i5-1035G1 CPU @ 1.00GHz |
|||
<pre> |
<pre> |
||
nth forward rt.sum rt.diff digs block.et total.et |
|||
Rare 10 |
|||
1 65 11 3 2: 0.00010s 0.00010s |
|||
n=2022652202 r=2022562202 n-r=90000 n+r=4045214404 |
|||
3: 0.00001s 0.00011s |
|||
n=2042832002 r=2002382402 n-r=40449600 n+r=4045214404 |
|||
4: 0.00001s 0.00013s |
|||
Rare 11 |
|||
5: 0.00002s 0.00015s |
|||
Rare 12 |
|||
2 621770 836 738 6: 0.00005s 0.00021s |
|||
n=872546974178 r=871479645278 n-r=1067328900 n+r=1744026619456 |
|||
7: 0.00027s 0.00048s |
|||
n=872568754178 r=871457865278 n-r=1110888900 n+r=1744026619456 |
|||
8: 0.00084s 0.00132s |
|||
n=868591084757 r=757480195868 n-r=111110888889 n+r=1626071280625 |
|||
3 281089082 23708 330 9: 0.00529s 0.00662s |
|||
Rare 13 |
|||
4 2022652202 63602 300 |
|||
n=6979302951885 r=5881592039796 n-r=1097710912089 n+r=12860894991681 |
|||
5 2042832002 63602 6360 10: 0.01652s 0.02314s |
|||
Rare 14 |
|||
11: 0.09748s 0.12063s |
|||
n=20331657922202 r=20222975613302 n-r=108682308900 n+r=40554633535504 |
|||
6 868591084757 1275175 333333 |
|||
n=20331875722202 r=20222757813302 n-r=109117908900 n+r=40554633535504 |
|||
7 872546974178 1320616 32670 |
|||
n=40351893720200 r=202739815304 n-r=40149153904896 n+r=40554633535504 |
|||
8 872568754178 1320616 33330 12: 0.00898s 0.12961s |
|||
n=20313693904202 r=20240939631302 n-r=72754272900 n+r=40554633535504 |
|||
9 6979302951885 3586209 1047717 13: 0.04020s 0.16982s |
|||
n=20313839704202 r=20240793831302 n-r=73045872900 n+r=40554633535504 |
|||
10 20313693904202 6368252 269730 |
|||
n=20333875702202 r=20220757833302 n-r=113117868900 n+r=40554633535504 |
|||
11 20313839704202 6368252 270270 |
|||
n=40313893704200 r=240739831304 n-r=40073153872896 n+r=40554633535504 |
|||
12 20331657922202 6368252 329670 |
|||
Rare 15 |
|||
13 20331875722202 6368252 330330 |
|||
n=245518996076442 r=244670699815542 n-r=848296260900 n+r=490189695891984 |
|||
14 20333875702202 6368252 336330 |
|||
n=204238494066002 r=200660494832402 n-r=3577999233600 n+r=404898988898404 |
|||
15 40313893704200 6368252 6330336 |
|||
n=248359494187442 r=244781494953842 n-r=3577999233600 n+r=493140989141284 |
|||
16 40351893720200 6368252 6336336 14: 0.12043s 0.29025s |
|||
n=200142385731002 r=200137583241002 n-r=4802490000 n+r=400279968972004 |
|||
17 200142385731002 20006998 69300 |
|||
n=221462345754122 r=221457543264122 n-r=4802490000 n+r=442919889018244 |
|||
18 204238494066002 20122102 1891560 |
|||
n=441054594034340 r=43430495450144 n-r=397624098584196 n+r=484485089484484 |
|||
19 221462345754122 21045662 69300 |
|||
n=403058392434500 r=5434293850304 n-r=397624098584196 n+r=408492686284804 |
|||
20 244062891224042 22011022 1908060 |
|||
21 245518996076442 22140228 921030 |
|||
n=816984566129618 r=816921665489618 n-r=62900640000 n+r=1633906231619236 |
|||
22 248359494187442 22206778 1891560 |
|||
Rare 16 |
|||
23 403058392434500 20211202 19940514 |
|||
n=2135568943984212 r=2124893498655312 n-r=10675445328900 n+r=4260462442639524 |
|||
24 441054594034340 22011022 19940514 |
|||
n=2078311262161202 r=2021612621138702 n-r=56698641022500 n+r=4099923883299904 |
|||
25 816984566129618 40421606 250800 15: 0.71955s 1.00981s |
|||
n=8191154686620818 r=8180266864511918 n-r=10887822108900 n+r=16371421551132736 |
|||
26 2078311262161202 64030648 7529850 |
|||
n=8191156864620818 r=8180264686511918 n-r=10892178108900 n+r=16371421551132736 |
|||
27 2133786945766212 65272218 2666730 |
|||
n=6889765708183410 r=143818075679886 n-r=6745947632503524 n+r=7033583783863296 |
|||
28 2135568943984212 65272218 3267330 |
|||
n=2135764587964212 r=2124697854675312 n-r=11066733288900 n+r=4260462442639524 |
|||
29 2135764587964212 65272218 3326670 |
|||
n=2135786765764212 r=2124675676875312 n-r=11111088888900 n+r=4260462442639524 |
|||
30 2135786765764212 65272218 3333330 |
|||
n=2133786945766212 r=2126675496873312 n-r=7111448892900 n+r=4260462442639524 |
|||
31 4135786945764210 65272218 63333336 |
|||
32 6157577986646405 105849161 33333333 |
|||
n=8191376864400818 r=8180044686731918 n-r=11332177668900 n+r=16371421551132736 |
|||
33 6889765708183410 83866464 82133718 |
|||
n=8650327689541457 r=7541459867230568 n-r=1108867822310889 n+r=16191787556772025 |
|||
34 8052956026592517 123312255 29999997 |
|||
n=8650349867341457 r=7541437689430568 n-r=1108912177910889 n+r=16191787556772025 |
|||
35 8052956206592517 123312255 30000003 |
|||
n=8052956026592517 r=7152956206592508 n-r=899999820000009 n+r=15205912233185025 |
|||
36 8191154686620818 127950856 3299670 |
|||
n=8052956206592517 r=7152956026592508 n-r=900000180000009 n+r=15205912233185025 |
|||
37 8191156864620818 127950856 3300330 |
|||
n=6157577986646405 r=5046466897757516 n-r=1111111088888889 n+r=11204044884403921 |
|||
38 8191376864400818 127950856 3366330 |
|||
39 8650327689541457 127246955 33299667 |
|||
40 8650349867341457 127246955 33300333 16: 2.23272s 3.24253s |
|||
41 22542040692914522 212329862 333300 |
|||
42 67725910561765640 269040196 251135808 |
|||
43 86965750494756968 417050956 33000 17: 13.6255s 16.8680s |
|||
44 225342456863243522 671330638 297000 |
|||
45 225342458663243522 671330638 303000 |
|||
46 225342478643243522 671330638 363000 |
|||
47 284684666566486482 754565658 30000 |
|||
48 284684868364486482 754565658 636000 |
|||
49 297128548234950692 770186978 32697330 |
|||
50 297128722852950692 770186978 32702670 |
|||
51 297148324656930692 770186978 33296670 |
|||
52 297148546434930692 770186978 33303330 |
|||
53 497168548234910690 770186978 633363336 |
|||
54 619431353040136925 1071943279 299667003 |
|||
55 619631153042134925 1071943279 300333003 |
|||
56 631688638047992345 1083968809 297302703 |
|||
57 633288858025996145 1083968809 302637303 |
|||
58 633488632647994145 1083968809 303296697 |
|||
59 653488856225994125 1083968809 363303363 |
|||
60 811865096390477018 1273828556 33030330 |
|||
61 865721270017296468 1315452006 32071170 |
|||
62 871975098681469178 1320582934 3303300 |
|||
63 898907259301737498 1339270086 64576740 18: 42.3791s 59.2472s |
|||
64 2042401829204402402 2021001202 18915600 |
|||
65 2060303819041450202 2020110202 199405140 |
|||
66 2420424089100600242 2200110022 19080600 |
|||
67 2551755006254571552 2259094848 693000 |
|||
68 2702373360882732072 2324811012 693000 |
|||
69 2825378427312735282 2377130742 2508000 |
|||
70 6531727101458000045 3454234451 1063822617 |
|||
71 6988066446726832640 2729551744 2554541088 |
|||
72 8066308349502036608 4016542096 2508000 |
|||
73 8197906905009010818 4046976144 133408770 |
|||
74 8200756128308135597 4019461925 495417087 |
|||
75 8320411466598809138 4079154376 36366330 19: 5m10.26s 6m9.513s |
|||
Rare 17 |
|||
n=67725910561765640 r=4656716501952776 n-r=63069194059812864 n+r=72382627063718416 |
|||
n=86965750494756968 r=86965749405756968 n-r=1089000000 n+r=173931499900513936 |
|||
n=22542040692914522 r=22541929604024522 n-r=111088890000 n+r=45083970296939044 |
|||
real 0m33.328s |
|||
user 0m32.078s |
|||
sys 0m0.015s |
|||
Rare 18 |
|||
n=865721270017296468 r=864692710072127568 n-r=1028559945168900 n+r=1730413980089424036 |
|||
n=297128548234950692 r=296059432845821792 n-r=1069115389128900 n+r=593187981080772484 |
|||
n=297128722852950692 r=296059258227821792 n-r=1069464625128900 n+r=593187981080772484 |
|||
n=898907259301737498 r=894737103952709898 n-r=4170155349027600 n+r=1793644363254447396 |
|||
n=811865096390477018 r=810774093690568118 n-r=1091002699908900 n+r=1622639190081045136 |
|||
n=284684666566486482 r=284684665666486482 n-r=900000000 n+r=569369332232972964 |
|||
n=225342456863243522 r=225342368654243522 n-r=88209000000 n+r=450684825517487044 |
|||
n=225342458663243522 r=225342366854243522 n-r=91809000000 n+r=450684825517487044 |
|||
n=225342478643243522 r=225342346874243522 n-r=131769000000 n+r=450684825517487044 |
|||
n=284684868364486482 r=284684463868486482 n-r=404496000000 n+r=569369332232972964 |
|||
n=297148324656930692 r=296039656423841792 n-r=1108668233088900 n+r=593187981080772484 |
|||
n=297148546434930692 r=296039434645841792 n-r=1109111789088900 n+r=593187981080772484 |
|||
n=871975098681469178 r=871964186890579178 n-r=10911790890000 n+r=1743939285572048356 |
|||
n=497168548234910690 r=96019432845861794 n-r=401149115389048896 n+r=593187981080772484 |
|||
n=633488632647994145 r=541499746236884336 n-r=91988886411109809 n+r=1174988378884878481 |
|||
n=631688638047992345 r=543299740836886136 n-r=88388897211106209 n+r=1174988378884878481 |
|||
n=653488856225994125 r=521499522658884356 n-r=131989333567109769 n+r=1174988378884878481 |
|||
n=633288858025996145 r=541699520858882336 n-r=91589337167113809 n+r=1174988378884878481 |
|||
n=619631153042134925 r=529431240351136916 n-r=90199912690998009 n+r=1149062393393271841 |
|||
n=619431353040136925 r=529631040353134916 n-r=89800312687002009 n+r=1149062393393271841 |
|||
real 1m32.945s |
|||
user 1m31.656s |
|||
sys 0m0.000s |
|||
Rare 19 |
|||
n=6988066446726832640 r=462386276446608896 n-r=6525680170280223744 n+r=7450452723173441536 |
|||
n=2060303819041450202 r=2020541409183030602 n-r=39762409858419600 n+r=4080845228224480804 |
|||
n=2702373360882732072 r=2702372880633732072 n-r=480249000000 n+r=5404746241516464144 |
|||
n=2551755006254571552 r=2551754526005571552 n-r=480249000000 n+r=5103509532260143104 |
|||
n=8066308349502036608 r=8066302059438036608 n-r=6290064000000 n+r=16132610408940073216 |
|||
n=2825378427312735282 r=2825372137248735282 n-r=6290064000000 n+r=5650750564561470564 |
|||
n=8320411466598809138 r=8319088956641140238 n-r=1322509957668900 n+r=16639500423239949376 |
|||
n=2042401829204402402 r=2042044029281042402 n-r=357799923360000 n+r=4084445858485444804 |
|||
n=2420424089100600242 r=2420060019804240242 n-r=364069296360000 n+r=4840484108904840484 |
|||
n=8197906905009010818 r=8180109005096097918 n-r=17797899912912900 n+r=16378015910105108736 |
|||
n=8200756128308135597 r=7955318038216570028 n-r=245438090091565569 n+r=16156074166524705625 |
|||
n=6531727101458000045 r=5400008541017271356 n-r=1131718560440728689 n+r=11931735642475271401 |
|||
real 12m21.298s |
|||
user 12m19.890s |
|||
sys 0m0.030s |
|||
</pre> |
</pre> |
||
===20+ digits=== |
===20+ digits=== |
||
<lang cpp> |
<lang cpp> |