Rare numbers: Difference between revisions
→{{header|langur}}
(Added Wren) |
Langurmonkey (talk | contribs) |
||
(47 intermediate revisions by 22 users not shown) | |||
Line 26:
:* author's website: [http://www.shyamsundergupta.com/rare.html rare numbers] by Shyam Sunder Gupta. (lots of hints and some observations).
<br><br>
=={{header|ALGOL 68}}==
{{Trans|FreeBASIC}}
which is
{{Trans|Phix}}
(naive version)
<syntaxhighlight lang="algol68">
PROC revn = ( LONG INT na, nda )LONG INT:
BEGIN
LONG INT n := na, nd := nda, r := 0, i := 0;
WHILE i +:= 1;
i <= nd
DO
r *:= 10 +:= ( n MOD 10 );
n OVERAB 10
OD;
r
END # revn # ;
LONG INT nd := 2, count := 0, lim := 90, n := 20;
DO
n +:= 1;
LONG INT r = revn( n, nd );
IF r < n THEN
LONG INT s = n + r, d = n - r;
IF IF ODD nd
THEN d MOD 1089 = 0
ELSE s MOD 121 = 0
FI
THEN
IF LONG REAL root s = long sqrt( s );
root s = ENTIER root s
THEN
IF LONG REAL root d = long sqrt( d );
root d = ENTIER root d
THEN
count +:= 1;
print( ( whole( count, 0 ), ": ", whole( n, 0 ), newline ) );
IF count >= 5 THEN stop FI
FI
FI
FI;
IF n = lim
THEN
lim *:= 10;
nd +:= 1;
n := ( lim OVER 9 ) * 2
FI
FI
OD
</syntaxhighlight>
{{out}}
<pre>
1: 65
2: 621770
3: 281089082
4: 2022652202
5: 2042832002
</pre>
=={{header|C sharp|C#}}==
Line 31 ⟶ 91:
{{trans|Go}}
Converted to unsigned longs in order to reach 19 digits.
<
using System.Collections.Generic;
using System.Linq;
Line 125 ⟶ 185:
count = 0; foreach (var rare in res) WriteLine("{0,2}:{1,27:n0}", ++count, rare);
if (System.Diagnostics.Debugger.IsAttached) ReadKey(); }
}</
{{out}}
Results from a core i7-7700 @ 3.6Ghz. This C# version isn't as fast as the Go version using the same hardware. C# computes up to 17, 18 and 19 digits in under 9 minutes, 1 2/3 hours and over 2 1/2 hours respectively. (Go is about 6 minutes, 1 1/4 hours, and under 2 hours).
Line 304 ⟶ 364:
===Quicker===
Along the lines of the C++ version. Computing the possible squares for the sums and differences, then comparing them together and reporting the ones that have a proper forward, reverse result. To save computation time, some shortcuts have been taken to avoid generating many non-square numbers. <br/><br/>Update, added computation of digital root, which increased performance a few percentage points. Interestingly, the digital root is always zero for the ''difference list of squares'', so no advantage is given by tracking it. Only the ''sum list of squares'' benefits from calculating the digital root of the partial sum and using an abbreviated sequence for the last round of permutation.
<
using System.Collections.Generic; // for List<>, .Count
using System.Linq; // for .Last(), .ToList()
Line 489 ⟶ 549:
static bool IsRev(int nd, ulong f, ulong r) { nd--; return f / (ulong)p[nd] != r % 10 ? false : (nd < 1 ? true : IsRev(nd, f % (ulong)p[nd], r / 10)); }
#endregion 19
}</
{{out}}
Results on the core i7-7700 @ 3.6Ghz.
Line 576 ⟶ 636:
=={{header|C++}}==
===Calculate L and H independently===
<syntaxhighlight lang="cpp">
// Rare Numbers : Nigel Galloway - December 20th., 2019;
//
#include <functional>
#include <bitset>
#include <cmath>
using namespace std;
using Z2 = optional<long long>; using Z1 = function<Z2()>;
// powers of 10 array
constexpr
long long acc, l;
bool izRev(int n, unsigned long long i, unsigned long 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 long step, long long &l) {
return [n, i{step * start}, g{step * end}, e{step * reset}, &l, step] () mutable {
while (i<g){i+=step; return Z2(l+=step);}
l-=g-(i=e); return n();};
}
struct nLH {
vector<unsigned long long>even{}, odd{};
nLH(const Z1 a, const vector<long long> b, long long llim){while (auto i = a()) for (auto ng : b)
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);}}
};
const double fac = 3.94;
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;++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};
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(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);
}
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};
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 (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];}}}}}}
return q ? nLH(g,w,0) : nLH(g,{0},pow10[n-1]<<2);
}
#include <chrono>
using namespace chrono; using VU = vector<unsigned long long>; using VS = vector<string>;
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 c{0}; // solution counter
auto st{steady_clock::now()}, st0{st}, tmp{st}; // for determining elasped time
// 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;
}
// 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;
}
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);
}
</syntaxhighlight>
{{out}}
Processor Intel(R) Core(TM) i5-1035G1 CPU @ 1.00GHz
<pre>
nth forward rt.sum rt.diff digs block.et total.et
1 65 11 3 2: 0.00003s 0.00003s
3: 0.00002s 0.00006s
4: 0.00001s 0.00008s
5: 0.00003s 0.00011s
2 621770 836 738 6: 0.00007s 0.00018s
7: 0.00035s 0.00054s
8: 0.00110s 0.00164s
3 281089082 23708 330 9: 0.00657s 0.00821s
4 2022652202 63602 300
5 2042832002 63602 6360 10: 0.02246s 0.03068s
11: 0.11082s 0.14151s
6 868591084757 1275175 333333
7 872546974178 1320616 32670
8 872568754178 1320616 33330 12: 0.00868s 0.15019s
9 6979302951885 3586209 1047717 13: 0.03915s 0.18935s
10 20313693904202 6368252 269730
11 20313839704202 6368252 270270
12 20331657922202 6368252 329670
13 20331875722202 6368252 330330
14 20333875702202 6368252 336330
15 40313893704200 6368252 6330336
16 40351893720200 6368252 6336336 14: 0.11688s 0.30624s
17 200142385731002 20006998 69300
18 204238494066002 20122102 1891560
19 221462345754122 21045662 69300
21 245518996076442 22140228 921030
22 248359494187442 22206778 1891560
23 403058392434500 20211202 19940514
24 441054594034340 22011022 19940514
25 816984566129618 40421606 250800 15: 0.69490s 1.00114s
26 2078311262161202 64030648 7529850
27 2133786945766212 65272218 2666730
28 2135568943984212 65272218 3267330
29 2135764587964212 65272218 3326670
30 2135786765764212 65272218 3333330
32 6157577986646405 105849161 33333333
33 6889765708183410 83866464 82133718
34 8052956026592517 123312255 29999997
35 8052956206592517 123312255 30000003
36 8191154686620818 127950856 3299670
37 8191156864620818 127950856 3300330
38 8191376864400818 127950856 3366330
39 8650327689541457 127246955 33299667
40 8650349867341457 127246955 33300333 16: 2.18232s 3.18347s
41 22542040692914522 212329862 333300
42 67725910561765640 269040196 251135808
43 86965750494756968 417050956 33000 17: 13.1765s 16.3599s
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: 41.6983s 58.0583s
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: 5m1.342s 5m59.40s
</pre>
===20+ digits===
<
// Rare Numbers : Nigel Galloway - December 20th., 2019
#include <iostream>
Line 881 ⟶ 854:
Rare(20);
}
</syntaxhighlight>
{{out}}
<pre>
Line 928 ⟶ 901:
{{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.
<
import std.array;
import std.conv;
Line 1,140 ⟶ 1,113:
writefln(" %2d: %25s", i + 1, commatize(rare));
}
}</
{{out}}
<pre>Aggregate timings to process all numbers up to:
Line 1,240 ⟶ 1,213:
39: 8,650,327,689,541,457
40: 8,650,349,867,341,457</pre>
=={{header|EasyLang}}==
{{trans|Ring}}
<syntaxhighlight lang=easylang>
fastfunc next n .
while 1 = 1
n += 1
h = n
nrev = 0
while h > 0
nrev = nrev * 10 + h mod 10
h = h div 10
.
if sqrt (n + nrev) mod 1 = 0
if n - nrev >= 1 and sqrt (n - nrev) mod 1 = 0
return n
.
.
.
.
for cnt to 5
n = next n
print n
.
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
===The Function===
This solution demonstrates the concept described in [[Talk:Rare_numbers#30_mins_not_30_years]]. It doesn't use [[Cartesian_product_of_two_or_more_lists#Extra_Credit]]
<
// Find all Rare numbers with a digits. Nigel Galloway: September 18th., 2019.
let rareNums a=
Line 1,256 ⟶ 1,255:
|_->if n>(pown 10L (a-1)) then for l in (if a%2=0 then [0L] else [0L..9L]) do let g=l*(pown 10L (a/2)) in if izPS (n+i+2L*g) then yield (i+g,n+g)}
fN [0L..9L] [] (a/2) |> Seq.collect(List.rev >> fG 0L 0L (pown 10L (a-1)) 1L)
</syntaxhighlight>
===43 down===
<
let test n=
let t = System.Diagnostics.Stopwatch.StartNew()
Line 1,267 ⟶ 1,266:
[2..17] |> Seq.iter test
</syntaxhighlight>
{{out}}
<pre>
Line 1,330 ⟶ 1,329:
Elapsed Time: 11275839 ms for length 17
</pre>
=={{header|FreeBASIC}}==
Made some changes and added a simple test to speed things up. Results in about 1 minute.
{{trans|Phix}}
<syntaxhighlight lang="freebasic">Function revn(n As ULongInt, nd As ULongInt) As ULongInt
Dim As ULongInt r
For i As UInteger = 1 To nd
r = r * 10 + n Mod 10
n = n \ 10
Next i
Return r
End Function
Dim As UInteger nd = 2, count, lim = 90, n = 20
Do
n += 1
Dim As ULongInt r = revn(n,nd)
If r < n Then
Dim As ULongInt s = n + r, d = n - r
If nd And 1 Then
If d Mod 1089 <> 0 Then GoTo jump
Else
If s Mod 121 <> 0 Then GoTo jump
End If
If Frac(Sqr(s)) = 0 And Frac(Sqr(d)) = 0 Then
count += 1
Print count; ": "; n
If count = 5 Then Exit Do : End If
End If
End If
jump:
If n = lim Then
lim = lim * 10
nd += 1
n = (lim \ 9) * 2
End If
Loop
Print
Print "Done"
Sleep</syntaxhighlight>
{{out}}
<pre>1: 65
2: 621770
3: 281089082
4: 2022652202
5: 2042832002</pre>
=={{header|Go}}==
Line 1,336 ⟶ 1,383:
As the algorithm used does not generate the Rare numbers in order, a sorted list is also printed.
<
import (
Line 1,545 ⟶ 1,592:
fmt.Printf(" %2d: %25s\n", i+1, commatize(rare))
}
}</
{{output}}
Line 1,726 ⟶ 1,773:
{{trans|C#}}
Twice as quick as the first Go version though, despite being a faithful translation, a little slower than the C# and VB.NET versions.
<
import (
Line 2,272 ⟶ 2,319:
ftTime := formatTime(time.Since(tStart))
fmt.Printf("%2d: %s %s\n", nd, fbTime, ftTime)
}</
{{out}}
Line 2,367 ⟶ 2,414:
Curiously, the C++ program itself when compiled with g++ 7.5.0 (-std=c++17 -O3) on the same machine (and incorporating the same improvements) completes in just over 21 minutes though I understand that when using other C++ compilers (clang, mingw) it's much faster than this.
<
import (
Line 2,628 ⟶ 2,675:
bStart = time.Now() // restart block timing
}
}</
{{out}}
Line 2,707 ⟶ 2,754:
75 8,320,411,466,598,809,138 19: 00:12:48.590 00:15:14.316
</pre>
=={{header|J}}==
The following function determines whether a given integer is "rare", as can be seen in the sample output.
To use it to find rare numbers, one would simply apply it to each integer seriatim, and keep the numbers where its output is true (I.@:rare i. AS_HIGH_AS_YOU_WANT_TO_CHECK); but since these numbers are, well, rare, actually doing so would take a very long time.
<syntaxhighlight lang="j">rare =: ( np@:] *. (nbrPs rr) ) b10
np =: -.@:(-: |.) NB. Not palindromic
nbrPs =: > *. sdPs NB. n is Bigger than R and the perfect square constraint is satisfied
sdPs =: + *.&:ps - NB. n > rr and both their sum and difference are perfect squares
ps =: 0 = 1 | %: NB. Perfect square (integral sqrt)
rr =: 10&#.@:|. NB. Do note we do reverse the digits twice (once here, once in np)
b10 =: 10&#.^:_1 NB. Base 10 digits</syntaxhighlight>
{{out}}
<syntaxhighlight lang="j"> NB. From OEIS
R =: 65 621770 281089082 2022652202 2042832002 868591084757 872546974178 872568754178 6979302951885 20313693904202 20313839704202 20331657922202 20331875722202 20333875702202 40313893704200
rare"0 R
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1</syntaxhighlight>
=={{header|Java}}==
{{trans|Kotlin}}
<
import java.time.LocalDateTime;
import java.util.ArrayList;
Line 2,981 ⟶ 3,047:
}
}
}</
{{out}}
<pre>Aggregate timings to process all numbers up to:
Line 3,084 ⟶ 3,150:
=={{header|Julia}}==
{{trans|Go}}
<
struct Term
Line 3,257 ⟶ 3,323:
findrare()
</
Timings are on a 2.9 GHz i5 processor, 16 Gb RAM, under Windows 10.
<pre style="height:126ex;overflow:scroll">
Line 3,435 ⟶ 3,501:
=={{header|Kotlin}}==
{{trans|D}}
<
import java.time.LocalDateTime
import kotlin.math.sqrt
Line 3,672 ⟶ 3,738:
println(" %2d: %25s".format(i_rare.index + 1, commatize(i_rare.value)))
}
}</
{{out}}
<pre>Aggregate timings to process all numbers up to:
Line 3,772 ⟶ 3,838:
39: 8,650,327,689,541,457
40: 8,650,349,867,341,457</pre>
=={{header|Lambdatalk}}==
Just coding the definition of a rare number without any optimization.
<syntaxhighlight lang="Scheme">
{def lt_israre
{lambda {:n}
{let { {:n :n}
{:r {W.reverse :n}}
} {if {and {> :n :r}
{isInt {sqrt {+ :n :r}}}
{isInt {sqrt {- :n :r}}}}
then :n
else}}}}
-> lt_israre
{S.map lt_israre {S.serie 1 700000}}
-> 65 621770 // computed in 7650ms
Testing:
{S.map lt_israre {S.serie 1 280000000}}
-> ... crushes Firefox working in my small iPad Pro.
And so I ask javascript some help:
LAMBDATALK.DICT["js_israres"] = function() {
var args = arguments[0].trim().split(" "),
i0 = Number( args[0] ),
i1 = Number( args[1] ),
a = [];
var israre = function(n) {
var r = Number( n.toString().split("").reverse().join("") );
return (n > r) && (Number.isInteger(Math.sqrt(n+r)))
&& (Number.isInteger(Math.sqrt(n-r)))
};
for (var i=i0; i < i1; i++)
if (israre(i)) a.push(i);
return a
};
Testing:
{js_israres 1 2050000000}
-> [65,621770,281089082,2022652202,2042832002]]
// computed in 784307ms ~ 13 minutes
Too slow to try to go further.
</syntaxhighlight>
=={{header|langur}}==
=== not optimized ===
It could look something like the following (ignoring whatever optimizations the other examples are using), if it was fast enough. I did not have the time/processor to test finding the first 5. The
<syntaxhighlight lang="langur">
val
val
if
val
val
}
val
for[=[]]
if
_for ~= [
}
}
val findandprint = impure fn(mx) {
for[cnt=0] i = 0; cnt < mx ; i += 1 {
if israre(i) {
writeln "\n rare ", i, " "
cnt += 1
}
}
Line 3,799 ⟶ 3,925:
# if you have the time...
writeln "the first 5 rare numbers: ",
</syntaxhighlight>
=={{header|Lua}}==
{{Trans|Phix|niave version, via FreeBASIC and Algol 68}}
<syntaxhighlight lang="lua">
do -- find the first five rare numbers
local function revn ( na )
local n, r = na, 0
while n > 0 do
r = r * 10 r = r + ( n % 10 )
n = math.floor( n / 10 )
end
return r
end -- revn
local nd, count, lim, n = 2, 0, 90, 20
local oddNd = nd % 2 == 1
while true do
n = n + 1
local r = revn( n )
if r < n then
local s, d = n + r, n - r
local tryThis = false
if oddNd
then tryThis = d % 1089 == 0
else tryThis = s % 121 == 0
end
if tryThis then
local rootS = math.sqrt( s )
if rootS == math.floor(rootS )
then
local rootD = math.sqrt( d )
if rootD == math.floor( rootD )
then
count = count + 1
io.write( count, ": ", n, "\n" )
if count >= 5 then os.exit() end
end
end
end
if n == lim
then
lim = lim * 10
nd = nd + 1
oddNd = not oddNd
n = math.floor( lim / 9 ) * 2
end
end
end
end
</syntaxhighlight>
{{out}}
<pre>
1: 65
2: 621770
3: 281089082
4: 2022652202
5: 2042832002
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">c = Compile[{{k, _Integer}},
Module[{out = {0}, start = 0, stop = 0, rlist = {0}, r = 0,
sum = 0.0, diff = 0.0, imax = 8, step = 10},
Do[
If[j == k, imax = 2, imax = 8];
Do[
If[i == 2,
start = i 10^j + 2;
stop = (i + 1) 10^j - 1;
step = 10;
,
start = i 10^j;
stop = (i + 1) 10^j - 1;
step = 1;
];
Do[
rlist = IntegerDigits[n];
r = 0;
Do[
r += rlist[[ri]] 10^(ri - 1)
,
{ri, 1, Length[rlist]}
];
If[r != n,
sum = n + r;
sum = Sqrt[sum];
If[Floor[sum] == sum,
diff = n - r;
If[diff > 0,
diff = Sqrt[diff];
If[Floor[diff] == diff,
AppendTo[out, n]
]
]
]
]
,
{n, start, stop, step}
]
,
{i, 2, imax, 2}
]
,
{j, 0, k}
];
out
]
];
Rest[c[9]] (*takes about 310 sec*)</syntaxhighlight>
{{out}}
<pre>{65, 621770, 281089082, 2022652202, 2042832002}</pre>
=={{header|Nim}}==
{{trans|Go}}
Translation of the second Go version, limited to 18 digits.
<syntaxhighlight lang="nim">import algorithm, math, strformat, times
type Llst = seq[seq[int]]
const
# Powers of 10.
P = block:
var p: array[19, int64]
p[0] = 1i64
for i in 1..18: p[i] = 10 * p[i - 1]
p
# Digital root lookup array.
Drar = block:
var drar: array[19, int]
for i in 0..18: drar[i] = i shl 1 mod 9
drar
var
d: seq[int] # permutation working slice
dac: seq[int] # running digital root slice
ac: seq[int64] # accumulator slice
pp: seq[int64] # coefficient slice that combines with digits of working slice
sr: seq[int64] # temporary list of squares used for building
var
odd = false # flag for odd number of digits
sum: int64 # calculated sum of terms (square candidate)
cn = 0 # solution counter
nd = 2 # number of digits
nd1 = nd - 1 # 'nd' helper
ln: int # previous value of 'n' (in recurse())
dl: int # length of 'd' slice
func newIntSeq(f, t, s: int): seq[int] =
## Return a sequence of integers.
result = newSeq[int]((t - f) div s + 1)
var f = f
for i in 0..result.high:
result[i] = f
inc f, s
const
Tlo = @[0, 1, 4, 5, 6] # primary differences starting point
All = newIntSeq(-9, 9, 1) # all possible differences
Odl = newIntSeq(-9, 9, 2) # odd possible differences
Evl = newIntSeq(-8, 8, 2) # even possible differences
Thi = @[4, 5, 6, 9, 10, 11, 14, 15, 16] # primary sums starting point
Alh = newIntSeq(0, 18, 1) # all possible sums
Odh = newIntSeq(1, 17, 2) # odd possible sums
Evh = newIntSeq(0, 18, 2) # even possible sums
Ten = newIntSeq(0, 9, 1) # used for odd number of digits
Z = newIntSeq(0, 0, 1) # no difference, avoids generating a bunch of negative square candidates
T7 = @[-3, 7] # shortcut for low 5
Nin = @[9] # shortcut for hi 10
Tn = @[10] # shortcut for hi 0 (unused, unneeded)
T12 = @[2, 12] # shortcut for hi 5
O11 = @[1, 11] # shortcut for hi 15
Pos = @[0, 1, 4, 5, 6, 9] # shortcut for 2nd lo 0
var
lul: Llst = @[Z, Odl, @[], @[], Evl, T7, Odl] # shortcut lookup lo primary
luh: Llst = @[Tn, Evh, @[], @[], Evh, T12, Odh, @[], @[],
Evh, Nin, Odh, @[], @[], Odh, O11, Evh] # shortcut lookup hi primary
l2l: Llst = @[Pos, @[], @[], @[], All, @[], All] # shortcut lookup lo secondary
l2h: Llst = @[@[], @[], @[], @[], Alh, @[], Alh, @[], @[],
@[], Alh, @[], @[], @[], Alh, @[], Alh] # shortcut lookup hi secondary
chTen: Llst = @[@[0, 2, 5, 8, 9], @[0, 3, 4, 6, 9], @[1, 4, 7, 8],
@[2, 3, 5, 8], @[0, 3, 6, 7, 9], @[1, 2, 4, 7],
@[2, 5, 6, 8], @[0, 1, 3, 6, 9], @[1, 4, 5, 7]]
chAH: Llst = @[@[0, 2, 5, 8, 9, 11, 14, 17, 18], @[0, 3, 4, 6, 9, 12, 13, 15, 18],
@[1, 4, 7, 8, 10, 13, 16, 17], @[2, 3, 5, 8, 11, 12, 14, 17],
@[0, 3, 6, 7, 9, 12, 15, 16, 18], @[1, 2, 4, 7, 10, 11, 13, 16],
@[2, 5, 6, 8, 11, 14, 15, 17], @[0, 1, 3, 6, 9, 10, 12, 15, 18],
@[1, 4, 5, 7, 10, 13, 14, 16]]
var lu, l2: Llst
func isr(s: int64): int64 {.inline.} =
## Return integer square root.
int64(sqrt(float(s)))
proc isRev(nd: int; f, r: int64): bool =
## Recursively determines whether 'r' is the reverse of 'f'.
let nd = nd - 1
if f div P[nd] != r mod 10: return false
if nd < 1: return true
result = isRev(nd, f mod P[nd], r div 10)
proc recurseLE5(lst: Llst; lv: int) =
## Recursive function to evaluate the permutations, no shortcuts.
if lv == dl: # Check if on last stage of permutation.
sum = ac[lv - 1]
if sum > 0:
let rt = int64(sqrt(float(sum)))
if rt * rt == sum: sr.add sum
else:
for n in lst[lv]: # Set up next permutation.
d[lv] = n
if lv == 0: ac[0] = pp[0] * n
else: ac[lv] = ac[lv - 1] + pp[lv] * n # Update accumulated sum.
recurseLE5(lst, lv + 1) # Recursively call next level.
proc recursehi(lst: var Llst; lv: int) =
## Recursive function to evaluate the hi permutations.
## Shortcuts added to avoid generating many non-squares, digital root calc added.
let lv1 = lv - 1
if lv == dl: # Check if on last stage of permutation.
sum = ac[lv1]
if (0x202021202030213 and (1 shl (sum and 63))) != 0:
# Test accumulated sum, append to result if square.
let rt = int64(sqrt(float64(sum)))
if rt * rt == sum: sr.add sum
else:
for n in lst[lv]: # Set up next permutation.
d[lv] = n
if lv == 0:
ac[0] = pp[0] * n
dac[0] = Drar[n] # Update accumulated sum and running dr.
else:
ac[lv] = ac[lv1] + pp[lv] * n
dac[lv] = dac[lv1] + Drar[n]
if dac[lv] > 8: dec dac[lv], 9
case lv # Shortcuts to be performed on designated levels.
of 0: # Primary level: set shortcuts for secondary level.
ln = n
lst[1] = lu[ln]
lst[2] = l2[n]
of 1: # Secondary level: set shortcuts for tertiary level.
case ln # For sums.
of 5, 15: lst[2] = if n < 10: Evh else: Odh
of 9: lst[2] = if (n shr 1 and 1) == 0: Evh else: Odh
of 11: lst[2] = if (n shr 1 and 1) == 1: Evh else: Odh
else: discard
else: discard
if lv == dl - 2:
# Reduce last round according to dr calc.
lst[dl - 1] = if odd: chTen[dac[dl - 2]] else: chAH[dac[dl - 2]]
recursehi(lst, lv + 1) # Recursively call next level.
proc recurselo(lst: var Llst; lv: int) =
## Recursive function to evaluate the lo permutations.
## Shortcuts added to avoid generating many non-squares.
let lv1 = lv - 1
if lv == dl: # Check if on last stage of permutation.
sum = ac[lv1]
if sum > 0:
let rt = int64(sqrt(float64(sum)))
if rt * rt == sum: sr.add sum
else:
for n in lst[lv]: # Set up next permutation.
d[lv] = n
if lv == 0: ac[0] = pp[0] * n
else: ac[lv] = ac[lv1] + pp[lv] * n # Update accumulated sum.
case lv # Shortcuts to be performed on designated levels.
of 0: # Primary level: set shortcuts for secondary level.
ln = n
lst[1] = lu[ln]
lst[2] = l2[n]
of 1: # Secondary level: set shortcuts for tertiary level.
case ln # For difs.
of 1: lst[2] = if ((n + 9) shr 1 and 1) == 0: Evl else: Odl
of 5: lst[2] = if n < 0: Evl else: Odl
else: discard
else: discard
recurselo(lst, lv + 1) # Recursively call next level.
proc listEm(lst: var Llst; plu, pl2: Llst): seq[int64] =
## Produces a list of candidate square numbers.
dl = lst.len
d = newSeq[int](dl)
sr.setLen(0)
lu = plu
l2 = pl2
ac = newSeq[int64](dl)
dac = newSeq[int](dl)
pp = newSeq[int64](dl)
# Build coefficients array.
for i in 0..<dl:
pp[i] = if lst[0].len > 6: P[nd1 - i] + P[i] else: P[nd1 - i] - P[i]
# Call appropriate recursive function.
if nd <= 5: recurseLE5(lst, 0)
elif lst[0].len > 8: recursehi(lst, 0)
else: recurselo(lst, 0)
result = sr
proc reveal(lo, hi: openArray[int64]) =
## Reveal whether combining two lists of squares can produce a rare number.
var s: seq[string] # Temporary list of results.
for l in lo:
for h in hi:
let r = (h - l) shr 1
let f = h - r # Generate all possible fwd & rev candidates from lists.
if isRev(nd, f, r):
s.add &"{f:20} {isr(h):11} {isr(l):10} "
s.sort()
if s.len > 0:
for t in s:
inc cn
let tt = if t != s[^1]: "\n" else: ""
stdout.write &"{cn:2} {t}{tt}"
else:
stdout.write &"{\"\":48}"
func formatTime(d: Duration): string =
var f = d.inMilliseconds
var s = f div 1000
f = f mod 1000
var m = s div 60
s = s mod 60
let h = m div 60
m = m mod 60
result = &"{h:02}:{m:02}:{s:02}.{f:03}"
var
lls: Llst = @[Tlo]
hls: Llst = @[Thi]
var bstart, tstart = now()
echo &"""nth {"forward":>19} {"rt.sum":>11} {"rt.dif":>10} digs {"block time":>11} {"total time":>13}"""
while nd <= 18:
if nd > 2:
if odd:
hls.add Ten
else:
lls.add All
hls[^1] = Alh
reveal(listEm(lls, lul, l2l), listEm(hls, luh, l2h))
if not odd and nd > 5:
# Restore last element of hls, so that dr shortcut doesn't mess up next nd.
hls[^1] = Alh
let bTime = formatTime(now() - bstart)
let tTime = formatTime(now() - tstart)
echo &"{nd:2}: {bTime} {tTime}"
bstart = now() # Restart block timing.
nd1 = nd
inc nd
odd = not odd</syntaxhighlight>
{{out}}
<pre>nth forward rt.sum rt.dif digs block time total time
1 65 11 3 2: 00:00:00.000 00:00:00.000
3: 00:00:00.000 00:00:00.000
4: 00:00:00.000 00:00:00.000
5: 00:00:00.000 00:00:00.000
2 621770 836 738 6: 00:00:00.000 00:00:00.000
7: 00:00:00.000 00:00:00.001
8: 00:00:00.001 00:00:00.002
3 281089082 23708 330 9: 00:00:00.002 00:00:00.005
4 2022652202 63602 300
5 2042832002 63602 6360 10: 00:00:00.005 00:00:00.010
11: 00:00:00.040 00:00:00.051
6 868591084757 1275175 333333
7 872546974178 1320616 32670
8 872568754178 1320616 33330 12: 00:00:00.066 00:00:00.117
9 6979302951885 3586209 1047717 13: 00:00:00.486 00:00:00.603
10 20313693904202 6368252 269730
11 20313839704202 6368252 270270
12 20331657922202 6368252 329670
13 20331875722202 6368252 330330
14 20333875702202 6368252 336330
15 40313893704200 6368252 6330336
16 40351893720200 6368252 6336336 14: 00:00:00.968 00:00:01.572
17 200142385731002 20006998 69300
18 204238494066002 20122102 1891560
19 221462345754122 21045662 69300
20 244062891224042 22011022 1908060
21 245518996076442 22140228 921030
22 248359494187442 22206778 1891560
23 403058392434500 20211202 19940514
24 441054594034340 22011022 19940514
25 816984566129618 40421606 250800 15: 00:00:09.416 00:00:10.989
26 2078311262161202 64030648 7529850
27 2133786945766212 65272218 2666730
28 2135568943984212 65272218 3267330
29 2135764587964212 65272218 3326670
30 2135786765764212 65272218 3333330
31 4135786945764210 65272218 63333336
32 6157577986646405 105849161 33333333
33 6889765708183410 83866464 82133718
34 8052956026592517 123312255 29999997
35 8052956206592517 123312255 30000003
36 8191154686620818 127950856 3299670
37 8191156864620818 127950856 3300330
38 8191376864400818 127950856 3366330
39 8650327689541457 127246955 33299667
40 8650349867341457 127246955 33300333 16: 00:00:18.483 00:00:29.472
41 22542040692914522 212329862 333300
42 67725910561765640 269040196 251135808
43 86965750494756968 417050956 33000 17: 00:02:49.293 00:03:18.766
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: 00:05:45.616 00:09:04.383</pre>
=={{header|Perl}}==
<syntaxhighlight lang="perl">#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Rare_numbers
use warnings;
use integer;
my $count = 0;
my @squares;
for my $large ( 0 .. 1e5 )
{
my $largesquared = $squares[$large] = $large * $large; # $large ** 2;
for my $small ( 0 .. $large - 1 )
{
my $n = $largesquared + $squares[$small];
2 * $large * $small == reverse $n or next;
printf "%12s %s\n", $n, scalar reverse $n;
$n == reverse $n and die "oops!"; # palindrome check
++$count >= 5 and exit;
}
}</syntaxhighlight>
{{out}}
<pre>
65 56
621770 077126
281089082 280980182
2022652202 2022562202
2042832002 2002382402
</pre>
=={{header|Phix}}==
===naive===
Ridiculously slow, 90s just for the first 3, though twice as fast (41s) under p2js.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">revn</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">nd</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">nd</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">99</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">revn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nd</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;"><</span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">r</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d: %d (%s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">lim</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- ?{"lim",lim,elapsed(time()-t0)}</span>
<span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lim</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span><span style="color: #0000FF;">+</span><span style="color: #000000;">9</span>
<span style="color: #000000;">nd</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 3,844 ⟶ 4,428:
{3,281089082,"1 minute and 29s"}
</pre>
===advanced===
{{trans|VB.NET}}
Line 3,852 ⟶ 4,437:
for over 30% of the run time. Improvements welcome: run p -d test, examine the list.asm produced from this source, and discuss or
make suggestions on [[User_talk:Petelomax|my talk page]].
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">maxDigits</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">10</span><span style="color: #0000FF;">:</span><span style="color: #000000;">15</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">COEFF</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">TDXA</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">TDXB</span> <span style="color: #000080;font-style:italic;">-- struct term = {atom coeff, integer idxa, idxb}
-- (see allTerms below)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nd</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- number of digits</span>
<span style="color: #000000;">count</span> <span style="color: #000080;font-style:italic;">-- of solutions found earlier, for lower nd</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rares</span> <span style="color: #000080;font-style:italic;">-- (cleared after sorting/printing for each nd)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">to_atom</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- convert digits array to an atom value</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">10</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #000080;font-style:italic;">-- psq eliminates 52 out of 64 of numbers fairly cheaply, which translates
-- to approximately 66% of numbers, or around 10% off the overall time.
-- NB: only tested to 9,007,199,254,740,991, then again I found no more new
-- bit patterns after just 15^2.</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">psq</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">int_to_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">#02030213</span><span style="color: #0000FF;">,</span><span style="color: #000000;">32</span><span style="color: #0000FF;">)&</span> <span style="color: #000080;font-style:italic;">-- #0202021202030213 --> bits,</span>
<span style="color: #7060A8;">int_to_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">#02020212</span><span style="color: #0000FF;">,</span><span style="color: #000000;">32</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- in 32/64-bit compatible way.</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">isSquare</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- determine if n is a perfect square or not</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">psq</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">63</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">fnpr</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">nmr</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">di</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dis</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">candidates</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">indices</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fml</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dmd</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- generate (n+r) candidates from (n-r) candidates</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dis</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nd</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- (the precise why of how this populates digits has eluded me...)</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">indices</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">candidates</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">di</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">a</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">fml</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">][</span><span style="color: #000000;">d</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">b</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">fml</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">][</span><span style="color: #000000;">d</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">le</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">di</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nd</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">di</span><span style="color: #0000FF;">[</span><span style="color: #000000;">le</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">le</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">le</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">indices</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">candidates</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">10</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">di</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">a</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dmd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">][</span><span style="color: #000000;">d</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">b</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dmd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">][</span><span style="color: #000000;">d</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">npr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nmr</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">to_atom</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">))*</span><span style="color: #000000;">2</span> <span style="color: #000080;font-style:italic;">-- (npr == 'n + r')</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">isSquare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">npr</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">rares</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">to_atom</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- (note this gets overwritten by sorted set:)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"working... %2d: %,d\r"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rares</span><span style="color: #0000FF;">),</span><span style="color: #000000;">rares</span><span style="color: #0000FF;">[$]})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">di</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">di</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">dis</span><span style="color: #0000FF;">[</span><span style="color: #000000;">level</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">di</span><span style="color: #0000FF;">[</span><span style="color: #000000;">level</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #000000;">fnpr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">level</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nmr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">di</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dis</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">candidates</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">indices</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fml</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dmd</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">fnmr</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">terms</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">list</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">candidates</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">indices</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fml</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dmd</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- generate (n-r) candidates with a given number of digits.</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">list</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">nmr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- (nmr == 'n - r')</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">terms</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">nmr</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">terms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">COEFF</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">candidates</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nmr</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">isSquare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nmr</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">candidates</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fml</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">])-</span><span style="color: #000000;">1</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">dis</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">l</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">candidates</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">candidates</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">10</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dmd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">])-</span><span style="color: #000000;">1</span>
<span style="color: #000000;">dis</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dis</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">dis</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dis</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- (above generates dis of eg {1,4,7,9} for nd=7, which as far
-- as I (lightly) understand it scans for far fewer candidate
-- pairs than a {9,9,9,9} would, or something like that.)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">di</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dis</span><span style="color: #0000FF;">))</span>
<span style="color: #000080;font-style:italic;">-- (di is the current "dis-scan", eg {0,0,0,0} to {1,4,7,9})</span>
<span style="color: #000000;">fnpr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nmr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">di</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dis</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">candidates</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">indices</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fml</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dmd</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">candidates</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">candidates</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">list</span><span style="color: #0000FF;">[</span><span style="color: #000000;">level</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">candidates</span><span style="color: #0000FF;">[</span><span style="color: #000000;">level</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">list</span><span style="color: #0000FF;">[</span><span style="color: #000000;">level</span><span style="color: #0000FF;">][</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">fnmr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">terms</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">list</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">candidates</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">indices</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fml</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dmd</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">dl</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">9</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- all differences (-9..+9 by 1)</span>
<span style="color: #000000;">zl</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- zero difference (0 only)</span>
<span style="color: #000000;">el</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- even differences (-8 to +8 by 2)</span>
<span style="color: #000000;">ol</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- odd differences (-9..+9 by 2)</span>
<span style="color: #000000;">il</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- all integers (0..9 by 1)</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">start</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #000080;font-style:italic;">-- terms of (n-r) expression for number of digits from 2 to maxdigits</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">allTerms</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">pow</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">maxDigits</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">terms</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #000000;">pow</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">10</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">p1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pow</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">tdxa</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tdxb</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">tdxa</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">tdxb</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">terms</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">terms</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tdxa</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tdxb</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- {COEFF,TDXA,TDXB}</span>
<span style="color: #000000;">p1</span> <span style="color: #0000FF;">/=</span> <span style="color: #000000;">10</span>
<span style="color: #000000;">p2</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">10</span>
<span style="color: #000000;">tdxa</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">tdxb</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">allTerms</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">allTerms</span><span style="color: #0000FF;">,</span><span style="color: #000000;">terms</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">--/*
--(This is what the above loop creates:)
--pp(allTerms,{pp_Nest,1,pp_StrFmt,3,pp_IntCh,false,pp_IntFmt,"%d",pp_FltFmt,"%d",pp_Maxlen,148})
<nowiki>{{</nowiki>{9,0,1<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>99,0,2<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>999,0,3}, {90,1,2<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>9999,0,4}, {990,1,3<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>99999,0,5}, {9990,1,4}, {900,2,3<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>999999,0,6}, {99990,1,5}, {9900,2,4<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>9999999,0,7}, {999990,1,6}, {99900,2,5}, {9000,3,4<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>99999999,0,8}, {9999990,1,7}, {999900,2,6}, {99000,3,5<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>999999999,0,9}, {99999990,1,8}, {9999900,2,7}, {999000,3,6}, {90000,4,5<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>9999999999,0,10}, {999999990,1,9}, {99999900,2,8}, {9999000,3,7}, {990000,4,6<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>99999999999,0,11}, {9999999990,1,10}, {999999900,2,9}, {99999000,3,8}, {9990000,4,7}, {900000,5,6<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>999999999999,0,12}, {99999999990,1,11}, {9999999900,2,10}, {999999000,3,9}, {99990000,4,8}, {9900000,5,7<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>9999999999999,0,13}, {999999999990,1,12}, {99999999900,2,11}, {9999999000,3,10}, {999990000,4,9}, {99900000,5,8}, {9000000,6,7<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>99999999999999,0,14}, {9999999999990,1,13}, {999999999900,2,12}, {99999999000,3,11}, {9999990000,4,10}, {999900000,5,9}, {99000000,6,8<nowiki>}}</nowiki>}
--*/
-- map of first minus last digits for 'n' to pairs giving this value</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">fml</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({},</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (aka 0..9)
-- (fml == 'first minus last')</span>
<span style="color: #000000;">fml</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">}}</span>
<span style="color: #000000;">fml</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">}}</span>
<span style="color: #000000;">fml</span><span style="color: #0000FF;">[</span><span style="color: #000000;">5</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">}}</span>
<span style="color: #000080;font-style:italic;">-- fml[6] = <nowiki>{{</nowiki>8, 3<nowiki>}}</nowiki> -- (um? - needs longer lists, & that append(lists[4],dl) below)</span>
<span style="color: #000000;">fml</span><span style="color: #0000FF;">[</span><span style="color: #000000;">7</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">}}</span>
<span style="color: #000080;font-style:italic;">-- sequence lists = <nowiki>{{</nowiki>{0<nowiki>}}</nowiki>,<nowiki>{{</nowiki>1<nowiki>}}</nowiki>,<nowiki>{{</nowiki>4<nowiki>}}</nowiki>,<nowiki>{{</nowiki>5<nowiki>}}</nowiki>,<nowiki>{{</nowiki>6<nowiki>}}</nowiki>}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">lists</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">}}}</span>
<span style="color: #000080;font-style:italic;">-- map of other digit differences for 'n' to pairs giving this value</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">dmd</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({},</span><span style="color: #000000;">19</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (aka -9..+9, so add 10 when indexing dmd)
-- (dmd == 'digit minus digit')</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">tens</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tens</span><span style="color: #0000FF;">+</span><span style="color: #000000;">10</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">ones</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">dmd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dmd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">],</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">tens</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ones</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">--/*
--(This is what the above loop creates:)
--pp(dmd,{pp_Nest,1,pp_StrFmt,3,pp_IntCh,false})
<nowiki>{{</nowiki>{0,9<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>0,8}, {1,9<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>1,0}, {2,1}, {3,2}, {4,3}, {5,4}, {6,5}, {7,6}, {8,7}, {9,8<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>2,0}, {3,1}, {4,2}, {5,3}, {6,4}, {7,5}, {8,6}, {9,7<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>3,0}, {4,1}, {5,2}, {6,3}, {7,4}, {8,5}, {9,6<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>4,0}, {5,1}, {6,2}, {7,3}, {8,4}, {9,5<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>5,0}, {6,1}, {7,2}, {8,3}, {9,4<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>6,0}, {7,1}, {8,2}, {9,3<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>7,0}, {8,1}, {9,2<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>8,0}, {9,1<nowiki>}}</nowiki>,
<nowiki>{{</nowiki>9,0<nowiki>}}</nowiki>}
--*/</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"digits time nth rare numbers:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">nd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">nd</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">maxDigits</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">rares</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">terms</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">allTerms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nd</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nd</span><span style="color: #0000FF;">=</span><span style="color: #000000;">4</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">lists</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lists</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">zl</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">lists</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lists</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">ol</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">lists</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lists</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">],</span><span style="color: #000000;">el</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- lists[4] = append(lists[4],dl) -- if fml[6] = <nowiki>{{</nowiki>8, 3<nowiki>}}</nowiki>
-- lists[5] = append(lists[5],ol) -- ""
-- lists[4] = append(lists[4],ol) -- else</span>
<span style="color: #000000;">lists</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lists</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4</span><span style="color: #0000FF;">]),</span><span style="color: #000000;">ol</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- else</span>
<span style="color: #008080;">elsif</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">terms</span><span style="color: #0000FF;">)></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lists</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lists</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">--
<span style="color: #000000;">lists</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lists</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]),</span><span style="color: #000000;">dl</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">indices</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">terms</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">term</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">terms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">]</span>
<span style="color: #000080;font-style:italic;">-- (we may as well make this 1-based while here)</span>
<span style="color: #000000;">indices</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">indices</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">term</span><span style="color: #0000FF;">[</span><span style="color: #000000;">TDXA</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">term</span><span style="color: #0000FF;">[</span><span style="color: #000000;">TDXB</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lists</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">list</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lists</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">candidates</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">list</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">fnmr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">terms</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">list</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">candidates</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">indices</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fml</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dmd</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- (re-)output partial results for this nd-set in sorted order:
-- rares = sort(rares)</span>
<span style="color: #000000;">rares</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rares</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rares</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%12s %2d: %,19d \n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rares</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" %2d %5s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">nd</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">elapsed_short</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">start</span><span style="color: #0000FF;">)})</span>
<span style="color: #000000;">nd</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 4,125 ⟶ 4,720:
15 10:42
</pre>
=={{header|Python}}==
===naive===
A simple implementation, just to show how elegant python can be. Searches up to 10^11 in about 3hours w/ pypy on my Intel Core i5.
<syntaxhighlight lang="python">
# rare.py
# find rare numbers
# by kHz
from math import floor, sqrt
from datetime import datetime
def main():
start = datetime.now()
for i in xrange(1, 10 ** 11):
if rare(i):
print "found a rare:", i
end = datetime.now()
print "time elapsed:", end - start
def is_square(n):
s = floor(sqrt(n + 0.5))
return s * s == n
def reverse(n):
return int(str(n)[::-1])
def is_palindrome(n):
return n == reverse(n)
def rare(n):
r = reverse(n)
return (
not is_palindrome(n) and
n > r and
is_square(n+r) and is_square(n-r)
)
if __name__ == '__main__':
main()
</syntaxhighlight>
===hodgepodge optimized===
A mess of code that can return the first 5 rare numbers in 1m19s on a i7-7700k using pypy3.9.
<syntaxhighlight lang="python">
# rare.py
# by xing216
import time as t
from functools import cache
@cache
def isSquare(n: int) ->bool:
if n < 0:
return False
if n == 0:
return True
while n&3 == 0:
n=n>>2
if n&7 != 1:
return False
if n==1:
return True
c = n%10
if c in {3, 7}:
return False
if n % 7 in {3, 5, 6}:
return False
if n % 9 in {2,3,5,6,8}:
return False
if n % 13 in {2,5,6,7,8,11}:
return False
if c == 5:
if (n//10)%10 != 2:
return False
if (n//100)%10 not in {0,2,6}:
return False
if (n//100)%10 == 6:
if (n//1000)%10 not in {0,5}:
return False
else:
if (n//10)%4 != 0:
return False
s = (len(str(n))-1) // 2
x = (10**s) * 4
A = {x, n}
while x * x != n:
x = (x + (n // x)) >> 1
if x in A:
return False
A.add(x)
return True
@cache
def main() -> None:
r = 1
start = t.time()
while True:
strr = str(r)
if int(strr[0]) % 2 != 0:
r += int('1' + (len(strr)-1)*'0' )
r1 = int(strr[::-1])
x = r + r1
y = r - r1
if isSquare(x) and isSquare(y) and r != r1:
print(f'success: {r} ~{t.time()-start}s')
r+=1
if __name__ == '__main__':
main()
</syntaxhighlight>
=={{header|Quackery}}==
Naive version.
Timings for Quackery running on PyPy3 on one core of a 3 GHz 6-Core Intel Core i5 Mac mini at 100%.
First result; less than a second. Second result; less than five minutes (possibly a lot less - I went to make a cup of tea), third result; more than twelve and less than fifteen hours. At this point I estimated from other timings on this page that getting the fourth and fifth results would take about a week and killed the process. :-(
On the other hand; code development time, less than five minutes. :-)
<syntaxhighlight lang="quackery">[ dup 1
[ 2dup > while
+ 1 >>
2dup / again ]
drop nip ] is sqrt ( n --> n )
[ dup sqrt 2 ** = not ] is !square ( n --> b )
[ number$ reverse
$->n drop ] is revnumber ( n --> n )
[ 0 swap
[ base share /mod
rot + swap
dup 0 = until ]
drop ] is digitalroot ( n --> n )
[ true swap
dup revnumber
2dup > not iff
[ 2drop not ] done
2dup + !square iff
[ 2drop not ] done
2dup - !square iff
[ 2drop not ] done
2drop ] is rare ( n --> b )
[ 0
[ 1+ dup rare if
[ dup echo cr
dip [ 1 - ] ]
over 0 = until ]
2drop ] is echorarenums ( n --> b )
5 echorarenums</syntaxhighlight>
{{Out}}
<pre>5
621770
281089082</pre>
=={{header|Racket}}==
===naive===
<syntaxhighlight lang="racket" line>; 20231024 Racket programming naive solution
#lang racket
(require control)
(require text-block/text)
(define (is-palindrome n)
(define (digit-list n)
(if (zero? n)
'()
(cons (remainder n 10) (digit-list (quotient n 10)))))
(define (reverse-list lst)
(if (null? lst)
'()
(append (reverse-list (cdr lst)) (list (car lst)))))
(define digits (digit-list n))
(equal? digits (reverse-list digits)))
(define (perfect-square? n)
(if (rational? (sqrt n))
(= n (expt (floor (sqrt n)) 2))
false))
(define (reverse-number n)
(string->number (string-reverse (number->string n))))
(define (find-rare-numbers count)
(define rare-numbers '())
(define i 1)
(define (is-rare? n)
(and (not (is-palindrome n))
(let* ((r (reverse-number n))
(sum (+ n r))
(diff (- n r)))
(and (perfect-square? sum)
(perfect-square? diff)))))
(define start-time (current-inexact-milliseconds))
(while (< (length rare-numbers) count)
(cond [(is-rare? i)
(displayln (format "Number: ~a | Elapsed time: ~a ms" i (round (- (current-inexact-milliseconds) start-time))))
(set! rare-numbers (cons i rare-numbers))])
(set! i (+ i 1)))
(reverse rare-numbers))
(displayln "The first 5 rare numbers are:")
(for-each (λ (x) (display x) (display "\n")) (find-rare-numbers 5))
</syntaxhighlight>
=={{header|Raku}}==
===Translation of Rust===
{{trans|Rust}}
<syntaxhighlight lang="raku" line># 20220315 Raku programming solution
sub rare (\target where ( target > 0 and target ~~ Int )) {
my \digit = $ = 2;
my $count = 0;
my @numeric_digits = 0..9 Z, 0 xx *;
my @diffs1 = 0,1,4,5,6;
# all possible digits pairs to calculate potential diffs
my @pairs = 0..9 X 0..9;
my @all_diffs = -9..9;
# lookup table for the first diff
my @lookup_1 = [ [[2, 2], [8, 8]], # Diff = 0
[[8, 7], [6, 5]], # Diff = 1
[],
[],
[[4, 0], ], # Diff = 4
[[8, 3], ], # Diff = 5
[[6, 0], [8, 2]], ]; # Diff = 6
# lookup table for all the remaining diffs
given my %lookup_n { for @pairs -> \pair { $_{ [-] pair.values }.push: pair } }
loop {
my @powers = 10 <<**<< (0..digit-1); # powers like 1, 10, 100, 1000....
# for n-r (aka L) the required terms, like 9/ 99 / 999 & 90 / 99999 & 9999 & 900 etc
my @terms = (@powers.reverse Z- @powers).grep: * > 0 ;
# create a cartesian product for all potential diff numbers
# for the first use the very short one, for all other the complete 19 element
my @diff_list = digit == 2 ?? @diffs1 !! [X] @diffs1, |(@all_diffs xx digit div 2 - 1);
my @diff_list_iter = gather for @diff_list -> \k {
# remove invalid first diff/second diff combinations
{ take k andthen next } if k.elems == 1 ;
given (my (\a,\b) = k.values) {
when a == 0 && b != 0 { next }
when a == 1 && b ∉ [ -7, -5, -3, -1, 1, 3, 5, 7 ] { next }
when a == 4 && b ∉ [ -8, -6, -4, -2, 0, 2, 4, 6, 8 ] { next }
when a == 5 && b ∉ [ -3, 7 ] { next }
when a == 6 && b ∉ [ -9, -7, -5, -3, -1, 1, 3, 5, 7, 9 ] { next }
default { take k }
}
}
for @diff_list_iter -> \diffs {
# calculate difference of original n and its reverse (aka L = n-r)
# which must be a perfect square
if (my \L = [+] diffs <<*>> @terms) > 0 and { $_ == $_.Int }(L.sqrt) {
# potential candiate, at least L is a perfect square
# placeholder for the digits
my \dig = @ = 0 xx digit;
# generate a cartesian product for each identified diff using the lookup tables
my @c_iter = digit == 2
?? @lookup_1[diffs[0]].map: { [ $_ ] }
!! [X] @lookup_1[diffs[0]], |(1..(+diffs + (digit % 2 - 1))).map: -> \k {
k == diffs ?? @numeric_digits !! %lookup_n{diffs[k]} }
# check each H (n+r) by using digit combination
for @c_iter -> \elt {
for elt.kv -> \i, \pair { dig[i,digit-1-i] = pair.values }
# for numbers with odd # digits restore the middle digit
# which has been overwritten at the end of the previous cycle
dig[(digit - 1) div 2] = elt[+elt - 1][0] if digit % 2 == 1 ;
my \rev = ( my \num = [~] dig ).flip;
if num > rev and { $_ == $_.Int }((num+rev).sqrt) {
printf "%d: %12d reverse %d\n", $count+1, num, rev;
exit if ++$count == target;
}
}
}
}
digit++
}
}
my $N = 5;
say "The first $N rare numbers are,";
rare $N;</syntaxhighlight>
{{Out}}
<pre>The first 5 rare numbers are,
1: 65 reverse 56
2: 621770 reverse 77126
3: 281089082 reverse 280980182
4: 2022652202 reverse 2022562202
5: 2042832002 reverse 2002382402</pre>
===Using NativeCall with Rust===
This example will make use of a modified version of the 'advanced' routine from the Rust entry.
<syntaxhighlight lang="bash">~> cargo new --lib Rare && cd $_
Created library `Rare` package</syntaxhighlight>
Add to the stock manifest file, Cargo.toml, all required dependencies and build target,
<syntaxhighlight lang="bash">~/Rare> tail -5 Cargo.toml
[dependencies]
itertools = "0.10.3"
[lib]
crate-type = ["cdylib"]</syntaxhighlight>
Now replace the src/lib.rs file with the following,
lib.rs
<syntaxhighlight lang="rust">use itertools::Itertools;
use std::collections::HashMap;
fn isqrt(n: u64) -> u64 {
let mut s = (n as f64).sqrt() as u64;
s = (s + n / s) >> 1;
if s * s > n {
s - 1
} else {
s
}
}
fn is_square(n: u64) -> bool {
match n & 0xf {
0 | 1 | 4 | 9 => {
let t = isqrt(n);
t * t == n
}
_ => false,
}
}
#[no_mangle]
/// This algorithm uses an advanced search strategy based on Nigel Galloway's approach
pub extern "C" fn advanced64(target: u8) -> *mut u64 {
// setup
let digit = 2u8;
let mut results = Vec::new();
let mut counter = 0_u8;
let numeric_digits = (0..=9).map(|x| [x, 0]).collect::<Vec<_>>();
let diffs1: Vec<i8> = vec![0, 1, 4, 5, 6];
// all possible digits pairs to calculate potential diffs
let pairs = (0_i8..=9)
.cartesian_product(0_i8..=9)
.map(|x| [x.0, x.1])
.collect::<Vec<_>>();
let all_diffs = (-9i8..=9).collect::<Vec<_>>();
// lookup table for the first diff
let lookup_1 = vec![
vec![[2, 2], [8, 8]], //Diff = 0
vec![[8, 7], [6, 5]], //Diff = 1
vec![],
vec![],
vec![[4, 0]], // Diff = 4
vec![[8, 3]], // Diff = 5
vec![[6, 0], [8, 2]], // Diff = 6
];
// lookup table for all the remaining diffs
let lookup_n: HashMap<i8, Vec<_>> = pairs.into_iter().into_group_map_by(|elt| elt[0] - elt[1]);
let mut d = digit;
while target > counter {
// powers like 1, 10, 100, 1000....
let powers = (0..d).map(|x| 10_u64.pow(x.into())).collect::<Vec<u64>>();
// for n-r (aka L) the required terms, like 9/ 99 / 999 & 90 / 99999 & 9999 & 900 etc
let terms = powers
.iter()
.zip(powers.iter().rev())
.map(|(a, b)| b.checked_sub(*a).unwrap_or(0))
.filter(|x| *x != 0)
.collect::<Vec<u64>>();
// create a cartesian product for all potential diff numbers
// for the first use the very short one, for all other the complete 19 element
let diff_list_iter = (0_u8..(d / 2))
.map(|i| match i {
0 => diffs1.iter(),
_ => all_diffs.iter(),
})
.multi_cartesian_product()
// remove invalid first diff/second diff combinations - custom iterator would be probably better
.filter(|x| {
if x.len() == 1 {
return true;
}
match (*x[0], *x[1]) {
(a, b) if (a == 0 && b != 0) => false,
(a, b) if (a == 1 && ![-7, -5, -3, -1, 1, 3, 5, 7].contains(&b)) => false,
(a, b) if (a == 4 && ![-8, -6, -4, -2, 0, 2, 4, 6, 8].contains(&b)) => false,
(a, b) if (a == 5 && ![7, -3].contains(&b)) => false,
(a, b) if (a == 6 && ![-9, -7, -5, -3, -1, 1, 3, 5, 7, 9].contains(&b)) => {
false
}
_ => true,
}
});
'OUTER: for diffs in diff_list_iter {
// calculate difference of original n and its reverse (aka L = n-r)
// which must be a perfect square
let l: i64 = diffs
.iter()
.zip(terms.iter())
.map(|(diff, term)| **diff as i64 * *term as i64)
.sum();
if l > 0 && is_square(l.try_into().unwrap()) {
// potential candiate, at least L is a perfect square
// placeholder for the digits
let mut dig: Vec<i8> = vec![0_i8; d.into()];
// generate a cartesian product for each identified diff using the lookup tables
let c_iter = (0..(diffs.len() + d as usize % 2))
.map(|i| match i {
0 => lookup_1[*diffs[0] as usize].iter(),
_ if i != diffs.len() => lookup_n.get(diffs[i]).unwrap().iter(),
_ => numeric_digits.iter(), // for the middle digits
})
.multi_cartesian_product();
// check each H (n+r) by using digit combination
c_iter.for_each(|elt| {
for (i, digit_pair) in elt.iter().enumerate() {
dig[i] = digit_pair[0];
dig[d as usize - 1 - i] = digit_pair[1]
}
// for numbers with odd # digits restore the middle digit
// which has been overwritten at the end of the previous cycle
if d % 2 == 1 {
dig[(d as usize - 1) / 2] = elt[elt.len() - 1][0];
}
let num = dig
.iter()
.rev()
.enumerate()
.fold(0_u64, |acc, (i, d)| acc + 10_u64.pow(i as u32) * *d as u64);
let reverse = dig
.iter()
.enumerate()
.fold(0_u64, |acc, (i, d)| acc + 10_u64.pow(i as u32) * *d as u64);
if num > reverse && is_square(num + reverse) {
counter += 1;
results.push(num);
}
});
if counter == target {
break 'OUTER;
}
}
}
d += 1
}
let ptr = results.as_mut_ptr();
std::mem::forget(results); // circumvent the destructor
ptr
}</syntaxhighlight>
The needful shared library will be available after the build command,
<syntaxhighlight lang="bash">~/Rare> cargo build
~/Rare> file target/debug/libRare.so
target/debug/libRare.so: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, BuildID[sha1]=4f904cce7f8e82130826bf46f93fe9fe944ab9d0, with debug_info, not stripped</syntaxhighlight>
Here is the main Raku program,
<syntaxhighlight lang="raku" line>
use NativeCall;
constant LIB = '/home/hkdtam/Rare/target/debug/libRare.so';
sub advanced64(uint8) returns Pointer[uint64] is native(LIB) {*}
my $N = 5;
say "The first $N rare numbers are,";
for (advanced64 $N)[^$N].kv -> \nth,\rare {
printf "%d: %12d reverse %d\n", nth+1, { $_, $_.flip }(rare)
}</syntaxhighlight>
Output is the same.
=={{header|REXX}}==
Line 4,133 ⟶ 5,236:
These improvements made this REXX version around '''25%''' faster than the previous version (see the discussion page).
<
numeric digits 20; w= digits() + digits() % 3 /*use enough dec. digs for calculations*/
parse arg many . /*obtain optional argument from the CL.*/
Line 4,214 ⟶ 5,317:
iSqrt: parse arg x; $= 0; q= 1; do while q<=x; q=q*4; end
do while q>1; q=q%4; _= x-$-q; $= $%2; if _>=0 then do; x=_; $=$+q; end
end /*while q>1*/; return $</
{{out|output|text= when using the input of: <tt> 8 </tt>}}
<pre>
Line 4,225 ⟶ 5,328:
7th rare number is: 872,546,974,178
8th rare number is: 872,568,754,178
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
load "stdlib.ring"
see "working..." + nl
see "the first 5 rare numbers are:" + nl
num = 0
for n = 1 to 2042832002
strn = string(n)
nrev = ""
for m = len(strn) to 1 step -1
nrev = nrev + strn[m]
next
nrev = number(nrev)
sum = n + nrev
diff = n - nrev
if diff < 1
loop
ok
sqrtsum = sqrt(sum)
flagsum = (sqrtsum = floor(sqrtsum))
sqrtdiff = sqrt(diff)
flagdiff= (sqrtdiff = floor(sqrtdiff))
if flagsum = 1 and flagdiff = 1
num = num + 1
see "" + num + ": " + n + nl
ok
next
see "done..." + nl
</syntaxhighlight>
{{out}}
<pre>
working...
the first 5 rare numbers are:
1: 65
2: 621770
3: 281089082
4: 2022652202
5: 2042832002
done...
</pre>
=={{header|Ruby}}==
{{trans|Kotlin}}
Not sure where, but there seems to be a bug that introduces false rare numbers as output beyond what is shown
<syntaxhighlight lang="ruby">Term = Struct.new(:coeff, :ix1, :ix2) do
end
MAX_DIGITS = 16
def toLong(digits, reverse)
sum = 0
if reverse then
i = digits.length - 1
while i >=0
sum = sum *10 + digits[i]
i = i - 1
end
else
i = 0
while i < digits.length
sum = sum * 10 + digits[i]
i = i + 1
end
end
return sum
end
def isSquare(n)
root = Math.sqrt(n).to_i
return root * root == n
end
def seq(from, to, step)
res = []
i = from
while i <= to
res << i
i = i + step
end
return res
end
def format_number(number)
number.to_s.reverse.gsub(/(\d{3})(?=\d)/, '\\1,').reverse
end
def main
pow = 1
allTerms = []
for i in 0 .. MAX_DIGITS - 2
allTerms << []
end
for r in 2 .. MAX_DIGITS
terms = []
pow = pow * 10
pow1 = pow
pow2 = 1
i1 = 0
i2 = r - 1
while i1 < i2
terms << Term.new(pow1 - pow2, i1, i2)
pow1 = (pow1 / 10).to_i
pow2 = pow2 * 10
i1 = i1 + 1
i2 = i2 - 1
end
allTerms[r - 2] = terms
end
# map of first minus last digits for 'n' to pairs giving this value
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
dmd = {}
for i in 0 .. 99
a = [(i / 10).to_i, (i % 10)]
d = a[0] - a[1]
if dmd.include?(d) then
dmd[d] << a
else
dmd[d] = [a]
end
end
fl = [0, 1, 4, 6]
dl = seq(-9, 9, 1) # all differences
zl = [0] # zero differences only
el = seq(-8, 8, 2) # even differences
ol = seq(-9, 9, 2) # odd differences only
il = seq(0, 9, 1)
rares = []
lists = []
for i in 0 .. 3
lists << []
end
fl.each_with_index { |f, i|
lists[i] = [[f]]
}
digits = []
count = 0
# Recursive closure to generate (n+r) candidates from (n-r) candidates
# and hence find Rare numbers with a given number of digits.
fnpr = lambda { |cand, di, dis, indices, nmr, nd, level|
if level == dis.length then
digits[indices[0][0]] = fml[cand[0]][di[0]][0]
digits[indices[0][1]] = fml[cand[0]][di[0]][1]
le = di.length
if nd % 2 == 1 then
le = le - 1
digits[(nd / 2).to_i] = di[le]
end
di[1 .. le - 1].each_with_index { |d, i|
digits[indices[i + 1][0]] = dmd[cand[i + 1]][d][0]
digits[indices[i + 1][1]] = dmd[cand[i + 1]][d][1]
}
r = toLong(digits, true)
npr = nmr + 2 * r
if not isSquare(npr) then
return
end
count = count + 1
print " R/N %2d:" % [count]
n = toLong(digits, false)
print " (%s)\n" % [format_number(n)]
rares << n
else
for num in dis[level]
di[level] = num
fnpr.call(cand, di, dis, indices, nmr, nd, level + 1)
end
end
}
# Recursive closure to generate (n-r) candidates with a given number of digits.
fnmr = lambda { |cand, list, indices, nd, level|
if level == list.length then
nmr = 0
nmr2 = 0
allTerms[nd - 2].each_with_index { |t, i|
if cand[i] >= 0 then
nmr = nmr + t.coeff * cand[i]
else
nmr2 = nmr2 = t.coeff * -cand[i]
if nmr >= nmr2 then
nmr = nmr - nmr2
nmr2 = 0
else
nmr2 = nmr2 - nmr
nmr = 0
end
end
}
if nmr2 >= nmr then
return
end
nmr = nmr - nmr2
if not isSquare(nmr) then
return
end
dis = []
dis << seq(0, fml[cand[0]].length - 1, 1)
for i in 1 .. cand.length - 1
dis << seq(0, dmd[cand[i]].length - 1, 1)
end
if nd % 2 == 1 then
dis << il.dup
end
di = []
for i in 0 .. dis.length - 1
di << 0
end
fnpr.call(cand, di, dis, indices, nmr, nd, 0)
else
for num in list[level]
cand[level] = num
fnmr.call(cand, list, indices, nd, level + 1)
end
end
}
#for nd in 2 .. MAX_DIGITS - 1
for nd in 2 .. 10
digits = []
for i in 0 .. nd - 1
digits << 0
end
if nd == 4 then
lists[0] << zl.dup
lists[1] << ol.dup
lists[2] << el.dup
lists[3] << ol.dup
elsif allTerms[nd - 2].length > lists[0].length then
for i in 0 .. 3
lists[i] << dl.dup
end
end
indices = []
for t in allTerms[nd - 2]
indices << [t.ix1, t.ix2]
end
for list in lists
cand = []
for i in 0 .. list.length - 1
cand << 0
end
fnmr.call(cand, list, indices, nd, 0)
end
print " %2d digits\n" % [nd]
end
rares.sort()
print "\nThe rare numbers with up to %d digits are:\n" % [MAX_DIGITS]
rares.each_with_index { |rare, i|
print " %2d: %25s\n" % [i + 1, format_number(rare)]
}
end
main()</syntaxhighlight>
{{out}}
<pre> R/N 1: (65)
2 digits
3 digits
4 digits
5 digits
R/N 2: (621,770)
6 digits
7 digits
8 digits
R/N 3: (281,089,082)
9 digits
R/N 4: (2,022,652,202)
R/N 5: (2,042,832,002)
10 digits
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</pre>
=={{header|Rust}}==
A naive and an advanced version based on Nigel Galloway
<syntaxhighlight lang="rust">
use itertools::Itertools;
use std::collections::HashMap;
use std::convert::TryInto;
use std::fmt;
use std::time::Instant;
#[derive(Debug)]
struct RareResults {
digits: u8,
time_to_find: u128,
counter: u32,
number: u64,
}
impl fmt::Display for RareResults {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(
f,
"{:>6} {:>6} ms {:>2}. {}",
self.digits, self.time_to_find, self.counter, self.number
)
}
}
fn print_results(results: Vec<RareResults>) {
if results.len() != 0 {
// println!("Results:");
println!("digits time #. Rare number");
for r in results {
println!("{}", r);
}
}
}
fn isqrt(n: u64) -> u64 {
let mut s = (n as f64).sqrt() as u64;
s = (s + n / s) >> 1;
if s * s > n {
s - 1
} else {
s
}
}
fn is_square(n: u64) -> bool {
match n & 0xf {
0 | 1 | 4 | 9 => {
let t = isqrt(n);
t * t == n
}
_ => false,
}
}
fn get_reverse(number: &u64) -> u64 {
number
.to_string()
.chars()
.map(|c| c.to_digit(10).unwrap())
.enumerate()
.fold(0_u64, |a, (i, d)| a + 10_u64.pow(i as u32) * d as u64)
}
fn is_rare(number: u64) -> bool {
let reverse = get_reverse(&number);
reverse != number
&& number > reverse
&& is_square(number + reverse)
&& is_square(number - reverse)
}
/// This method is a very simple naive search, using brute-force to check a high amount of numbers
/// for satisfying the rare number criterias. As such it is rather slow, and above 10 digits it's
/// not really performant, release version takes ~30 secs to find the first 5 (max 10 digits)
fn naive(digit: u8) -> Vec<RareResults> {
let bp_equal = (0_u8..=9).zip(0_u8..=9).collect::<Vec<(u8, u8)>>();
let bp_zero_or_even = (0_u8..=9)
.cartesian_product(0_u8..=9)
.filter(|pair| (pair.0 == pair.1) || (pair.0 as i32 - pair.1 as i32).abs() % 2 == 0)
.collect::<Vec<(u8, u8)>>();
let bp_odd = (0_u8..=9)
.cartesian_product(0_u8..=9)
.filter(|pair| (pair.0 as i32 - pair.1 as i32).abs() % 2 == 1)
.collect::<Vec<(u8, u8)>>();
let bp_9 = (0_u8..=9)
.cartesian_product(0_u8..=9)
.filter(|pair| pair.0 + pair.1 == 9)
.collect::<Vec<(u8, u8)>>();
let bp_73 = (0_u8..=9)
.cartesian_product(0_u8..=9)
.filter(|pair| [7, 3].contains(&(pair.0 as i8 - pair.1 as i8)))
.collect::<Vec<(u8, u8)>>();
let bp_11 = (0_u8..=9)
.cartesian_product(0_u8..=9)
.filter(|pair| pair.0 + pair.1 == 11 || pair.1 + pair.0 == 1)
.collect::<Vec<(u8, u8)>>();
let aq_bp_setup: Vec<((u8, u8), &Vec<(u8, u8)>)> = vec![
((2, 2), &bp_equal),
((4, 0), &bp_zero_or_even),
((6, 0), &bp_odd),
((6, 5), &bp_odd),
((8, 2), &bp_9),
((8, 3), &bp_73),
((8, 7), &bp_11),
((8, 8), &bp_equal),
];
//generate AB-PQ combinations
let aq_bp = aq_bp_setup
.iter()
.map(|e| {
e.1.iter().fold(vec![], |mut out, b| {
out.push(vec![e.0 .0, b.0, b.1, e.0 .1]);
out
})
})
.flatten()
.collect::<Vec<_>>();
let mut results: Vec<RareResults> = Vec::new();
let mut counter = 0_u32;
let start_time = Instant::now();
let d = digit;
print!("Digits: {} ", d);
if d < 4 {
for n in 10_u64.pow((d - 1).into())..10_u64.pow(d.into()) {
if is_rare(n) {
counter += 1;
results.push(RareResults {
digits: d,
time_to_find: start_time.elapsed().as_millis(),
counter,
number: n,
});
}
}
} else {
aq_bp.iter().for_each(|abqp| {
let start = abqp[0] as u64 * 10_u64.pow((d - 1).into())
+ abqp[1] as u64 * 10_u64.pow((d - 2).into())
+ 10_u64 * abqp[2] as u64
+ abqp[3] as u64;
// brute-force checking all numbers which matches the pattern AB...PQ
// very slow
for n in (start..start + 10_u64.pow((d - 2).into())).step_by(100) {
if is_rare(n) {
counter += 1;
results.push(RareResults {
digits: d,
time_to_find: start_time.elapsed().as_millis(),
counter,
number: n,
});
}
}
});
}
println!(
"Digits: {} done - Elapsed time(ms): {}",
d,
start_time.elapsed().as_millis()
);
results
}
/// This algorithm uses an advanced search strategy based on Nigel Galloway's approach,
/// and can find the first 40 rare numers (16 digits) within reasonable
/// time in release version
fn advanced(digit: u8) -> Vec<RareResults> {
// setup
let mut results: Vec<RareResults> = Vec::new();
let mut counter = 0_u32;
let start_time = Instant::now();
let numeric_digits = (0..=9).map(|x| [x, 0]).collect::<Vec<_>>();
let diffs1: Vec<i8> = vec![0, 1, 4, 5, 6];
// all possible digits pairs to calculate potential diffs
let pairs = (0_i8..=9)
.cartesian_product(0_i8..=9)
.map(|x| [x.0, x.1])
.collect::<Vec<_>>();
let all_diffs = (-9i8..=9).collect::<Vec<_>>();
// lookup table for the first diff
let lookup_1 = vec![
vec![[2, 2], [8, 8]], //Diff = 0
vec![[8, 7], [6, 5]], //Diff = 1
vec![],
vec![],
vec![[4, 0]], // Diff = 4
vec![[8, 3]], // Diff = 5
vec![[6, 0], [8, 2]], // Diff = 6
];
// lookup table for all the remaining diffs
let lookup_n: HashMap<i8, Vec<_>> = pairs.into_iter().into_group_map_by(|elt| elt[0] - elt[1]);
let d = digit;
// powers like 1, 10, 100, 1000....
let powers = (0..d).map(|x| 10_u64.pow(x.into())).collect::<Vec<u64>>();
// for n-r (aka L) the required terms, like 9/ 99 / 999 & 90 / 99999 & 9999 & 900 etc
let terms = powers
.iter()
.zip(powers.iter().rev())
.map(|(a, b)| b.checked_sub(*a).unwrap_or(0))
.filter(|x| *x != 0)
.collect::<Vec<u64>>();
// create a cartesian product for all potential diff numbers
// for the first use the very short one, for all other the complete 19 element
let diff_list_iter = (0_u8..(d / 2))
.map(|i| match i {
0 => diffs1.iter(),
_ => all_diffs.iter(),
})
.multi_cartesian_product()
// remove invalid first diff/second diff combinations - custom iterator would be probably better
.filter(|x| {
if x.len() == 1 {
return true;
}
match (*x[0], *x[1]) {
(a, b) if (a == 0 && b != 0) => false,
(a, b) if (a == 1 && ![-7, -5, -3, -1, 1, 3, 5, 7].contains(&b)) => false,
(a, b) if (a == 4 && ![-8, -6, -4, -2, 0, 2, 4, 6, 8].contains(&b)) => false,
(a, b) if (a == 5 && ![7, -3].contains(&b)) => false,
(a, b) if (a == 6 && ![-9, -7, -5, -3, -1, 1, 3, 5, 7, 9].contains(&b)) => {
false
}
_ => true,
}
});
#[cfg(debug_assertions)]
{
println!(" powers: {:?}", powers);
println!(" terms: {:?}", terms);
}
diff_list_iter.for_each(|diffs| {
// calculate difference of original n and its reverse (aka L = n-r)
// which must be a perfect square
let l: i64 = diffs
.iter()
.zip(terms.iter())
.map(|(diff, term)| **diff as i64 * *term as i64)
.sum();
if l > 0 && is_square(l.try_into().unwrap()) {
// potential candiate, at least L is a perfect square
#[cfg(debug_assertions)]
println!(" square L: {}, diffs: {:?}", l, diffs);
// placeholder for the digits
let mut dig: Vec<i8> = vec![0_i8; d.into()];
// generate a cartesian product for each identified diff using the lookup tables
let c_iter = (0..(diffs.len() + d as usize % 2))
.map(|i| match i {
0 => lookup_1[*diffs[0] as usize].iter(),
_ if i != diffs.len() => lookup_n.get(diffs[i]).unwrap().iter(),
_ => numeric_digits.iter(), // for the middle digits
})
.multi_cartesian_product();
// check each H (n+r) by using digit combination
c_iter.for_each(|elt| {
// print!(" digits combinations: {:?}", elt);
for (i, digit_pair) in elt.iter().enumerate() {
// print!(" digit pairs: {:?}, len: {}", digit_pair, l.len());
dig[i] = digit_pair[0];
dig[d as usize - 1 - i] = digit_pair[1]
}
// for numbers with odd # digits restore the middle digit
// which has been overwritten at the end of the previous cycle
if d % 2 == 1 {
dig[(d as usize - 1) / 2] = elt[elt.len() - 1][0];
}
let num = dig
.iter()
.rev()
.enumerate()
.fold(0_u64, |acc, (i, d)| acc + 10_u64.pow(i as u32) * *d as u64);
let reverse = dig
.iter()
.enumerate()
.fold(0_u64, |acc, (i, d)| acc + 10_u64.pow(i as u32) * *d as u64);
if num > reverse && is_square(num + reverse) {
println!(" FOUND: {}, reverse: {}", num, reverse);
counter += 1;
results.push(RareResults {
digits: d,
time_to_find: start_time.elapsed().as_millis(),
counter,
number: num,
});
}
});
}
});
println!(
"Digits: {} done - Elapsed time(ms): {}",
d,
start_time.elapsed().as_millis()
);
results
}
fn main() {
println!("Run this program in release mode for measuring performance");
println!("Naive version:");
(1..=10).for_each(|x| print_results(naive(x)));
println!("Advanced version:");
(1..=15).for_each(|x| print_results(advanced(x)));
}
</syntaxhighlight>
{{out}}
<pre>
Run this program in release mode for measuring performance
Naive version:
Digits: 1 Digits: 1 done - Elapsed time(ms): 0
Digits: 2 Digits: 2 done - Elapsed time(ms): 0
digits time #. Rare number
2 0 ms 1. 65
Digits: 3 Digits: 3 done - Elapsed time(ms): 0
Digits: 4 Digits: 4 done - Elapsed time(ms): 0
Digits: 5 Digits: 5 done - Elapsed time(ms): 0
Digits: 6 Digits: 6 done - Elapsed time(ms): 11
digits time #. Rare number
6 3 ms 1. 621770
Digits: 7 Digits: 7 done - Elapsed time(ms): 76
Digits: 8 Digits: 8 done - Elapsed time(ms): 641
Digits: 9 Digits: 9 done - Elapsed time(ms): 6375
digits time #. Rare number
9 232 ms 1. 281089082
Digits: 10 Digits: 10 done - Elapsed time(ms): 37598
digits time #. Rare number
10 44 ms 1. 2022652202
10 82 ms 2. 2042832002
Advanced version:
Digits: 1 done - Elapsed time(ms): 6
FOUND: 65, reverse: 56
Digits: 2 done - Elapsed time(ms): 0
digits time #. Rare number
2 0 ms 1. 65
Digits: 3 done - Elapsed time(ms): 0
Digits: 4 done - Elapsed time(ms): 0
Digits: 5 done - Elapsed time(ms): 0
FOUND: 621770, reverse: 77126
Digits: 6 done - Elapsed time(ms): 0
digits time #. Rare number
6 0 ms 1. 621770
Digits: 7 done - Elapsed time(ms): 0
Digits: 8 done - Elapsed time(ms): 5
FOUND: 281089082, reverse: 280980182
Digits: 9 done - Elapsed time(ms): 5
digits time #. Rare number
9 0 ms 1. 281089082
FOUND: 2022652202, reverse: 2022562202
FOUND: 2042832002, reverse: 2002382402
Digits: 10 done - Elapsed time(ms): 107
digits time #. Rare number
10 6 ms 1. 2022652202
10 22 ms 2. 2042832002
Digits: 11 done - Elapsed time(ms): 161
FOUND: 872546974178, reverse: 871479645278
FOUND: 872568754178, reverse: 871457865278
FOUND: 868591084757, reverse: 757480195868
Digits: 12 done - Elapsed time(ms): 1707
digits time #. Rare number
12 319 ms 1. 872546974178
12 342 ms 2. 872568754178
12 846 ms 3. 868591084757
FOUND: 6979302951885, reverse: 5881592039796
Digits: 13 done - Elapsed time(ms): 2409
digits time #. Rare number
13 540 ms 1. 6979302951885
FOUND: 20313693904202, reverse: 20240939631302
FOUND: 20313839704202, reverse: 20240793831302
FOUND: 20331657922202, reverse: 20222975613302
FOUND: 20331875722202, reverse: 20222757813302
FOUND: 20333875702202, reverse: 20220757833302
FOUND: 40313893704200, reverse: 240739831304
FOUND: 40351893720200, reverse: 202739815304
Digits: 14 done - Elapsed time(ms): 41440
digits time #. Rare number
14 6568 ms 1. 20313693904202
14 6642 ms 2. 20313839704202
14 7727 ms 3. 20331657922202
14 7881 ms 4. 20331875722202
14 8287 ms 5. 20333875702202
14 25737 ms 6. 40313893704200
14 25845 ms 7. 40351893720200
FOUND: 200142385731002, reverse: 200137583241002
FOUND: 221462345754122, reverse: 221457543264122
FOUND: 816984566129618, reverse: 816921665489618
FOUND: 245518996076442, reverse: 244670699815542
FOUND: 204238494066002, reverse: 200660494832402
FOUND: 248359494187442, reverse: 244781494953842
FOUND: 244062891224042, reverse: 240422198260442
FOUND: 403058392434500, reverse: 5434293850304
FOUND: 441054594034340, reverse: 43430495450144
Digits: 15 done - Elapsed time(ms): 42591
digits time #. Rare number
15 2788 ms 1. 200142385731002
15 2970 ms 2. 221462345754122
15 5616 ms 3. 816984566129618
15 6999 ms 4. 245518996076442
15 7229 ms 5. 204238494066002
15 7291 ms 6. 248359494187442
15 7547 ms 7. 244062891224042
15 23704 ms 8. 403058392434500
15 23883 ms 9. 441054594034340
</pre>
Line 4,230 ⟶ 6,058:
===Traditional===
{{trans|C#}} via {{trans|Go}} Surprisingly slow, I expected performance to be a little slower than C#, but this is quite a bit slower. This vb.net version takes 1 2/3 minutes to do what the C# version can do in 2/3 of a minute.
<
Imports DT = System.DateTime
Imports Lsb = System.Collections.Generic.List(Of SByte)
Line 4,356 ⟶ 6,184:
If System.Diagnostics.Debugger.IsAttached Then ReadKey()
End Sub
End Module</
{{out}}
<pre style="height:64ex;overflow:scroll"> digs elapsed(ms) R/N Rare Numbers
Line 4,425 ⟶ 6,253:
24: 441,054,594,034,340
25: 816,984,566,129,618</pre>
===Quicker===
{{trans|C#}} (translation of the quicker version)
Performance is better, only about 4% slower than '''C#'''.
<syntaxhighlight lang="vbnet">Imports System.Math
Imports System.Console
Imports llst = System.Collections.Generic.List(Of Integer())
Module Module1
Dim d, dac As Integer(), drar As Integer() = New Integer(19) {} : Dim ac, pp As Long(), p As Long() = New Long(18) {}
Dim odd As Boolean = False : Dim sum, rt As Long : Dim ln, dl As Integer, cn As Integer = 0, nd As Integer = 2, nd1 As Integer = nd - 1
Dim sw As Stopwatch = New Stopwatch(), swt As Stopwatch = New Stopwatch() : Dim sr As List(Of Long) = New List(Of Long)()
ReadOnly tlo As Integer() = New Integer() {0, 1, 4, 5, 6}, all As Integer() = Seq(-9, 9), odl As Integer() = Seq(-9, 9, 2), evl As Integer() = Seq(-8, 8, 2),
thi As Integer() = New Integer() {4, 5, 6, 9, 10, 11, 14, 15, 16}, alh As Integer() = Seq(0, 18), odh As Integer() = Seq(1, 17, 2),
evh As Integer() = Seq(0, 18, 2), ten As Integer() = Seq(0, 9), z As Integer() = Seq(0, 0), t7 As Integer() = New Integer() {-3, 7}, nin As Integer() = New Integer() {9}, tn As Integer() = New Integer() {10}, t12 As Integer() = New Integer() {2, 12}, o11 As Integer() = New Integer() {1, 11}, pos As Integer() = New Integer() {0, 1, 4, 5, 6, 9}
Dim lu, l2 As llst, lul As llst = New llst From {z, odl, Nothing, Nothing, evl, t7, odl},
luh As llst = New llst From {tn, evh, Nothing, Nothing, evh, t12, odh, Nothing, Nothing, evh, nin, odh, Nothing, Nothing, odh, o11, evh},
l2l As llst = New llst From {pos, Nothing, Nothing, Nothing, all, Nothing, all},
l2h As llst = New llst From {Nothing, Nothing, Nothing, Nothing, alh, Nothing, alh, Nothing, Nothing, Nothing, alh, Nothing, Nothing, Nothing, alh, Nothing, alh}
Dim chTen As Integer()() = New Integer()() {New Integer() {0, 2, 5, 8, 9}, New Integer() {0, 3, 4, 6, 9}, New Integer() {1, 4, 7, 8},
New Integer() {2, 3, 5, 8}, New Integer() {0, 3, 6, 7, 9}, New Integer() {1, 2, 4, 7},
New Integer() {2, 5, 6, 8}, New Integer() {0, 1, 3, 6, 9}, New Integer() {1, 4, 5, 7}}
Dim chAH As Integer()() = New Integer()() {
New Integer() {0, 2, 5, 8, 9, 11, 14, 17, 18}, New Integer() {0, 3, 4, 6, 9, 12, 13, 15, 18}, New Integer() {1, 4, 7, 8, 10, 13, 16, 17},
New Integer() {2, 3, 5, 8, 11, 12, 14, 17}, New Integer() {0, 3, 6, 7, 9, 12, 15, 16, 18}, New Integer() {1, 2, 4, 7, 10, 11, 13, 16},
New Integer() {2, 5, 6, 8, 11, 14, 15, 17}, New Integer() {0, 1, 3, 6, 9, 10, 12, 15, 18}, New Integer() {1, 4, 5, 7, 10, 13, 14, 16}}
Function Seq(ByVal f As Integer, ByVal t As Integer, ByVal Optional s As Integer = 1) As Integer()
Dim r As Integer() = New Integer((t - f) / s + 1 - 1) {}
For i As Integer = 0 To r.Length - 1 : r(i) = f : f += s : Next : Return r : End Function
Function ISR(ByVal s As Long) As Long
Return Sqrt(s) : End Function
Function IsRev(ByVal nd As Integer, ByVal f As Long, ByVal r As Long) As Boolean
nd -= 1 : Return If(f \ p(nd) <> r Mod 10, False, (If(nd < 1, True, IsRev(nd, f Mod p(nd), r \ 10)))) : End Function
Sub RecurseLE5(ByVal lst As llst, ByVal lv As Integer)
If lv = dl Then
sum = ac(lv - 1) : If sum > 0 Then rt = CLng(Sqrt(sum)) : If rt * rt = sum Then sr.Add(sum)
Else For Each n As Integer In lst(lv)
d(lv) = n : If lv = 0 Then ac(0) = pp(0) * n Else ac(lv) = ac(lv - 1) + pp(lv) * n
RecurseLE5(lst, lv + 1) : Next : End If : End Sub
Sub Recursehi(ByVal lst As llst, ByVal lv As Integer)
Dim lv1 As Integer = lv - 1 : If lv = dl Then
sum = ac(lv1) : If (&H202021202030213 And (1L << (sum And 63))) > 0 Then rt = CLng(Sqrt(sum)) : If rt * rt = sum Then sr.Add(sum)
Else For Each n As Integer In lst(lv)
d(lv) = n : If lv = 0 Then ac(0) = pp(0) * n : dac(0) = drar(n) _
Else ac(lv) = ac(lv1) + pp(lv) * n : dac(lv) = dac(lv1) + drar(n) : If dac(lv) > 8 Then dac(lv) -= 9
Select Case lv
Case 0 : ln = n : lst(1) = lu(n) : lst(2) = l2(n)
Case 1 : Select Case ln
Case 5, 15 : lst(2) = If(n < 10, evh, odh)
Case 9 : lst(2) = If(((n >> 1) And 1) = 0, evh, odh)
Case 11 : lst(2) = If(((n >> 1) And 1) = 1, evh, odh)
End Select : End Select
If lv = dl - 2 Then lst(dl - 1) = If(odd, chTen(dac(dl - 2)), chAH(dac(dl - 2)))
Recursehi(lst, lv + 1) : Next : End If : End Sub
Sub Recurselo(ByVal lst As llst, ByVal lv As Integer)
Dim lv1 As Integer = lv - 1 : If lv = dl Then
sum = ac(lv1) : If sum > 0 Then rt = CLng(Sqrt(sum)) : If rt * rt = sum Then sr.Add(sum)
Else For Each n As Integer In lst(lv)
d(lv) = n : If lv = 0 Then ac(0) = pp(0) * n Else ac(lv) = ac(lv1) + pp(lv) * n
Select Case lv
Case 0 : ln = n : lst(1) = lu(n) : lst(2) = l2(n)
Case 1 : Select Case ln
Case 1 : lst(2) = If((((n + 9) >> 1) And 1) = 0, evl, odl)
Case 5 : lst(2) = If(n < 0, evl, odl)
End Select : End Select
Recurselo(lst, lv + 1) : Next : End If : End Sub
Function listEm(ByVal lst As llst, ByVal plu As llst, ByVal pl2 As llst) As List(Of Long)
dl = lst.Count : d = New Integer(dl - 1) {} : sr.Clear() : lu = plu : l2 = pl2
ac = New Long(dl - 1) {} : dac = New Integer(dl - 1) {} : pp = New Long(dl - 1) {}
Dim j As Integer = nd1 : For i As Integer = 0 To dl - 1 : pp(i) = If(lst(0).Length > 6, p(j) + p(i), p(j) - p(i)) : j -= 1 : Next
If nd <= 5 Then RecurseLE5(lst, 0) Else If lst(0).Length > 6 Then Recursehi(lst, 0) Else Recurselo(lst, 0)
Return sr : End Function
Sub Reveal(ByVal lo As List(Of Long), ByVal hi As List(Of Long))
Dim s As List(Of String) = New List(Of String)() : For Each l As Long In lo : For Each h As Long In hi
Dim r As Long = (h - l) \ 2, f As Long = h - r
If IsRev(nd, f, r) Then s.Add(String.Format("{0,20} {1,11} {2,10} ", f, ISR(h), ISR(l)))
Next : Next : s.Sort() : If s.Count > 0 Then _
For Each t As String In s : cn += 1 : Write("{0,2} {1}{2}", cn, t, If(t = s.Last(), "", vbLf)) : Next Else Write("{0,48}", "")
End Sub
Sub Main(ByVal args As String())
WriteLine("{0,3}{1,20} {2,11} {3,10} {4,4}{5,16} {6, 17}", "nth", "forward", "rt.sum", "rt.dif", "digs", "block time", "total time")
p(0) = 1 : Dim j As Integer = 0 : For i As Integer = 1 To p.Length - 1 : p(i) = p(j) * 10 : j = i : Next
For i As Integer = 0 To drar.Length - 1 : drar(i) = (i * 2) Mod 9 : Next
Dim lls As llst = New llst From {tlo}, hls As llst = New llst From {thi} : sw.Start() : swt.Start()
While nd <= 18
If nd > 2 Then If odd Then hls.Add(ten) Else lls.Add(all) : hls(hls.Count - 1) = alh
Reveal(listEm(lls, lul, l2l).ToList(), listEm(hls, luh, l2h))
If Not odd AndAlso nd > 5 Then hls(hls.Count - 1) = alh
WriteLine("{0,2}: {1} {2}", nd, sw.Elapsed, swt.Elapsed) : sw.Restart()
nd1 = nd : nd += 1 : odd = Not odd
End While
' 19
hls.Add(ten)
Reveal(listEmU(lls, lul, l2l).ToList(), listEmU(hls, luh, l2h))
WriteLine("{0,2}: {1} {2}", nd, sw.Elapsed, swt.Elapsed) : End Sub
#Region "19"
Dim usum, urt As ULong
Dim acu, ppu As ULong()
Dim sru As List(Of ULong) = New List(Of ULong)()
Sub Reveal(ByVal lo As List(Of ULong), ByVal hi As List(Of ULong))
Dim s As List(Of String) = New List(Of String)() : For Each l As ULong In lo : For Each h As ULong In hi
Dim r As ULong = (h - l) >> 1, f As ULong = h - r
If IsRev(nd, f, r) Then s.Add(String.Format("{0,20} {1,11} {2,10} ", f, ISR(h), ISR(l)))
Next : Next : s.Sort() : If s.Count > 0 Then _
For Each t As String In s : cn += 1 : Write("{0,2} {1}{2}", cn, t, If(t = s.Last(), "", vbLf)) : Next Else Write("{0,48}", "")
End Sub
Function listEmU(ByVal lst As llst, ByVal plu As llst, ByVal pl2 As llst) As List(Of ULong)
dl = lst.Count : d = New Integer(dl - 1) {} : sru.Clear() : lu = plu : l2 = pl2
acu = New ULong(dl - 1) {} : dac = New Integer(dl - 1) {} : ppu = New ULong(dl - 1) {}
Dim j As Integer = nd1 : For i As Integer = 0 To dl - 1 : ppu(i) = CULng(If(lst(0).Length > 6, p(j) + p(i), p(j) - p(i))) : j -= 1 : Next
If lst(0).Length > 8 Then RecurseUhi(lst, 0) Else RecurseUlo(lst, 0)
Return sru : End Function
Sub RecurseUhi(ByVal lst As llst, ByVal lv As Integer)
Dim lv1 As Integer = lv - 1 : If lv = dl Then
usum = acu(lv1)
If (&H202021202030213 And (1UL << (usum And 63))) <> 0 Then urt = Sqrt(usum) : If urt * urt = usum Then sru.Add(usum)
Else For Each n As Integer In lst(lv)
d(lv) = n : If lv = 0 Then
acu(0) = ppu(0) * CUInt(n) : dac(0) = drar(n)
Else
acu(lv) = If(n >= 0, acu(lv1) + ppu(lv) * CUInt(n), acu(lv1) - ppu(lv) * CUInt(-n))
dac(lv) = dac(lv1) + drar(n) : If dac(lv) > 8 Then dac(lv) -= 9
End If
Select Case lv
Case 0 : ln = n : lst(1) = lu(n) : lst(2) = l2(n)
Case 1 : Select Case ln
Case 5, 15 : lst(2) = If(n < 10, evh, odh)
Case 9 : lst(2) = If(((n >> 1) And 1) = 0, evh, odh)
Case 11 : lst(2) = If(((n >> 1) And 1) = 1, evh, odh)
End Select : End Select
If lv = dl - 2 Then lst(dl - 1) = If(odd, chTen(dac(dl - 2)), chAH(dac(dl - 2)))
RecurseUhi(lst, lv + 1) : Next : End If : End Sub
Sub RecurseUlo(ByVal lst As llst, ByVal lv As Integer)
Dim lv1 As Integer = lv - 1 : If lv = dl Then
usum = acu(lv1)
If usum > 0 Then urt = Sqrt(usum) : If urt * urt = usum Then sru.Add(usum)
Else For Each n As Integer In lst(lv)
d(lv) = n : If lv = 0 Then acu(0) = ppu(0) * CUInt(n) Else _
acu(lv) = If(n >= 0, acu(lv1) + ppu(lv) * CUInt(n), acu(lv1) - ppu(lv) * CUInt(-n))
Select Case lv
Case 0 : ln = n : lst(1) = lu(n) : lst(2) = l2(n)
Case 1 : Select Case ln
Case 1 : lst(2) = If((((n + 9) >> 1) And 1) = 0, evl, odl)
Case 5 : lst(2) = If(n < 0, evl, odl)
End Select : End Select
RecurseUlo(lst, lv + 1) : Next : End If : End Sub
Function ISR(ByVal s As ULong) As ULong
Return Sqrt(s) : End Function
Function IsRev(ByVal nd As Integer, ByVal f As ULong, ByVal r As ULong) As Boolean
nd -= 1 : Return If(f \ CULng(p(nd)) <> r Mod 10, False, (If(nd < 1, True, IsRev(nd, f Mod CULng(p(nd)), r \ 10UL)))) : End Function
#End Region
End Module</syntaxhighlight>
Results on the core i7-7700 @ 3.6Ghz.
<pre style="height:64ex;overflow:scroll">nth forward rt.sum rt.dif digs block time total time
1 65 11 3 2: 00:00:00.0037657 00:00:00.0037657
3: 00:00:00.0001034 00:00:00.0040327
4: 00:00:00.0000951 00:00:00.0042102
5: 00:00:00.0000928 00:00:00.0043867
2 621770 836 738 6: 00:00:00.0022229 00:00:00.0066922
7: 00:00:00.0001703 00:00:00.0069250
8: 00:00:00.0002647 00:00:00.0072713
3 281089082 23708 330 9: 00:00:00.0013320 00:00:00.0086847
4 2022652202 63602 300
5 2042832002 63602 6360 10: 00:00:00.0043004 00:00:00.0130515
11: 00:00:00.0202717 00:00:00.0334094
6 868591084757 1275175 333333
7 872546974178 1320616 32670
8 872568754178 1320616 33330 12: 00:00:00.0553298 00:00:00.0889160
9 6979302951885 3586209 1047717 13: 00:00:00.3615348 00:00:00.4505467
10 20313693904202 6368252 269730
11 20313839704202 6368252 270270
12 20331657922202 6368252 329670
13 20331875722202 6368252 330330
14 20333875702202 6368252 336330
15 40313893704200 6368252 6330336
16 40351893720200 6368252 6336336 14: 00:00:00.9808061 00:00:01.4315251
17 200142385731002 20006998 69300
18 204238494066002 20122102 1891560
19 221462345754122 21045662 69300
20 244062891224042 22011022 1908060
21 245518996076442 22140228 921030
22 248359494187442 22206778 1891560
23 403058392434500 20211202 19940514
24 441054594034340 22011022 19940514
25 816984566129618 40421606 250800 15: 00:00:06.8062687 00:00:08.2378833
26 2078311262161202 64030648 7529850
27 2133786945766212 65272218 2666730
28 2135568943984212 65272218 3267330
29 2135764587964212 65272218 3326670
30 2135786765764212 65272218 3333330
31 4135786945764210 65272218 63333336
32 6157577986646405 105849161 33333333
33 6889765708183410 83866464 82133718
34 8052956026592517 123312255 29999997
35 8052956206592517 123312255 30000003
36 8191154686620818 127950856 3299670
37 8191156864620818 127950856 3300330
38 8191376864400818 127950856 3366330
39 8650327689541457 127246955 33299667
40 8650349867341457 127246955 33300333 16: 00:00:18.5333654 00:00:26.7713563
41 22542040692914522 212329862 333300
42 67725910561765640 269040196 251135808
43 86965750494756968 417050956 33000 17: 00:02:08.5301411 00:02:35.3016150
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: 00:05:50.9239434 00:08:26.2256326
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: 00:45:09.0009635 00:53:36.4768204</pre>
=={{header|Wren}}==
Line 4,438 ⟶ 6,517:
===Traditional===
About 9.5 minutes to find the first 25 rare numbers.
<
import "./fmt" for Fmt
class Term {
Line 4,564 ⟶ 6,643:
for (num in dis[level]) {
di[level] = num
fnpr.call(cand, di, dis, indices, nmr, nd, level+1)
}
Line 4,606 ⟶ 6,684:
for (num in list[level]) {
cand[level] = num
fnmr.call(cand, list, indices, nd, level+1)
}
Line 4,638 ⟶ 6,715:
Fmt.print(" $2d: $,21d", i+1, rare)
i = i + 1
}</
{{out}}
Line 4,714 ⟶ 6,791:
===Turbo===
Ruffles the feathers a little with a time 5 times quicker than the 'traditional' version.
<
import "./fmt" for Fmt
import "./date" for Date
class Z2 {
Line 4,743 ⟶ 6,820:
if ((i/Pow10[n-1]).floor != g%10) return false
if (n < 2) return true
return izRev.call(n-1, i%Pow10[n-1], (g/10).floor)
}
Line 4,959 ⟶ 7,035:
Fmt.print(" $2d: $s $s", nd, fbTime, ftTime)
bStart = System.clock // restart block timing
}</
{{out}}
Line 4,988 ⟶ 7,064:
25 816,984,566,129,618 15: 00:01:34.206 00:01:53.632
</pre>
|