Talk:Rare numbers

comments concerning   interesting observations   from an webpage

(The author's webpage, the last URL reference from this task's preamble, re-shown below:)

(a URL reference):

•   author's  website:   rare numbers   by Shyam Sunder Gupta.     (lots of hints and some observations).

I was considering adding checks   (to the REXX program)   to assert that for:

•   when the number of digits in a rare number is even,   the   sum   must be divisible by   11,     and
•   when the number of digits in a rare number is   odd,   the   difference   must be divisible by   9.

n-r is divisible by 9 for all Rare numbers. n-r is also divisible by 99 when the number of digits is odd. (see Talk:Rare_numbers#30_mins_not_30_years)--Nigel Galloway (talk) 13:48, 21 September 2019 (UTC)

30 mins not 30 years

If Shyam Sunder Gupta has really spent 30 years on this he should have stayed in bed. Let me spend 30mins on it. The following took 9mins so any questions and I have 21mins to spare.

Let me consider n-r=l for a 2 digit number ng n<g. Then l=(10g+n)-(g+10n)=9(g-n) where n is 0..8 and g is 1..9.
l is one of 9 18 27 36 45 54 63 72 81. l must be a perfect square so only 9 36 and 81 are of interest.

9 -> ng=89 78 67 56 45 34 23 12 01
36-> ng=59 48 37 26 15 04
81-> ng=09

For each of these candidate ng I must determine if ng+gn is a perfect square.

09+90  99 n
59+95 154 n
48+84 132 n
37+73 110 n
26+62 114 n
15+51  66 n
04+40  44 n
89+98 187 n
78+87 165 n
67+76 143 n
56+65 121 y
45+54  99 n
34+43  77 n
23+32  55 n  
12+21  33 n
01+10  11 n

From which I see that 65 is the only Rare 2 digit number.

I love an odd number of digits. Let me call the 3 digit number nxg. l=(100g+10x+n)-(g+10x+100n).
x disappears and I am left with 99(g-n). None of 99 198 297 396 495 594 693 792 or 894 are perfect squares.
So there are no Rare 3 digit numbers.

At 4 I begin to think about using a computer. Consider nige. l=(1000e+100g+10i+n)-(e+10g+100i+1000n).
I need a table for l as above for 9(111(e-n)+10(g-i)) where n<=e and if n=e then i<g.

Before turning the computer on I'll add that for 5 digits nixge l=(10000e+1000g+100x+10i+n)-(e+10g+100x+1000i+10000n).
x disappears leaving 99(111(e-n)+10(g-i))

--Nigel Galloway (talk) 13:34, 12 September 2019 (UTC)

I have turned the computer on and produced a solution using only the above and nothing from the referenced website which completes in under a minute. The reference is rubbish, consider removing it--Nigel Galloway (talk) 10:42, 18 September 2019 (UTC)

Rubbish or not, is there anything on the referenced (Gupta's) website that is incorrect?   The properties and observations is what the REXX solution used (and others have as well) to calculate   rare   numbers,   albeit not as fast as your algorithm.   I have no idea how long Shyam Sunder Gupta's program(s) executed before it found eight rare numbers   (or how much virtual memory it needed).   Is the   F#   algorithm suitable in finding larger   rare   numbers?   I suspect (not knowing F#) that virtual memory may become a limitation.   Eight down, seventy-six more to go.     -- Gerard Schildberger (talk) 18:18, 18 September 2019 (UTC)

So is the task now to replicate [[1]]? This may not be reasonable for a RC task as I now discuss.
Why have you "no idea how long Shyam Sunder Gupta's program(s) executed before it found eight rare numbers"? On the webpage it says "the program has been made so powerful that all numbers up to 10^14 can be just checked for Rare numbers in less than a minute". This implies that it can search 10^13 in 5 secs. I believe this. The problem with the webpage is not that it is wrong, but that it is disingenuous. I estimate that the following is achievable:
10^13 -> 5 secs;
10^15 -> 60 secs;
10^17 -> 20 mins;
10^19 -> 7 hours;
10^21 -> 6 days;
10^23 -> 4 months.
I would say that 10^17 is reasonable for a RC task and is in line with the timings given on the webpage. Those who have recently obtained an 8th. generation i7 might want to observe that there is an obvious multithreading strategy and might want to prove that Goroutines are more than a bad pun on coroutines, as a suitable punishment for making me envious. (Warning, from my experience of i7s it might be wise to take it back to the shop and have water cooling installed before attempting to run it for a day and a half on full throttle). I remain to be convinced that these benchmarks are achieved by the Fortran, Ubasic programs on the webpage, or can be achieved in this task using the methods described on the webpage.
It is necessary to distinguish the algorithm I describe above from the F# implementation on the task page. The algorithm can be written to require very little memory. Obviously the F# as it stands calculates all candidates before checking them and this list grows with increasing number of digits. It is more than adequate for the current task, and I anticipate little difficulty in accommodating reasonable changes to make the task less trivial as layed out above--Nigel Galloway (talk) 14:01, 20 September 2019 (UTC)

Obviously, this task's requirement is not to replicate the list of 84   rare   numbers on  [Shyam Sunder Gupta's webpage: a list of 84 rare numbers].   The task requirements have not changed:   find and show the first   5   rare   numbers.   The last two requirements are optional.   Any hints and properties can be used as one sees fit.     -- Gerard Schildberger (talk) 17:55, 20 September 2019 (UTC)

Well, I have to admit that Nigel's (n-r) approach is considerably faster than what SSG has published as I've just added a second Go version which finds the first 25 Rare numbers (up to 15 digits) in about 42 seconds, albeit on my Core i7 which is kept cool when hitting turbo mode by a rather noisy fan.

Although I don't doubt SSG's claims (he is presumably a numerical expert), he must be using much more sophisticated methods than he has published to achieve those sort of times on antique hardware.

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. --PureFox (talk) 23:04, 24 September 2019 (UTC)

the 1^st REXX version

This is the 1^st REXX version,   before all the optimizations were added: <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.*/ if many== | many=="," then many= 3 /*Not specified? Then use the default.*/

1. = 0 /*the number of rare numbers (so far)*/

   do n=10                                      /*N=10, 'cause 1 dig #s are palindromic*/
   r= reverse(n)                                /*obtain the reverse of the number  N. */
   if r>n   then iterate                        /*Difference will be negative?  Skip it*/
   if n==r  then iterate                        /*Palindromic?   Then it can't be rare.*/
   s= n+r                                       /*obtain the    sum     of  N  and  R. */
   d= n-r                                       /*   "    "  difference  "  "   "   "  */
   if iSqrt(s)**2 \== s  then iterate           /*Not a perfect square?  Then skip it. */
   if iSqrt(d)**2 \== d  then iterate           /* "  "    "       "       "    "   "  */
   #= # + 1                                     /*bump the counter of  rare  numbers.  */
   say right( th(#), length(#) + 9)       ' rare number is:  '       right( commas(n), w)
   if #>=many  then leave                       /* [↑]  W:  the width of # with commas.*/
   end   /*n*/

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _ th: parse arg th;return th||word('th st nd rd',1+(th//10)*(th//100%10\==1)*(th//10<4)) /*──────────────────────────────────────────────────────────────────────────────────────*/ iSqrt: parse arg x; $= 0; q= 1; do while q<=x; q= q*4

                                                                 end  /*while q<=x*/
                 do while q>1;  q= q % 4;   _= x-$-q;   $= $ % 2
                 if _>=0  then do;          x= _;       $= $ + q
                               end
                 end   /*while q>1*/;                            return $</lang>

Pretty simple,   but slow as molasses in January.

Not ready for prime time.

the 2^nd REXX version

This is the 2^nd REXX version,   after all of the hints   (properties of   rare   numbers)   within Shyam Sunder Gupta's
webpage   have been incorporated in this REXX program. <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.*/ if many== | many=="," then many= 5 /*Not specified? Then use the default.*/

@dr.=0; @dr.2= 1; @dr.5=1 ; @dr.8= 1; @dr.9= 1 /*rare # must have these digital roots.*/ @ps.=0; @ps.2= 1; @ps.3= 1; @ps.7= 1; @ps.8= 1 /*perfect squares must end in these.*/ @end.=0; @end.1=1; @end.4=1; @end.6=1; @end.9=1 /*rare # must not end in these digits.*/ @dif.=0; @dif.2=1; @dif.3=1; @dif.7=1; @dif.8=1; @dif.9=1 /* A─Q mustn't be these digs.*/ @noq.=0; @noq.0=1; @noq.1=1; @noq.4=1; @noq.5=1; @noq.6=1; @noq.9=1 /*A=8, Q mustn't be*/ @149.=0; @149.1=1; @149.4=1; @149.9=1 /*values for Z that need a even Y. */

1. = 0 /*the number of rare numbers (so far)*/

@n05.=0; do i= 1 to 9; if i==0 | i==5 then iterate; @n05.i= 1; end /*¬1 ¬5*/ @eve.=0; do i=-8 by 2 to 8; @eve.i=1; end /*define even " some are negative.*/ @odd.=0; do i=-9 by 2 to 9; @odd.i=1; end /* " odd " " " " */

                                                /*N=10, 'cause 1 dig #s are palindromic*/
   do n=10;  parse var  n  a 2 b 3  -2 p +1 q /*get 1st\2nd\penultimate\last digits. */
   if @end.q  then iterate                      /*rare numbers can't end in: 1 4 6 or 9*/
   if q==3    then iterate

      select                                    /*weed some integers based on 1st digit*/
      when a==q  then do
                      if a==2|a==8 then nop     /*if A = Q,   then A must be  2  or 8. */
                                   else iterate /*A  not two or eight?       Then skip.*/
                      if b\==p  then iterate    /*B  not equal to  P?        Then skip.*/
                      end
      when a==2  then do; if q\==2 then iterate /*A = 2?     Then  Q  must also be  2. */
                          if b\==p then iterate /*" " "      Then  B  must equal    P. */
                 end
      when a==4  then do
                      if q\==0   then iterate   /*if Q not equal to zero, then skip it.*/
                      _= b - p                  /*calculate difference between B and P.*/
                      if @eve._  then iterate   /*Positive not even?      Then skip it.*/
                      end
      when a==6  then do
                      if @n05.q  then iterate   /*Q  not a zero or five?  Then skip it.*/
                      _= b - p                  /*calculate difference between B and P.*/
                      if @eve._  then iterate
                      end
      when a==8  then do
                      if @noq.q  then iterate   /*Q  isn't one of 2, 3, 7, 8?  Skip it.*/
                        select
                        when q==2  then            if b+p\==9                then iterate
                        when q==3  then do; if b>p         then if b-p\== 7  then iterate

else if b

1 then if b+p\==11 then iterate else if b==0 then if b+p\== 1 then iterate end when q==8 then if b\==p then iterate otherwise nop end /*select*/ end /* [↓] A is an odd digit. */ otherwise n= n + 10**(length(n) - 1) - 1 /*bump N so next N starts with even dig*/ iterate /*Now, go and use the next value of N.*/ end /*select*/ _= a - q; if @dif._ then iterate /*diff of A─Q must be: 0, 1, 4, 5, or 6*/ r= reverse(n) /*obtain the reverse of the number N. */ if r>n then iterate /*Difference will be negative? Skip it*/ if n==r then iterate /*Palindromic? Then it can't be rare.*/ d= n-r; parse var d -2 y +1 z /*obtain the last 2 digs of difference.*/ if @ps.z then iterate /*Not 0, 1, 4, 5, 6, 9? Not perfect sq.*/ select when z==0 then if y\==0 then iterate /*Does Z = 0? Then Y must be zero. */ when z==5 then if y\==2 then iterate /*Does Z = 5? Then Y must be two. */ when z==6 then if y//2==0 then iterate /*Does Z = 6? Then Y must be odd. */ otherwise if @149.z then if y//2 then iterate /*Z=1,4,9? Y must be even*/ end /*select*/ s= n+r; parse var s -2 y +1 z /*obtain the last two digits of the sum*/ if @ps.z then iterate /*Not 0, 2, 5, 8, or 9? Not perfect sq.*/ select when z==0 then if y\==0 then iterate /*Does Z = 0? Then Y must be zero. */ when z==5 then if y\==2 then iterate /*Does Z = 5? Then Y must be two. */ when z==6 then if y//2==0 then iterate /*Does Z = 6? Then Y must be odd. */ otherwise if @149.z then if y//2 then iterate /*Z=1,4,9? Y must be even*/ end /*select*/ $= a + b /*a head start on figuring digital root*/ do k=3 for length(n) - 2 /*now, process the rest of the digits. */ $= $ + substr(n, k, 1) /*add the remainder of the digits in N.*/ end /*k*/ /*This REXX pgm uses 20 decimal digits.*/ do while $>9 /* [◄] Algorithm is good for 111 digs.*/ if $>9 then $= left($,1) + substr($,2,1)+ substr($,3,1,0) /*>9? Reduce to a dig*/ end /*while*/ if \@dr.$ then iterate /*Doesn't have good digital root? Skip*/ if iSqrt(s)**2 \== s then iterate /*Not a perfect square? Then skip it. */ if iSqrt(d)**2 \== d then iterate /* " " " " " " " */ #= # + 1 /*bump the counter of rare numbers. */ say right( th(#), length(#) + 9) ' rare number is: ' right( commas(n), w) if #>=many then leave /* [↑] W: the width of # with commas.*/ end /*n*/ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _ th: parse arg th;return th||word('th st nd rd',1+(th//10)*(th//100%10\==1)*(th//10<4)) /*──────────────────────────────────────────────────────────────────────────────────────*/ iSqrt: parse arg x; $= 0; q= 1; do while q<=x; q= q*4 end /*while q<=x*/ do while q>1; q= q % 4; _= x-$-q; $= $ % 2 if _>=0 then do; x= _; $= $ + q end end /*while q>1*/; return $</lang> Still pretty sluggish,   like molasses in March. The above REXX program was modified to generate a group of numbers which were   AB   (two digit) numbers
concatenated with   PQ   (two digit)   numbers to yield a list of four digit numbers. AB   are the 1^st two digits of a   rare   number,   and   PQ   are the   last two digits.
This list was sorted and the duplicates removed,   and it formed a list of   (left 2 digits abutted with the right 2 digits)
numbers that every   rare   number must have   (except for the first   rare   number   (65),   which is found the  hard
(slow)   way.

Tweaks, F#

Kudos to Nigel Galloway for the F# version. I don't know the language well, but was able to cut a few corners to improve performance slightly and add some stats:

Output at Tio.run (linked):

nth        Rare Number    elapsed  completed
 1                  65      97 ms 
                           120 ms    2
                           126 ms    3
                           127 ms    4
                           140 ms    5
 2             621,770     148 ms 
                           148 ms    6
                           151 ms    7
                           253 ms    8
 3         281,089,082     261 ms 
                           283 ms    9
 4       2,022,652,202     606 ms 
 5       2,042,832,002    1162 ms 
                          2528 ms   10
                          3423 ms   11
 6     872,546,974,178   16583 ms 
 7     872,568,754,178   17427 ms 
 8     868,591,084,757   28471 ms 
                         37612 ms   12

Of course, it can't get too far in the 60 second timeout window. Sometimes it doesn't get past the 5th number, due to poor luck at Tio.run. It can do 13 digits at Tio.run, as long as you start at 13:

nth        Rare Number    elapsed  completed
 1   6,979,302,951,885   21129 ms 
                         27470 ms   13

Output on a i7 core (Visual Studio Console App):

nth        Rare Number    elapsed  completed
 1                  65      22 ms
                            24 ms    2
                            26 ms    3
                            27 ms    4
                            28 ms    5
 2             621,770      31 ms
                            31 ms    6
                            33 ms    7
                            65 ms    8
 3         281,089,082      69 ms
                            76 ms    9
 4       2,022,652,202     221 ms
 5       2,042,832,002     373 ms
                           859 ms   10
                          1220 ms   11
 6     872,546,974,178    6284 ms
 7     872,568,754,178    6486 ms
 8     868,591,084,757   10336 ms
                         13739 ms   12
 9   6,979,302,951,885   16890 ms
                         19075 ms   13
10  20,313,693,904,202  105822 ms
11  20,313,839,704,202  106337 ms
12  20,331,657,922,202  116631 ms
13  20,331,875,722,202  118324 ms
14  20,333,875,702,202  122171 ms
15  40,313,893,704,200  257026 ms
16  40,351,893,720,200  258086 ms
                        283465 ms   14

Checking up to 14 digit numbers in under 5 minutes. Given more time, it can get the correct 17th number (first 15 digit number), but has problems after that. Not sure if it's the memory requirements, or perhaps I pared down Nigel's original program too much for valid output after 14 digits.

I added this here in the discussion and did not post the revised code on the main codepage out of respect for Nigel's original contribution. All I did was tweak it, and did not add any core improvements.

I've been trying to figure out how to put some limits on the permutation of numbers generated, but don't know F# well enough to do it effectively. And when I work in languages I am familiar with, the performance is decades of magnitude worse.--Enter your username (talk) 18:37, 22 September 2019 (UTC)

As mentioned earlier in this page, I've just added a second Go version based on Nigel's approach which is infinitely faster than the first. You're welcome to try and optimize it further as you're much better at this sort of thing than I am. The perfect square checking might be capable of improvement as I'm just using a simple math.Sqrt approach here rather than having a number of preliminary filters as I did in the first version. --PureFox (talk) 23:11, 24 September 2019 (UTC)

Tweaks, Go

Thank you PureFox for the Go translation. Here are the results of some code tweaking. Feel free to re-use anything you like on the main page. Some of the corners that were cut: 1. Computed the forward number, the reverse number and the digital root from the "digits" array all at the same time, rather than going back when needed. 2. Used a Boolean array of the last 2 digits of valid squares to determine whether to do the more computationally expensive floating point square root call. 3. The dl array can be seq(-9, 8), rather than seq(-9, 9). It doesn't seem to matter on the low number of digits ( <16 ) we are covering. The digital root fail check can be either before or after the !isSquare() check, you might find it slightly faster one way or the other.

Output from a core i7:

nth               number         time   completed
 1                    65             0s
                                970.4µs  2
                                970.4µs  3
                                970.4µs  4
                                970.4µs  5
 2               621,770        970.4µs
                                970.4µs  6
                               1.9676ms  7
                               4.9833ms  8
 3           281,089,082       5.9569ms
                               6.9785ms  9
 4         2,022,652,202      19.9197ms
 5         2,042,832,002      40.8908ms
                              84.7729ms 10
                              137.632ms 11
 6       872,546,974,178     646.2443ms
 7       872,568,754,178     677.1611ms
 8       868,591,084,757     1.0701309s
                             1.2416797s 12
 9     6,979,302,951,885     1.6326327s
                             1.9797045s 13
10    20,313,693,904,202    10.5358443s
11    20,313,839,704,202    10.6046898s
12    20,331,657,922,202    12.1206037s
13    20,331,875,722,202    12.3569934s
14    20,333,875,702,202    13.0172337s
15    40,313,893,704,200    22.9626308s
16    40,351,893,720,200    23.1066218s
                            24.4769465s 14
17   200,142,385,731,002    27.4160929s
18   221,462,345,754,122    27.6274982s
19   816,984,566,129,618     30.293394s
20   245,518,996,076,442    31.7365338s
21   204,238,494,066,002    31.9389919s
22   248,359,494,187,442    32.0028151s
23   244,062,891,224,042    32.3977374s
24   403,058,392,434,500    36.6045135s
25   441,054,594,034,340    36.8109598s
                            38.1518922s 15

It can't get past 15 digits, due to the memory requirement. I purposely let the "natural" order of the results display, as I was more interested in the performance time of each result.

Output from Tio.run (linked):

nth               number         time   completed
 1                    65      104.828µs
                              131.427µs  2
                              139.331µs  3
                              178.561µs  4
                              200.489µs  5
 2               621,770      698.249µs
                              757.813µs  6
                              1.42756ms  7
                             8.927975ms  8
 3           281,089,082    10.244811ms
                            12.738426ms  9
 4         2,022,652,202     72.43969ms
 5         2,042,832,002   123.310535ms
                           218.093377ms 10
                           415.295536ms 11
 6       872,546,974,178    1.93598265s
 7       872,568,754,178   2.000165728s
 8       868,591,084,757   2.821645253s
                           3.286164167s 12
 9     6,979,302,951,885   5.924838452s
                           6.864383645s 13

It can't get past 13 digits on Tio.run, due to memory requirement. Execution time at Tio.run is often worse than this, but it always completes in the 60 second time limit. --Enter your username (talk) 22:30, 28 September 2019 (UTC)