Self numbers: Difference between revisions

=={{header|ALGOL 68}}==

{{Trans|Go}}

INT max number = 1 999 999 999 + 82; # maximum n plus g we will condifer #

# sieve the self numbers up to 1 999 999 999 #

FI

OD

{{out}}

<pre>

I couldn't follow the math in the Wikipedia entry, nor the discussion and code here so far. But an initial expedient of generating a list of all the integers from 1 to just over ten times the required number of results and then deleting those that ''could'' be derived by the described method revealed the sequencing pattern on which the code below is based. On the test machine, it completes all three of the tests at the bottom in a total of around a millisecond.

 

Base-10 self numbers by index (single or range).

Follows an observed sequence pattern whereby, after the initial single-digit odd numbers, self numbers are

-- 97,777,777,792nd:

selfNumbers(9.7777777792E+10)

 

=={{header|AWK}}==

# syntax: GAWK -f SELF_NUMBERS.AWK

# converted from Go (low memory example)

}

function max(x,y) { return((x > y) ? x : y) }

{{out}}

<pre>

{{trans|Go}}

About 25% faster than Go (using GCC 7.5.0 -O3) mainly due to being able to iterate through the sieve using a pointer.

#include <stdlib.h>

#include <time.h>

printf("Took %lf seconds.\n", (double)(clock() - begin) / CLOCKS_PER_SEC);

return 0;

 

{{out}}

===Extended===

{{trans|Pascal}}

#include <stdlib.h>

#include <time.h>

printf("\nOverall took %lf seconds.\n", (double)(clock() - begin) / CLOCKS_PER_SEC);

return 0;

 

{{out}}

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

{{trans|Java}}

#include <iomanip>

#include <iostream>

 

return 0;

{{out}}

<pre>The first 50 self numbers are:

=={{header|C#|CSharp}}==

{{trans|Pascal}}via{{trans|Go}}(third version) Stripped down, as C# limits the size of an array to Int32.MaxValue, so the sieve isn't large enough to hit the 1,000,000,000th value.

using static System.Console;

 

WriteLine("\nOverall took {0}s", (DateTime.Now - st). TotalSeconds);

}

{{out}}Timing from tio.run

<pre>Sieving took 3.4266187s

 

=={{header|Elixir}}==

defmodule SelfNums do

 

end

 

{{out}}

 

=={{header|F_Sharp|F#}}==

// Self numbers. Nigel Galloway: October 6th., 2020

let fN g=let rec fG n g=match n/10 with 0->n+g |i->fG i (g+(n%10)) in fG g g

Self |> Seq.take 50 |> Seq.iter(printf "%d "); printfn ""

printfn "\n%d" (Seq.item 99999999 Self)

{{out}}

<pre>

=={{header|FreeBASIC}}==

{{trans|Ring}}

Dim As Boolean flag

Dim As Ulong m, p, sum, number(), sum2

End If

Loop

 

 

===Low memory===

Simple-minded, uses very little memory (no sieve) but slow - over 2.5 minutes.

 

import (

fmt.Println("\nThe 100 millionth self number is", lastSelf)

fmt.Println("Took", time.Since(st))

 

{{out}}

 

Have also incorporated Enter your username's suggestion (see Talk page) of using partial sums for each loop which improves performance by about 25%.

 

import (

}

fmt.Println("Took", time.Since(st))

 

{{out}}

{{trans|Pascal}}

This uses horst.h's ideas (see Talk page) to find up to the 1 billionth self number in a reasonable time and using less memory than the simple 'sieve based' approach above would have needed.

 

import (

}

fmt.Println("\nOverall took", time.Since(st))

 

{{out}}

The solution is quite straightforward. The length of the foreseeing window in filtering procedure (81) is chosen empirically and doesn't have any theoretical background.

 

import Text.Printf

 

print $ take 50 selfs

forM_ [1..8] $ \i ->

 

<pre>$ ghc -O2 SelfNum.hs && time ./SelfNum

=={{header|Java}}==

{{trans|C#}}

private static final int MC = 103 * 1000 * 10000 + 11 * 9 + 1;

private static final boolean[] SV = new boolean[MC + 1];

}

}

{{out}}

<pre>The first 50 self numbers are:

'''Adapted from [[#Julia|Julia]]'''

{{works with|jq}}

def sumdigits: tostring | explode | map([.]|implode|tonumber) | add;

 

then "Yes, \(.) is the 100,000,000th self number."

else "No, \(.i) is actually the 100,000,000th self number."

{{out}}

<pre>

Note that 81 is the window size because the sum of digits of 999,999,999

(the largest digit sum of a counting number less than 1022727208) is 81.

isnonself(i) = any(x -> gsum(x) == i, i-1:-1:i-max(1, ndigits(i)*9))

const last81 = filter(isnonself, 1:5000)[1:81]

 

checkselfnumbers()

<pre>

1 3 5 7 9 20 31 42 53 64 75 86 97 108 110 121 132 143 154 165 176 187 198 209 211 222 233 244 255 266 277 288 299 310 312 323 334 345 356 367 378 389 400 411 413 424 435 446 457 468

{{trans|Pascal}}

Contains tweaks peculiar to the "10 to the nth" self number. Timings include compilation times.

 

function dosieve!(sieve, digitsum9999)

 

@time findselves()

<pre>

Sieve time:

=={{header|Kotlin}}==

{{trans|Java}}

private val SV = BooleanArray(MC + 1)

 

i++

}

{{out}}

<pre>The first 50 self numbers are:

10,000,000 102,272,662

100,000,000 1,022,727,208</pre>

 

=={{header|Nim}}==

 

Note that we used a sequence of ten nested loops as in the Go solution but we have not memorized the intermediate sums as the C compiler does a good job to detect the loop invariants (remember, Nim produces C code and this code has proved to be quite optimizable by the C compiler). The ten loops looks a lot better this way, too 🙂.

 

const MaxCount = 2 * 1_000_000_000 + 9 * 9

echo ($count).align(10), ($n).align(12)

limit *= 10

 

{{out}}

Of course, the program is slower but not in the same proportion that in the previous program: it is about twice slower than the Pascal version. Note that the execution time varies significantly according to the way statements are written. For instance, writing <code>if not sieve[n]: inc count</code> has proved to be more efficient than writing <code>inc count, ord(not sieve[n])</code> or <code>inc count, 1 - ord(sieve[n])</code> which is surprising as the latter forms avoid a jump. Maybe changing some other statements could give better results, but current time is already satisfying.

 

 

const MaxCount = 103 * 10_000 * 10_000 + 11 * 9 + 1

echo ($count).align(10), ($n).align(12)

limit *= 10

 

{{out}}

Just "sieving" with only one follower of every number {{trans|Go}}

Extended to 10.23e9

{$IFDEF FPC}

{$MODE Delphi}

end;

end;

{{out}}

<pre> time ./selfnumb

=={{header|Perl}}==

{{trans|Raku}}

use warnings;

use feature 'say';

use List::Util qw(max sum);

 

 

my $final = 50;

 

if ($isSelf) {

last if @selfs == $final;

}

 

$pow *= 10;

$offset = 9 * $digits++

}

 

{{out}}

<pre>The first 50 self numbers are:

Certainly puts my previous rubbish attempts ([[Self_numbers\Phix|archived here]]) to shame.<br>

The precise nature of the difference-pattern eludes me, I will admit.

<span style="color: #000080;font-style:italic;">--

-- Base-10 self numbers by index (single or range).

<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;">"completed in %s\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>

{{out}}

<pre>

=={{header|Python}}==

{{works with|Python|2.7}}

def __init__(self):

sumdigit = lambda n : sum( map( int,str( n )))

if i == p :

print '%7.1f sec %9dth = %d'%( time.time()-t,i,s )

{{out}}

<pre>1 3 5 7 9 20 31 42 53 64 75 86 97 108 110 121 132 143 154 165 176 187 198 209 211 222 233 244 255 266 277 288 299 310 312 323 334 345 356 367 378 389 400 411 413 424 435 446 457 468

Translated the low memory version of the Go entry but showed only the first 50 self numbers. The machine for running this task (a Xeon E3110+8GB memory) is showing its age as, 1) took over 6 minutes to complete the Go entry, 2) not even able to run the other two Go alternative entries and 3) needed over 47 minutes to reach 1e6 iterations here. Anyway I will try this on an i5 box later to see how it goes.

