Self numbers: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
(→{{header|Haskell}}: added solution) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (14 intermediate revisions by 9 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}}==
Line 17 ⟶ 97:
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
Line 122 ⟶ 202:
-- 97,777,777,792nd:
selfNumbers(9.7777777792E+10)
--> {9.99999999997E+11}</
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f SELF_NUMBERS.AWK
# converted from Go (low memory example)
Line 174 ⟶ 255:
}
function max(x,y) { return((x > y) ? x : y) }
</syntaxhighlight>
{{out}}
<pre>
Line 197 ⟶ 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.
<
#include <stdlib.h>
#include <time.h>
Line 260 ⟶ 341:
printf("Took %lf seconds.\n", (double)(clock() - begin) / CLOCKS_PER_SEC);
return 0;
}</
{{out}}
Line 273 ⟶ 354:
===Extended===
{{trans|Pascal}}
<
#include <stdlib.h>
#include <time.h>
Line 349 ⟶ 430:
printf("\nOverall took %lf seconds.\n", (double)(clock() - begin) / CLOCKS_PER_SEC);
return 0;
}</
{{out}}
Line 375 ⟶ 456:
=={{header|C++}}==
{{trans|Java}}
<
#include <iomanip>
#include <iostream>
Line 427 ⟶ 508:
return 0;
}</
{{out}}
<pre>The first 50 self numbers are:
Line 445 ⟶ 526:
=={{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;
Line 477 ⟶ 558:
WriteLine("\nOverall took {0}s", (DateTime.Now - st). TotalSeconds);
}
}</
{{out}}Timing from tio.run
<pre>Sieving took 3.4266187s
Line 498 ⟶ 579:
=={{header|Elixir}}==
<
defmodule SelfNums do
Line 525 ⟶ 606:
end
</syntaxhighlight>
{{out}}
Line 535 ⟶ 616:
=={{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
Line 542 ⟶ 623:
Self |> Seq.take 50 |> Seq.iter(printf "%d "); printfn ""
printfn "\n%d" (Seq.item 99999999 Self)
</syntaxhighlight>
{{out}}
<pre>
Line 549 ⟶ 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.
<
import (
Line 620 ⟶ 742:
fmt.Println("\nThe 100 millionth self number is", lastSelf)
fmt.Println("Took", time.Since(st))
}</
{{out}}
Line 637 ⟶ 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%.
<
import (
Line 699 ⟶ 821:
}
fmt.Println("Took", time.Since(st))
}</
{{out}}
Line 713 ⟶ 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.
<
import (
Line 788 ⟶ 910:
}
fmt.Println("\nOverall took", time.Since(st))
}</
{{out}}
Line 815 ⟶ 937:
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
Line 839 ⟶ 961:
print $ take 50 selfs
forM_ [1..8] $ \i ->
printf "1e%v\t%v\n" (i :: Int) (selfs !! (10^i-1))</
<pre>$ ghc -O2 SelfNum.hs && time ./SelfNum
Line 855 ⟶ 977:
=={{header|Java}}==
{{trans|C#}}
<
private static final int MC = 103 * 1000 * 10000 + 11 * 9 + 1;
private static final boolean[] SV = new boolean[MC + 1];
Line 901 ⟶ 1,023:
}
}
}</
{{out}}
<pre>The first 50 self numbers are:
Line 916 ⟶ 1,038:
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 921 ⟶ 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.
<
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 947 ⟶ 1,119:
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
Line 956 ⟶ 1,128:
{{trans|Pascal}}
Contains tweaks peculiar to the "10 to the nth" self number. Timings include compilation times.
<
function dosieve!(sieve, digitsum9999)
Line 999 ⟶ 1,171:
@time findselves()
</
<pre>
Sieve time:
Line 1,019 ⟶ 1,191:
=={{header|Kotlin}}==
{{trans|Java}}
<
private val SV = BooleanArray(MC + 1)
Line 1,095 ⟶ 1,267:
i++
}
}</
{{out}}
<pre>The first 50 self numbers are:
Line 1,110 ⟶ 1,282:
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}}==
Line 1,121 ⟶ 1,311:
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
Line 1,202 ⟶ 1,392:
echo ($count).align(10), ($n).align(12)
limit *= 10
echo "Total time: ", getMonoTime() - t0</
{{out}}
Line 1,229 ⟶ 1,419:
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
Line 1,318 ⟶ 1,508:
echo ($count).align(10), ($n).align(12)
limit *= 10
echo "Total time: ", getMonoTime() - t0</
{{out}}
Line 1,343 ⟶ 1,533:
Just "sieving" with only one follower of every number {{trans|Go}}
Extended to 10.23e9
<
{$IFDEF FPC}
{$MODE Delphi}
Line 1,439 ⟶ 1,629:
end;
end;
END.</
{{out}}
<pre> time ./selfnumb
Line 1,459 ⟶ 1,649:
=={{header|Perl}}==
{{trans|Raku}}
<
use warnings;
use feature 'say';
use List::Util qw(max sum);
my (
= (
my $final = 50;
Line 1,478 ⟶ 1,668:
if ($isSelf) {
push @selfs, $
last if @selfs == $final;
}
next unless ++$i % $pow == 0;
$pow *= 10;
$offset = 9 * $digits++
}
say "The first 50 self numbers are:\n" . join ' ', @selfs;</
{{out}}
<pre>The first 50 self numbers are:
Line 1,499 ⟶ 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.
<!--<
<span style="color: #000080;font-style:italic;">--
-- Base-10 self numbers by index (single or range).
Line 1,592 ⟶ 1,779:
<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>
Line 1,606 ⟶ 1,793:
=={{header|Python}}==
{{works with|Python|2.7}}
<
def __init__(self):
sumdigit = lambda n : sum( map( int,str( n )))
Line 1,640 ⟶ 1,827:
if i == p :
print '%7.1f sec %9dth = %d'%( time.time()-t,i,s )
p *= 10</
{{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 1,654 ⟶ 1,841:
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"
my ( $st, $count, $i, $pow, $digits, $offset, $lastSelf, $done, @selfs) =
Line 1,687 ⟶ 1,874:
# say "The 100 millionth self number is ", $lastSelf;
# say "Took ", now - $st, " seconds."</
{{out}}
<pre>The first 50 self numbers are:
Line 1,694 ⟶ 1,881:
=={{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.*/
Line 1,713 ⟶ 1,900:
/*stick a fork in it, we're all done. */
say n " self numbers were found." /*display the title for the output list*/
if tell then say list /*display list of self numbers ──►term.*/</
{{out|output|text= when using the default input:}}
<pre>
Line 1,722 ⟶ 1,909:
=== 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.*/
Line 1,758 ⟶ 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))</
{{out|output|text= when using the default input:}}
<pre>
Line 1,765 ⟶ 1,952:
=={{header|Ring}}==
<
load "stdlib.ring"
Line 1,808 ⟶ 1,995:
see "done..." + nl
</syntaxhighlight>
Output:
<pre>
Line 1,866 ⟶ 2,053:
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;
Line 1,894 ⟶ 2,164:
app ((fn s => print (s ^ " ")) o Int.toString o selfNumberNr) (tabulate (50,fn i=>i+1)) ;
selfNumberNr 100000000 ;
</syntaxhighlight>
output
<pre>
Line 1,908 ⟶ 2,178:
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
Line 1,959 ⟶ 2,229:
}
}
System.print("Took %(System.clock-st) seconds.")</
{{out}}
Line 1,968 ⟶ 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>
| |||