Rare numbers: Difference between revisions

Line 26:

:*   author's  website:   [http://www.shyamsundergupta.com/rare.htm rare numbers]   by Shyam Sunder Gupta.     (lots of hints and some observations).

=={{header|C++}}==

I am travelling at the moment so all timings for the following are made on my laptop. Expect better than half when I run them on my desktop in the new year.

===The task===

The following is a simple implementation that demonstrates the principle of n-r=L and n+r=H. Interestingly it compile with both g++ and clang++, but g++ produces incorrect output. It is sufficient to meet the unambitious requirements of this task.

// Rare Numbers : Nigel Galloway - December 20th., 2019

#include <iostream>

#include <functional>

#include <cmath>

#include <numeric>

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};

constexpr auto r1=([]{std::array<bool,10>n{}; for(auto g:{0,1,4,5,6,9}) n[g]=true; return n;})();

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);}

struct nLH{

std::vector<long>even{};

std::vector<long>odd{};

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);}}

};

template<int z>void Rare(){

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{

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]]) *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;}

}

int main(){

Rare<2>();

Rare<3>();

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>();

}

</lang>

<pre>

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

real 7m6.890s

user 7m6.614s

sys 0m0.156s

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

real 44m23.656s

user 44m22.729s

sys 0m0.401s

</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 but g++ takes 3 times as long. I expect some difference but 3000%, come on!!! It will not work for lengths less than 10 or greater than 19.

// 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;}

}

};

int main(){

Rare(19);

}