Talk:Rare numbers: Difference between revisions
m
→Tweaks, C++: Further syntax-highlighting fixes
(→21+ digit rare numbers: more 22s found) |
m (→Tweaks, C++: Further syntax-highlighting fixes) |
||
| (44 intermediate revisions by 6 users not shown) | |||
Line 6:
(a URL reference):
:* author's website: [http://www.shyamsundergupta.com/rare.
Line 68:
::::: Incidentally, I regard it as bad form to use concurrent processing (i.e. goroutines) in RC tasks unless this is specifically asked for or is otherwise unavoidable (for processing events in some GUI package for example). It is difficult for languages which don't have this stuff built in to compete and it may disguise the usage of what are basically poor algorithms. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 23:04, 24 September 2019 (UTC)
===A few more mins.===
Above I considered n-r=L and investigated the nature of L. It is difficult to estimate complexity with increasing number of digits for this algorithm because: it depends on the number of L which happen to be a perfect square, which is neither random nor easy to predict; each L which is a perfect square expands into varying number of r. At first sight n+r=H does not look promising. For the number n....g n+g may take the values 1 to 18 rather than 1 to 9 for n-g and for an odd number of digits x doesn't disappear, rather it creates 10 times the number of possibilites.
<br>
For a rare number H-L=(n+r)-(n-r)=2r which implies that for a Rare number H and L must both be odd or even. From the lists H and R I can produce all the candidates for r. n is H-r therefore I must simply determine for each candidate is r H-r reversed (see C++ on the task page). The nice thing is that it is easy to determine the size of H and L and they predict timings for this algorithm. The time does not depend on the number of L which happen to be a perfect square. This simplicity means that I can predict optimizations which will make significant difference to the run time for increasing number of digits. The programming skill then is to compute the Cartesian Product of n/2 for L and (n+1)/2 for H integer ranges; then calculate the Inner Product of each with 10**x-10**y for L and 10**x+10**y for H. Efficiently!!! I especially like that this can be described as a problem in Linear Algebra subject to analysis and representation as a graph.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 12:19, 20 December 2019 (UTC)
== the 1<sup>st</sup> REXX version ==
This is the 1<sup>st</sup> REXX version, before all the optimizations were added:
<syntaxhighlight lang="rexx">
/*REXX program to calculate and display an specified amount of rare numbers. */
numeric digits 20; w= digits() + digits() % 3 /*ensure enough decimal digs for calcs.*/
parse arg many start . /*obtain optional argument from the CL.*/
Line 98 ⟶ 104:
if _>=0 then do; x= _; $= $ + q
end
end /*while q>1*/; return $
</syntaxhighlight>
Pretty simple, but slow as molasses in January.
Line 107 ⟶ 114:
of ''rare'' numbers) within Shyam Sunder Gupta's
<br>[http://www.shyamsundergupta.com/rare.htm <u>webpage</u>] have been incorporated in this REXX program.
<
numeric digits 20; w= digits() + digits() % 3 /*ensure enough decimal digs for calcs.*/
parse arg many start . /*obtain optional argument from the CL.*/
Line 214 ⟶ 221:
if _>=0 then do; x= _; $= $ + q
end
end /*while q>1*/; return $</
Still pretty sluggish, like molasses in March.
Line 501 ⟶ 508:
::::To reliably go any further than this would require the use of big integers (unpleasant and relatively slow in Go) as signed 64 bit integers have a 19 digit maximum. It might be possible to use unsigned 64 bit integers (20 digit maximum) though this would require some fancy footwork to deal with negative numbers and subtraction. So I think that's my lot now :) --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 20:04, 2 October 2019 (UTC)
== Tweaks, Go (Turbo) ==
Still some performance hiding in there...
Skipping combinations 2 and 3 for the differences, and stopping at 6 instead of 9.
Since no square can end in the digit 2 or 3, these can be skipped safely. 6 is the highest possible
difference, so stopping at 6 is OK.
Skipping combinations 0 through 3, 7 through 9, and 12 through 14 on the sums.
Since lowest possible first digit of the rare number is 2, and the sum must be greater than the rare number,
and digits 2 and 3 cannot be the last digits of the sum, 4 is the lowest possible last digit of the sum.
Also, no square can end in digits 7 or 8, so combinations starting with 7, 8, 12, & 13 can be eliminated.
Removing combination 9 & 14 is cheating, however no solution up to 19 digits depends on the sum being a
square containing the combination 9 or 14 as the first/last digit.
<syntaxhighlight lang="go">package main
import (
"fmt"
"math"
"sort"
"time"
)
type (
z1 func() z2
z2 struct {
value int64
hasValue bool
}
)
var pow10 [19]int64
func init() {
pow10[0] = 1
for i := 1; i < 19; i++ {
pow10[i] = 10 * pow10[i-1]
}
}
func izRev(n int, i, g uint64) bool {
if i/uint64(pow10[n-1]) != g%10 {
return false
}
if n < 2 {
return true
}
return izRev(n-1, i%uint64(pow10[n-1]), g/10)
}
func fG(n z1, start, end, reset int, step int64, l *int64) z1 {
i, g, e := step*int64(start), step*int64(end), step*int64(reset)
return func() z2 {
for i < g {
*l += step
i += step
return z2{*l, true}
}
i = e
*l -= (g - e)
return n()
}
}
type nLH struct{ even, odd []uint64 }
type zp struct {
n z1
g [][2]int64
}
func newNLH(e zp) nLH {
var even, odd []uint64
n, g := e.n, e.g
for i := n(); i.hasValue; i = n() {
for _, p := range g {
ng, gg := p[0], p[1]
if (ng > 0) || (i.value > 0) {
w := uint64(ng*pow10[4] + gg + i.value)
ws := uint64(math.Sqrt(float64(w)))
if ws*ws == w {
if w%2 == 0 {
even = append(even, w)
} else {
odd = append(odd, w)
}
}
}
}
}
return nLH{even, odd}
}
func makeL(n int) zp {
g := make([]z1, n/2-3)
g[0] = func() z2 { return z2{} }
for i := 1; i < n/2-3; i++ {
s := -9
if i == n/2-4 {
s = -10
}
l := pow10[n-i-4] - pow10[i+3]
acc += l * int64(s)
g[i] = fG(g[i-1], s, 9, -9, l, &acc)
}
var g0, g1, g2, g3 int64
l0, l1, l2, l3 := pow10[n-5], pow10[n-6], pow10[n-7], pow10[n-8]
f := func() [][2]int64 {
var w [][2]int64
for g0 < 7 {
nn := g3*l3 + g2*l2 + g1*l1 + g0*l0
gg := -1000*g3 - 100*g2 - 10*g1 - g0
if g3 < 9 {
g3++
} else {
g3 = -9
if g2 < 9 {
g2++
} else {
g2 = -9
if g1 < 9 {
g1++
} else {
g1 = -9
if g0 == 1 { g0 += 2 }
g0++
}
}
}
if bs[(pow10[10]+gg)%10000] {
w = append(w, [2]int64{nn, gg})
}
}
return w
}
return zp{g[n/2-4], f()}
}
func makeH(n int) zp {
acc = -(pow10[n/2] + pow10[(n-1)/2])
g := make([]z1, (n+1)/2-3)
g[0] = func() z2 { return z2{} }
for i := 1; i < n/2-3; i++ {
j := 0
if i == (n+1)/2-3 {
j = -1
}
g[i] = fG(g[i-1], j, 18, 0, pow10[n-i-4]+pow10[i+3], &acc)
if n%2 == 1 {
g[(n+1)/2-4] = fG(g[n/2-4], -1, 9, 0, 2*pow10[n/2], &acc)
}
}
g0 := int64(4)
var g1, g2, g3 int64
l0, l1, l2, l3 := pow10[n-5], pow10[n-6], pow10[n-7], pow10[n-8]
f := func() [][2]int64 {
var w [][2]int64
for g0 < 17 {
nn := g3*l3 + g2*l2 + g1*l1 + g0*l0
gg := 1000*g3 + 100*g2 + 10*g1 + g0
if g3 < 18 {
g3++
} else {
g3 = 0
if g2 < 18 {
g2++
} else {
g2 = 0
if g1 < 18 {
g1++
} else {
g1 = 0
switch g0 {case 6, 9: g0 += 3 }
g0++
}
}
}
if bs[gg%10000] {
w = append(w, [2]int64{nn, gg})
}
}
return w
}
return zp{g[(n+1)/2-4], f()}
}
var (
acc int64
bs = make([]bool, 10000)
L, H nLH
)
func rare(n int) []uint64 {
acc = 0
for g := 0; g < 10000; g++ {
bs[(g*g)%10000] = true
}
L = newNLH(makeL(n))
H = newNLH(makeH(n))
var rares []uint64
for _, l := range L.even {
for _, h := range H.even {
r := (h - l) / 2
z := h - r
if izRev(n, r, z) {
rares = append(rares, z)
}
}
}
for _, l := range L.odd {
for _, h := range H.odd {
r := (h - l) / 2
z := h - r
if izRev(n, r, z) {
rares = append(rares, z)
}
}
}
if len(rares) > 0 {
sort.Slice(rares, func(i, j int) bool {
return rares[i] < rares[j]
})
}
return rares
}
// Formats time in form hh:mm:ss.fff (i.e. millisecond precision).
func formatTime(d time.Duration) string {
f := d.Milliseconds()
s := f / 1000
f %= 1000
m := s / 60
s %= 60
h := m / 60
m %= 60
return fmt.Sprintf("%02d:%02d:%02d.%03d", h, m, s, f)
}
func commatize(n uint64) string {
s := fmt.Sprintf("%d", n)
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
return s
}
func main() {
bStart := time.Now() // block time
tStart := bStart // total time
nth := 3 // i.e. count of rare numbers < 10 digits
fmt.Println("nth rare number digs block time total time")
for nd := 10; nd <= 19; nd++ {
rares := rare(nd)
if len(rares) > 0 {
for i, r := range rares {
nth++
t := ""
if i < len(rares)-1 {
t = "\n"
}
fmt.Printf("%2d %25s%s", nth, commatize(r), t)
}
} else {
fmt.Printf("%29s", "")
}
fbTime := formatTime(time.Since(bStart))
ftTime := formatTime(time.Since(tStart))
fmt.Printf(" %2d: %s %s\n", nd, fbTime, ftTime)
bStart = time.Now() // restart block timing
}
}</syntaxhighlight>
{{out}}
Results on the core i7-7700 @ 3.6Ghz.
<pre style="height:64ex;overflow:scroll">nth rare number digs block time total time
4 2,022,652,202
5 2,042,832,002 10: 00:00:00.001 00:00:00.001
11: 00:00:00.006 00:00:00.008
6 868,591,084,757
7 872,546,974,178
8 872,568,754,178 12: 00:00:00.015 00:00:00.024
9 6,979,302,951,885 13: 00:00:00.098 00:00:00.123
10 20,313,693,904,202
11 20,313,839,704,202
12 20,331,657,922,202
13 20,331,875,722,202
14 20,333,875,702,202
15 40,313,893,704,200
16 40,351,893,720,200 14: 00:00:00.269 00:00:00.392
17 200,142,385,731,002
18 204,238,494,066,002
19 221,462,345,754,122
20 244,062,891,224,042
21 245,518,996,076,442
22 248,359,494,187,442
23 403,058,392,434,500
24 441,054,594,034,340
25 816,984,566,129,618 15: 00:00:01.810 00:00:02.203
26 2,078,311,262,161,202
27 2,133,786,945,766,212
28 2,135,568,943,984,212
29 2,135,764,587,964,212
30 2,135,786,765,764,212
31 4,135,786,945,764,210
32 6,157,577,986,646,405
33 6,889,765,708,183,410
34 8,052,956,026,592,517
35 8,052,956,206,592,517
36 8,191,154,686,620,818
37 8,191,156,864,620,818
38 8,191,376,864,400,818
39 8,650,327,689,541,457
40 8,650,349,867,341,457 16: 00:00:05.122 00:00:07.325
41 22,542,040,692,914,522
42 67,725,910,561,765,640
43 86,965,750,494,756,968 17: 00:00:33.461 00:00:40.787
44 225,342,456,863,243,522
45 225,342,458,663,243,522
46 225,342,478,643,243,522
47 284,684,666,566,486,482
48 284,684,868,364,486,482
49 297,128,548,234,950,692
50 297,128,722,852,950,692
51 297,148,324,656,930,692
52 297,148,546,434,930,692
53 497,168,548,234,910,690
54 619,431,353,040,136,925
55 619,631,153,042,134,925
56 631,688,638,047,992,345
57 633,288,858,025,996,145
58 633,488,632,647,994,145
59 653,488,856,225,994,125
60 811,865,096,390,477,018
61 865,721,270,017,296,468
62 871,975,098,681,469,178
63 898,907,259,301,737,498 18: 00:01:37.823 00:02:18.611
64 2,042,401,829,204,402,402
65 2,060,303,819,041,450,202
66 2,420,424,089,100,600,242
67 2,551,755,006,254,571,552
68 2,702,373,360,882,732,072
69 2,825,378,427,312,735,282
70 6,531,727,101,458,000,045
71 6,988,066,446,726,832,640
72 8,066,308,349,502,036,608
73 8,197,906,905,009,010,818
74 8,200,756,128,308,135,597
75 8,320,411,466,598,809,138 19: 00:12:22.226 00:14:40.838</pre>--[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 01:32, 21 March 2020 (UTC)
:Hey, thanks for that! I must confess I was so pleased at getting the time down to 21 minutes (and so shell-shocked by Nigel's variable naming conventions) that I hadn't even bothered to look at whether further improvement was possible.
:It's a little slower on my machine (15 minutes 14 seconds), which seems to be suffering a bit of turbo lag, but a great improvement nonetheless so I'm going to update the version on the main page.
:I've also updated Nigel's C++ version with the same tweaks:
<syntaxhighlight lang="cpp">#include <iostream>
#include <functional>
#include <bitset>
#include <cmath>
using Z2=std::optional<long>; using Z1=std::function<Z2()>;
constexpr std::array<const long,19> pow10{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
constexpr bool izRev(int n,unsigned long i,unsigned long g){return (i/pow10[n-1]!=g%10)? false : (n<2)? true : izRev(n-1,i%pow10[n-1],g/10);}
const Z1 fG(Z1 n,int start, int end,int reset,const long step,long &l){return ([n,i{step*start},g{step*end},e{step*reset},&l,step]()mutable{
while(i<g){l+=step; i+=step; return Z2(l);} i=e; l-=(g-e); return n();});}
struct nLH{
std::vector<unsigned long>even{};
std::vector<unsigned long>odd{};
nLH(std::pair<Z1,std::vector<std::pair<long,long>>> e){auto [n,g]=e; while (auto i=n()){for(auto [ng,gg]:g){ if((ng>0)|(*i>0)){
unsigned long w=ng*pow10[4]+gg+*i; unsigned long g=sqrt(w); if(g*g==w) (w%2==0)? even.push_back(w) : odd.push_back(w);}}}}
};
class Rare{
long acc{0};
const std::bitset<10000>bs;
const std::pair<Z1,std::vector<std::pair<long,long>>> makeL(const int n){
Z1 g[n/2-3]; g[0]=([]{return Z2{};});
for(int i{1};i<n/2-3;++i){int s{(i==n/2-4)? -10:-9}; long l=pow10[n-i-4]-pow10[i+3]; acc+=l*s; g[i]=fG(g[i-1],s,9,-9,l,acc);}
return {g[n/2-4],([g0{0},g1{0},g2{0},g3{0},l3{pow10[n-8]},l2{pow10[n-7]},l1{pow10[n-6]},l0{pow10[n-5]},this]()mutable{std::vector<std::pair<long,long>>w{}; while (g0<7){
long n{g3*l3+g2*l2+g1*l1+g0*l0}; long g{-1000*g3-100*g2-10*g1-g0}; if(g3<9) ++g3; else{g3=-9; if(g2<9) ++g2; else{g2=-9; if(g1<9) ++g1; else{g1=-9; if(g0==1) g0=3; ++g0;}}}
if (bs[(pow10[10]+g)%10000]) w.push_back({n,g});} return w;})()};}
const std::pair<Z1,std::vector<std::pair<long,long>>> makeH(const int n){ acc=-(pow10[n/2]+pow10[(n-1)/2]);
Z1 g[(n+1)/2-3]; g[0]=([]{return Z2{};});
for(int i{1};i<n/2-3;++i) g[i]=fG(g[i-1],(i==(n+1)/2-3)? -1:0,18,0,pow10[n-i-4]+pow10[i+3],acc);
if(n%2==1) g[(n+1)/2-4]=fG(g[n/2-4],-1,9,0,2*pow10[n/2],acc);
return {g[(n+1)/2-4],([g0{4},g1{0},g2{0},g3{0},l3{pow10[n-8]},l2{pow10[n-7]},l1{pow10[n-6]},l0{pow10[n-5]},this]()mutable{std::vector<std::pair<long,long>>w{}; while (g0<17){
long n{g3*l3+g2*l2+g1*l1+g0*l0}; long g{g3*1000+g2*100+g1*10+g0}; if(g3<18) ++g3; else{g3=0; if(g2<18) ++g2; else{g2=0; if(g1<18) ++g1; else{g1=0; if(g0==6||g0==9)g0+=3; ++g0;}}}
if (bs[g%10000]) w.push_back({n,g});} return w;})()};}
const nLH L,H;
public: Rare(int n):L{makeL(n)},H{makeH(n)},bs{([]{std::bitset<10000>n{false}; for(int g{0};g<10000;++g) n[(g*g)%10000]=true; return n;})()}{
std::cout<<"Rare "<<n<<std::endl;
for(auto l:L.even) for(auto h:H.even){unsigned long r{(h-l)/2},z{(h-r)}; if(izRev(n,r,z)) std::cout<<"n="<<z<<" r="<<r<<" n-r="<<l<<" n+r="<<h<<std::endl;}
for(auto l:L.odd) for(auto h:H.odd) {unsigned long r{(h-l)/2},z{(h-r)}; if(izRev(n,r,z)) std::cout<<"n="<<z<<" r="<<r<<" n-r="<<l<<" n+r="<<h<<std::endl;}
}
};
int main(){
Rare(19);
}</syntaxhighlight>
:Compiling this with g++ brings the overall execution time down from 30 to 21 minutes in round figures. So the figures for clang or mingw may well come in at below 10 minutes now.
:Waiting to see now if Horst.h can blow us all out of the water with a super-fast Pascal version :)
--[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 12:55, 21 March 2020 (UTC)
::I recently installed mingw and verified that the tweaked c++ 10-19 version does indeed execute in 8 2/3 minutes for the 19 digit block. The overall time for blocks 10 - 19 is 10 1/3 minutes.
:: I also installed gmp and tried the c++ 20+ digit version, but found issues. 10, 12, & 13 had normal output, but digits 14 and up spent the approximate calculation time without producing any solutions. Has anyone else observed this issue? (By the way, I had to change ''long'' to ''long long'' in either version. Perhaps part of my issue?) --[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 02:30, 23 March 2020 (UTC)
::: Ah, just missed sub-10 minutes on the overall time but still impressively fast.
::: In C++ the width of the ''long'' type is, of course, implementation dependent and in g++ running on Ubuntu 18.04, amd64, sizeof(long) is 8 bytes. It looks like it's only 4 bytes on the version of mingw you're using (I don't know what Nigel's using), hence the need for ''long long''.
::: I haven't looked at the 20+ digit C++ version at all though, at first sight, it looks similar to the 10-19 digit version but with ''long'' replaced where necessary with ''mpz_t''. FWIW, I compiled (g++ -std=c++17 -O3 rare_ng3.cpp -lgmp -lgmpxx -o rare_ng3) and ran it on my machine and whilst it seemed to execute OK it wasn't very fast taking about 1 minute and 7.25 minutes respectively to complete up to and including the 16 and 17 digit blocks - g++ doesn't seem to be even at the races here :(
::: I've no idea what could be causing the issues you're having though it may be GMP related as it can be a pig to install correctly. A more fruitful approach might be to try and translate the C++ version to C# using the 128 bit integer library you found rather than System.Numerics.BigInteger though whether this will be any quicker than what you've done already I don't know. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 10:37, 23 March 2020 (UTC)
== Tweaks, C++ ==
Wringing out some more performance here, just over 5 minutes for 19 digits by themselves, and just over 6 minutes for digits 2 thru 19. See the code comments for details on what was tweaked. Curiously, I found that the g++ version executes faster than the clang++ version. Compiler arguments used: <code>g++ rare.cpp -o rare.exe -std=c++17 -O3</code><br/>Curious to see if it can go faster on a different platform - But the original executed faster on g++ than clang++ for me on my platform too. Perhaps I don't have clang++ set up the same as others?
<syntaxhighlight lang="cpp">// Rare Numbers : Nigel Galloway - December 20th., 2019
/*
speed related tweaks:
skip certain "outer" permutations which cannot produce squares (ends with 2, 3, 7, or 8), or will not produce squares for less than 20 digits (5 for diffs, and 9 & 14 for sums).
"outer" compute 5 digits instead of 4, that is, start at 12 digits instead of 10
diffs pre-computation of squares does only multiples of 9
don't compute every square up to 100_000, split diffs pre-computation of squares from sums pre-computation, and each has a separate limit for the pre-computation
do 2 through 11 digits by only looking at "middles" (no "outers") - accomplished by adding an additional definition for nLH() that takes only the function of optional long
when doing less that 12 digits, limit diffs to be above zero, and sums to be above a limit at which smaller squares produced are less than the forward number itself (pow10[n-1] * 4)
makeL(), makeH() return nLH() now, instead of nLH() components. That is, no pair<> construction
computes "outers" to a single value (vector of long instead of a vector of pair<long, long>)
sends one power of ten to the mutable section instead of four
nLH.odd / nLH.even selection based on oddness of current "outer" value, instead of the sqare itself
cosmetic or unnecessary tweaks:
start calculations at 2 digits instead of 10
converted output to printf()
indicate count of solutions
added elasped time indications
sorted output
optional command line argument for maximum number of digits to compute
compute the power of ten array instead of declaring it with literals
*/
#include <functional>
#include <bitset>
#include <cmath>
#include <chrono>
using namespace std;
using namespace chrono;
template <typename T> // concatenates vectors
vector<T>& operator +=(vector<T>& v, const vector<T>& w) { v.insert(v.end(), w.begin(), w.end()); return v; }
int sc = 0; // solution counter
auto st = steady_clock::now(), st0 = st, tmp = st; double dir = 0; // for determining elasped time
using Z2 = optional<long long>;
using Z1 = function<Z2()>;
using VU = vector<unsigned long long>;
using VS = vector<string>;
constexpr array<const int, 7> li { 1, 3, 0, 0, 2, 0, 1 };
constexpr array<const int, 17> lu { 1, 2, 0, 0, 1, 1, 4, 0, 0, 0, 1, 4, 0, 0, 0, 1, 1 };
// powers of 10 array
constexpr auto pow10 = [] { array <long long, 19> n {1}; for (int j{0}, i{1}; i < 19; j = i++) n[i] = n[j] * 10; return n; } ();
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(); };
}
int c = 0; // solution counter
long long acc, l, llim;
struct nLH {
vector<unsigned long long>even{}, odd{};
nLH(Z1 a) { unsigned long long r;
while (auto i = a()) if (*i > llim) {
r = sqrt(*i); if (r * r == i) *i & 1 ? even.push_back(*i) : odd.push_back(*i); } }
nLH(Z1 a, vector<long long> b) { unsigned long long sq, r;
while (auto i = a()) for (auto ng : b) if ((ng > 0) | (*i > 0)) {
r = sqrt(sq = ng + *i); if (r * r == sq) ng & 1 ? even.push_back(sq) : odd.push_back(sq); } }
};
// 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;
}
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+=3) n[(g*g)%100000]=true; return n;}()};
const bitset<100000>bt {[]{bitset<100000>n{false}; for(int g{11};g<mbt;g++) n[(g*g)%100000]=true; return n;}()};
// reports one block of digits
void doOne(int n, nLH L, nLH H) {
VS lines = dump(n, L.even, H.even); lines += dump(n, L.odd , H.odd); sort(lines.begin(), lines.end());
duration<double> tet = (tmp = steady_clock::now()) - st; int ls = lines.size();
if (ls-- > 0)
for (int i = 0; i <= ls; i++)
printf("%3d %s%s", ++c, lines[i].c_str(), i == ls ? "" : "\n");
else printf("%s", string(47, ' ').c_str());
printf(" %2d: %s %s\n", n, dFmt(tmp - st0, 8).c_str(), dFmt(tet, 8).c_str()); st0 = tmp;
}
class Rare {
const nLH makeL(const int n) {
constexpr int r = 9; acc = llim = 0; Z1 g = [] { return Z2 {}; }; int s = -r, q = (n > 11) * 5;
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); }
return q ? nLH( g, [g0{0}, g1{0}, g2{0}, g3{0}, g4{0}, l3{pow10[n - 5]}] () mutable {
vector<long long> w {}; long long g; while (g0 < 7) {
if (bs[((g = -10000 * g4 -1000 * g3 - 100 * g2 - 10 * g1 - g0) + 1000000000000LL) % 100000]) w.push_back(l3 * (g4 + g3 * 10 + g2 * 100 + g1 * 1000 + g0 * 10000) + g);
if (g4 < r) ++g4; else { g4 = -r; if (g3 < r) ++g3; else { g3 = -r; if (g2 < r) ++g2; else { g2 = -r; if (g1 < r) ++g1; else { g1 = -r; g0 += li[g0]; } } } } }
return w; } () ) : nLH(g);
}
const nLH makeH(const int n) {
constexpr int r = 18; llim = pow10[n - 1] << 2; acc = -pow10[n >> 1] - pow10[(n - 1) >> 1]; Z1 g = [] { return Z2 {}; };
int q = (n > 11) * 5;
for (int i = 1; i < (n >> 1) - q + 1; ++i)
g = fG(g, 0, r, 0, pow10[n - i - q] + pow10[i + q - 1], acc);
if (n & 1) { l = pow10[n >> 1] << 1; g = fG(g, 0, r >> 1, 0, l, acc += l); }
return q ? nLH(g, [g0{4}, g1{0}, g2{0}, g3{0}, g4{0}, l3{pow10[n - 5]}] () mutable {
vector<long long> w {}; long long g; while (g0 < 17) {
if (bt[(g = g4 * 10000 + g3 * 1000 + g2 * 100 + g1 * 10 + g0) % 100000]) w.push_back(l3 * (g4 + g3 * 10 + g2 * 100 + g1 * 1000 + g0 * 10000) + g);
if (g4 < r) ++g4; else { g4 = 0; if (g3 < r) ++g3; else { g3 = 0; if (g2 < r) ++g2; else { g2 = 0; if (g1 < r) ++g1; else { g1 = 0; g0 += lu[g0]; } } } } }
return w; } () ) : nLH(g);
}
public: 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(int(nd));
}</syntaxhighlight>
{{out}}
Results on the core i7-7700 @ 3.6Ghz.
<pre style="height:64ex;overflow:scroll"> nth forward rt.sum rt.diff digs block.et total.et
1 65 11 3 2: 0.00334s 0.00334s
3: 0.00289s 0.00623s
4: 0.00244s 0.00868s
5: 0.00320s 0.01188s
2 621770 836 738 6: 0.00308s 0.01496s
7: 0.00281s 0.01777s
8: 0.00336s 0.02113s
3 281089082 23708 330 9: 0.00746s 0.02860s
4 2022652202 63602 300
5 2042832002 63602 6360 10: 0.01855s 0.04715s
11: 0.09707s 0.14422s
6 868591084757 1275175 333333
7 872546974178 1320616 32670
8 872568754178 1320616 33330 12: 0.01456s 0.15879s
9 6979302951885 3586209 1047717 13: 0.04947s 0.20826s
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.12746s 0.33572s
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: 0.73898s 1.07470s
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: 2.25107s 3.32578s
41 22542040692914522 212329862 333300
42 67725910561765640 269040196 251135808
43 86965750494756968 417050956 33000 17: 13.6768s 17.0026s
44 225342456863243522 671330638 297000
45 225342458663243522 671330638 303000
46 225342478643243522 671330638 363000
47 284684666566486482 754565658 30000
48 284684868364486482 754565658 636000
49 297128548234950692 770186978 32697330
50 297128722852950692 770186978 32702670
51 297148324656930692 770186978 33296670
52 297148546434930692 770186978 33303330
53 497168548234910690 770186978 633363336
54 619431353040136925 1071943279 299667003
55 619631153042134925 1071943279 300333003
56 631688638047992345 1083968809 297302703
57 633288858025996145 1083968809 302637303
58 633488632647994145 1083968809 303296697
59 653488856225994125 1083968809 363303363
60 811865096390477018 1273828556 33030330
61 865721270017296468 1315452006 32071170
62 871975098681469178 1320582934 3303300
63 898907259301737498 1339270086 64576740 18: 42.5039s 59.5065s
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: 5m3.388s 6m2.894s</pre>
--[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 23:46, 25 May 2020 (UTC)
::Good to see the spirit of C is alive and well multyplying bools by integers and mysterious 3.94's. Idiotmatic? who cares? but old fashioned never, so perhaps int sc{0}; rather than int sc=0;. I have compiled the code using mingw on an Core I5 1035G1 and using g++ and clang++ on a Core I7 Q720 (now a very old machine). Interestingly the poor old Q720 takes about the same time for g++ and clang++ with this code. The time taken by the Core I5 1035G1 is the same as your i7 for 2..18 but interestingly about 10secs faster for 19. I shall look at the actual changes over the next few days, the important thing is that they mustnot be based on knowing the result. The timings I have obtained are:
<pre>
nth forward rt.sum rt.diff digs block.et total.et
1 65 11 3 2: 0.00027s 0.00027s
3: 0.00002s 0.00030s
4: 0.00001s 0.00031s
5: 0.00002s 0.00034s
2 621770 836 738 6: 0.00005s 0.00040s
7: 0.00025s 0.00066s
8: 0.00075s 0.00142s
3 281089082 23708 330 9: 0.00477s 0.00619s
4 2022652202 63602 300
5 2042832002 63602 6360 10: 0.01432s 0.02051s
11: 0.08783s 0.10835s
6 868591084757 1275175 333333
7 872546974178 1320616 32670
8 872568754178 1320616 33330 12: 0.01142s 0.11977s
9 6979302951885 3586209 1047717 13: 0.05034s 0.17011s
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.12319s 0.29331s
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: 0.72540s 1.01872s
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: 2.24472s 3.26344s
41 22542040692914522 212329862 333300
42 67725910561765640 269040196 251135808
43 86965750494756968 417050956 33000 17: 13.9236s 17.1870s
44 225342456863243522 671330638 297000
45 225342458663243522 671330638 303000
46 225342478643243522 671330638 363000
47 284684666566486482 754565658 30000
48 284684868364486482 754565658 636000
49 297128548234950692 770186978 32697330
50 297128722852950692 770186978 32702670
51 297148324656930692 770186978 33296670
52 297148546434930692 770186978 33303330
53 497168548234910690 770186978 633363336
54 619431353040136925 1071943279 299667003
55 619631153042134925 1071943279 300333003
56 631688638047992345 1083968809 297302703
57 633288858025996145 1083968809 302637303
58 633488632647994145 1083968809 303296697
59 653488856225994125 1083968809 363303363
60 811865096390477018 1273828556 33030330
61 865721270017296468 1315452006 32071170
62 871975098681469178 1320582934 3303300
63 898907259301737498 1339270086 64576740 18: 42.8003s 59.9873s
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: 4m52.40s 5m52.39s
g++ (SUSE Linux) 9.2.1 20200109 [gcc-9-branch revision 280039]
40 8650349867341457 127246955 33300333 16: 15.5694s 22.0091s
43 86965750494756968 417050956 33000 17: 1m33.80s 1m55.81s
63 898907259301737498 1339270086 64576740 18: 4m57.66s 6m53.47s
75 8320411466598809138 4079154376 36366330 19: 30m31.1s 37m24.5s
clang version 9.0.1
40 8650349867341457 127246955 33300333 16: 15.1173s 21.4643s
43 86965750494756968 417050956 33000 17: 1m32.36s 1m53.82s
63 898907259301737498 1339270086 64576740 18: 4m47.22s 6m41.04s
75 8320411466598809138 4079154376 36366330 19: 29m5.71s 35m46.7s
</pre>
--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:05, 10 June 2020 (UTC)
:::Thanks for those comparisons, appreciated. Re ''3.94'', the limit is 4, I was just undercutting it a bit. --[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 00:58, 17 June 2020 (UTC)
* nLH.odd / nLH.even selection based on oddness of current "outer" value, instead of the sqare itself: Okay but the odd numbers seem to be in the even bucket and the even numbers are in the odd bucket. Probably my fault for calling them odd and even since the only requirement is that the are split, not what the bucket is called, but I couldn't sleep with them the wrong way round so I've but them in the correct named bucket.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:09, 4 January 2021 (UTC)
* skip certain "outer" permutations which cannot produce squares (ends with 2, 3, 7, or 8), or will not produce squares for less than 20 digits (5 for diffs, and 9 & 14 for sums): There is no reason why 5 can not produce a rare number. 9 & 14 will not for any Rare number of any length. The situation for g0 and g1 for all rare numbers is:
<pre>
Diffs (L)
g0 -> g1
0 -> 0
1 -> -7..2..9
4 -> -8..2..8
5 -> -3;7
6 -> -9..2..9
Sums (H)
g0 -> g1
4 -> 0..2..18
6 -> 1..2..17
10 -> 9
11 -> 1..2..17
15 -> 1;11
16 -> 0..2..18
</pre>
--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:09, 4 January 2021 (UTC)
* Do 2 through 11 digits by only looking at "middles" (no "outers") - accomplished by adding an additional definition for nLH() that takes only the function of optional long when doing less that 12 digits, limit diffs to be above zero, and sums to be above a limit at which smaller squares produced are less than the forward number itself (pow10[n-1] * 4) makeL(), makeH() return nLH() now, instead of nLH() components: Okay but no need for an extra global variable. It is really a parameter to nLH's constructor (single) as now only one constructor is required.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:09, 4 January 2021 (UTC)
* The pair "construction" shouldn't incur an overhead as the compiler should optimize it away. It adds flexability to the design, the need for which I shall reserve judgement.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:09, 4 January 2021 (UTC)
:::Thank you for the code review and adopting some of the tweaks I presented. Good fix for my awkward handling of digits 2-11. I agree about the pair construction, I only removed it to speed up my C# translation, which was slightly impacting performance (perhaps due to an awkward translation on my part.)<br><br>
:::I agree that digit '5' ought to be considered in the "diff" side. Even though it doesn't contribute to any solution in the ''Int64'' range, if ''Int128'' ever becomes part of C++, your program should be easily extended to the point where checking "diff 5" will contribute a solution. My decision to omit checking '5' was for performance reasons since we are constricted to ''Int64''.--[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 00:01, 25 January 2021 (UTC)
== 21+ digit rare numbers ==
Well, one anyway (so far). I tweaked the BigInteger version of the C# program to skip to start at 21 digits. Around 6 hours, I got the first one: '''219,518,549,668,074,815,912''', with the sum = '''20,953,210,268
I am also running another instance that checks the block of 20 digit numbers (in order to verify the algorithm against the table of known rare numbers), but after 6 hours, it still hasn't come up with anything yet. A little surprising, as there are a few 20 digit rare numbers with 7 digit differences. If I don't see anything on the 20 digit run in 6 more hours, there may be some kind of issue to work out. --[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 02:52, 21 October 2019 (UTC)
Line 509 ⟶ 1,285:
P.S. 5 found so far:
<pre>
Nth Time (hours) rare number
85 6 219,518,549,668,074,815,912
86 10 1/2 837,982,875,780,054,779,738
87 11 1/2 208,393,425,242,000,083,802
88 12 1/3 286,694,688,797,362,186,682
89 13 2/3 257,661,195,832,219,326,752</pre>
--[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 21:29, 22 October 2019 (UTC)
Line 523 ⟶ 1,299:
::Regarding missing solutions at 20 digits, I found that the Math.Sqrt() function may drop a few bits of resolution at 20 digits or more. Not totally unexpected. However, the Math.Sqrt() function can be used as an initial accurate first guess in a Newton's method integer square root function.
::::: There is an integer square root function that only uses integers and floating point multiple and division isn't used. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 07:31, 12 January 2020 (UTC)
::I agree the 8,3 combo should be added for 21+ digits computation. For the task as defined, (5th to 8th number), it's not needed. But for going beyond the table on Shyam Sunder Gupta's webpage, one really needs to consider that combination.
::::: I e-mailed Shyam Sunder Gupta and he said he'd update his webpage. He said that he figured nobody would compute ''rare'' numbers that high, so he didn't bother to enter the updated list before. He also mentioned that he had found a ''rare'' number ending in the decimal digit '''3'''. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 07:26, 12 January 2020 (UTC)
::I see this BigInteger conversion attempt as a means of reaching a few 21 digit numbers (which it did) and a means to reveal any shortcomings in the existing ulong algorithm which don't translate well to the BigInteger version (which it also did, I guess). If only it wasn't so impractically slow. If I could get it an order of magnitude faster, it would easier to persue this further. Creating a multi-tasking version would probably only go 2 to 4 times faster.--[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 06:57, 24 October 2019 (UTC)
There only seem to be 5 21 digit rare numbers, so I started looking at 22 digits. I found that each odd number of digits takes less time (about 80% of the time) of the previous even number of digits, but each even/odd pair (number of digits such as 16/17 vs 14/15) takes about 20 times a long as the previous pair, so the computation time increases dramatically for results above 19 digits. Here are
<font color=blue>'''S.No.''' '''R''' '''R+R1''' '''R-R1'''</font>
85 208393425242000083802 20415029402<sup>2</sup> 115866300<sup>2</sup>
86 219518549668074815912 20953210268<sup>2</sup> 8877000<sup>2</sup>
87 257661195832219326752 22699892248<sup>2</sup> 193089600<sup>2</sup>
88 286694688797362186682 23945269942<sup>2</sup> 115866300<sup>2</sup>
89 837982875780054779738 40938494426<sup>2</sup> 73659300<sup>2</sup>
90 2414924301133245383042 69417286928<sup>2</sup> 3329996670<sup>2</sup>
91 2414924323311045383042 69417286928<sup>2</sup> 3330003330<sup>2</sup>
92 2414946523311023183042 69417286928<sup>2</sup> 3336663330<sup>2</sup>
93 2576494891793995836752 71783569748<sup>2</sup> 329996700<sup>2</sup>
94 2576494893971995836752 1783569748<sup>2</sup> 330003300<sup>2</sup>
95 2620937863931054483162 72351795868<sup>2</sup> 2663336730<sup>2</sup>
96 2620955623931476283162 72351795868<sup>2</sup> 2669996730<sup>2</sup>
97 2620955641393276283162 72351795868<sup>2</sup> 2670003270<sup>2</sup>
98 2622935621573476481162 72351795868<sup>2</sup> 3329996670<sup>2</sup>
99 2622935643751276481162 72351795868<sup>2</sup> 3330003330<sup>2</sup>
100 2622937641933274481162 72351795868<sup>2</sup> 3330603330<sup>2</sup>
101 2622955841933256281162 72351795868<sup>2</sup> 3336063330<sup>2</sup>
102 2622957843751254281162 72351795868<sup>2</sup> 3336663330<sup>2</sup>
103 2727651947516658327272 73857230612<sup>2</sup> 642947400<sup>2</sup>
104 2747736918335953517072 73857230612<sup>2</sup> 6370504140<sup>2</sup>
105 2788047668617596408872 74673252412<sup>2</sup> 26673000<sup>2</sup>
106 2788047848617776408872 74673252412<sup>2</sup> 32733000<sup>2</sup>
107 2788047868437576408872 74673252412<sup>2</sup> 33333000<sup>2</sup>
108 2788047888617376408872 74673252412<sup>2</sup> 33933000<sup>2</sup>
109 2939501759705522349392 76674206972<sup>2</sup> 263637300<sup>2</sup>
110 2939503375709360349392 76674206972<sup>2</sup> 269697300<sup>2</sup>
111 2939503537707740349392 76674206972<sup>2</sup> 270297300<sup>2</sup>
112 2939521359525562149392 76674206972<sup>2</sup> 329703300<sup>2</sup>
113 2939521557527542149392 76674206972<sup>2</sup> 330303300<sup>2</sup>
114 2939523577527340149392 76674206972<sup>2</sup> 336363300<sup>2</sup>
115 2939523779525320149392 76674206972<sup>2</sup> 336963300<sup>2</sup>
116 2959503377707360349192 76674206972<sup>2</sup> 6330303360<sup>2</sup>
<font color=red> '''117''' '''6344828989519887483525''' '''107697153531'''<sup>'''2'''</sup> '''33030003033'''<sup>'''2'''</sup></font>
118 8045841652464561594308 126810067846<sup>2</sup> 3299999670<sup>2</sup>
119 8045841654642561594308 126810067846<sup>2</sup> 3300000330<sup>2</sup>
120 8655059576513659814468 131526610006<sup>2</sup> 3296970330<sup>2</sup>
121 8655059772157639814468 131526610006<sup>2</sup> 3297029670<sup>2</sup>
122 8655079374155679614468 131526610006<sup>2</sup> 3302969670<sup>2</sup>
123 8655079574515659614468 131526610006<sup>2</sup> 3303030330<sup>2</sup>
That took about 5 3/4 days of computation. Only one odd number. Lots of 2,2 combinations there. Nearly half of all rare numbers under 21 digits start and end with 2. The trend continues above 20 digits with over half starting and ending with 2. --[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 06:17, 2 December 2019 (UTC)
: Oops, it appears that I missed one, '''Shyam Sunder Gupta''' has published an updated list of 124 Rare numbers up to 22 digits on his webpage, back on December 15th. The one I missed is the first Rare number ending with 3.
<font color=red> '''124''' '''8888070771864228883913''' '''109917964849'''<sup>'''2'''</sup> '''75459807495'''<sup>'''2'''</sup></font>
:At least that verifies that there are only 5 21 digit Rare numbers. --[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 22:46, 26 December 2019 (UTC)
Some 23s:
125 (20,006,212,343,920,163,220,002)
126 (20,404,210,361,902,143,200,402)
127 (21,544,373,975,964,337,344,512)
128 (22,781,275,420,027,357,218,722)
129 (80,618,209,916,486,890,281,608)
130 (81,313,065,142,333,312,588,218)
131 (84,247,683,299,691,574,674,248)
132 (89,650,295,750,128,200,205,698)
That's 8 found for 23 digits, taking ~4 1/5 days to go through the combinations. --[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 17:54, 15 December 2019 (UTC)
:Now that you've established that there are five 21 digit rare numbers, it might be worth mailing SSG (at guptass@rediffmail.com) to see if he'll add them to his list.
Line 576 ⟶ 1,378:
::To get to 22 digits, I had to use multitasking and that C# UI128 package you spotted. The performance of the UI128 package is good, only about two and a half times worse than UI64's, whereas BigInteger is around 7 to 8 times worse. The UI128 package should go up to 38 decimal digits or so. But because it takes 20 times longer for each additional pair of digits, I don't think 38 digits a possibilty with the current algorithm. I am contemplating a new algorithm that could be more efficient.
::Regarding the 5 21 digit rare numbers found, to prove that there are only 5, what is really needed is to prove that all 10<sup>21</sup> - 5 of the possible 10
:::Congratulations on completing the 23 digit rare numbers! You've a lot more patience (and spare computing capacity) than me :) --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 18:19, 15 December 2019 (UTC)
::::I've entered code in C++ which I expect using clang++ on the monster beasts you have for computers will complete 21 in a day and a quarter and 22 in less than 4 days. The difference between clang++ and g++ is suprising. It would be interesting to know how MSVC does.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 12:28, 20 December 2019 (UTC)
:::::I don't have clang but, compiling your C++ code for 10 to 19 digits on my core i7 using g++ v7.4 (-std=c++17 -O3) on Ubuntu 18.04, produces execution times of 11.7, 78, 221 and 1484 seconds for rare numbers with 16, 17, 18 and 19 digits respectively. The corresponding times for the Go entry (with the Julia entry not far behind) were 221, 355, 4532 and 6610 seconds so, even if we assume these languages are 2 or 3 times slower than C++, the algorithm you're now using is considerably more efficient than what we had before.
::::::Thanks for that. I've timed it on a Core I5 1035G1 and obtained 17->33sec; 18->92sec; and 19->741sec. For comparison I compiled the C# and obtained 17->6m45sec (compared to 2m12sec on an i7 7700 claimed on the page).--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 16:40, 13 March 2020 (UTC)
:::::::We've certainly had a wide variation in the timings for this task and it appears now that g++ is much slower than both clang and mingw for some reason. The C# time for 17 numbers looks right to me as my Go translation was only a second or two behind, again using Core I7. I'm surprised how much quicker C++ is than C#, its stable-mate VB.NET and Go for this task. Although Enter your Username has clearly tried hard to minimize the effect of GC by declaring huge swathes of variables 'static', the performance gap is still huge. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 11:35, 14 March 2020 (UTC)
::::::::I thought for good measure I'd add a Go translation of your C++ program (10 to 19 digits version) and this has cut the execution time from 54 to 21 minutes in round figures which seems more in line with expectations. For comparison, I compiled the C++ program again (using g++ 7.5.0 this time) and ran it on the same machine but the total execution time was almost identical at around 30 minutes so it's difficult to know what to make of it. Perhaps g++ is not yet quite up to speed with C++ 17 features? --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 17:07, 16 March 2020 (UTC)
::::::::I thought for good measure I'd (tit for tat?) install Go and run your goTurbo code on my i5-1035G1. I obtained the following:
40 8,650,349,867,341,457 16: 00:00:06.403 00:00:09.163
43 86,965,750,494,756,968 17: 00:00:42.818 00:00:51.982 (mingw real 0m33.328s)
63 898,907,259,301,737,498 18: 00:02:01.282 00:02:53.264 (mingw real 1m32.945s)
75 8,320,411,466,598,809,138 19: 00:15:36.454 00:18:29.719 (mingw real 12m21.298s)
I think this demonstrates that the task should require at least the first 63 Rare numbers!!!
--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 12:22, 19 March 2020 (UTC)
::::LOL, the Go version is even faster on your i5 than it is on my i7, and only about 50% behind mingw! I imagine you're running it on Windows 10 whereas I'm using Ubuntu 18.04 but that shouldn't make much difference. Probably should have bought an i7 with a higher basic clock speed as performance can be a bit disappointing at times.
::::The stretch goal is already open-ended and Enter your username has certainly gone well beyond the call of duty there :) --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 14:32, 19 March 2020 (UTC)
::::: I find it hard to believe that clang++ could be 3 times faster than g++ (though you can get some strange results with these CPU-intensive tasks) and, although I no longer have an up to date Windows machine, on past form I'd be surprised if Visual C++ were any faster than g++ itself. Enter your username may be able to confirm the position there. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 20:53, 20 December 2019 (UTC)
::::::I tried compiling it using MSVC. It crashed the compiler, well at least caused it to catch an internal error.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 16:40, 13 March 2020 (UTC)
==Broken Link==
The link to lots of facts and hints on the main page seems to be broken!
| |||