Rosetta Code

Self numbers: Difference between revisions

Page Discussion

Self numbers (view source)

Revision as of 10:55, 4 February 2024

49,413 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
m (→‎{{header|AppleScript}}: Fixed test code change left over from testing the fix.)
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(42 intermediate revisions by 21 users not shown)
Line 12:
;*[[oeis:A003052|OEIS: A003052 - Self numbers or Colombian numbers]]
;*[[wp:Self_number|Wikipedia: Self numbers]]
 
=={{header|ALGOL 68}}==
{{Trans|Go}}
<syntaxhighlight lang="algol68">BEGIN # find some self numbers numbers n such that there is no g such that g + sum of g's digits = n #
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 #
[ 0 : max number ]BOOL self; FOR i TO UPB self DO self[ i ] := TRUE OD;
INT n := 0;
FOR s0 FROM 0 TO 1 DO
FOR d1 FROM 0 TO 9 DO
INT s1 = s0 + d1;
FOR d2 FROM 0 TO 9 DO
INT s2 = s1 + d2;
FOR d3 FROM 0 TO 9 DO
INT s3 = s2 + d3;
FOR d4 FROM 0 TO 9 DO
INT s4 = s3 + d4;
FOR d5 FROM 0 TO 9 DO
INT s5 = s4 + d5;
FOR d6 FROM 0 TO 9 DO
INT s6 = s5 + d6;
FOR d7 FROM 0 TO 9 DO
INT s7 = s6 + d7;
FOR d8 FROM 0 TO 9 DO
INT s8 = s7 + d8;
FOR d9 FROM 0 TO 9 DO
INT s9 = s8 + d9;
self[ s9 + n ] := FALSE;
n +:= 1
OD
OD
OD
OD
OD
OD
OD
OD
OD
OD;
# show the first 50 self numbers #
INT s count := 0;
FOR i TO UPB self WHILE s count < 50 DO
IF self[ i ] THEN
print( ( " ", whole( i, -3 ) ) );
IF ( s count +:= 1 ) MOD 18 = 0 THEN print( ( newline ) ) FI
FI
OD;
print( ( newline ) );
# show the self numbers with power-of-10 indxes #
INT s show := 1;
s count := 0;
print( ( " nth self", newline ) );
print( ( " n number", newline ) );
FOR i TO UPB self DO
IF self[ i ] THEN
s count +:= 1;
IF s count = s show THEN
print( ( whole( s show, -9 ), " ", whole( i, -11 ), newline ) );
s show *:= 10
FI
FI
OD
END</syntaxhighlight>
{{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
nth self
n number
1 1
10 64
100 973
1000 10188
10000 102225
100000 1022675
1000000 10227221
10000000 102272662
100000000 1022727208
</pre>
 
=={{header|AppleScript}}==
 
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 usingby 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.
 
<langsyntaxhighlight lang="applescript">(*
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
Line 25 ⟶ 105:
This connection with significant digit change means every ten blocks form a higher-order block, every ten
of these a higher-order-still block, and so on.
The code below appears to be good up to the last self number before 10^12 — ie. 999,999,999,997, which is
returned as the 97,777,777,792nd such number. After this, instead of zero-length shorter runs, the actual
pattern apparently starts again with a single run of 10, like the one at the beginning.
*)
on selfNumbers(indexRange)
Line 48 ⟶ 132:
on fastForward()
if (counter ≥ startIndex) then return
-- The highest-order blocks whose ends this script is thought to handlehandles correctly contain 9,777,777,778 self numbers.
-- The difference between equivalently positioned numbers in these blocks is 100,000,000,001.
-- The figures for successively lower-order blocks are obtained byhave successively removingfewer 7s and 0s!
set indexDiff to 9.777777778E+9
set numericDiff to 1.00000000001E+11
Line 59 ⟶ 143:
set currentSelf to (currentSelf + numericDiff)
else
set indexDiff to (indexDiff div+ 102) +div 110
set numericDiff to numericDiff div 10 + 1
end if
Line 114 ⟶ 198:
-- One hundred millionth:
selfNumbers(100000000)
--> {1.022727208E+9}</lang>
 
-- 97,777,777,792nd:
selfNumbers(9.7777777792E+10)
--> {9.99999999997E+11}</syntaxhighlight>
 
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f SELF_NUMBERS.AWK
# converted from Go (low memory example)
BEGIN {
print("HH:MM:SS INDEX SELF")
print("-------- ---------- ----------")
count = 0
digits = 1
i = 1
last_self = 0
offset = 9
pow = 10
while (count < 1E8) {
is_self = 1
start = max(i-offset,0)
sum = sum_digits(start)
for (j=start; j<i; j++) {
if (j + sum == i) {
is_self = 0
break
}
sum = ((j+1) % 10 != 0) ? ++sum : sum_digits(j+1)
}
if (is_self) {
last_self = i
if (++count <= 50) {
selfs = selfs i " "
}
}
if (++i % pow == 0) {
pow *= 10
digits++
offset = digits * 9
}
if (count ~ /^10*$/ && arr[count]++ == 0) {
printf("%8s %10s %10s\n",strftime("%H:%M:%S"),count,last_self)
}
}
printf("\nfirst 50 self numbers:\n%s\n",selfs)
exit(0)
}
function sum_digits(x, sum,y) {
while (x) {
y = x % 10
sum += y
x = int(x/10)
}
return(sum)
}
function max(x,y) { return((x > y) ? x : y) }
</syntaxhighlight>
{{out}}
<pre>
HH:MM:SS INDEX SELF
-------- ---------- ----------
00:36:35 1 1
00:36:35 10 64
00:36:35 100 973
00:36:35 1000 10188
00:36:36 10000 102225
00:36:46 100000 1022675
00:38:49 1000000 10227221
01:03:01 10000000 102272662
05:27:35 100000000 1022727208
 
first 50 self numbers:
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
</pre>
 
=={{header|C}}==
Line 120 ⟶ 278:
{{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.
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <time.h>
Line 183 ⟶ 341:
printf("Took %lf seconds.\n", (double)(clock() - begin) / CLOCKS_PER_SEC);
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 196 ⟶ 354:
===Extended===
{{trans|Pascal}}
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <time.h>
Line 272 ⟶ 430:
printf("\nOverall took %lf seconds.\n", (double)(clock() - begin) / CLOCKS_PER_SEC);
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 295 ⟶ 453:
Overall took 11.574158 seconds.
</pre>
 
=={{header|C++}}==
{{trans|Java}}
<syntaxhighlight lang="cpp">#include <array>
#include <iomanip>
#include <iostream>
 
const int MC = 103 * 1000 * 10000 + 11 * 9 + 1;
std::array<bool, MC + 1> SV;
 
void sieve() {
std::array<int, 10000> dS;
for (int a = 9, i = 9999; a >= 0; a--) {
for (int b = 9; b >= 0; b--) {
for (int c = 9, s = a + b; c >= 0; c--) {
for (int d = 9, t = s + c; d >= 0; d--) {
dS[i--] = t + d;
}
}
}
}
for (int a = 0, n = 0; a < 103; a++) {
for (int b = 0, d = dS[a]; b < 1000; b++, n += 10000) {
for (int c = 0, s = d + dS[b] + n; c < 10000; c++) {
SV[dS[c] + s++] = true;
}
}
}
}
 
int main() {
sieve();
 
std::cout << "The first 50 self numbers are:\n";
for (int i = 0, count = 0; count <= 50; i++) {
if (!SV[i]) {
count++;
if (count <= 50) {
std::cout << i << ' ';
} else {
std::cout << "\n\n Index Self number\n";
}
}
}
for (int i = 0, limit = 1, count = 0; i < MC; i++) {
if (!SV[i]) {
if (++count == limit) {
//System.out.printf("%,12d %,13d%n", count, i);
std::cout << std::setw(12) << count << " " << std::setw(13) << i << '\n';
limit *= 10;
}
}
}
 
return 0;
}</syntaxhighlight>
{{out}}
<pre>The first 50 self numbers are:
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
 
Index Self number
1 1
10 64
100 973
1000 10188
10000 102225
100000 1022675
1000000 10227221
10000000 102272662
100000000 1022727208</pre>
 
=={{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.
<langsyntaxhighlight lang="csharp">using System;
using static System.Console;
 
Line 330 ⟶ 558:
WriteLine("\nOverall took {0}s", (DateTime.Now - st). TotalSeconds);
}
}</langsyntaxhighlight>
{{out}}Timing from tio.run
<pre>Sieving took 3.4266187s
Line 351 ⟶ 579:
 
=={{header|Elixir}}==
<langsyntaxhighlight lang="elixir">
defmodule SelfNums do
 
Line 370 ⟶ 598:
 
import SelfNums
stop = 1000
 
stop = 468
 
Enum.to_list 1..stop |>
Enum.map(&digAndSum/1) |>
SelfNums.selfFilter(stop) |>
Enum.take(50) |>
IO.inspect
end
</syntaxhighlight>
</lang>
 
{{out}}
Line 387 ⟶ 614:
323, 334, 345, 356, 367, 378, 389, 400, 411, 413, 424, 435, 446, 457, 468]
</pre>
 
=={{header|F_Sharp|F#}}==
<langsyntaxhighlight lang="fsharp">
// 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
Line 395 ⟶ 623:
Self |> Seq.take 50 |> Seq.iter(printf "%d "); printfn ""
printfn "\n%d" (Seq.item 99999999 Self)
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 402 ⟶ 630:
1022727208
</pre>
 
 
=={{header|FreeBASIC}}==
{{trans|Ring}}
<syntaxhighlight lang="freebasic">Print "The first 50 self numbers are:"
Dim As Boolean flag
Dim As Ulong m, p, sum, number(), sum2
Dim As Ulong n = 0
Dim As Ulong num = 0
Dim As Ulong limit = 51
Dim As Ulong limit2 = 100000000
Dim As String strnum
 
Do
n += 1
For m = 1 To n
flag = True
sum = 0
strnum = Str(m)
For p = 1 To Len(strnum)
sum += Val(Mid(strnum,p,1))
Next p
sum2 = m + sum
If sum2 = n Then
flag = False
Exit For
Else
flag = True
End If
Next m
If flag = True Then
num += 1
If num < limit Then Print ""; num; ". "; n
If num >= limit2 Then
Print "The "; limit2; "th self number is: "; n
Exit Do
End If
End If
Loop
Sleep</syntaxhighlight>
 
 
=={{header|Go}}==
===Low memory===
Simple-minded, uses very little memory (no sieve) but slow - over 2.5 minutes.
<langsyntaxhighlight lang="go">package main
 
import (
Line 473 ⟶ 742:
fmt.Println("\nThe 100 millionth self number is", lastSelf)
fmt.Println("Took", time.Since(st))
}</langsyntaxhighlight>
 
{{out}}
Line 490 ⟶ 759:
 
Have also incorporated Enter your username's suggestion (see Talk page) of using partial sums for each loop which improves performance by about 25%.
<langsyntaxhighlight lang="go">package main
 
import (
Line 552 ⟶ 821:
}
fmt.Println("Took", time.Since(st))
}</langsyntaxhighlight>
 
{{out}}
Line 566 ⟶ 835:
{{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.
<langsyntaxhighlight lang="go">package main
 
import (
Line 641 ⟶ 910:
}
fmt.Println("\nOverall took", time.Since(st))
}</langsyntaxhighlight>
 
{{out}}
Line 664 ⟶ 933:
Overall took 14.647314803s
</pre>
 
=={{header|Haskell}}==
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.
 
<syntaxhighlight lang="haskell">import Control.Monad (forM_)
import Text.Printf
 
selfs :: [Integer]
selfs = sieve (sumFs [0..]) [0..]
where
sumFs = zipWith (+) [ a+b+c+d+e+f+g+h+i+j
| a <- [0..9] , b <- [0..9]
, c <- [0..9] , d <- [0..9]
, e <- [0..9] , f <- [0..9]
, g <- [0..9] , h <- [0..9]
, i <- [0..9] , j <- [0..9] ]
 
-- More idiomatic list generator is about three times slower
-- sumFs = zipWith (+) $ sum <$> replicateM 10 [0..9]
 
sieve (f:fs) (n:ns)
| n > f = sieve fs (n:ns)
| n `notElem` take 81 (f:fs) = n : sieve (f:fs) ns
| otherwise = sieve (f:fs) ns
 
main = do
print $ take 50 selfs
forM_ [1..8] $ \i ->
printf "1e%v\t%v\n" (i :: Int) (selfs !! (10^i-1))</syntaxhighlight>
 
<pre>$ ghc -O2 SelfNum.hs && time ./SelfNum
[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]
1e1 64
1e2 973
1e3 10188
1e4 102225
1e5 1022675
1e6 10227221
1e7 102272662
1e8 1022727208
275.98 user 3.11 system 4:41.02 elapsed</pre>
 
=={{header|Java}}==
{{trans|C#}}
<syntaxhighlight lang="java">public class SelfNumbers {
private static final int MC = 103 * 1000 * 10000 + 11 * 9 + 1;
private static final boolean[] SV = new boolean[MC + 1];
 
private static void sieve() {
int[] dS = new int[10_000];
for (int a = 9, i = 9999; a >= 0; a--) {
for (int b = 9; b >= 0; b--) {
for (int c = 9, s = a + b; c >= 0; c--) {
for (int d = 9, t = s + c; d >= 0; d--) {
dS[i--] = t + d;
}
}
}
}
for (int a = 0, n = 0; a < 103; a++) {
for (int b = 0, d = dS[a]; b < 1000; b++, n += 10000) {
for (int c = 0, s = d + dS[b] + n; c < 10000; c++) {
SV[dS[c] + s++] = true;
}
}
}
}
 
public static void main(String[] args) {
sieve();
System.out.println("The first 50 self numbers are:");
for (int i = 0, count = 0; count <= 50; i++) {
if (!SV[i]) {
count++;
if (count <= 50) {
System.out.printf("%d ", i);
} else {
System.out.printf("%n%n Index Self number%n");
}
}
}
for (int i = 0, limit = 1, count = 0; i < MC; i++) {
if (!SV[i]) {
if (++count == limit) {
System.out.printf("%,12d %,13d%n", count, i);
limit *= 10;
}
}
}
}
}</syntaxhighlight>
{{out}}
<pre>The first 50 self numbers are:
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
 
Index Self number
1 1
10 64
100 973
1,000 10,188
10,000 102,225
100,000 1,022,675
1,000,000 10,227,221
10,000,000 102,272,662
100,000,000 1,022,727,208</pre>
 
=={{header|jq}}==
'''Adapted from [[#Julia|Julia]]'''
{{works with|jq}}
<syntaxhighlight lang="jq">
def sumdigits: tostring | explode | map([.]|implode|tonumber) | add;
 
def gsum: . + sumdigits;
 
def isnonself:
def ndigits: tostring|length;
. as $i
| ($i - ($i|ndigits)*9) as $n
| any( range($i-1; [0,$n]|max; -1);
gsum == $i);
 
# an array
def last81:
[limit(81; range(1; infinite) | select(isnonself))];
 
# output an unbounded stream
def selfnumbers:
foreach range(1; infinite) as $i ( [0, last81];
.[0] = false
| .[1] as $last81
| if $last81 | bsearch($i) < 0
then .[0] = $i
| if $i > $last81[-1] then .[1] = $last81[1:] + [$i | gsum ] else . end
else .
end;
.[0] | select(.) );
 
 
"The first 50 self numbers are:", last81[:50],
"",
(nth(100000000 - 1; selfnumbers)
| if . == 1022727208
then "Yes, \(.) is the 100,000,000th self number."
else "No, \(.i) is actually the 100,000,000th self number."
end)</syntaxhighlight>
{{out}}
<pre>
The first 50 self numbers are:
[2,4,6,8,10,11,12,13,14,15,16,17,18,19,21,22,23,24,25,26,27,28,29,30,32,33,34,35,36,37,38,39,40,41,43,44,45,46,47,48,49,50,51,52,54,55,56,57,58,59]
 
Yes, 1022727208 is the 100,000,000th self number.
 
</pre>
 
 
 
=={{header|Julia}}==
Line 669 ⟶ 1,093:
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.
<langsyntaxhighlight lang="julia">gsum(i) = sum(digits(i)) + i
isnonself(i) = any(x -> gsum(x) == i, i-1:-1:i-max(1, ndigits(i)*9))
const last81 = filter(isnonself, 1:5000)[1:81]
Line 695 ⟶ 1,119:
 
checkselfnumbers()
</langsyntaxhighlight>{{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
Line 704 ⟶ 1,128:
{{trans|Pascal}}
Contains tweaks peculiar to the "10 to the nth" self number. Timings include compilation times.
<langsyntaxhighlight lang="julia">const MAXCOUNT = 103 * 10000 * 10000 + 11 * 9 + 1
 
function dosieve!(sieve, digitsum9999)
Line 747 ⟶ 1,171:
 
@time findselves()
</langsyntaxhighlight>{{out}}
<pre>
Sieve time:
Line 764 ⟶ 1,188:
16.999383 seconds (42.92 k allocations: 9.595 GiB, 0.01% gc time)
</pre>
 
=={{header|Kotlin}}==
{{trans|Java}}
<syntaxhighlight lang="scala">private const val MC = 103 * 1000 * 10000 + 11 * 9 + 1
private val SV = BooleanArray(MC + 1)
 
private fun sieve() {
val dS = IntArray(10000)
run {
var a = 9
var i = 9999
while (a >= 0) {
for (b in 9 downTo 0) {
var c = 9
val s = a + b
while (c >= 0) {
var d = 9
val t = s + c
while (d >= 0) {
dS[i--] = t + d
d--
}
c--
}
}
a--
}
}
var a = 0
var n = 0
while (a < 103) {
var b = 0
val d = dS[a]
while (b < 1000) {
var c = 0
var s = d + dS[b] + n
while (c < 10000) {
SV[dS[c] + s++] = true
c++
}
b++
n += 10000
}
a++
}
}
 
fun main() {
sieve()
println("The first 50 self numbers are:")
run {
var i = 0
var count = 0
while (count <= 50) {
if (!SV[i]) {
count++
if (count <= 50) {
print("$i ")
} else {
println()
println()
println(" Index Self number")
}
}
i++
}
}
var i = 0
var limit = 1
var count = 0
while (i < MC) {
if (!SV[i]) {
if (++count == limit) {
println("%,12d %,13d".format(count, i))
limit *= 10
}
}
i++
}
}</syntaxhighlight>
{{out}}
<pre>The first 50 self numbers are:
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
 
Index Self number
1 1
10 64
100 973
1,000 10,188
10,000 102,225
100,000 1,022,675
1,000,000 10,227,221
10,000,000 102,272,662
100,000,000 1,022,727,208</pre>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">
sum[g_] := g + Total@IntegerDigits@g
 
ming[n_] := n - IntegerLength[n]*9
 
self[n_] := NoneTrue [Range[ming[n], n - 1], sum[#] == n &]
 
Module[{t = 1, x = 1},
Reap[
While[t <= 50,
If[self[x], Sow[x]; t++]; x++]
][[2, 1]]]
</syntaxhighlight>
 
{{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}</pre>
 
=={{header|Nim}}==
In order to use less memory, we have chosen to use indexing at bit level. So, our sieve is a custom object defined by its length in bits and its value which is a sequence of bytes. With bit indexing, the sieve uses eight times less memory than with byte indexing.
 
Of course, there is a trade off to this strategy: reading values from and writing values to the sieve are significantly slower.
 
===Simple sieve===
{{trans|Go}}
We use the Go algorithm with bit indexing. As a consequence the sieve uses about 250MB instead of 1 GB. And the program is about five times slower.
 
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 🙂.
<syntaxhighlight lang="nim">import bitops, strutils, std/monotimes, times
 
const MaxCount = 2 * 1_000_000_000 + 9 * 9
 
# Bit string used to represent an array of booleans.
type BitString = object
len: Natural # length in bits.
values: seq[byte] # Sequence containing the bits.
 
 
proc newBitString(n: Natural): BitString =
## Return a new bit string of length "n" bits.
result.len = n
result.values.setLen((n + 7) shr 3)
 
 
template checkIndex(i, length: Natural) {.used.} =
## Check if index "i" is less than the array length.
if i >= length:
raise newException(IndexDefect, "index $1 not in 0 .. $2".format(i, length))
 
 
proc `[]`(bs: BitString; i: Natural): bool =
## Return the value of bit at index "i" as a boolean.
when compileOption("boundchecks"):
checkIndex(i, bs.len)
result = bs.values[i shr 3].testbit(i and 0x07)
 
 
proc `[]=`(bs: var BitString; i: Natural; value: bool) =
## Set the bit at index "i" to the given value.
when compileOption("boundchecks"):
checkIndex(i, bs.len)
if value: bs.values[i shr 3].setBit(i and 0x07)
else: bs.values[i shr 3].clearBit(i and 0x07)
 
 
proc fill(sieve: var BitString) =
## Fill a sieve.
var n = 0
for a in 0..1:
for b in 0..9:
for c in 0..9:
for d in 0..9:
for e in 0..9:
for f in 0..9:
for g in 0..9:
for h in 0..9:
for i in 0..9:
for j in 0..9:
sieve[a + b + c + d + e + f + g + h + i + j + n] = true
inc n
 
 
let t0 = getMonoTime()
 
var sieve = newBitString(MaxCount + 1)
sieve.fill()
echo "Sieve time: ", getMonoTime() - t0
 
# Find first 50.
echo "\nFirst 50 self numbers:"
var count = 0
var line = ""
for n in 0..MaxCount:
if not sieve[n]:
inc count
line.addSep(" ")
line.add $n
if count == 50: break
echo line
 
# Find 1st, 10th, 100th, ..., 100_000_000th.
echo "\n Rank Value"
var limit = 1
count = 0
for n in 0..MaxCount:
if not sieve[n]: inc count
if count == limit:
echo ($count).align(10), ($n).align(12)
limit *= 10
echo "Total time: ", getMonoTime() - t0</syntaxhighlight>
 
{{out}}
<pre>Sieve time: 2 seconds, 59 milliseconds, 67 microseconds, and 152 nanoseconds
 
First 50 self numbers:
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
 
Rank Value
1 1
10 64
100 973
1000 10188
10000 102225
100000 1022675
1000000 10227221
10000000 102272662
100000000 1022727208
 
Total time: 7 seconds, 903 milliseconds, 752 microseconds, and 944 nanoseconds</pre>
 
===Improved sieve===
{{trans|Pascal}}
Using bit indexing is very useful here as with byte indexing, the sieve needs 10GB. On a computer with only 8 GB , as this is the case of the laptop I use to run these programs, it fails to execute (I have a very small swap and don’t want to use the swap anyway). With bit indexing, the sieve needs only 1,25GB which is more reasonable.
 
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.
 
<syntaxhighlight lang="nim">import bitops, strutils, std/monotimes, times
 
const MaxCount = 103 * 10_000 * 10_000 + 11 * 9 + 1
 
# Bit string used to represent an array of booleans.
type BitString = object
len: Natural
values: seq[byte]
 
 
proc newBitString(n: Natural): BitString =
## Return a new bit string of length "n" bits.
result.len = n
result.values.setLen((n + 7) shr 3)
 
 
template checkIndex(i, length: Natural) {.used.} =
## Check if index "i" is less than the array length.
if i >= length:
raise newException(IndexDefect, "index $1 not in 0 .. $2".format(i, length))
 
 
proc `[]`(bs: BitString; i: Natural): bool =
## Return the value of bit at index "i" as a boolean.
when compileOption("boundchecks"):
checkIndex(i, bs.len)
result = bs.values[i shr 3].testbit(i and 0x07)
 
 
proc `[]=`(bs: var BitString; i: Natural; value: bool) =
## Set the bit at index "i" to the given value.
when compileOption("boundchecks"):
checkIndex(i, bs.len)
if value: bs.values[i shr 3].setBit(i and 0x07)
else: bs.values[i shr 3].clearBit(i and 0x07)
 
 
proc initDigitSum9999(): array[10000, byte] {.compileTime.} =
## Return the array of the digit sums for numbers 0 to 9999.
var i = 0
for a in 0..9:
for b in 0..9:
for c in 0..9:
for d in 0..9:
result[i] = byte(a + b + c + d)
inc i
 
const DigitSum9999 = initDigitSum9999()
 
 
proc fill(sieve: var BitString) =
## Fill a sieve.
var n = 0
for a in 0..102:
for b in 0..9999:
var s = DigitSum9999[a].int + DigitSum9999[b].int + n
for c in 0..9999:
sieve[DigitSum9999[c].int + s] = true
inc s
inc n, 10_000
 
 
let t0 = getMonoTime()
 
var sieve = newBitString(MaxCount + 1)
sieve.fill()
echo "Sieve time: ", getMonoTime() - t0
 
# Find first 50.
echo "\nFirst 50 self numbers:"
var count = 0
var line = ""
for n in 0..MaxCount:
if not sieve[n]:
inc count
line.addSep(" ")
line.add $n
if count == 50: break
echo line
 
# Find 1st, 10th, 100th, ..., 1_000_000_000th.
echo "\n Rank Value"
var limit = 1
count = 0
for n in 0..MaxCount:
if not sieve[n]: inc count
if count == limit:
echo ($count).align(10), ($n).align(12)
limit *= 10
echo "Total time: ", getMonoTime() - t0</syntaxhighlight>
 
{{out}}
<pre>Sieve time: 13 seconds, 340 milliseconds, 45 microseconds, and 528 nanoseconds
 
First 50 self numbers:
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
 
Rank Value
1 1
10 64
100 973
1000 10188
10000 102225
100000 1022675
1000000 10227221
10000000 102272662
100000000 1022727208
1000000000 10227272649
Total time: 28 seconds, 135 milliseconds, 481 microseconds, and 697 nanoseconds</pre>
 
=={{header|Pascal}}==
Line 769 ⟶ 1,533:
Just "sieving" with only one follower of every number {{trans|Go}}
Extended to 10.23e9
<langsyntaxhighlight lang="pascal">program selfnumb;
{$IFDEF FPC}
{$MODE Delphi}
Line 865 ⟶ 1,629:
end;
end;
END.</langsyntaxhighlight>
{{out}}
<pre> time ./selfnumb
Line 882 ⟶ 1,646:
 
real 0m13,252s</pre>
 
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
use List::Util qw(max sum);
 
my ($i, $pow, $digits, $offset, $lastSelf, @selfs)
= ( 1, 10, 1, 9, 0, );
 
my $final = 50;
 
while () {
my $isSelf = 1;
my $sum = my $start = sum split //, max(($i-$offset), 0);
for ( my $j = $start; $j < $i; $j++ ) {
if ($j+$sum == $i) { $isSelf = 0 ; last }
($j+1)%10 != 0 ? $sum++ : ( $sum = sum split '', ($j+1) );
}
 
if ($isSelf) {
push @selfs, $lastSelf = $i;
last if @selfs == $final;
}
 
next unless ++$i % $pow == 0;
$pow *= 10;
$offset = 9 * $digits++
}
 
say "The first 50 self numbers are:\n" . join ' ', @selfs;</syntaxhighlight>
{{out}}
<pre>The first 50 self numbers are:
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</pre>
 
=={{header|Phix}}==
Line 887 ⟶ 1,686:
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.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<lang Phix>--
<span style="color: #000080;font-style:italic;">--
-- Base-10 self numbers by index (single or range).
-- 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
-- Follows an observed sequence pattern whereby, after the initial single-digit odd numbers, self numbers are
-- grouped in runs whose members occur at numeric intervals of 11. Runs after the first one come in blocks of
-- grouped in runs whose members occur at numeric intervals of 11. Runs after the first one come in blocks of
-- ten: eight runs of ten numbers followed by two shorter runs. The numeric interval between runs is usually 2,
-- ten: eight runs of ten numbers followed by two shorter runs. The numeric interval between runs is usually 2,
-- but that between shorter runs, and their length, depend on the highest-order digit change occurring in them.
-- but that between shorter runs, and their length, depend on the highest-order digit change occurring in them.
-- This connection with significant digit change means every ten blocks form a higher-order block, every ten
-- ofThis theseconnection with significant digit change means every ten blocks form a higher-order-still block, and soevery on.ten
-- of these a higher-order-still block, and so on.
--
--
integer startIndex, endIndex, counter
-- The code below appears to be good up to the last self number before 10^12 — ie. 999,999,999,997, which is
atom currentSelf
-- returned as the 97,777,777,792nd such number. After this, instead of zero-length shorter runs, the actual
sequence output
-- pattern apparently starts again with a single run of 10, like the one at the beginning.
 
--</span>
function doneAfterAdding(integer interval, n)
<span style="color: #004080;">integer</span> <span style="color: #000000;">startIndex</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">endIndex</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">counter</span>
-- Advance to the next self number in the sequence, append it to the output if required, indicate if finished.
<span style="color: #004080;">atom</span> <span style="color: #000000;">currentSelf</span>
for i=1 to n do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">output</span>
currentSelf += interval
counter += 1
<span style="color: #008080;">function</span> <span style="color: #000000;">doneAfterAdding</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">interval</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
if counter >= startIndex then
<span style="color: #000080;font-style:italic;">-- Advance to the next self number in the sequence, append it to the output if required, indicate if finished.</span>
output &= currentSelf
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
end if
<span style="color: #000000;">currentSelf</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">interval</span>
if counter = endIndex then return true end if
<span style="color: #000000;">counter</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
end for
<span style="color: #008080;">if</span> <span style="color: #000000;">counter</span> <span style="color: #0000FF;">>=</span> <span style="color: #000000;">startIndex</span> <span style="color: #008080;">then</span>
return false
<span style="color: #000000;">output</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">currentSelf</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">counter</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">endIndex</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
function selfNumbers(sequence indexRange)
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
startIndex = indexRange[1]
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
endIndex = indexRange[$]
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
counter = 0
currentSelf = -1
<span style="color: #008080;">function</span> <span style="color: #000000;">selfNumbers</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">indexRange</span><span style="color: #0000FF;">)</span>
output = {}
<span style="color: #000000;">startIndex</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">indexRange</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">endIndex</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">indexRange</span><span style="color: #0000FF;">[$]</span>
-- Main process. Start with the single-digit odd numbers and first run.
<span style="color: #000000;">counter</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
if doneAfterAdding(2,5) then return output end if
<span style="color: #000000;">currentSelf</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
if doneAfterAdding(11,9) then return output end if
<span style="color: #000000;">output</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
-- If necessary, fast forward to last self number before the lowest-order block containing the first number required.
<span style="color: #000080;font-style:italic;">-- Main process. Start with the single-digit odd numbers and first run.</span>
if counter!=startIndex then
<span style="color: #008080;">if</span> <span style="color: #000000;">doneAfterAdding</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">output</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-- The highest-order blocks whose ends this is thought to handle correctly contain 97,777,777,778 self numbers.
<span style="color: #008080;">if</span> <span style="color: #000000;">doneAfterAdding</span><span style="color: #0000FF;">(</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">output</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-- The difference between equivalently positioned numbers in these blocks is 1,000,000,000,001.
-- The figures for successively lower-order blocks are obtained by successively removing 7s and 0s!
<span style="color: #000080;font-style:italic;">-- If necessary, fast forward to last self number before the lowest-order block containing first number rqd.</span>
atom indexDiff = 97777777778,
<span style="color: #008080;">if</span> <span style="color: #000000;">counter</span><span style="color: #0000FF;"><</span><span style="color: #000000;">startIndex</span> <span style="color: #008080;">then</span>
numericDiff = 1000000000001
<span style="color: #000080;font-style:italic;">-- The highest-order blocks whose ends this handles correctly contain 9,777,777,778 self numbers.
while indexDiff>=98 and counter!=startIndex do
-- The difference between equivalently positioned numbers in these blocks is 100,000,000,001.
if counter+indexDiff > startIndex then
-- The figures for successively lower-order blocks have successively fewer 7s and 0s!</span>
indexDiff = floor(indexDiff/10) + 1
<span style="color: #004080;">atom</span> <span style="color: #000000;">indexDiff</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">9777777778</span><span style="color: #0000FF;">,</span>
numericDiff = floor(numericDiff/10) + 1
<span style="color: #000000;">numericDiff</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">100000000001</span>
else
<span style="color: #008080;">while</span> <span style="color: #000000;">indexDiff</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">98</span> <span style="color: #008080;">and</span> <span style="color: #000000;">counter</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">startIndex</span> <span style="color: #008080;">do</span>
counter += indexDiff
<span style="color: #008080;">if</span> <span style="color: #000000;">counter</span><span style="color: #0000FF;">+</span><span style="color: #000000;">indexDiff</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">startIndex</span> <span style="color: #008080;">then</span>
currentSelf += numericDiff
<span style="color: #000000;">counter</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">indexDiff</span>
end if
<span style="color: #000000;">currentSelf</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">numericDiff</span>
end while
<span style="color: #008080;">else</span>
end if
<span style="color: #000000;">indexDiff</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">indexDiff</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">10</span> <span style="color: #000080;font-style:italic;">-- (..78-&gt;80-&gt;8)</span>
 
<span style="color: #000000;">numericDiff</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">numericDiff</span><span style="color: #0000FF;">+</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">10</span> <span style="color: #000080;font-style:italic;">-- (..01-&gt;10-&gt;1)</span>
-- Sequencing loop, per lowest-order block.
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
while true do
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
-- Eight ten-number runs, each at a numeric interval of 2 from the end of the previous one.
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
for i=1 to 8 do
if doneAfterAdding(2,1) then return output end if
<span style="color: #000080;font-style:italic;">-- Sequencing loop, per lowest-order block.</span>
if doneAfterAdding(11,9) then return output end if
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
end for
<span style="color: #000080;font-style:italic;">-- TwoEight shorterten-number runs, the secondeach at ana numeric interval inverselyof related2 tofrom the end of the theirprevious lengthone.</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span>
integer shorterRunLength = 8,
<span style="color: #008080;">if</span> <span style="color: #000000;">doneAfterAdding</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">output</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
temp = floor(currentSelf/1000)
<span style="color: #008080;">if</span> <span style="color: #000000;">doneAfterAdding</span><span style="color: #0000FF;">(</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">output</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-- Work out a shorter run length based on the most significant digit change about to happen.
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
while remainder(temp,10)=9 do
<span style="color: #000080;font-style:italic;">-- Two shorter runs, the second at an interval inversely related to their length.</span>
shorterRunLength -= 1
<span style="color: #004080;">integer</span> <span style="color: #000000;">shorterRunLength</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span>
temp = floor(temp/10)
<span style="color: #000000;">temp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">currentSelf</span><span style="color: #0000FF;">/</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">)</span>
end while
<span style="color: #000080;font-style:italic;">-- Work out a shorter run length based on the most significant digit change about to happen.</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">temp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
integer interval = 2
<span style="color: #000000;">shorterRunLength</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
for i=1 to 2 do
<span style="color: #000000;">temp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">temp</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
if doneAfterAdding(interval,1) then return output end if
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
if doneAfterAdding(11,shorterRunLength) then return output end if
interval += (9-shorterRunLength)*13
<span style="color: #004080;">integer</span> <span style="color: #000000;">interval</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
end for
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
end while
<span style="color: #008080;">if</span> <span style="color: #000000;">doneAfterAdding</span><span style="color: #0000FF;">(</span><span style="color: #000000;">interval</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">output</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end function
<span style="color: #008080;">if</span> <span style="color: #000000;">doneAfterAdding</span><span style="color: #0000FF;">(</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">shorterRunLength</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">output</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">interval</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">9</span><span style="color: #0000FF;">-</span><span style="color: #000000;">shorterRunLength</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">13</span>
atom t0 = time()
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
printf(1,"The first 50 self numbers are:\n")
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
pp(selfNumbers({1, 50}),{pp_IntFmt,"%3d",pp_IntCh,false})
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
for p=8 to 9 do
integer n = power(10,p)
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
printf(1,"The %,dth safe number is %,d\n",{n,selfNumbers({n})[1]})
<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;">"The first 50 self numbers are:\n"</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">selfNumbers</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">50</span><span style="color: #0000FF;">}),{</span><span style="color: #004600;">pp_IntFmt</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%3d"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">})</span>
printf(1,"completed in %s\n",elapsed(time()-t0))</lang>
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">8</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</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;">"The %,dth safe number is %,d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">selfNumbers</span><span style="color: #0000FF;">({</span><span style="color: #000000;">n</span><span style="color: #0000FF;">})[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]})</span>
<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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 985 ⟶ 1,790:
completed in 0.1s
</pre>
 
=={{header|Python}}==
{{works with|Python|2.7}}
<syntaxhighlight lang="python">class DigitSumer :
def __init__(self):
sumdigit = lambda n : sum( map( int,str( n )))
self.t = [sumdigit( i ) for i in xrange( 10000 )]
def __call__ ( self,n ):
r = 0
while n >= 10000 :
n,q = divmod( n,10000 )
r += self.t[q]
return r + self.t[n]
 
 
def self_numbers ():
d = DigitSumer()
s = set([])
i = 1
while 1 :
n = i + d( i )
if i in s :
s.discard( i )
else:
yield i
s.add( n )
i += 1
 
import time
p = 100
t = time.time()
for i,s in enumerate( self_numbers(),1 ):
if i <= 50 :
print s,
if i == 50 : print
if i == p :
print '%7.1f sec %9dth = %d'%( time.time()-t,i,s )
p *= 10</syntaxhighlight>
{{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
0.0 sec 100th = 973
0.0 sec 1000th = 10188
0.1 sec 10000th = 102225
1.0 sec 100000th = 1022675
11.4 sec 1000000th = 10227221
143.4 sec 10000000th = 102272662
1812.0 sec 100000000th = 1022727208</pre>
 
=={{header|Raku}}==
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}}
<syntaxhighlight lang="raku" line># 20201127 Raku programming solution
 
my ( $st, $count, $i, $pow, $digits, $offset, $lastSelf, $done, @selfs) =
now, 0, 1, 10, 1, 9, 0, False;
 
# while ( $count < 1e8 ) {
until $done {
my $isSelf = True;
my $sum = (my $start = max ($i-$offset), 0).comb.sum;
loop ( my $j = $start; $j < $i; $j+=1 ) {
if $j+$sum == $i { $isSelf = False and last }
($j+1)%10 != 0 ?? ( $sum+=1 ) !! ( $sum = ($j+1).comb.sum ) ;
}
if $isSelf {
$count+=1;
$lastSelf = $i;
if $count ≤ 50 {
@selfs.append: $i;
if $count == 50 {
say "The first 50 self numbers are:\n", @selfs;
$done = True;
}
}
}
$i+=1;
if $i % $pow == 0 {
$pow *= 10;
$digits+=1 ;
$offset = $digits * 9
}
}
 
# say "The 100 millionth self number is ", $lastSelf;
# say "Took ", now - $st, " seconds."</syntaxhighlight>
{{out}}
<pre>The first 50 self numbers are:
[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]</pre>
 
=={{header|REXX}}==
=== first 50 self numbers ===
<langsyntaxhighlight lang="rexx">/*REXX program displays N self numbers, (aka Colombian or Devlali numbers). OEIS A3052.*/
parse arg n . /*obtain optional argument from the CL.*/
if n=='' | n=="," then n= 50 /*Not specified? Then use the default.*/
tell = n>0; n= abs(n) /*TELL: show the self numbers if N>0 */
@.= . /*initialize the array of self numbers.*/
do j=1 for n*10 /*scan through ten times the #s wanted.*/
$= j /*1st part of sum is the number itself.*/
do k=1 for length(j) /*sum the decimal digits in the number.*/
$= $ + substr(j, k, 1) /*add a particular digit to the sum. */
end /*k*/
@.$= /*mark J as not being a self number. */
end /*j*/ /* ─── */
list= 1 /*initialize the list to the 1st number*/
#= 1 /*the count of self numbers (so far). */
Line 1,005 ⟶ 1,898:
#= # + 1; list= list i /*bump counter of self #'s; add to list*/
end /*i*/
/*stick a fork in it, we're all done. */
 
say n n " self numbers were found." /*display the title for the output list*/
if tell then say list /*display list of self numbers ──►term.*/</syntaxhighlight>
exit 0 /*stick a fork in it, we're all done. */</lang>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
Line 1,017 ⟶ 1,909:
=== ten millionth self number ===
{{trans|Go (low memory)}}
<langsyntaxhighlight lang="rexx">/*REXX pgm displays the Nth self number, aka Colombian or Devlali numbers. OEIS A3052.*/
numeric digits 20 /*ensure enough decimal digits for #. */
parse arg high . /*obtain optional argument from the CL.*/
if high=='' | high=="," then high= 10000000010000000 /*Not specified? Then use 100M10M default.*/
i= 1; pow= 10; digs= 1; offset= 9; $= 0 /*$: the last self number found. */
#= 0 /*count of self numbers (so far). */
do while #<high; isSelf= 1 /*assume a self number (so far). */
start= max(i-offset, 0) /*find start #; must be non-negative. */
sum= sumDigs(start) /*obtain the sum of the decimal digits.*/
 
do j=start to i-1
Line 1,031 ⟶ 1,923:
iterate /*keep looking for more self numbers. */
end
if (j+1)//10==0 then sum= sumDigs(j+1) /*obtain the sum of the decimal digits.*/
jp= j + 1 /*shortcut variable for next statement.*/
else sum= sum + 1 /*bump " " " " " " */
if jp//10==0 then sum= sumDigs(jp)
else sum= sum + 1
end /*j*/
 
Line 1,039 ⟶ 1,930:
$= i /*save the last self number found. */
end
i= i + 1 /*bump the self number by unity. */
i= i + 1
if i//pow==0 then do; pow digs= powdigs + 1 /* 10 " " number of decimal digits. */
digs= digs + 1pow= pow * 10 /*bump the number" of decimal digits." power " a factor of ten. */
offset= digs * 9 /*bump the " " offset by a" " " factor of" nine. */
end
end /*while*/
Line 1,054 ⟶ 1,945:
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg _; do c=length(_)-3 to 1 by -3; _=insert(',', _, c); end; return _
th: parse arg th; return word('th st nd rd', 1 +(th//10)*(th//100%10\==1)*(th//10<4))</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
the 100,000,000th self number is: 1,022,727,208
</pre>
 
=={{header|Ring}}==
<syntaxhighlight lang="ring">
load "stdlib.ring"
 
see "working..." + nl
see "The first 50 self numbers are:" + nl
 
n = 0
num = 0
limit = 51
limit2 = 10000000
 
while true
n = n + 1
for m = 1 to n
flag = 1
sum = 0
strnum = string(m)
for p = 1 to len(strnum)
sum = sum + number(strnum[p])
next
sum2 = m + sum
if sum2 = n
flag = 0
exit
else
flag = 1
ok
next
if flag = 1
num = num + 1
if num < limit
see "" + num + ". " + n + nl
ok
if num = limit2
see "The " + limit2 + "th self number is: " + n + nl
ok
if num > limit2
exit
ok
ok
end
 
see "done..." + nl
</syntaxhighlight>
Output:
<pre>
working...
The first 50 self numbers are:
1. 1
2. 3
3. 5
4. 7
5. 9
6. 20
7. 31
8. 42
9. 53
10. 64
11. 75
12. 86
13. 97
14. 108
15. 110
16. 121
17. 132
18. 143
19. 154
20. 165
21. 176
22. 187
23. 198
24. 209
25. 211
26. 222
27. 233
28. 244
29. 255
30. 266
31. 277
32. 288
33. 299
34. 310
35. 312
36. 323
37. 334
38. 345
39. 356
40. 367
41. 378
42. 389
43. 400
44. 411
45. 413
46. 424
47. 435
48. 446
49. 457
50. 468
The 10000000th self number is: 1022727208
done...
</pre>
 
=={{header|RPL}}==
====Brute force====
Using a sieve:
« 0
'''WHILE''' OVER '''REPEAT'''
SWAP 10 MOD LASTARG / IP
ROT ROT +
'''END''' +
» '<span style="color:blue">DIGSUM</span>' STO
« 500 0 → max n
« { } DUP max + 0 CON
1 CF
'''DO''' 'n' INCR
DUP <span style="color:blue">DIGSUM</span> +
'''IFERR''' 1 PUT '''THEN''' DROP2 1 SF '''END'''
'''UNTIL''' 1 FS? '''END'''
1
'''WHILE''' 3 PICK SIZE 50 < '''REPEAT'''
'''IF''' DUP2 GET NOT '''THEN''' ROT OVER + ROT ROT '''END'''
1 +
'''END''' DROP2
» » '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1: { 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 }
</pre>
Runs in 2 minutes 8 seconds on a HP-48SX.
====Maximilian F. Hasler's algorithm====
Translation of the PARI/GP formula on the OEIS page:
« → n
« { } 1 SF
1 n 2 / IP n XPON 1 + 9 * MIN '''FOR''' j
'''IF''' n j - <span style="color:blue">DIGSUM</span> j == '''THEN''' 1 CF n 'j' STO '''END'''
'''NEXT'''
1 FS?
» '<span style="color:blue">SELF?</span>' STO
« { }
'''WHILE''' OVER SIZE 50 < REPEAT
'''IF''' DUP <span style="color:blue">SELF?</span> '''THEN''' SWAP OVER + SWAP '''END'''
1 +
'''END''' DROP
» '<span style="color:blue">TASK</span>' STO
Same result as above. No need for sieve, but much slower: 10 minutes 52 seconds on a HP-48SX.
 
=={{header|Sidef}}==
Algorithm by David A. Corneth (OEIS: A003052).
<syntaxhighlight lang="ruby">func is_self_number(n) {
 
if (n < 30) {
return (((n < 10) && (n.is_odd)) || (n == 20))
}
 
var qd = (1 + n.ilog10)
var r = (1 + (n-1)%9)
var h = (r + 9*(r%2))/2
var ld = 10
 
while (h + 9*qd >= n%ld) {
ld *= 10
}
 
var vs = idiv(n, ld).sumdigits
n %= ld
 
0..qd -> none { |i|
vs + sumdigits(n - h - 9*i) == (h + 9*i)
}
}
 
say is_self_number.first(50).join(' ')</syntaxhighlight>
{{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
</pre>
 
Simpler algorithm (by M. F. Hasler):
 
<syntaxhighlight lang="ruby">func is_self_number(n) {
1..min(n>>1, 9*n.len) -> none {|i| sumdigits(n-i) == i } && (n > 0)
}</syntaxhighlight>
 
=={{header|Standard ML}}==
<syntaxhighlight lang="ocaml">
open List;
 
val rec selfNumberNr = fn NR =>
let
val rec sumdgt = fn 0 => 0 | n => Int.rem (n, 10) + sumdgt (Int.quot(n ,10));
val rec isSelf = fn ([],l1,l2) => []
| (x::tt,l1,l2) => if exists (fn i=>i=x) l1 orelse exists (fn i=>i=x) l2
then ( isSelf (tt,l1,l2)) else x::isSelf (tt,l1,l2) ;
 
val rec partcount = fn (n, listIn , count , selfs) =>
if count >= NR then nth (selfs, length selfs + NR - count -1)
else
let
val range = tabulate (81 , fn i => 81*n +i+1) ;
val listOut = map (fn i => i + sumdgt i ) range ;
val selfs = isSelf (range,listIn,listOut)
in
partcount ( n+1 , listOut , count+length (selfs) , selfs )
end;
in
partcount (0,[],0,[])
end;
 
app ((fn s => print (s ^ " ")) o Int.toString o selfNumberNr) (tabulate (50,fn i=>i+1)) ;
selfNumberNr 100000000 ;
</syntaxhighlight>
output
<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
1022727208
</pre>
 
Line 1,067 ⟶ 2,178:
 
Unsurprisingly, very slow compared to the Go version as Wren is interpreted and uses floating point arithmetic for all numerical work.
<langsyntaxhighlight ecmascriptlang="wren">var sieve = Fn.new {
var sv = List.filled(2*1e9+9*9+1, false)
var n = 0
Line 1,118 ⟶ 2,229:
}
}
System.print("Took %(System.clock-st) seconds.")</langsyntaxhighlight>
 
{{out}}
Line 1,127 ⟶ 2,238:
The 100 millionth self number is 1022727208
Took 222.789713 seconds.
</pre>
 
=={{header|XPL0}}==
{{trans|Go}}
As run on Raspberry Pi4.
<syntaxhighlight lang "XPL0">def LenSV = 2_000_000_000 + 9*9 + 1;
 
func Sieve;
char SV;
int N, S(8), A, B, C, D, E, F, G, H, I, J;
[SV:= MAlloc(LenSV);
N:= 0;
for A:= 0 to 1 do
[for B:= 0 to 9 do
[S(0):= A + B;
for C:= 0 to 9 do
[S(1):= S(0) + C;
for D:= 0 to 9 do
[S(2):= S(1) + D;
for E:= 0 to 9 do
[S(3):= S(2) + E;
for F:= 0 to 9 do
[S(4):= S(3) + F;
for G:= 0 to 9 do
[S(5):= S(4) + G;
for H:= 0 to 9 do
[S(6):= S(5) + H;
for I:= 0 to 9 do
[S(7):= S(6) + I;
for J:= 0 to 9 do
[SV(S(7)+J+N):= true;
N:= N+1;
]
]
]
]
]
]
]
]
]
];
return SV;
];
 
char SV;
int ST, Count, I;
[ST:= GetTime;
SV:= Sieve;
Count:= 0;
Text(0, "The first 50 self numbers are:^m^j");
for I:= 0 to LenSV-1 do
[if SV(I) = false then
[Count:= Count+1;
if Count <= 50 then
[IntOut(0, I); ChOut(0, ^ )];
if Count = 100_000_000 then
[Text(0, "^m^j^m^jThe 100 millionth self number is ");
IntOut(0, I);
CrLf(0);
I:= LenSV;
];
];
];
Text(0, "Took "); RlOut(0, float(GetTime-ST) / 1e6); CrLf(0);
]</syntaxhighlight>
{{out}}
<pre>
The first 50 self numbers are:
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
 
The 100 millionth self number is 1022727208
Took 29.46575
</pre>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/302845...354312"