Self numbers: Difference between revisions
m
syntax highlighting fixup automation
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: removed unused variables) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 15:
=={{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 #
Line 74:
FI
OD
END</
{{out}}
<pre>
Line 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 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 255:
}
function max(x,y) { return((x > y) ? x : y) }
</syntaxhighlight>
{{out}}
<pre>
Line 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 341:
printf("Took %lf seconds.\n", (double)(clock() - begin) / CLOCKS_PER_SEC);
return 0;
}</
{{out}}
Line 354:
===Extended===
{{trans|Pascal}}
<
#include <stdlib.h>
#include <time.h>
Line 430:
printf("\nOverall took %lf seconds.\n", (double)(clock() - begin) / CLOCKS_PER_SEC);
return 0;
}</
{{out}}
Line 456:
=={{header|C++}}==
{{trans|Java}}
<
#include <iomanip>
#include <iostream>
Line 508:
return 0;
}</
{{out}}
<pre>The first 50 self numbers are:
Line 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 558:
WriteLine("\nOverall took {0}s", (DateTime.Now - st). TotalSeconds);
}
}</
{{out}}Timing from tio.run
<pre>Sieving took 3.4266187s
Line 579:
=={{header|Elixir}}==
<
defmodule SelfNums do
Line 606:
end
</syntaxhighlight>
{{out}}
Line 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 623:
Self |> Seq.take 50 |> Seq.iter(printf "%d "); printfn ""
printfn "\n%d" (Seq.item 99999999 Self)
</syntaxhighlight>
{{out}}
<pre>
Line 634:
=={{header|FreeBASIC}}==
{{trans|Ring}}
<
Dim As Boolean flag
Dim As Ulong m, p, sum, number(), sum2
Line 669:
End If
Loop
Sleep</
Line 675:
===Low memory===
Simple-minded, uses very little memory (no sieve) but slow - over 2.5 minutes.
<
import (
Line 742:
fmt.Println("\nThe 100 millionth self number is", lastSelf)
fmt.Println("Took", time.Since(st))
}</
{{out}}
Line 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 821:
}
fmt.Println("Took", time.Since(st))
}</
{{out}}
Line 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 910:
}
fmt.Println("\nOverall took", time.Since(st))
}</
{{out}}
Line 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 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 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 1,023:
}
}
}</
{{out}}
<pre>The first 50 self numbers are:
Line 1,042:
'''Adapted from [[#Julia|Julia]]'''
{{works with|jq}}
<syntaxhighlight lang="jq">
def sumdigits: tostring | explode | map([.]|implode|tonumber) | add;
Line 1,077:
then "Yes, \(.) is the 100,000,000th self number."
else "No, \(.i) is actually the 100,000,000th self number."
end)</
{{out}}
<pre>
Line 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 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 1,128:
{{trans|Pascal}}
Contains tweaks peculiar to the "10 to the nth" self number. Timings include compilation times.
<
function dosieve!(sieve, digitsum9999)
Line 1,171:
@time findselves()
</
<pre>
Sieve time:
Line 1,191:
=={{header|Kotlin}}==
{{trans|Java}}
<
private val SV = BooleanArray(MC + 1)
Line 1,267:
i++
}
}</
{{out}}
<pre>The first 50 self numbers are:
Line 1,284:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">
sum[g_] := g + Total@IntegerDigits@g
Line 1,296:
If[self[x], Sow[x]; t++]; x++]
][[2, 1]]]
</syntaxhighlight>
{{out}}
Line 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,392:
echo ($count).align(10), ($n).align(12)
limit *= 10
echo "Total time: ", getMonoTime() - t0</
{{out}}
Line 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,508:
echo ($count).align(10), ($n).align(12)
limit *= 10
echo "Total time: ", getMonoTime() - t0</
{{out}}
Line 1,533:
Just "sieving" with only one follower of every number {{trans|Go}}
Extended to 10.23e9
<
{$IFDEF FPC}
{$MODE Delphi}
Line 1,629:
end;
end;
END.</
{{out}}
<pre> time ./selfnumb
Line 1,649:
=={{header|Perl}}==
{{trans|Raku}}
<
use warnings;
use feature 'say';
Line 1,677:
}
say "The first 50 self numbers are:\n" . join ' ', @selfs;</
{{out}}
<pre>The first 50 self numbers are:
Line 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,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,793:
=={{header|Python}}==
{{works with|Python|2.7}}
<
def __init__(self):
sumdigit = lambda n : sum( map( int,str( n )))
Line 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,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,874:
# say "The 100 millionth self number is ", $lastSelf;
# say "Took ", now - $st, " seconds."</
{{out}}
<pre>The first 50 self numbers are:
Line 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,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,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,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,952:
=={{header|Ring}}==
<
load "stdlib.ring"
Line 1,995:
see "done..." + nl
</syntaxhighlight>
Output:
<pre>
Line 2,056:
=={{header|Sidef}}==
Algorithm by David A. Corneth (OEIS: A003052).
<
if (n < 30) {
Line 2,079:
}
say is_self_number.first(50).join(' ')</
{{out}}
<pre>
Line 2,087:
Simpler algorithm (by M. F. Hasler):
<
1..min(n>>1, 9*n.len) -> none {|i| sumdigits(n-i) == i } && (n > 0)
}</
=={{header|Standard ML}}==
<syntaxhighlight lang="ocaml">
open List;
Line 2,118:
app ((fn s => print (s ^ " ")) o Int.toString o selfNumberNr) (tabulate (50,fn i=>i+1)) ;
selfNumberNr 100000000 ;
</syntaxhighlight>
output
<pre>
Line 2,132:
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 2,183:
}
}
System.print("Took %(System.clock-st) seconds.")</
{{out}}
|