Rare numbers: Difference between revisions

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

<br><br>

 

=={{header|C sharp|C#}}==

{{trans|Go}}

Converted to unsigned longs in order to reach 19 digits.

using System.Collections.Generic;

using System.Linq;

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).

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

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.

 

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

#include <functional>

#include <cmath>

}

}

};

}

{{out}}

<pre>

</pre>

===20+ digits===

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

#include <iostream>

Rare(20);

}

{{out}}

<pre>

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

writefln(" %2d: %25s", i + 1, commatize(rare));

}

{{out}}

<pre>Aggregate timings to process all numbers up to:

39: 8,650,327,689,541,457

40: 8,650,349,867,341,457</pre>

 

=={{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=

|_->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)

 

===43 down===

let test n=

let t = System.Diagnostics.Stopwatch.StartNew()

 

[2..17] |> Seq.iter test

{{out}}

<pre>

Elapsed Time: 11275839 ms for length 17

</pre>

 

=={{header|Go}}==

 

As the algorithm used does not generate the Rare numbers in order, a sorted list is also printed.

 

import (

fmt.Printf(" %2d: %25s\n", i+1, commatize(rare))

}

 

{{output}}

{{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 (

ftTime := formatTime(time.Since(tStart))

fmt.Printf("%2d: %s %s\n", nd, fbTime, ftTime)

 

{{out}}

 

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 (

bStart = time.Now() // restart block timing

}

 

{{out}}

75 8,320,411,466,598,809,138 19: 00:12:48.590 00:15:14.316

</pre>

 

=={{header|Java}}==

{{trans|Kotlin}}

import java.time.LocalDateTime;

import java.util.ArrayList;

}

}

{{out}}

<pre>Aggregate timings to process all numbers up to:

=={{header|Julia}}==

{{trans|Go}}

 

struct Term

 

findrare()

Timings are on a 2.9 GHz i5 processor, 16 Gb RAM, under Windows 10.

<pre style="height:126ex;overflow:scroll">

=={{header|Kotlin}}==

{{trans|D}}

import java.time.LocalDateTime

import kotlin.math.sqrt

println(" %2d: %25s".format(i_rare.index + 1, commatize(i_rare.value)))

}

{{out}}

<pre>Aggregate timings to process all numbers up to:

39: 8,650,327,689,541,457

40: 8,650,349,867,341,457</pre>

 

=={{header|langur}}==

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 .israre() function appears to return the right answer, tested with individual numbers.

 

 

val .r = reverse(.n)

if .n == .r: return false

}

 

if .israre(.i) {

_for ~= [.i]

}

}

 

# if you have the time...

 

 

 

=={{header|Phix}}==

===naive===

{{out}}

<pre>

{3,281089082,"1 minute and 29s"}

</pre>

===advanced===

{{trans|VB.NET}}

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]].

{{out}}

<pre>

15 10:42

</pre>

 

=={{header|REXX}}==

 

These improvements made this REXX version around &nbsp; '''25%''' &nbsp; faster than the previous version &nbsp; (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.*/

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

{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 8 </tt>}}

<pre>

7th rare number is: 872,546,974,178

8th rare number is: 872,568,754,178

</pre>

 

===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)

If System.Diagnostics.Debugger.IsAttached Then ReadKey()

End Sub

{{out}}

<pre style="height:64ex;overflow:scroll"> digs elapsed(ms) R/N Rare Numbers

 

Performance is better, only about 4% slower than '''C#'''.

Imports System.Console

Imports llst = System.Collections.Generic.List(Of Integer())

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

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

===Traditional===

About 9.5 minutes to find the first 25 rare numbers.

 

class Term {

Fmt.print(" $2d: $,21d", i+1, rare)

i = i + 1

 

{{out}}

===Turbo===

Ruffles the feathers a little with a time 5 times quicker than the 'traditional' version.

 

class Z2 {

Fmt.print(" $2d: $s $s", nd, fbTime, ftTime)

bStart = System.clock // restart block timing

 

{{out}}