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++}}==

===Calculate L and H independently===

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

// Nigel Galloway/Enter your username - January 4th., 2021 (see discussion page.

for (int nd{2}; nd <= max; ++nd) Rare(nd);

}

{{out}}

Processor Intel(R) Core(TM) i5-1035G1 CPU @ 1.00GHz

</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|FreeBASIC}}==

Made some changes and added a simple test to speed things up. Results in about 1 minute.

{{trans|Phix}}

Dim As ULongInt r

For i As UInteger = 1 To nd

Print

Print "Done"

{{out}}

<pre>1: 65

 

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

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.

 

np =: -.@:(-: |.) NB. Not palindromic

nbrPs =: > *. sdPs NB. n is Bigger than R and the perfect square constraint is satisfied

ps =: 0 = 1 | %: NB. Perfect square (integral sqrt)

rr =: 10&#.@:|. NB. Do note we do reverse the digits twice (once here, once in np)

 

{{out}}

R =: 65 621770 281089082 2022652202 2042832002 868591084757 872546974178 872568754178 6979302951885 20313693904202 20313839704202 20331657922202 20331875722202 20333875702202 40313893704200

rare"0 R

 

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

 

 

 

Module[{out = {0}, start = 0, stop = 0, rlist = {0}, r = 0,

sum = 0.0, diff = 0.0, imax = 8, step = 10},

]

];

{{out}}

<pre>{65, 621770, 281089082, 2022652202, 2042832002}</pre>

 

=={{header|Nim}}==

{{trans|Go}}

Translation of the second Go version, limited to 18 digits.

 

type Llst = seq[seq[int]]

nd1 = nd

inc nd

 

{{out}}

62 871975098681469178 1320582934 3303300

63 898907259301737498 1339270086 64576740 18: 00:05:45.616 00:09:04.383</pre>

 

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

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.

 

# rare.py

# find rare numbers

main()

 

 

 

=={{header|Quackery}}==

On the other hand; code development time, less than five minutes. :-)

 

[ 2dup > while

+ 1 >>

2drop ] is echorarenums ( n --> b )

 

{{Out}}

281089082</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>

 

=={{header|Ring}}==

load "stdlib.ring"

 

next

see "done..." + nl

{{out}}

<pre>

{{trans|Kotlin}}

Not sure where, but there seems to be a bug that introduces false rare numbers as output beyond what is shown

end

 

end

 

{{out}}

<pre> R/N 1: (65)

=={{header|Rust}}==

A naive and an advanced version based on Nigel Galloway

use itertools::Itertools;

use std::collections::HashMap;

let diffs1: Vec<i8> = vec![0, 1, 4, 5, 6];

 

let pairs = (0_i8..=9)

.cartesian_product(0_i8..=9)

.collect::<Vec<u64>>();

 

// for the first use the very short one, for all other the complete 19 element

let diff_list_iter = (0_u8..(d / 2))

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

false

}

}

 

{{out}}

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