{{trans|Go}}

 

my ( $st, $count, $i, $pow, $digits, $offset, $lastSelf, $done, @selfs) =

 

# say "The 100 millionth self number is ", $lastSelf;

{{out}}

<pre>The first 50 self numbers are:

=={{header|REXX}}==

=== first 50 self numbers ===

parse arg n . /*obtain optional argument from the CL.*/

if n=='' | n=="," then n= 50 /*Not specified? Then use the default.*/

/*stick a fork in it, we're all done. */

say n " self numbers were found." /*display the title for the output list*/

{{out|output|text=&nbsp; when using the default input:}}

<pre>

=== ten millionth self number ===

{{trans|Go (low memory)}}

numeric digits 20 /*ensure enough decimal digits for #. */

parse arg high . /*obtain optional argument from the CL.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

commas: parse arg _; do c=length(_)-3 to 1 by -3; _=insert(',', _, c); end; return _

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

=={{header|Ring}}==

load "stdlib.ring"

 

 

see "done..." + nl

Output:

<pre>

done...

</pre>

 

=={{header|Sidef}}==

Algorithm by David A. Corneth (OEIS: A003052).

 

if (n < 30) {

}

 

{{out}}

<pre>

Simpler algorithm (by M. F. Hasler):

 

1..min(n>>1, 9*n.len) -> none {|i| sumdigits(n-i) == i } && (n > 0)

 

=={{header|Standard ML}}==

open List;

 

app ((fn s => print (s ^ " ")) o Int.toString o selfNumberNr) (tabulate (50,fn i=>i+1)) ;

selfNumberNr 100000000 ;

output

<pre>

 

Unsurprisingly, very slow compared to the Go version as Wren is interpreted and uses floating point arithmetic for all numerical work.

var sv = List.filled(2*1e9+9*9+1, false)

var n = 0

}

}

 

{{out}}

The 100 millionth self number is 1022727208

Took 222.789713 seconds.

</pre>