Pernicious numbers: Difference between revisions
(Add Rust implementation) |
m (Added Easylang) |
||
(32 intermediate revisions by 22 users not shown) | |||
Line 6: | Line 6: | ||
;Example |
;Example |
||
'''22''' (which is '''10110''' in binary) has a population count of '''3''', which is prime, |
'''22''' (which is '''10110''' in binary) has a population count of '''3''', which is prime, and therefore |
||
<br>'''22''' is a pernicious number. |
|||
Line 21: | Line 22: | ||
=={{header|11l}}== |
=={{header|11l}}== |
||
< |
<syntaxhighlight lang="11l">F is_prime(n) |
||
R bin(n).count(‘1’) |
|||
F is_prime(n) |
|||
I n < 2 |
I n < 2 |
||
R 0B |
R 0B |
||
Line 35: | Line 33: | ||
V cnt = 0 |
V cnt = 0 |
||
L |
L |
||
I is_prime(popcount(i)) |
I is_prime(bits:popcount(i)) |
||
print(i, end' ‘ ’) |
print(i, end' ‘ ’) |
||
cnt++ |
cnt++ |
||
Line 44: | Line 42: | ||
print() |
print() |
||
L(i) 888888877..888888888 |
L(i) 888888877..888888888 |
||
I is_prime(popcount(i)) |
I is_prime(bits:popcount(i)) |
||
print(i, end' ‘ ’)</ |
print(i, end' ‘ ’)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 57: | Line 55: | ||
For maximum compatibility, this program uses only the basic instruction set (S/360) |
For maximum compatibility, this program uses only the basic instruction set (S/360) |
||
with 2 ASSIST macros (XDECO,XPRNT). |
with 2 ASSIST macros (XDECO,XPRNT). |
||
< |
<syntaxhighlight lang="360asm">* Pernicious numbers 04/05/2016 |
||
PERNIC CSECT |
PERNIC CSECT |
||
USING PERNIC,R13 base register and savearea pointer |
USING PERNIC,R13 base register and savearea pointer |
||
Line 182: | Line 180: | ||
XDEC DS CL12 edit zone |
XDEC DS CL12 edit zone |
||
YREGS |
YREGS |
||
END PERNIC</ |
END PERNIC</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 189: | Line 187: | ||
</pre> |
</pre> |
||
=={{header| |
=={{header|Action!}}== |
||
Action! integers are limited to 16 bits, so this implements 32 bit addition and multiplication by 8-bit values to handle the larger numbers. |
|||
<syntaxhighlight lang="action!"> |
|||
;;; find some pernicious numbers - numbers where the population count is prime |
|||
;;; As the task requires 32 bit integers, this implements 32-bit unsigend |
|||
;;; integer addition and multiplication by an 8-bit integer. |
|||
;;; The 32-bit values are stored in 4 separate bytes |
|||
;;; returns the population (number of bits on) of the non-negative integer n |
|||
BYTE FUNC population( CARD n ) |
|||
CARD number |
|||
BYTE result |
|||
number = n |
|||
result = 0; |
|||
WHILE number > 0 DO |
|||
IF number AND 1 THEN result ==+ 1 FI |
|||
number ==/ 2 |
|||
OD |
|||
RETURN( result ) |
|||
;;; returns TRUE if n is a prime; n must be <= 32 |
|||
BYTE FUNC isSmallPrime( BYTE n ) |
|||
BYTE result |
|||
IF n = 2 THEN result = 1 |
|||
ELSEIF ( n AND 1 ) = 0 THEN result = 0 |
|||
ELSEIF n = 1 OR n = 9 OR n = 15 |
|||
OR n = 21 OR n = 25 OR n = 27 |
|||
THEN result = 0 |
|||
ELSE result = 1 |
|||
FI |
|||
RETURN( result ) |
|||
;;; returns TRUE if n is pernicious, FALSE otherwise |
|||
BYTE FUNC isPernicious( CARD n ) RETURN( isSmallPrime( population( n ) ) ) |
|||
;;; returns TRUE if the 32 bit integer in i1, i2, i3, i4 is pernicious, |
|||
;;; FALSE otherwise |
|||
BYTE FUNC isPernicious32( BYTE i1, i2, i3, i4 ) |
|||
BYTE p |
|||
p = population( i1 ) + population( i2 ) |
|||
+ population( i3 ) + population( i4 ) |
|||
RETURN( isSmallPrime( p ) ) |
|||
;;; adds b to the 32 bit unsigned integer in i1, i2, i3 and i4 |
|||
PROC i32add8( BYTE POINTER i1, i2, i3, i4, BYTE b ) |
|||
CARD c1, c2, c3, c4 |
|||
c1 = i1^ c2 = i2^ c3 = i3^ c4 = i4^ |
|||
c4 ==+ b |
|||
i4 ^= c4 MOD 256 |
|||
c3 ==+ c4 / 256 |
|||
i3 ^= c3 MOD 256 |
|||
c2 ==+ c3 / 256 |
|||
i2 ^= c2 MOD 256 |
|||
c1 ==+ c2 / 256 |
|||
i1 ^= c1 MOD 256 |
|||
RETURN |
|||
;;; multiplies the 32 bit unsigned integer in i1, i2, i3 and i4 by b |
|||
PROC i32mul8( BYTE POINTER i1, i2, i3, i4, BYTE b ) |
|||
CARD c1, c2, c3, c4, r |
|||
c1 = i1^ c2 = i2^ c3 = i3^ c4 = i4^ |
|||
r = c4 * b |
|||
i4 ^= r MOD 256 |
|||
r = ( c3 * b ) + ( r / 256 ) |
|||
i3 ^= r MOD 256 |
|||
r = ( c2 * b ) + ( r / 256 ) |
|||
i2 ^= r MOD 256 |
|||
r = ( c1 * b ) + ( r / 256 ) |
|||
i1 ^= r MOD 256 |
|||
RETURN |
|||
;;; find the first 25 pernicious numbers |
|||
PROC Main() |
|||
BYTE perniciousCount, i |
|||
BYTE i81, i82, i83, i84 |
|||
BYTE p81, p82, p83, p84 |
|||
perniciousCount = 0 |
|||
i = 0 |
|||
WHILE perniciousCount < 25 DO |
|||
IF isPernicious( i ) THEN |
|||
; found a pernicious number |
|||
PrintB( i )Put(' ) |
|||
perniciousCount ==+ 1 |
|||
FI |
|||
i ==+ 1 |
|||
OD |
|||
PutE() |
|||
; find the pernicious numbers between 888 888 877 and 888 888 888 |
|||
; form 888 888 800 in i81, i82, i83 and i84 |
|||
i81 = 0 i82 = 0 i83 = 0 i84 = 88 ; 88 |
|||
i32mul8( @i81, @i82, @i83, @i84, 100 ) ; 8 800 |
|||
i32add8( @i81, @i82, @i83, @i84, 88 ) ; 8 888 |
|||
i32mul8( @i81, @i82, @i83, @i84, 100 ) ; 888 800 |
|||
i32add8( @i81, @i82, @i83, @i84, 88 ) ; 888 888 |
|||
i32mul8( @i81, @i82, @i83, @i84, 10 ) ; 8 888 880 |
|||
i32add8( @i81, @i82, @i83, @i84, 8 ) ; 8 888 888 |
|||
i32mul8( @i81, @i82, @i83, @i84, 100 ) ; 888 888 800 |
|||
FOR i = 77 TO 88 DO |
|||
p81 = i81 p82 = i82 p83 = i83 p84 = i84 |
|||
i32add8( @p81, @p82, @p83, @p84, i ) |
|||
IF isPernicious32( p81, p82, p83, p84 ) |
|||
THEN |
|||
print( "8888888" )PrintB( i )Put(' ) |
|||
FI |
|||
OD |
|||
PutE() |
|||
RETURN |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
|||
888888877 888888878 888888880 888888883 888888885 888888886 |
|||
</pre> |
|||
=={{header|Ada}}== |
|||
Uses package Population_Count from [[Population count#Ada]]. |
Uses package Population_Count from [[Population count#Ada]]. |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO, Population_Count; use Population_Count; |
||
procedure Pernicious is |
procedure Pernicious is |
||
Line 232: | Line 354: | ||
end loop; |
end loop; |
||
Ada.Text_IO.New_Line; |
Ada.Text_IO.New_Line; |
||
end;</ |
end;</syntaxhighlight> |
||
Line 242: | Line 364: | ||
A small modification allows to count all the pernicious numbers between 1 and 2**32 in about 32 seconds: |
A small modification allows to count all the pernicious numbers between 1 and 2**32 in about 32 seconds: |
||
< |
<syntaxhighlight lang="ada"> Counter: Natural; |
||
begin |
begin |
||
-- initialize array Prime; Prime(I) must be true if and only if I is a prime |
-- initialize array Prime; Prime(I) must be true if and only if I is a prime |
||
Line 255: | Line 377: | ||
end loop; |
end loop; |
||
Ada.Text_IO.Put_Line(Natural'Image(Counter)); |
Ada.Text_IO.Put_Line(Natural'Image(Counter)); |
||
end Count_Pernicious;</ |
end Count_Pernicious;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 267: | Line 389: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
< |
<syntaxhighlight lang="algol68"># calculate various pernicious numbers # |
||
# returns the population (number of bits on) of the non-negative integer n # |
# returns the population (number of bits on) of the non-negative integer n # |
||
Line 314: | Line 436: | ||
OD; |
OD; |
||
print( ( newline ) ) |
print( ( newline ) ) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 320: | Line 442: | ||
888888877 888888878 888888880 888888883 888888885 888888886 |
888888877 888888878 888888880 888888883 888888885 888888886 |
||
</pre> |
</pre> |
||
=={{header|ALGOL W}}== |
|||
<syntaxhighlight lang="algolw">begin % find some pernicious numbers: numbers with a prime population count % |
|||
% returns the population count of n % |
|||
integer procedure populationCount( integer value n ) ; |
|||
begin |
|||
integer v, count; |
|||
count := 0; |
|||
v := abs n; |
|||
while v > 0 do begin |
|||
if odd( v ) then count := count + 1; |
|||
v := v div 2 |
|||
end while_v_gt_0 ; |
|||
count |
|||
end populationCount ; |
|||
% sets p( 1 :: n ) to a sieve of primes up to n % |
|||
procedure Eratosthenes ( logical array p( * ) ; integer value n ) ; |
|||
begin |
|||
p( 1 ) := false; p( 2 ) := true; |
|||
for i := 3 step 2 until n do p( i ) := true; |
|||
for i := 4 step 2 until n do p( i ) := false; |
|||
for i := 3 step 2 until truncate( sqrt( n ) ) do begin |
|||
integer ii; ii := i + i; |
|||
if p( i ) then for pr := i * i step ii until n do p( pr ) := false |
|||
end for_i ; |
|||
end Eratosthenes ; |
|||
% returns true if p is pernicious, false otherwise, s must be a sieve % |
|||
% of primes upto 32 % |
|||
logical procedure isPernicious ( integer value p; logical array s ( * ) ) ; p > 0 and s( populationCount( p ) ); |
|||
% find the pernicious numbers % |
|||
begin |
|||
% as we are dealing with 32 bit numbers, the maximum possible % |
|||
% population is 32 % |
|||
logical array isPrime ( 1 :: 32 ); |
|||
integer p, pCount; |
|||
Eratosthenes( isPrime, 32 ); |
|||
% show the first 25 pernicious numbers % |
|||
pCount := 0; |
|||
p := 2; % 0 and 1 aren't pernicious, so start at 2 % |
|||
while pCount < 25 do begin |
|||
if isPernicious( p, isPrime ) then begin |
|||
% have a pernicious number % |
|||
pCount := pCount + 1; |
|||
writeon( i_w := 1, s_w := 0, " ", p ) |
|||
end if_pernicious_p ; |
|||
p := P + 1 |
|||
end for_p ; |
|||
write(); |
|||
% find the pernicious numbers between 888 888 877 and 888 888 888 % |
|||
for p := 888888877 until 888888888 do begin |
|||
if isPernicious( p, isPrime ) then writeon( i_w := 1, s_w := 0, " ", p ) |
|||
end for_p ; |
|||
write(); |
|||
end |
|||
end.</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
|||
888888877 888888878 888888880 888888883 888888885 888888886 |
|||
</pre> |
|||
=={{header|AppleScript}}== |
|||
<syntaxhighlight lang="applescript">on isPrime(n) |
|||
if (n < 4) then return (n > 1) |
|||
if ((n mod 2 is 0) or (n mod 3 is 0)) then return false |
|||
repeat with i from 5 to (n ^ 0.5) div 1 by 6 |
|||
if ((n mod i is 0) or (n mod (i + 2) is 0)) then return false |
|||
end repeat |
|||
return true |
|||
end isPrime |
|||
on isPernicious(n) |
|||
-- 8 bits at a time is statistically slightly more efficient than 1 bit at a time. |
|||
set popCount to (n mod 4 + 1) div 2 + (n mod 16 + 4) div 8 |
|||
set n to n div 16 |
|||
repeat until (n = 0) |
|||
set popCount to popCount + (n mod 4 + 1) div 2 + (n mod 16 + 4) div 8 |
|||
set n to n div 16 |
|||
end repeat |
|||
return isPrime(popCount) |
|||
end isPernicious |
|||
-- Task code: |
|||
on intToText(n) |
|||
set output to "" |
|||
repeat until (n < 100000000) |
|||
set output to text 2 thru 9 of ((100000000 + (n mod 100000000 as integer)) as text) & output |
|||
set n to n div 100000000 |
|||
end repeat |
|||
set output to (n as integer as text) & output |
|||
return output |
|||
end intToText |
|||
on join(lst, delim) |
|||
set astid to AppleScript's text item delimiters |
|||
set AppleScript's text item delimiters to delim |
|||
set output to lst as text |
|||
set AppleScript's text item delimiters to astid |
|||
return output |
|||
end join |
|||
on task() |
|||
set l1 to {} |
|||
set n to 0 |
|||
set counter to 0 |
|||
repeat until (counter = 25) |
|||
if (isPernicious(n)) then |
|||
set end of l1 to n |
|||
set counter to counter + 1 |
|||
end if |
|||
set n to n + 1 |
|||
end repeat |
|||
set l2 to {} |
|||
-- One solution to 8,888,877 and up being too large to be AppleScript repeat indices. |
|||
repeat with i from 88888877 to 88888888 |
|||
set n to 8.0E+8 + i |
|||
if (isPernicious(n)) then set end of l2 to intToText(n) |
|||
end repeat |
|||
return join(l1, " ") & (linefeed & join(l2, " ")) |
|||
end task |
|||
task()</syntaxhighlight> |
|||
{{output}} |
|||
<syntaxhighlight lang="applescript">"3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
|||
888888877 888888878 888888880 888888883 888888885 888888886"</syntaxhighlight> |
|||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="rebol">pernicious?: function [n][ |
|||
prime? size filter split as.binary n 'x -> x="0" |
|||
] |
|||
i: 1 |
|||
found: 0 |
|||
while [found<25][ |
|||
if pernicious? i [ |
|||
prints i |
|||
prints " " |
|||
found: found + 1 |
|||
] |
|||
i: i + 1 |
|||
] |
|||
print "" |
|||
print select 888888877..888888888 => pernicious?</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
|||
888888877 888888878 888888880 888888883 888888885 888888886</pre> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
{{works with|AutoHotkey 1.1}} |
{{works with|AutoHotkey 1.1}} |
||
< |
<syntaxhighlight lang="autohotkey">c := 0 |
||
while c < 25 |
while c < 25 |
||
if IsPern(A_Index) |
if IsPern(A_Index) |
||
Line 338: | Line 615: | ||
, x := (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f |
, x := (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f |
||
return p[(x * 0x0101010101010101) >> 56] |
return p[(x * 0x0101010101010101) >> 56] |
||
}</ |
}</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
||
Line 344: | Line 621: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f PERNICIOUS_NUMBERS.AWK |
# syntax: GAWK -f PERNICIOUS_NUMBERS.AWK |
||
BEGIN { |
BEGIN { |
||
Line 399: | Line 676: | ||
return gsub(/1/,"&",n) |
return gsub(/1/,"&",n) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 405: | Line 682: | ||
888888877 888888878 888888880 888888883 888888885 888888886 |
888888877 888888878 888888880 888888883 888888885 888888886 |
||
</pre> |
</pre> |
||
=={{header|BASIC}}== |
|||
==={{header|BASIC256}}=== |
|||
<syntaxhighlight lang="basic">n = 1 |
|||
cont = 0 |
|||
print "The following are the first 25 pernicious numbers:" |
|||
print |
|||
do |
|||
if isPernicious(n) then |
|||
print rjust(string(n), 3); |
|||
cont += 1 |
|||
end if |
|||
n += 1 |
|||
until cont = 25 |
|||
print : print |
|||
print "The pernicious numbers between 888,888,877 and 888,888,888 inclusive are:" |
|||
print |
|||
for n = 888888877 to 888888888 |
|||
if isPernicious(n) then print rjust(string(n), 10); |
|||
next n |
|||
end |
|||
function SumBinaryDigits(number) |
|||
if number < 0 then number = -number # convert negative numbers to positive |
|||
sum = 0 |
|||
while number > 0 |
|||
sum += number mod 2 |
|||
number /= 2 |
|||
end while |
|||
return sum |
|||
end function |
|||
function isPrime(v) |
|||
if v < 2 then return False |
|||
if v mod 2 = 0 then return v = 2 |
|||
if v mod 3 = 0 then return v = 3 |
|||
d = 5 |
|||
while d * d <= v |
|||
if v mod d = 0 then return False else d += 2 |
|||
end while |
|||
return True |
|||
end function |
|||
function isPernicious(number) |
|||
popcont = SumBinaryDigits(number) |
|||
return isPrime(popcont) |
|||
end function</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
==={{header|Gambas}}=== |
|||
<syntaxhighlight lang="vbnet">Public Sub Main() |
|||
Dim n As Integer = 1, count As Integer = 0 |
|||
Print "The following are the first 25 pernicious numbers:\n" |
|||
Do |
|||
If isPernicious(n) Then |
|||
Print Format$(n, "###"); |
|||
count += 1 |
|||
End If |
|||
n += 1 |
|||
Loop Until count = 25 |
|||
Print "\n\nThe pernicious numbers between 888,888,877 and 888,888,888 inclusive are:\n" |
|||
For n = 888888877 To 888888888 |
|||
If isPernicious(n) Then Print Format$(n, "##########"); |
|||
Next |
|||
Print |
|||
End |
|||
Public Sub isPrime(ValorEval As Long) As Boolean |
|||
If ValorEval < 2 Then Return False |
|||
If ValorEval Mod 2 = 0 Then Return ValorEval = 2 |
|||
If ValorEval Mod 3 = 0 Then Return ValorEval = 3 |
|||
Dim d As Long = 5 |
|||
While d * d <= ValorEval |
|||
If ValorEval Mod d = 0 Then Return False Else d += 2 |
|||
Wend |
|||
Return True |
|||
End Function |
|||
Public Function SumBinaryDigits(number As Integer) As Integer |
|||
If number < 0 Then number = -number ' convert negative numbers to positive |
|||
Dim sum As Integer = 0 |
|||
While number > 0 |
|||
sum += number Mod 2 |
|||
number \= 2 |
|||
Wend |
|||
Return sum |
|||
End Function |
|||
Public Function isPernicious(number As Integer) As Boolean |
|||
Dim popCount As Integer = SumBinaryDigits(number) |
|||
Return isPrime(popCount) |
|||
End Function</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
==={{header|Yabasic}}=== |
|||
<syntaxhighlight lang="basic">n = 1 |
|||
cont = 0 |
|||
print "The following are the first 25 pernicious numbers:\n" |
|||
repeat |
|||
if isPernicious(n) then |
|||
print n using ("###"); |
|||
cont = cont + 1 |
|||
fi |
|||
n = n + 1 |
|||
until cont = 25 |
|||
print "\n\nThe pernicious numbers between 888,888,877 and 888,888,888 inclusive are:\n" |
|||
for n = 888888877 to 888888888 |
|||
if isPernicious(n) print n using("##########"); |
|||
next n |
|||
print |
|||
end |
|||
sub SumBinaryDigits(number) |
|||
if number < 0 number = -number // convert negative numbers to positive |
|||
sum = 0 |
|||
while number > 0 |
|||
sum = sum + mod(number, 2) |
|||
number = int(number / 2) |
|||
wend |
|||
return sum |
|||
end sub |
|||
sub isPrime(v) |
|||
if v < 2 return False |
|||
if mod(v, 2) = 0 return v = 2 |
|||
if mod(v, 3) = 0 return v = 3 |
|||
d = 5 |
|||
while d * d <= v |
|||
if mod(v, d) = 0 then return False else d = d + 2 : fi |
|||
wend |
|||
return True |
|||
end sub |
|||
sub isPernicious(number) |
|||
popcont = SumBinaryDigits(number) |
|||
return isPrime(popcont) |
|||
end sub</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
=={{header|Befunge}}== |
=={{header|Befunge}}== |
||
Line 411: | Line 844: | ||
Also note that the extra spaces in the output are just to ensure it's readable on buggy interpreters that don't include a space after numeric output. They can easily be removed by replacing the comma on line 3 with a dollar. |
Also note that the extra spaces in the output are just to ensure it's readable on buggy interpreters that don't include a space after numeric output. They can easily be removed by replacing the comma on line 3 with a dollar. |
||
< |
<syntaxhighlight lang="befunge">55*00p1>:"ZOA>/"***7-*>\:2>/\v |
||
>8**`!#^_$@\<(^v^)>/#2^#\<2 2 |
>8**`!#^_$@\<(^v^)>/#2^#\<2 2 |
||
^+**"X^yYo":+1<_:.48*,00v|: <% |
^+**"X^yYo":+1<_:.48*,00v|: <% |
||
v".D}Tx"$,+55_^#!p00:-1g<v |< |
v".D}Tx"$,+55_^#!p00:-1g<v |< |
||
> * + : * * + ^^ ! % 2 $ <^ <^</ |
> * + : * * + ^^ ! % 2 $ <^ <^</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 422: | Line 855: | ||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
typedef unsigned uint; |
typedef unsigned uint; |
||
Line 446: | Line 879: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 454: | Line 887: | ||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Linq; |
using System.Linq; |
||
Line 516: | Line 949: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 524: | Line 957: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp"> |
||
#include <iostream> |
#include <iostream> |
||
using namespace std; |
using namespace std; |
||
Line 584: | Line 1,017: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 592: | Line 1,025: | ||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
< |
<syntaxhighlight lang="clojure">(defn counting-numbers |
||
([] (counting-numbers 1)) |
([] (counting-numbers 1)) |
||
([n] (lazy-seq (cons n (counting-numbers (inc n)))))) |
([n] (lazy-seq (cons n (counting-numbers (inc n)))))) |
||
Line 600: | Line 1,033: | ||
(prime? (count (filter #(= % \1) (Integer/toString n 2))))) |
(prime? (count (filter #(= % \1) (Integer/toString n 2))))) |
||
(println (take 25 (filter pernicious? (counting-numbers)))) |
(println (take 25 (filter pernicious? (counting-numbers)))) |
||
(println (filter pernicious? (range 888888877 888888889)))</ |
(println (filter pernicious? (range 888888877 888888889)))</syntaxhighlight> |
||
{{Output}} |
{{Output}} |
||
<pre>(3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36) |
<pre>(3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36) |
||
(888888877 888888878 888888880 888888883 888888885 888888886)</pre> |
(888888877 888888878 888888880 888888883 888888885 888888886)</pre> |
||
=={{header|CLU}}== |
|||
<syntaxhighlight lang="clu">% The population count of an integer is never going to be |
|||
% higher than the amount of bits in it (max 64) |
|||
% so we can get away with a very simple primality test. |
|||
is_prime = proc (n: int) returns (bool) |
|||
if n<=2 then return(n=2) end |
|||
if n//2=0 then return(false) end |
|||
for i: int in int$from_to_by(n+2, n/2, 2) do |
|||
if n//i=0 then return(false) end |
|||
end |
|||
return(true) |
|||
end is_prime |
|||
% Find the population count of a number |
|||
pop_count = proc (n: int) returns (int) |
|||
c: int := 0 |
|||
while n > 0 do |
|||
c := c + n // 2 |
|||
n := n / 2 |
|||
end |
|||
return(c) |
|||
end pop_count |
|||
% Is N pernicious? |
|||
pernicious = proc (n: int) returns (bool) |
|||
return(is_prime(pop_count(n))) |
|||
end pernicious |
|||
start_up = proc () |
|||
po: stream := stream$primary_output() |
|||
stream$putl(po, "First 25 pernicious numbers: ") |
|||
n: int := 1 |
|||
seen: int := 0 |
|||
while seen<25 do |
|||
if pernicious(n) then |
|||
stream$puts(po, int$unparse(n) || " ") |
|||
seen := seen + 1 |
|||
end |
|||
n := n + 1 |
|||
end |
|||
stream$putl(po, "\nPernicious numbers between 888,888,877 and 888,888,888:") |
|||
for i: int in int$from_to(888888877,888888888) do |
|||
if pernicious(i) then |
|||
stream$puts(po, int$unparse(i) || " ") |
|||
end |
|||
end |
|||
end start_up</syntaxhighlight> |
|||
{{out}} |
|||
<pre>First 25 pernicious numbers: |
|||
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
|||
Pernicious numbers between 888,888,877 and 888,888,888: |
|||
888888877 888888878 888888880 888888883 888888885 888888886</pre> |
|||
=={{header|COBOL}}== |
|||
<syntaxhighlight lang="cobol"> IDENTIFICATION DIVISION. |
|||
PROGRAM-ID. PERNICIOUS-NUMBERS. |
|||
DATA DIVISION. |
|||
WORKING-STORAGE SECTION. |
|||
01 VARIABLES. |
|||
03 AMOUNT PIC 99. |
|||
03 CAND PIC 9(9). |
|||
03 POPCOUNT PIC 99. |
|||
03 POP-N PIC 9(9). |
|||
03 FILLER REDEFINES POP-N. |
|||
05 FILLER PIC 9(8). |
|||
05 FILLER PIC 9. |
|||
88 ODD VALUES 1, 3, 5, 7, 9. |
|||
03 DSOR PIC 99. |
|||
03 DIV-RSLT PIC 99V99. |
|||
03 FILLER REDEFINES DIV-RSLT. |
|||
05 FILLER PIC 99. |
|||
05 FILLER PIC 99. |
|||
88 DIVISIBLE VALUE ZERO. |
|||
03 PRIME-FLAG PIC X. |
|||
88 PRIME VALUE '*'. |
|||
01 FORMAT. |
|||
03 SIZE-FLAG PIC X. |
|||
88 SMALL VALUE 'S'. |
|||
88 LARGE VALUE 'L'. |
|||
03 SMALL-NUM PIC ZZ9. |
|||
03 LARGE-NUM PIC Z(9)9. |
|||
03 OUT-STR PIC X(80). |
|||
03 OUT-PTR PIC 99. |
|||
PROCEDURE DIVISION. |
|||
BEGIN. |
|||
PERFORM SMALL-PERNICIOUS. |
|||
PERFORM LARGE-PERNICIOUS. |
|||
STOP RUN. |
|||
INIT-OUTPUT-VARS. |
|||
MOVE ZERO TO AMOUNT. |
|||
MOVE 1 TO OUT-PTR. |
|||
MOVE SPACES TO OUT-STR. |
|||
SMALL-PERNICIOUS. |
|||
PERFORM INIT-OUTPUT-VARS. |
|||
MOVE 'S' TO SIZE-FLAG. |
|||
PERFORM ADD-PERNICIOUS |
|||
VARYING CAND FROM 1 BY 1 UNTIL AMOUNT IS EQUAL TO 25. |
|||
DISPLAY OUT-STR. |
|||
LARGE-PERNICIOUS. |
|||
PERFORM INIT-OUTPUT-VARS. |
|||
MOVE 'L' TO SIZE-FLAG. |
|||
PERFORM ADD-PERNICIOUS |
|||
VARYING CAND FROM 888888877 BY 1 |
|||
UNTIL CAND IS GREATER THAN 888888888. |
|||
DISPLAY OUT-STR. |
|||
ADD-NUM. |
|||
ADD 1 TO AMOUNT. |
|||
IF SMALL, |
|||
MOVE CAND TO SMALL-NUM, |
|||
STRING SMALL-NUM DELIMITED BY SIZE INTO OUT-STR |
|||
WITH POINTER OUT-PTR. |
|||
IF LARGE, |
|||
MOVE CAND TO LARGE-NUM, |
|||
STRING LARGE-NUM DELIMITED BY SIZE INTO OUT-STR |
|||
WITH POINTER OUT-PTR. |
|||
ADD-PERNICIOUS. |
|||
PERFORM FIND-POPCOUNT. |
|||
PERFORM CHECK-PRIME. |
|||
IF PRIME, PERFORM ADD-NUM. |
|||
FIND-POPCOUNT. |
|||
MOVE ZERO TO POPCOUNT. |
|||
MOVE CAND TO POP-N. |
|||
PERFORM COUNT-BIT UNTIL POP-N IS EQUAL TO ZERO. |
|||
COUNT-BIT. |
|||
IF ODD, ADD 1 TO POPCOUNT. |
|||
DIVIDE 2 INTO POP-N. |
|||
CHECK-PRIME. |
|||
IF POPCOUNT IS LESS THAN 2, |
|||
MOVE SPACE TO PRIME-FLAG |
|||
ELSE |
|||
MOVE '*' TO PRIME-FLAG. |
|||
PERFORM CHECK-DSOR VARYING DSOR FROM 2 BY 1 |
|||
UNTIL NOT PRIME OR DSOR IS NOT LESS THAN POPCOUNT. |
|||
CHECK-DSOR. |
|||
DIVIDE POPCOUNT BY DSOR GIVING DIV-RSLT. |
|||
IF DIVISIBLE, MOVE SPACE TO PRIME-FLAG.</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
|||
888888877 888888878 888888880 888888883 888888885 888888886</pre> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
Using <code>primep</code> from [[Primality_by_trial_division#Common_Lisp|Primality by trial division]] task. |
Using <code>primep</code> from [[Primality_by_trial_division#Common_Lisp|Primality by trial division]] task. |
||
< |
<syntaxhighlight lang="lisp">(format T "~{~a ~}~%" |
||
(loop for n = 1 then (1+ n) |
(loop for n = 1 then (1+ n) |
||
when (primep (logcount n)) |
when (primep (logcount n)) |
||
Line 618: | Line 1,205: | ||
(loop for n from 888888877 to 888888888 |
(loop for n from 888888877 to 888888888 |
||
when (primep (logcount n)) |
when (primep (logcount n)) |
||
collect n))</ |
collect n))</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
||
888888877 888888878 888888880 888888883 888888885 888888886</pre> |
|||
=={{header|Cowgol}}== |
|||
<syntaxhighlight lang="cowgol">include "cowgol.coh"; |
|||
sub prime(n: uint8): (r: uint8) is |
|||
if n<2 then |
|||
r := 0; |
|||
return; |
|||
end if; |
|||
r := 1; |
|||
var d: uint8 := 2; |
|||
while d*d <= n loop |
|||
if n%d == 0 then |
|||
r := 0; |
|||
return; |
|||
end if; |
|||
d := d + 1; |
|||
end loop; |
|||
end sub; |
|||
sub popcount(n: uint32): (count: uint8) is |
|||
count := 0; |
|||
while n > 0 loop |
|||
count := count + (n as uint8 & 1); |
|||
n := n >> 1; |
|||
end loop; |
|||
end sub; |
|||
sub pernicious(n: uint32): (r: uint8) is |
|||
r := prime(popcount(n)); |
|||
end sub; |
|||
var candidate: uint32 := 0; |
|||
var seen: uint8 := 0; |
|||
while seen < 25 loop |
|||
candidate := candidate + 1; |
|||
if pernicious(candidate) != 0 then |
|||
print_i32(candidate); |
|||
print_char(' '); |
|||
seen := seen + 1; |
|||
end if; |
|||
end loop; |
|||
print_nl(); |
|||
candidate := 888888877; |
|||
while candidate < 888888888 loop |
|||
if pernicious(candidate) != 0 then |
|||
print_i32(candidate); |
|||
print_char(' '); |
|||
end if; |
|||
candidate := candidate + 1; |
|||
end loop; |
|||
print_nl();</syntaxhighlight> |
|||
{{out}} |
|||
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
|||
888888877 888888878 888888880 888888883 888888885 888888886</pre> |
888888877 888888878 888888880 888888883 888888885 888888886</pre> |
||
=={{header|D}}== |
=={{header|D}}== |
||
< |
<syntaxhighlight lang="d">void main() { |
||
import std.stdio, std.algorithm, std.range, core.bitop; |
import std.stdio, std.algorithm, std.range, core.bitop; |
||
Line 631: | Line 1,276: | ||
uint.max.iota.filter!pernicious.take(25).writeln; |
uint.max.iota.filter!pernicious.take(25).writeln; |
||
iota(888_888_877, 888_888_889).filter!pernicious.writeln; |
iota(888_888_877, 888_888_889).filter!pernicious.writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] |
<pre>[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] |
||
Line 639: | Line 1,284: | ||
This high-level code is fast enough to allow to count all the |
This high-level code is fast enough to allow to count all the |
||
1_421_120_880 Pernicious numbers in the unsigned 32 bit range in less than 48 seconds with this line: |
1_421_120_880 Pernicious numbers in the unsigned 32 bit range in less than 48 seconds with this line: |
||
< |
<syntaxhighlight lang="d">uint.max.iota.filter!pernicious.walkLength.writeln;</syntaxhighlight> |
||
=={{header|EasyLang}}== |
|||
<syntaxhighlight> |
|||
fastfunc isprim num . |
|||
if num < 2 |
|||
return 0 |
|||
. |
|||
i = 2 |
|||
while i <= sqrt num |
|||
if num mod i = 0 |
|||
return 0 |
|||
. |
|||
i += 1 |
|||
. |
|||
return 1 |
|||
. |
|||
func popc n . |
|||
while n > 0 |
|||
r += n mod 2 |
|||
n = n div 2 |
|||
. |
|||
return r |
|||
. |
|||
n = 1 |
|||
while cnt < 25 |
|||
if isprim popc n = 1 |
|||
write n & " " |
|||
cnt += 1 |
|||
. |
|||
n += 1 |
|||
. |
|||
print "" |
|||
n = 1 |
|||
for n = 888888877 to 888888888 |
|||
if isprim popc n = 1 |
|||
write n & " " |
|||
. |
|||
. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
|||
888888877 888888878 888888880 888888883 888888885 888888886 |
|||
</pre> |
|||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
< |
<syntaxhighlight lang="scheme"> |
||
(lib 'sequences) |
(lib 'sequences) |
||
Line 653: | Line 1,344: | ||
(take (filter pernicious? [888888877 .. 888888889]) #:all) |
(take (filter pernicious? [888888877 .. 888888889]) #:all) |
||
→ (888888877 888888878 888888880 888888883 888888885 888888886) |
→ (888888877 888888878 888888880 888888883 888888885 888888886) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Eiffel}}== |
=={{header|Eiffel}}== |
||
<syntaxhighlight lang="eiffel"> |
|||
<lang Eiffel> |
|||
class |
class |
||
APPLICATION |
APPLICATION |
||
Line 757: | Line 1,448: | ||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 765: | Line 1,456: | ||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
<syntaxhighlight lang="elixir"> |
|||
<lang Elixir> |
|||
defmodule SieveofEratosthenes do |
defmodule SieveofEratosthenes do |
||
def init(lim) do |
def init(lim) do |
||
Line 807: | Line 1,498: | ||
def pernicious?(n,primes), do: Enum.member?(primes,ones(n)) |
def pernicious?(n,primes), do: Enum.member?(primes,ones(n)) |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
<syntaxhighlight lang="elixir"> |
|||
<lang Elixir> |
|||
PerniciousNumbers.take(25) |
PerniciousNumbers.take(25) |
||
PerniciousNumbers.between(888_888_877..888_888_888) |
PerniciousNumbers.between(888_888_877..888_888_888) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 819: | Line 1,510: | ||
=={{header|F#|F sharp}}== |
=={{header|F#|F sharp}}== |
||
< |
<syntaxhighlight lang="fsharp">open System |
||
//Taken from https://gist.github.com/rmunn/bc49d32a586cdfa5bcab1c3e7b45d7ac |
//Taken from https://gist.github.com/rmunn/bc49d32a586cdfa5bcab1c3e7b45d7ac |
||
Line 840: | Line 1,531: | ||
[1 .. 100] |> Seq.filter (bitcount >> isPrime) |> Seq.take 25 |> Seq.toList |> printfn "%A" |
[1 .. 100] |> Seq.filter (bitcount >> isPrime) |> Seq.take 25 |> Seq.toList |> printfn "%A" |
||
[888888877 .. 888888888] |> Seq.filter (bitcount >> isPrime) |> Seq.toList |> printfn "%A" |
[888888877 .. 888888888] |> Seq.filter (bitcount >> isPrime) |> Seq.toList |> printfn "%A" |
||
0 // return an integer exit code</ |
0 // return an integer exit code</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[3; 5; 6; 7; 9; 10; 11; 12; 13; 14; 17; 18; 19; 20; 21; 22; 24; 25; 26; 28; 31; 33; 34; 35; 36] |
<pre>[3; 5; 6; 7; 9; 10; 11; 12; 13; 14; 17; 18; 19; 20; 21; 22; 24; 25; 26; 28; 31; 33; 34; 35; 36] |
||
Line 846: | Line 1,537: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: lists lists.lazy math.bitwise math.primes math.ranges |
||
prettyprint sequences ; |
prettyprint sequences ; |
||
Line 852: | Line 1,543: | ||
25 0 lfrom [ pernicious? ] lfilter ltake list>array . ! print first 25 pernicious numbers |
25 0 lfrom [ pernicious? ] lfilter ltake list>array . ! print first 25 pernicious numbers |
||
888,888,877 888,888,888 [a,b] [ pernicious? ] filter . ! print pernicious numbers in range</ |
888,888,877 888,888,888 [a,b] [ pernicious? ] filter . ! print pernicious numbers in range</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
{ 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 } |
{ 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 } |
||
{ 888888877 888888878 888888880 888888883 888888885 888888886 } |
{ 888888877 888888878 888888880 888888883 888888885 888888886 } |
||
</pre> |
|||
=={{header|Forth}}== |
|||
{{works with|Gforth}} |
|||
<syntaxhighlight lang="forth">: popcount { n -- u } |
|||
0 |
|||
begin |
|||
n 0<> |
|||
while |
|||
n n 1- and to n |
|||
1+ |
|||
repeat ; |
|||
\ primality test for 0 <= n <= 63 |
|||
: prime? ( n -- ? ) |
|||
1 swap lshift 0x28208a20a08a28ac and 0<> ; |
|||
: pernicious? ( n -- ? ) |
|||
popcount prime? ; |
|||
: first_n_pernicious_numbers { n -- } |
|||
." First " n . ." pernicious numbers:" cr |
|||
1 |
|||
begin |
|||
n 0 > |
|||
while |
|||
dup pernicious? if |
|||
dup . |
|||
n 1- to n |
|||
then |
|||
1+ |
|||
repeat |
|||
drop cr ; |
|||
: pernicious_numbers_between { m n -- } |
|||
." Pernicious numbers between " m . ." and " n 1 .r ." :" cr |
|||
n 1+ m do |
|||
i pernicious? if i . then |
|||
loop |
|||
cr ; |
|||
25 first_n_pernicious_numbers |
|||
888888877 888888888 pernicious_numbers_between |
|||
bye</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 25 pernicious numbers: |
|||
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
|||
Pernicious numbers between 888888877 and 888888888: |
|||
888888877 888888878 888888880 888888883 888888885 888888886 |
|||
</pre> |
</pre> |
||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
{{works with|Fortran|95 and later}} |
{{works with|Fortran|95 and later}} |
||
< |
<syntaxhighlight lang="fortran">program pernicious |
||
implicit none |
implicit none |
||
Line 915: | Line 1,658: | ||
end if |
end if |
||
end function |
end function |
||
end program</ |
end program</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
||
Line 922: | Line 1,665: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
{{trans|PureBasic}} |
{{trans|PureBasic}} |
||
< |
<syntaxhighlight lang="freebasic"> |
||
' FreeBASIC v1.05.0 win64 |
' FreeBASIC v1.05.0 win64 |
||
Line 980: | Line 1,723: | ||
Sleep |
Sleep |
||
End |
End |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 992: | Line 1,735: | ||
888888877 888888878 888888880 888888883 888888885 888888886 |
888888877 888888878 888888880 888888883 888888885 888888886 |
||
</pre> |
</pre> |
||
=={{header|Frink}}== |
|||
<syntaxhighlight lang="frink">isPernicious = {|x| |
|||
bits = countToDict[integerDigits[x,2]].get[1,0] |
|||
return bits > 1 and isPrime[bits] |
|||
} |
|||
println["First 25: " + first[select[count[1], isPernicious], 25]] |
|||
println[select[888_888_877 to 888_888_888, isPernicious]]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 25: [3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] |
|||
[888888877, 888888878, 888888880, 888888883, 888888885, 888888886] |
|||
</pre> |
|||
=={{header|Fōrmulæ}}== |
|||
{{FormulaeEntry|page=https://formulae.org/?script=examples/Pernicious_numbers}} |
|||
'''Solution''' |
|||
[[File:Fōrmulæ - Pernicious numbers 01.png]] |
|||
'''Case 1. Display the first 25 pernicious numbers (in decimal)''' |
|||
[[File:Fōrmulæ - Pernicious numbers 02.png]] |
|||
[[File:Fōrmulæ - Pernicious numbers 03.png]] |
|||
'''Case 2. display all pernicious numbers between 888,888,877 and 888,888,888 (inclusive).''' |
|||
[[File:Fōrmulæ - Pernicious numbers 04.png]] |
|||
[[File:Fōrmulæ - Pernicious numbers 05.png]] |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 1,026: | Line 1,803: | ||
} |
} |
||
fmt.Println() |
fmt.Println() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,034: | Line 1,811: | ||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
<syntaxhighlight lang="groovy"> |
|||
<lang Groovy> |
|||
class example{ |
class example{ |
||
static void main(String[] args){ |
static void main(String[] args){ |
||
Line 1,059: | Line 1,836: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,067: | Line 1,844: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">module Pernicious |
||
where |
where |
||
Line 1,083: | Line 1,860: | ||
solution1 = take 25 $ filter isPernicious [1 ..] |
solution1 = take 25 $ filter isPernicious [1 ..] |
||
solution2 = filter isPernicious [888888877 .. 888888888]</ |
solution2 = filter isPernicious [888888877 .. 888888888]</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
<pre>[3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36] |
<pre>[3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36] |
||
Line 1,090: | Line 1,867: | ||
Or, in a point-free and applicative style, using unfoldr for the population count: |
Or, in a point-free and applicative style, using unfoldr for the population count: |
||
< |
<syntaxhighlight lang="haskell">import Data.Numbers.Primes (isPrime) |
||
import Data.List (unfoldr) |
import Data.List (unfoldr) |
||
import Data.Tuple (swap) |
import Data.Tuple (swap) |
||
Line 1,108: | Line 1,885: | ||
[ take 25 $ filter isPernicious [1 ..] |
[ take 25 $ filter isPernicious [1 ..] |
||
, filter isPernicious [888888877 .. 888888888] |
, filter isPernicious [888888877 .. 888888888] |
||
]</ |
]</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>[3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36] |
<pre>[3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36] |
||
Line 1,114: | Line 1,891: | ||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
Works in both languages: |
Works in both languages: |
||
< |
<syntaxhighlight lang="unicon">link "factors" |
||
procedure main(A) |
procedure main(A) |
||
Line 1,131: | Line 1,907: | ||
while n > 0 do c +:= 1(n%2, n/:=2) |
while n > 0 do c +:= 1(n%2, n/:=2) |
||
return c |
return c |
||
end</ |
end</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 1,142: | Line 1,918: | ||
=={{header|J}}== |
=={{header|J}}== |
||
Implementation: |
Implementation: |
||
< |
<syntaxhighlight lang="j">ispernicious=: 1 p: +/"1@#:</syntaxhighlight> |
||
Task (thru taken from the [[Loops/Downward_for#J|Loops/Downward for]] task).: |
Task (thru taken from the [[Loops/Downward_for#J|Loops/Downward for]] task).: |
||
< |
<syntaxhighlight lang="j"> 25{.I.ispernicious i.100 |
||
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
||
thru=: <. + i.@(+*)@-~ |
thru=: <. + i.@(+*)@-~ |
||
(#~ ispernicious) 888888877 thru 888888888 |
|||
888888877 888888878 888888880 888888883 888888885 888888886</ |
888888877 888888878 888888880 888888883 888888885 888888886</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java">public class Pernicious{ |
||
//very simple isPrime since x will be <= Long.SIZE |
//very simple isPrime since x will be <= Long.SIZE |
||
public static boolean isPrime(int x){ |
public static boolean isPrime(int x){ |
||
Line 1,185: | Line 1,960: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
||
Line 1,193: | Line 1,968: | ||
{{works with|jq|1.4}} |
{{works with|jq|1.4}} |
||
The most interesting detail in the following is perhaps the use of ''recurse/1'' to define the helper function ''bin'', which generates the binary bits. |
The most interesting detail in the following is perhaps the use of ''recurse/1'' to define the helper function ''bin'', which generates the binary bits. |
||
< |
<syntaxhighlight lang="jq"># is_prime is designed to work with jq 1.4 |
||
def is_prime: |
def is_prime: |
||
if . == 2 then true |
if . == 2 then true |
||
Line 1,229: | Line 2,004: | ||
; |
; |
||
task</ |
task</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
[3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36] |
[3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36] |
||
Line 1,236: | Line 2,011: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{works with|Julia|0.6}} |
{{works with|Julia|0.6}} |
||
<syntaxhighlight lang="julia">using Primes |
|||
<lang julia>using Primes |
|||
ispernicious(n::Integer) = isprime(count_ones(n)) |
ispernicious(n::Integer) = isprime(count_ones(n)) |
||
Line 1,252: | Line 2,026: | ||
println("First 25 pernicious numbers: ", join(perniciouses(25), ", ")) |
println("First 25 pernicious numbers: ", join(perniciouses(25), ", ")) |
||
println("Perniciouses in [888888877, 888888888]: ", join(perniciouses(888888877, 888888888), ", ")) </ |
println("Perniciouses in [888888877, 888888888]: ", join(perniciouses(888888877, 888888888), ", ")) </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,259: | Line 2,033: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.0.5-2 |
||
fun isPrime(n: Int): Boolean { |
fun isPrime(n: Int): Boolean { |
||
Line 1,305: | Line 2,079: | ||
if (isPernicious(i)) print("$i ") |
if (isPernicious(i)) print("$i ") |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,316: | Line 2,090: | ||
888888877 888888878 888888880 888888883 888888885 888888886 |
888888877 888888878 888888880 888888883 888888885 888888886 |
||
</pre> |
|||
=={{header|Ksh}}== |
|||
<syntaxhighlight lang="ksh"> |
|||
#!/bin/ksh |
|||
# Positive integer whose population count is a prime |
|||
# # Variables: |
|||
# |
|||
integer PNUM=25 MINN=888888877 MAXN=888888888 |
|||
# # Functions: |
|||
# |
|||
# # Function _dec2bin(n) - return binary representation of decimal n |
|||
# |
|||
function _dec2bin { |
|||
typeset _n ; integer _n=$1 |
|||
typeset _base ; integer _base=2 |
|||
typeset _q _r _buff ; integer _q _r |
|||
typeset -a _arr _barr |
|||
(( _q = _n / _base )) |
|||
(( _r = _n % _base )) |
|||
_arr+=( ${_r} ) |
|||
until (( _q == 0 )); do |
|||
_n=${_q} |
|||
(( _q = _n / _base )) |
|||
(( _r = _n % _base )) |
|||
_arr+=( ${_r} ) |
|||
done |
|||
_revarr _arr _barr |
|||
_buff=${_barr[@]} |
|||
echo ${_buff// /} |
|||
} |
|||
# # Function _revarr(arr, barr) - reverse arr into barr |
|||
# |
|||
function _revarr { |
|||
typeset _arr ; nameref _arr="$1" |
|||
typeset _barr ; nameref _barr="$2" |
|||
typeset _i ; integer _i |
|||
for ((_i=${#_arr[*]}-1; _i>=0; _i--)); do |
|||
_barr+=( ${_arr[_i]} ) |
|||
done |
|||
} |
|||
# # Function _isprime(n) return 1 for prime, 0 for not prime |
|||
# |
|||
function _isprime { |
|||
typeset _n ; integer _n=$1 |
|||
typeset _i ; integer _i |
|||
(( _n < 2 )) && return 0 |
|||
for (( _i=2 ; _i*_i<=_n ; _i++ )); do |
|||
(( ! ( _n % _i ) )) && return 0 |
|||
done |
|||
return 1 |
|||
} |
|||
# # Function _sumdigits(n) return sum of n's digits |
|||
# |
|||
function _sumdigits { |
|||
typeset _n ; _n=$1 |
|||
typeset _i _sum ; integer _i _sum=0 |
|||
for ((_i=0; _i<${#_n}; _i++)); do |
|||
(( _sum+=${_n:${_i}:1} )) |
|||
done |
|||
echo ${_sum} |
|||
} |
|||
###### |
|||
# main # |
|||
###### |
|||
integer i sbi n=3 cnt=0 |
|||
printf "First $PNUM Pernicious numbers:\n" |
|||
for ((n = cnt = 0; cnt < PNUM; n++)); do |
|||
bi=$(_dec2bin ${n}) # $n as Binary |
|||
sbi=${bi//0/} # Strip zeros (i.e. count ones) |
|||
_isprime ${#sbi} # One count prime? |
|||
(( $? )) && { printf "%4d " ${n} ; ((++cnt)) } |
|||
done |
|||
printf "\n\nPernicious numbers between %11,d and %11,d inclusive:\n" $MINN $MAXN |
|||
for ((i=MINN; i<=MAXN; i++)); do |
|||
bi=$(_dec2bin ${i}) |
|||
sbi=${bi//0/} |
|||
_isprime ${#sbi} |
|||
(( $? )) && printf "%12,d " ${i} |
|||
done |
|||
echo |
|||
</syntaxhighlight> |
|||
{{out}}<pre> |
|||
First 25 Pernicious numbers: |
|||
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
|||
Pernicious numbers between 888,888,877 and 888,888,888 inclusive: |
|||
888,888,877 888,888,878 888,888,880 888,888,883 888,888,885 888,888,886 |
|||
</pre> |
</pre> |
||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang="lua">-- Test primality by trial division |
||
function isPrime (x) |
function isPrime (x) |
||
if x < 2 then return false end |
if x < 2 then return false end |
||
Line 1,371: | Line 2,247: | ||
-- Main procedure |
-- Main procedure |
||
pernicious(25) |
pernicious(25) |
||
pernicious(888888877, 888888888)</ |
pernicious(888888877, 888888888)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
||
Line 1,377: | Line 2,253: | ||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
< |
<syntaxhighlight lang="maple">ispernicious := proc(n::posint) |
||
return evalb(isprime(rhs(Statistics:-Tally(StringTools:-Explode(convert(convert(n, binary), string)))[-1]))); |
return evalb(isprime(rhs(Statistics:-Tally(StringTools:-Explode(convert(convert(n, binary), string)))[-1]))); |
||
end proc; |
end proc; |
||
Line 1,403: | Line 2,279: | ||
end do; |
end do; |
||
return list_num; |
return list_num; |
||
end proc:</ |
end proc:</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] |
<pre>[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] |
||
Line 1,409: | Line 2,285: | ||
</pre> |
</pre> |
||
=={{header|Mathematica}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">popcount[n_Integer] := IntegerDigits[n, 2] // Total |
||
perniciousQ[n_Integer] := popcount[n] // PrimeQ |
perniciousQ[n_Integer] := popcount[n] // PrimeQ |
||
perniciouscount = 0; |
perniciouscount = 0; |
||
Line 1,426: | Line 2,302: | ||
, {i, 888888877, 888888888}] |
, {i, 888888877, 888888888}] |
||
Print["Pernicious numbers between 888,888,877 and 888,888,888 (inclusive)"] |
Print["Pernicious numbers between 888,888,877 and 888,888,888 (inclusive)"] |
||
perniciouslist2</ |
perniciouslist2</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>first 25 pernicious numbers |
<pre>first 25 pernicious numbers |
||
Line 1,435: | Line 2,311: | ||
===Alternate Code=== |
===Alternate Code=== |
||
test function |
test function |
||
< |
<syntaxhighlight lang="mathematica">perniciousQ[n_Integer] := PrimeQ@Total@IntegerDigits[n, 2]</syntaxhighlight> |
||
First 25 pernicious numbers |
First 25 pernicious numbers |
||
< |
<syntaxhighlight lang="mathematica">n = 0; NestWhile[Flatten@{#, If[perniciousQ[++n], n, {}]} &, {}, Length@# < 25 &]</syntaxhighlight> |
||
Pernicious numbers betweeen 888888877 and 888888888 inclusive |
Pernicious numbers betweeen 888888877 and 888888888 inclusive |
||
< |
<syntaxhighlight lang="mathematica">Cases[Range[888888877, 888888888], _?(perniciousQ@# &)]</syntaxhighlight> |
||
=={{header|Miranda}}== |
|||
<syntaxhighlight lang="miranda">main :: [sys_message] |
|||
main = [Stdout (lay (map show [first25, large]))] |
|||
first25 :: [num] |
|||
first25 = take 25 (filter pernicious [1..]) |
|||
large :: [num] |
|||
large = filter pernicious [888888877..888888888] |
|||
pernicious :: num->bool |
|||
pernicious = prime . popcount |
|||
popcount :: num->num |
|||
popcount 0 = 0 |
|||
popcount n = n mod 2 + popcount (n div 2) |
|||
prime :: num->bool |
|||
prime n = n >= 2 & and [n mod d ~= 0 | d<-[2..sqrt n]] |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36] |
|||
[888888877,888888878,888888880,888888883,888888885,888888886]</pre> |
|||
=={{header|Modula-2}}== |
=={{header|Modula-2}}== |
||
< |
<syntaxhighlight lang="modula2">MODULE Pernicious; |
||
FROM FormatString IMPORT FormatString; |
FROM FormatString IMPORT FormatString; |
||
FROM Terminal IMPORT WriteString,WriteLn,ReadChar; |
FROM Terminal IMPORT WriteString,WriteLn,ReadChar; |
||
Line 1,491: | Line 2,391: | ||
ReadChar |
ReadChar |
||
END Pernicious.</ |
END Pernicious.</syntaxhighlight> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="nim">import strutils |
||
proc count(s: string; sub: char): int = |
proc count(s: string; sub: char): int = |
||
Line 1,524: | Line 2,424: | ||
inc i |
inc i |
||
echo p</ |
echo p</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>@[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] |
<pre>@[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] |
||
@[888888877, 888888878, 888888880, 888888883, 888888885, 888888886]</pre> |
@[888888877, 888888878, 888888880, 888888883, 888888885, 888888886]</pre> |
||
=={{header|OCaml}}== |
|||
<syntaxhighlight lang="ocaml">let rec popcount n = |
|||
if n = 0 then 0 else succ (popcount (n land pred n)) |
|||
let is_prime n = |
|||
let rec test d = d * d > n || n mod d <> 0 && test (d + 2) in |
|||
if n < 3 then n = 2 else n land 1 <> 0 && test 3 |
|||
let is_pernicious n = |
|||
is_prime (popcount n) |
|||
let () = |
|||
Seq.ints 0 |> Seq.filter is_pernicious |> Seq.take 25 |
|||
|> Seq.iter (Printf.printf " %u") |> print_newline |
|||
and () = |
|||
Seq.ints 888888877 |> Seq.take 12 |> Seq.filter is_pernicious |
|||
|> Seq.iter (Printf.printf " %u") |> print_newline</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
|||
888888877 888888878 888888880 888888883 888888885 888888886</pre> |
|||
=={{header|Panda}}== |
=={{header|Panda}}== |
||
< |
<syntaxhighlight lang="panda">fun prime(a) type integer->integer |
||
a where count{{a.factor}}==2 |
a where count{{a.factor}}==2 |
||
fun pernisc(a) type integer->integer |
fun pernisc(a) type integer->integer |
||
Line 1,536: | Line 2,457: | ||
1..36.pernisc |
1..36.pernisc |
||
888888877..888888888.pernisc</ |
888888877..888888888.pernisc</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,543: | Line 2,464: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp">pern(n)=isprime(hammingweight(n)) |
||
select(pern, [1..36]) |
select(pern, [1..36]) |
||
select(pern,[888888877..888888888])</ |
select(pern,[888888877..888888888])</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>%1 = [3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] |
<pre>%1 = [3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] |
||
Line 1,555: | Line 2,476: | ||
Added easy counting of pernicious numbers for full Bit ranges like 32-Bit |
Added easy counting of pernicious numbers for full Bit ranges like 32-Bit |
||
< |
<syntaxhighlight lang="pascal">program pernicious; |
||
{$IFDEF FPC} |
{$IFDEF FPC} |
||
{$OPTIMIZATION ON,Regvar,ASMCSE,CSE,PEEPHOLE}// 3x speed up |
{$OPTIMIZATION ON,Regvar,ASMCSE,CSE,PEEPHOLE}// 3x speed up |
||
Line 1,638: | Line 2,559: | ||
inc(k,k); |
inc(k,k); |
||
until k>64; |
until k>64; |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,653: | Line 2,574: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="perl">sub is_pernicious { |
||
my $n = shift; |
my $n = shift; |
||
my $c = 2693408940; # primes < 32 as set bits |
my $c = 2693408940; # primes < 32 as set bits |
||
Line 1,674: | Line 2,595: | ||
} |
} |
||
print join ' ', @p;</ |
print join ' ', @p;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
||
Line 1,681: | Line 2,602: | ||
Alternately, generating the same output using a method similar to Pari/GP: |
Alternately, generating the same output using a method similar to Pari/GP: |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use ntheory qw/is_prime hammingweight/; |
||
my $i = 1; |
my $i = 1; |
||
my @pern = map { $i++ while !is_prime(hammingweight($i)); $i++; } 1..25; |
my @pern = map { $i++ while !is_prime(hammingweight($i)); $i++; } 1..25; |
||
print "@pern\n"; |
print "@pern\n"; |
||
print join(" ", grep { is_prime(hammingweight($_)) } 888888877 .. 888888888), "\n";</ |
print join(" ", grep { is_prime(hammingweight($_)) } 888888877 .. 888888888), "\n";</syntaxhighlight> |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>function pernicious(integer n) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
return is_prime(sum(int_to_bits(n,32))) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">pernicious</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">int_to_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">32</span><span style="color: #0000FF;">)))</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
sequence s = {} |
|||
integer n = 1 |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
while length(s)<25 do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
if pernicious(n) then |
|||
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">25</span> <span style="color: #008080;">do</span> |
|||
s &= n |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">pernicious</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">n</span> |
|||
n += 1 |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end while |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
?s |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
s = {} |
|||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
for i=888_888_877 to 888_888_888 do |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
if pernicious(i) then |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">888_888_877</span> <span style="color: #008080;">to</span> <span style="color: #000000;">888_888_888</span> <span style="color: #008080;">do</span> |
|||
s &= i |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">pernicious</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">i</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
?s</lang> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,713: | Line 2,637: | ||
{888888877,888888878,888888880,888888883,888888885,888888886} |
{888888877,888888878,888888880,888888883,888888885,888888886} |
||
</pre> |
</pre> |
||
=={{header|Picat}}== |
|||
<syntaxhighlight lang="picat">go => |
|||
println(take_n(pernicious_number,25,1)), |
|||
println([J : J in 888888877..888888888, pernicious_number(J)]), |
|||
nl. |
|||
% Get the first N numbers that satisfies function F, starting with S |
|||
take_n(F,N,S) = L => |
|||
I = S, |
|||
C = 0, |
|||
L = [], |
|||
while(C < N) |
|||
if call(F,I) then |
|||
L := L ++ [I], |
|||
C := C + 1 |
|||
end, |
|||
I := I + 1 |
|||
end. |
|||
pop_count(N) = sum([1: I in N.to_binary_string(), I = '1']). |
|||
pernicious_number(N) => prime(pop_count(N)).</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36] |
|||
[888888877,888888878,888888880,888888883,888888885,888888886]</pre> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
Using 'prime?' from [[Primality by trial division#PicoLisp]]. |
Using 'prime?' from [[Primality by trial division#PicoLisp]]. |
||
< |
<syntaxhighlight lang="picolisp">(de pernicious? (N) |
||
(prime? (cnt = (chop (bin N)) '("1" .))) )</ |
(prime? (cnt = (chop (bin N)) '("1" .))) )</syntaxhighlight> |
||
Test: |
Test: |
||
< |
<syntaxhighlight lang="picolisp">: (let N 0 |
||
(do 25 |
(do 25 |
||
(until (pernicious? (inc 'N))) |
(until (pernicious? (inc 'N))) |
||
Line 1,726: | Line 2,678: | ||
: (filter pernicious? (range 888888877 888888888)) |
: (filter pernicious? (range 888888877 888888888)) |
||
-> (888888877 888888878 888888880 888888883 888888885 888888886)</ |
-> (888888877 888888878 888888880 888888883 888888885 888888886)</syntaxhighlight> |
||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
<syntaxhighlight lang="pl/i"> |
|||
<lang PL/I> |
|||
pern: procedure options (main); |
pern: procedure options (main); |
||
declare (i, n) fixed binary (31); |
declare (i, n) fixed binary (31); |
||
Line 1,758: | Line 2,710: | ||
end pern; |
end pern; |
||
</syntaxhighlight> |
|||
</lang> |
|||
Results: |
Results: |
||
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
||
Line 1,765: | Line 2,717: | ||
=={{header|Plain English}}== |
=={{header|Plain English}}== |
||
< |
<syntaxhighlight lang="plainenglish">To decide if a number is pernicious: |
||
Find a population count of the number. |
Find a population count of the number. |
||
If the population count is prime, say yes. |
If the population count is prime, say yes. |
||
Line 1,804: | Line 2,756: | ||
If the number is past the other number, exit. |
If the number is past the other number, exit. |
||
If the number is pernicious, show the number. |
If the number is pernicious, show the number. |
||
Repeat.</ |
Repeat.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,812: | Line 2,764: | ||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
function pop-count($n) { |
function pop-count($n) { |
||
(([Convert]::ToString($n, 2)).toCharArray() | where {$_ -eq '1'}).count |
(([Convert]::ToString($n, 2)).toCharArray() | where {$_ -eq '1'}).count |
||
Line 1,841: | Line 2,793: | ||
"pernicious numbers between 888,888,877 and 888,888,888" |
"pernicious numbers between 888,888,877 and 888,888,888" |
||
"$(888888877..888888888 | where{isprime(pop-count $_)})" |
"$(888888877..888888888 | where{isprime(pop-count $_)})" |
||
</syntaxhighlight> |
|||
</lang> |
|||
<b>Output:</b> |
<b>Output:</b> |
||
<pre> |
<pre> |
||
Line 1,855: | Line 2,807: | ||
The '''PopCount''' property is available in each of the returned integers. |
The '''PopCount''' property is available in each of the returned integers. |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
function Select-PerniciousNumber |
function Select-PerniciousNumber |
||
{ |
{ |
||
Line 1,900: | Line 2,852: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
$start, $end = 0, 999999 |
$start, $end = 0, 999999 |
||
$range1 = $start..$end | Select-PerniciousNumber | Select-Object -First 25 |
$range1 = $start..$end | Select-PerniciousNumber | Select-Object -First 25 |
||
Line 1,911: | Line 2,863: | ||
"Pernicious numbers between {0} and {1}:`n{2}`n" -f $start, $end, ($range2 -join ", ") |
"Pernicious numbers between {0} and {1}:`n{2}`n" -f $start, $end, ($range2 -join ", ") |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 1,922: | Line 2,874: | ||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
<syntaxhighlight lang="purebasic"> |
|||
<lang PureBasic> |
|||
EnableExplicit |
EnableExplicit |
||
Line 1,984: | Line 2,936: | ||
CloseConsole() |
CloseConsole() |
||
EndIf |
EndIf |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,999: | Line 2,951: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Procedural=== |
===Procedural=== |
||
< |
<syntaxhighlight lang="python">>>> def popcount(n): return bin(n).count("1") |
||
>>> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61} |
>>> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61} |
||
Line 2,018: | Line 2,970: | ||
>>> p |
>>> p |
||
[888888877, 888888878, 888888880, 888888883, 888888885, 888888886] |
[888888877, 888888878, 888888880, 888888883, 888888885, 888888886] |
||
>>> </ |
>>> </syntaxhighlight> |
||
===Functional=== |
===Functional=== |
||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
< |
<syntaxhighlight lang="python">'''Pernicious numbers''' |
||
from itertools import count, islice |
from itertools import count, islice |
||
Line 2,049: | Line 3,001: | ||
''' |
''' |
||
def go(x): |
def go(x): |
||
return |
return divmod(x, 2) if 0 < x else None |
||
return sum(unfoldl(go)(n)) |
return sum(unfoldl(go)(n)) |
||
# |
# ------------------------- TEST ------------------------- |
||
# main :: IO () |
# main :: IO () |
||
def main(): |
def main(): |
||
Line 2,059: | Line 3,011: | ||
[888,888,877..888,888,888] |
[888,888,877..888,888,888] |
||
''' |
''' |
||
print( |
print( |
||
take(25)( |
take(25)( |
||
Line 2,065: | Line 3,018: | ||
) |
) |
||
print([ |
print([ |
||
x for x in enumFromTo(888888877)( |
x for x in enumFromTo(888888877)(888888888) |
||
if isPernicious(x) |
|||
) if isPernicious(x) |
|||
]) |
]) |
||
# |
# ----------------------- GENERIC ------------------------ |
||
# Just :: a -> Maybe a |
|||
def Just(x): |
|||
'''Constructor for an inhabited Maybe (option type) value. |
|||
Wrapper containing the result of a computation. |
|||
''' |
|||
return {'type': 'Maybe', 'Nothing': False, 'Just': x} |
|||
# Nothing :: Maybe a |
|||
def Nothing(): |
|||
'''Constructor for an empty Maybe (option type) value. |
|||
Empty wrapper returned where a computation is not possible. |
|||
''' |
|||
return {'type': 'Maybe', 'Nothing': True} |
|||
# enumFromTo :: Int -> Int -> [Int] |
# enumFromTo :: Int -> Int -> [Int] |
||
Line 2,093: | Line 3,029: | ||
'''Enumeration of integer values [m..n]''' |
'''Enumeration of integer values [m..n]''' |
||
def go(n): |
def go(n): |
||
return |
return range(m, 1 + n) |
||
return |
return go |
||
Line 2,130: | Line 3,066: | ||
# unfoldl :: (b -> Maybe (b, a)) -> b -> [a] |
# unfoldl :: (b -> Maybe (b, a)) -> b -> [a] |
||
def unfoldl(f): |
def unfoldl(f): |
||
'''A lazy (generator) list unfolded from a seed value |
|||
'''Dual to reduce or foldl. |
|||
by repeated application of f until no residue remains. |
|||
Dual to fold/reduce. |
|||
f returns either None or just (residue, value). |
|||
For a strict output list, wrap the result with list() |
|||
application of f. |
|||
When f returns Nothing, the completed list is returned. |
|||
''' |
''' |
||
def go(v): |
def go(v): |
||
residueValue = f(v) |
|||
while residueValue: |
|||
yield residueValue[1] |
|||
residueValue = f(residueValue[0]) |
|||
return go |
|||
if mb.get('Nothing'): |
|||
return xs |
|||
else: |
|||
x, r = mb.get('Just') |
|||
xs.insert(0, r) |
|||
return xs |
|||
return lambda x: go(x) |
|||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] |
<pre>[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] |
||
Line 2,160: | Line 3,088: | ||
=={{header|Quackery}}== |
=={{header|Quackery}}== |
||
<syntaxhighlight lang="quackery"> [ $ "rosetta/seive.qky" loadfile |
|||
<lang Quackery> [ $ "rosetta/seive.qky" loadfile |
|||
$ "rosetta/popcount.qky" loadfile ] now! |
$ "rosetta/popcount.qky" loadfile ] now! |
||
Line 2,183: | Line 3,110: | ||
25 echopopwith isprime cr |
25 echopopwith isprime cr |
||
888888877 888888888 perniciousrange cr</ |
888888877 888888888 perniciousrange cr</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,191: | Line 3,118: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
<syntaxhighlight lang="racket">#lang racket |
|||
<lang racket>#lang racket |
|||
(require math/number-theory rnrs/arithmetic/bitwise-6) |
(require math/number-theory rnrs/arithmetic/bitwise-6) |
||
Line 2,212: | Line 3,138: | ||
(module+ test |
(module+ test |
||
(require rackunit) |
(require rackunit) |
||
(check-true (pernicious? 22)))</ |
(check-true (pernicious? 22)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,225: | Line 3,151: | ||
Straightforward implementation using Raku's ''is-prime'' built-in subroutine. |
Straightforward implementation using Raku's ''is-prime'' built-in subroutine. |
||
<lang |
<syntaxhighlight lang="raku" line>sub is-pernicious(Int $n --> Bool) { |
||
is-prime [+] $n.base(2).comb; |
is-prime [+] $n.base(2).comb; |
||
} |
} |
||
say (grep &is-pernicious, 0 .. *)[^25]; |
say (grep &is-pernicious, 0 .. *)[^25]; |
||
say grep &is-pernicious, 888_888_877 .. 888_888_888;</ |
say grep &is-pernicious, 888_888_877 .. 888_888_888;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
||
Line 2,256: | Line 3,182: | ||
╚════════════════════════════════════════════════════════════════════════════════════════╝ |
╚════════════════════════════════════════════════════════════════════════════════════════╝ |
||
</pre> |
</pre> |
||
< |
<syntaxhighlight lang="rexx">/*REXX program computes and displays a number (and also a range) of pernicious numbers.*/ |
||
numeric digits 100 /*be able to handle large numbers. */ |
numeric digits 100 /*be able to handle large numbers. */ |
||
parse arg N L H . /*obtain optional arguments from the CL*/ |
parse arg N L H . /*obtain optional arguments from the CL*/ |
||
Line 2,287: | Line 3,213: | ||
return substr($, 2) /*return the results, sans 1st blank. */ |
return substr($, 2) /*return the results, sans 1st blank. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
popCount: return length( space( translate( x2b( d2x(arg(1))) +0,, 0), 0)) /*count 1's.*/</ |
popCount: return length( space( translate( x2b( d2x(arg(1))) +0,, 0), 0)) /*count 1's.*/</syntaxhighlight> |
||
'''output''' when the default inputs are used: |
'''output''' when the default inputs are used: |
||
<pre> |
<pre> |
||
Line 2,299: | Line 3,225: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
Programming note: as written, this program can't handle the large numbers required for the 2<sup>nd</sup> task requirement (it receives a '''Numeric Overflow'''). |
Programming note: as written, this program can't handle the large numbers required for the 2<sup>nd</sup> task requirement (it receives a '''Numeric Overflow'''). |
||
< |
<syntaxhighlight lang="ring"> |
||
# Project : Pernicious numbers |
# Project : Pernicious numbers |
||
Line 2,339: | Line 3,265: | ||
next |
next |
||
return 1 |
return 1 |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
The first 25 pernicious numbers: |
The first 25 pernicious numbers: |
||
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
||
</pre> |
|||
=={{header|RPL}}== |
|||
≪ '''IF''' DUP 5 ≤ '''THEN''' |
|||
{ 2 3 5 } SWAP POS |
|||
'''ELSE''' |
|||
'''IF''' DUP 2 MOD NOT '''THEN''' 2 |
|||
'''ELSE''' |
|||
DUP √ CEIL → lim |
|||
≪ 3 '''WHILE''' DUP2 MOD OVER lim ≤ AND '''REPEAT''' 2 + '''END''' |
|||
≫ |
|||
'''END''' MOD |
|||
'''END''' SIGN |
|||
≫ ''''PRIM?'''' STO |
|||
≪ |
|||
BIN R→B →STR 0 |
|||
1 3 PICK SIZE '''FOR''' j |
|||
'''IF''' OVER j DUP SUB "1" == '''THEN''' 1 + '''END NEXT''' |
|||
SWAP DROP '''PRIM?''' |
|||
≫ ´'''PERN?'''’ STO |
|||
≪ { } 1 '''WHILE''' OVER SIZE 25 < '''REPEAT IF''' DUP PERN? '''THEN''' SWAP OVER + SWAP '''END''' 1 + '''END''' DROP |
|||
≫ ´'''TASK1'''’ STO |
|||
≪ { } 888888877 888888888 '''FOR''' n '''IF''' n '''PERN? THEN''' n + '''END NEXT''' |
|||
≫ ´'''TASK2'''’ STO |
|||
{{out}} |
|||
<pre> |
|||
2: { 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 } |
|||
1: { 888888877 888888878 888888880 888888883 888888885 888888886 } |
|||
</pre> |
</pre> |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">require "prime" |
||
class Integer |
class Integer |
||
Line 2,362: | Line 3,319: | ||
p 1.step.lazy.select(&:pernicious?).take(25).to_a |
p 1.step.lazy.select(&:pernicious?).take(25).to_a |
||
p ( 888888877..888888888).select(&:pernicious?)</ |
p ( 888888877..888888888).select(&:pernicious?)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,370: | Line 3,327: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust"> |
||
extern crate aks_test_for_primes; |
extern crate aks_test_for_primes; |
||
Line 2,395: | Line 3,352: | ||
is_prime(n.count_ones()) |
is_prime(n.count_ones()) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,403: | Line 3,360: | ||
=={{header|S-lang}}== |
=={{header|S-lang}}== |
||
< |
<syntaxhighlight lang="s-lang">% Simplistic prime-test from prime-by-trial-division: |
||
define is_prime(n) |
define is_prime(n) |
||
{ |
{ |
||
Line 2,449: | Line 3,406: | ||
} |
} |
||
print(strjoin(list_to_array(plist), " ")); |
print(strjoin(list_to_array(plist), " ")); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
"3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36" |
"3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36" |
||
Line 2,456: | Line 3,413: | ||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight lang="scala">def isPernicious( v:Long ) : Boolean = BigInt(v.toBinaryString.toList.filter( _ == '1' ).length).isProbablePrime(16) |
||
// Generate the output |
// Generate the output |
||
Line 2,463: | Line 3,420: | ||
println( Stream.from(2).filter( isPernicious(_) ).take(a).toList.mkString(",") ) |
println( Stream.from(2).filter( isPernicious(_) ).take(a).toList.mkString(",") ) |
||
println( {for( i <- b1 to b2 if( isPernicious(i) ) ) yield i}.mkString(",") ) |
println( {for( i <- b1 to b2 if( isPernicious(i) ) ) yield i}.mkString(",") ) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36 |
<pre>3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36 |
||
Line 2,474: | Line 3,431: | ||
is used to compute the population count of the bitset. |
is used to compute the population count of the bitset. |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
const set of integer: primes is {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61}; |
const set of integer: primes is {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61}; |
||
Line 2,499: | Line 3,456: | ||
end for; |
end for; |
||
writeln; |
writeln; |
||
end func;</ |
end func;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,508: | Line 3,465: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func is_pernicious(n) { |
||
n.sumdigits(2).is_prime |
n.sumdigits(2).is_prime |
||
} |
} |
||
say is_pernicious.first(25).join(' ') |
say is_pernicious.first(25).join(' ') |
||
say is_pernicious.grep(888_888_877..888_888_888).join(' ')</ |
say is_pernicious.grep(888_888_877..888_888_888).join(' ')</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,522: | Line 3,479: | ||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
<syntaxhighlight lang="swift">import Foundation |
|||
<lang swift>import Foundation |
|||
extension BinaryInteger { |
extension BinaryInteger { |
||
Line 2,556: | Line 3,512: | ||
print("First 25 Pernicious numbers: \(Array(first25))") |
print("First 25 Pernicious numbers: \(Array(first25))") |
||
print("Pernicious numbers between 888_888_877...888_888_888: \(Array(rng))")</ |
print("Pernicious numbers between 888_888_877...888_888_888: \(Array(rng))")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,564: | Line 3,520: | ||
=={{header|Symsyn}}== |
=={{header|Symsyn}}== |
||
<syntaxhighlight lang="symsyn"> |
|||
<lang symsyn> |
|||
primes : 0b0010100000100000100010100010000010100000100010100010100010101100 |
primes : 0b0010100000100000100010100010000010100000100010100010100010101100 |
||
Line 2,642: | Line 3,597: | ||
return |
return |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 2,653: | Line 3,608: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
{{tcllib|math::numtheory}} |
{{tcllib|math::numtheory}} |
||
< |
<syntaxhighlight lang="tcl">package require math::numtheory |
||
proc pernicious {n} { |
proc pernicious {n} { |
||
Line 2,666: | Line 3,621: | ||
if {[pernicious $n]} {lappend p $n} |
if {[pernicious $n]} {lappend p $n} |
||
} |
} |
||
puts [join $p ","]</ |
puts [join $p ","]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,674: | Line 3,629: | ||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
{{trans|Phix}}< |
{{trans|Phix}}<syntaxhighlight lang="vb">Private Function population_count(ByVal number As Long) As Integer |
||
Dim result As Integer |
Dim result As Integer |
||
Dim digit As Integer |
Dim digit As Integer |
||
Line 2,722: | Line 3,677: | ||
End If |
End If |
||
Next n |
Next n |
||
End Sub</ |
End Sub</syntaxhighlight>{{out}} |
||
<pre> 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
<pre> 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
||
888888877 888888878 888888880 888888883 888888885 888888886 </pre> |
888888877 888888878 888888880 888888883 888888885 888888886 </pre> |
||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
< |
<syntaxhighlight lang="vb">'check if the number is pernicious |
||
Function IsPernicious(n) |
Function IsPernicious(n) |
||
IsPernicious = False |
IsPernicious = False |
||
Line 2,790: | Line 3,745: | ||
End If |
End If |
||
Next |
Next |
||
WScript.StdOut.WriteLine</ |
WScript.StdOut.WriteLine</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,803: | Line 3,758: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="vbnet">Module Module1 |
||
Function PopulationCount(n As Long) As Integer |
Function PopulationCount(n As Long) As Integer |
||
Line 2,847: | Line 3,802: | ||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
<pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
||
Line 2,854: | Line 3,809: | ||
=={{header|Wortel}}== |
=={{header|Wortel}}== |
||
The following function returns true if it's argument is a pernicious number: |
The following function returns true if it's argument is a pernicious number: |
||
< |
<syntaxhighlight lang="wortel">:ispernum ^(@isPrime \@count \=1 @arr &\`![.toString 2])</syntaxhighlight> |
||
Task: |
Task: |
||
< |
<syntaxhighlight lang="wortel">!-ispernum 1..36 ; returns [3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36] |
||
!-ispernum 888888877..888888888 ; returns [888888877 888888878 888888880 888888883 888888885 888888886]</ |
!-ispernum 888888877..888888888 ; returns [888888877 888888878 888888880 888888883 888888885 888888886]</syntaxhighlight> |
||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="wren">var pernicious = Fn.new { |w| |
||
var ff = 2.pow(32) - 1 |
var ff = 2.pow(32) - 1 |
||
var mask1 = (ff / 3).floor |
var mask1 = (ff / 3).floor |
||
Line 2,886: | Line 3,841: | ||
if (pernicious.call(n)) System.write("%(n) ") |
if (pernicious.call(n)) System.write("%(n) ") |
||
} |
} |
||
System.print()</ |
System.print()</syntaxhighlight> |
||
{{out}} |
|||
<pre> |
|||
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 |
|||
888888877 888888878 888888880 888888883 888888885 888888886 |
|||
</pre> |
|||
=={{header|XPL0}}== |
|||
<syntaxhighlight lang "XPL0">func IsPrime(N); \Return 'true' if N is prime |
|||
int N, D; |
|||
[if N <= 2 then return N = 2; |
|||
D:= 2; |
|||
while D*D <= N do |
|||
[if rem(N/D) = 0 then return false; |
|||
D:= D+1; |
|||
]; |
|||
return true; |
|||
]; |
|||
func BitCount(N); \Return number of set bits in N |
|||
int N, C; |
|||
[C:= 0; |
|||
while N do |
|||
[C:= C+1; |
|||
N:= N & N-1; |
|||
]; |
|||
return C; |
|||
]; |
|||
int N, C; |
|||
[N:= 0; C:= 0; |
|||
loop [if IsPrime(BitCount(N)) then |
|||
[IntOut(0, N); ChOut(0, ^ ); |
|||
C:= C+1; |
|||
if C >= 25 then quit; |
|||
]; |
|||
N:= N+1; |
|||
]; |
|||
CrLf(0); |
|||
for N:= 888_888_877 to 888_888_888 do |
|||
if IsPrime(BitCount(N)) then |
|||
[IntOut(0, N); ChOut(0, ^ )]; |
|||
CrLf(0); |
|||
]</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,896: | Line 3,894: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
The largest number of bits is 30. |
The largest number of bits is 30. |
||
< |
<syntaxhighlight lang="zkl">primes:=T(2,3,5,7,11,13,17,19,23,29,31,37,41); |
||
N:=0; foreach n in ([2..]){ |
N:=0; foreach n in ([2..]){ |
||
if(n.num1s : primes.holds(_)){ |
if(n.num1s : primes.holds(_)){ |
||
Line 2,905: | Line 3,903: | ||
foreach n in ([0d888888877..888888888]){ |
foreach n in ([0d888888877..888888888]){ |
||
if (n.num1s : primes.holds(_)) "%,d; ".fmt(n).print(); |
if (n.num1s : primes.holds(_)) "%,d; ".fmt(n).print(); |
||
}</ |
}</syntaxhighlight> |
||
Int.num1s returns the number of 1 bits. eg (3).num1s-->2 |
Int.num1s returns the number of 1 bits. eg (3).num1s-->2 |
||
{{out}} |
{{out}} |
||
Line 2,913: | Line 3,911: | ||
</pre> |
</pre> |
||
Or in a more functional style: |
Or in a more functional style: |
||
< |
<syntaxhighlight lang="zkl">primes:=T(2,3,5,7,11,13,17,19,23,29,31,37,41); |
||
p:='wrap(n){ primes.holds(n.num1s) }; |
p:='wrap(n){ primes.holds(n.num1s) }; |
||
[1..].filter(25,p).toString(*).println(); |
[1..].filter(25,p).toString(*).println(); |
||
[0d888888877..888888888].filter(p).println();</ |
[0d888888877..888888888].filter(p).println();</syntaxhighlight> |
||
'wrap is syntactic sugar for a closure - it creates a function that |
'wrap is syntactic sugar for a closure - it creates a function that |
||
wraps local data (variable primes in this case). We assign that function to p. |
wraps local data (variable primes in this case). We assign that function to p. |
Latest revision as of 19:19, 21 February 2024
You are encouraged to solve this task according to the task description, using any language you may know.
A pernicious number is a positive integer whose population count is a prime.
The population count is the number of ones in the binary representation of a non-negative integer.
- Example
22 (which is 10110 in binary) has a population count of 3, which is prime, and therefore
22 is a pernicious number.
- Task
- display the first 25 pernicious numbers (in decimal).
- display all pernicious numbers between 888,888,877 and 888,888,888 (inclusive).
- display each list of integers on one line (which may or may not include a title).
- See also
- Sequence A052294 pernicious numbers on The On-Line Encyclopedia of Integer Sequences.
- Rosetta Code entry population count, evil numbers, odious numbers.
11l
F is_prime(n)
I n < 2
R 0B
L(i) 2 .. Int(sqrt(n))
I n % i == 0
R 0B
R 1B
V i = 0
V cnt = 0
L
I is_prime(bits:popcount(i))
print(i, end' ‘ ’)
cnt++
I cnt == 25
L.break
i++
print()
L(i) 888888877..888888888
I is_prime(bits:popcount(i))
print(i, end' ‘ ’)
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
360 Assembly
For maximum compatibility, this program uses only the basic instruction set (S/360) with 2 ASSIST macros (XDECO,XPRNT).
* Pernicious numbers 04/05/2016
PERNIC CSECT
USING PERNIC,R13 base register and savearea pointer
SAVEAREA B STM-SAVEAREA(R15)
DC 17F'0'
STM STM R14,R12,12(R13) save registers
ST R13,4(R15) link backward SA
ST R15,8(R13) link forward SA
LR R13,R15 establish addressability
SR R7,R7 n=0
MVC PG,=CL80' ' clear buffer
LA R10,PG pgi
LA R6,1 i=1
LOOPI1 C R7,=F'25' do i=1 while(n<25)
BNL ELOOPI1
LR R1,R6 i
BAL R14,POPCOUNT
LR R1,R0 popcount(i)
BAL R14,ISPRIME
C R0,=F'1' if isprime(popcount(i))=1
BNE NOTPRIM1
XDECO R6,XDEC edit i
MVC 0(3,R10),XDEC+9 output i format I3
LA R10,3(R10) pgi=pgi+3
LA R7,1(R7) n=n+1
NOTPRIM1 LA R6,1(R6) i=i+1
B LOOPI1
ELOOPI1 XPRNT PG,80 print buffer
MVC PG,=CL80' ' clear buffer
LA R10,PG pgi
L R6,=F'888888877' i=888888877
LOOPI2 C R6,=F'888888888' do i to 888888888
BH ELOOPI2
LR R1,R6 i
BAL R14,POPCOUNT
LR R1,R0 popcount(i)
BAL R14,ISPRIME
C R0,=F'1' if isprime(popcount(i))=1
BNE NOTPRIM2
XDECO R6,XDEC edit i
MVC 0(10,R10),XDEC+2 output i format I10
LA R10,10(R10) pgi=pgi+10
NOTPRIM2 LA R6,1(R6) i=i+1
B LOOPI2
ELOOPI2 XPRNT PG,80 print buffer
L R13,4(0,R13) restore savearea pointer
LM R14,R12,12(R13) restore registers
XR R15,R15 return code = 0
BR R14 -------------- end main
POPCOUNT CNOP 0,4 -------------- popcount(xx) [R8,R11]
ST R14,POPCOUSA save return address
ST R1,XX store argument
SR R11,R11 rr=0
SR R8,R8 ii=0
LOOPII C R8,=F'31' do ii=0 to 31
BH ELOOPII
L R1,XX xx
LR R2,R8 ii
BAL R14,BTEST
C R0,=F'1' if btest(xx,ii)=1
BNE NOTBTEST
LA R11,1(R11) rr=rr+1
NOTBTEST LA R8,1(R8) ii=ii+1
B LOOPII
ELOOPII LR R0,R11 return(rr)
L R14,POPCOUSA
BR R14 -------------- end popcount
ISPRIME CNOP 0,4 -------------- isprime(number) [R9]
ST R14,ISPRIMSA save return address
ST R1,NUMBER store argument
C R1,=F'2' if number=2
BNE ELSE1
MVC ISPRIMEX,=F'1' isprimex=1
B ELOOPJJ
ELSE1 L R1,NUMBER
C R1,=F'2' if number<2
BL EVEN
L R4,NUMBER
SRDA R4,32
D R4,=F'2' mod(number,2)
C R4,=F'0' if mod(number,2)=0
BNE ELSE2
EVEN MVC ISPRIMEX,=F'0' isprimex=0
B ELOOPJJ
ELSE2 MVC ISPRIMEX,=F'1' isprimex=1
LA R9,3 jj=3
LOOPJJ LR R5,R9 jj
MR R4,R9 jj*jj
C R5,NUMBER do jj=3 by 1 while jj*jj<=number
BH ELOOPJJ
L R4,NUMBER
SRDA R4,32
DR R4,R9 mod(number,jj)
LTR R4,R4 if mod(number,jj)=0
BNZ ITERJJ
MVC ISPRIMEX,=F'0' isprimex=0
L R0,ISPRIMEX return(isprimex)
B ISPRIMRT
ITERJJ LA R9,1(R9) jj=jj+1
B LOOPJJ
ELOOPJJ L R0,ISPRIMEX return(isprimex)
ISPRIMRT L R14,ISPRIMSA
BR R14 -------------- end isprime
BTEST CNOP 0,4 -------------- btest(word,n) [R0:R3]
LA R0,1 ok=1; return(1) if word(n)='1'b
LR R3,R2 i=n
LOOPB LTR R3,R3 if i=0
BZ ELOOPB
SRL R1,1 Shift Right Logical
BCTR R3,0 i=i-1
B LOOPB
ELOOPB STC R1,BTESTX x=word
TM BTESTX,B'00000001' if bit(word,n)='1'b
BO BTESTRET
LA R0,0 ok=0; return(0) if word(n)='0'b
BTESTRET BR R14 -------------- end btest
XX DS F paramter of popcount
NUMBER DS F paramter of isprime
ISPRIMEX DS F return value of isprime
BTESTX DS X byte to see in btest
POPCOUSA DS A return address of popcount
ISPRIMSA DS A return address of isprime
PG DS CL80 buffer
XDEC DS CL12 edit zone
YREGS
END PERNIC
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
Action!
Action! integers are limited to 16 bits, so this implements 32 bit addition and multiplication by 8-bit values to handle the larger numbers.
;;; find some pernicious numbers - numbers where the population count is prime
;;; As the task requires 32 bit integers, this implements 32-bit unsigend
;;; integer addition and multiplication by an 8-bit integer.
;;; The 32-bit values are stored in 4 separate bytes
;;; returns the population (number of bits on) of the non-negative integer n
BYTE FUNC population( CARD n )
CARD number
BYTE result
number = n
result = 0;
WHILE number > 0 DO
IF number AND 1 THEN result ==+ 1 FI
number ==/ 2
OD
RETURN( result )
;;; returns TRUE if n is a prime; n must be <= 32
BYTE FUNC isSmallPrime( BYTE n )
BYTE result
IF n = 2 THEN result = 1
ELSEIF ( n AND 1 ) = 0 THEN result = 0
ELSEIF n = 1 OR n = 9 OR n = 15
OR n = 21 OR n = 25 OR n = 27
THEN result = 0
ELSE result = 1
FI
RETURN( result )
;;; returns TRUE if n is pernicious, FALSE otherwise
BYTE FUNC isPernicious( CARD n ) RETURN( isSmallPrime( population( n ) ) )
;;; returns TRUE if the 32 bit integer in i1, i2, i3, i4 is pernicious,
;;; FALSE otherwise
BYTE FUNC isPernicious32( BYTE i1, i2, i3, i4 )
BYTE p
p = population( i1 ) + population( i2 )
+ population( i3 ) + population( i4 )
RETURN( isSmallPrime( p ) )
;;; adds b to the 32 bit unsigned integer in i1, i2, i3 and i4
PROC i32add8( BYTE POINTER i1, i2, i3, i4, BYTE b )
CARD c1, c2, c3, c4
c1 = i1^ c2 = i2^ c3 = i3^ c4 = i4^
c4 ==+ b
i4 ^= c4 MOD 256
c3 ==+ c4 / 256
i3 ^= c3 MOD 256
c2 ==+ c3 / 256
i2 ^= c2 MOD 256
c1 ==+ c2 / 256
i1 ^= c1 MOD 256
RETURN
;;; multiplies the 32 bit unsigned integer in i1, i2, i3 and i4 by b
PROC i32mul8( BYTE POINTER i1, i2, i3, i4, BYTE b )
CARD c1, c2, c3, c4, r
c1 = i1^ c2 = i2^ c3 = i3^ c4 = i4^
r = c4 * b
i4 ^= r MOD 256
r = ( c3 * b ) + ( r / 256 )
i3 ^= r MOD 256
r = ( c2 * b ) + ( r / 256 )
i2 ^= r MOD 256
r = ( c1 * b ) + ( r / 256 )
i1 ^= r MOD 256
RETURN
;;; find the first 25 pernicious numbers
PROC Main()
BYTE perniciousCount, i
BYTE i81, i82, i83, i84
BYTE p81, p82, p83, p84
perniciousCount = 0
i = 0
WHILE perniciousCount < 25 DO
IF isPernicious( i ) THEN
; found a pernicious number
PrintB( i )Put(' )
perniciousCount ==+ 1
FI
i ==+ 1
OD
PutE()
; find the pernicious numbers between 888 888 877 and 888 888 888
; form 888 888 800 in i81, i82, i83 and i84
i81 = 0 i82 = 0 i83 = 0 i84 = 88 ; 88
i32mul8( @i81, @i82, @i83, @i84, 100 ) ; 8 800
i32add8( @i81, @i82, @i83, @i84, 88 ) ; 8 888
i32mul8( @i81, @i82, @i83, @i84, 100 ) ; 888 800
i32add8( @i81, @i82, @i83, @i84, 88 ) ; 888 888
i32mul8( @i81, @i82, @i83, @i84, 10 ) ; 8 888 880
i32add8( @i81, @i82, @i83, @i84, 8 ) ; 8 888 888
i32mul8( @i81, @i82, @i83, @i84, 100 ) ; 888 888 800
FOR i = 77 TO 88 DO
p81 = i81 p82 = i82 p83 = i83 p84 = i84
i32add8( @p81, @p82, @p83, @p84, i )
IF isPernicious32( p81, p82, p83, p84 )
THEN
print( "8888888" )PrintB( i )Put(' )
FI
OD
PutE()
RETURN
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
Ada
Uses package Population_Count from Population count#Ada.
with Ada.Text_IO, Population_Count; use Population_Count;
procedure Pernicious is
Prime: array(0 .. 64) of Boolean;
-- we are using 64-bit numbers, so the population count is between 0 and 64
X: Num; use type Num;
Cnt: Positive;
begin
-- initialize array Prime; Prime(I) must be true if and only if I is a prime
Prime := (0 => False, 1 => False, others => True);
for I in 2 .. 8 loop
if Prime(I) then
Cnt := I + I;
while Cnt <= 64 loop
Prime(Cnt) := False;
Cnt := Cnt + I;
end loop;
end if;
end loop;
-- print first 25 pernicious numbers
X := 1;
for I in 1 .. 25 loop
while not Prime(Pop_Count(X)) loop
X := X + 1;
end loop;
Ada.Text_IO.Put(Num'Image(X));
X := X + 1;
end loop;
Ada.Text_IO.New_Line;
-- print pernicious numbers between 888_888_877 and 888_888_888 (inclusive)
for Y in Num(888_888_877) .. 888_888_888 loop
if Prime(Pop_Count(Y)) then
Ada.Text_IO.Put(Num'Image(Y));
end if;
end loop;
Ada.Text_IO.New_Line;
end;
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
A small modification allows to count all the pernicious numbers between 1 and 2**32 in about 32 seconds:
Counter: Natural;
begin
-- initialize array Prime; Prime(I) must be true if and only if I is a prime
...
Counter := 0;
-- count p. numbers below 2**32
for Y in Num(2) .. 2**32 loop
if Prime(Pop_Count(Y)) then
Counter := Counter + 1;
end if;
end loop;
Ada.Text_IO.Put_Line(Natural'Image(Counter));
end Count_Pernicious;
- Output:
> time ./count_pernicious 1421120880 real 0m33.375s user 0m33.372s sys 0m0.000s
ALGOL 68
# calculate various pernicious numbers #
# returns the population (number of bits on) of the non-negative integer n #
PROC population = ( INT n )INT:
BEGIN
INT number := n;
INT result := 0;
WHILE number > 0 DO
IF ODD number THEN result +:= 1 FI;
number OVERAB 2
OD;
result
END # population # ;
# as we are dealing with 32 bit numbers, the maximum possible population is 32 #
# so we only need a table of whether the integers 0 : 32 are prime or not #
# we use the sieve of Eratosthenes... #
INT max number = 32;
[ 0 : max number ]BOOL is prime;
is prime[ 0 ] := FALSE;
is prime[ 1 ] := FALSE;
FOR i FROM 2 TO max number DO is prime[ i ] := TRUE OD;
FOR i FROM 2 TO ENTIER sqrt( max number ) DO
IF is prime[ i ] THEN FOR p FROM i * i BY i TO max number DO is prime[ p ] := FALSE OD FI
OD;
# returns TRUE if n is pernicious, FALSE otherwise #
PROC is pernicious = ( INT n )BOOL: is prime[ population( n ) ];
# find the first 25 pernicious numbers, 0 and 1 are not pernicious #
INT pernicious count := 0;
FOR i FROM 2 WHILE pernicious count < 25 DO
IF is pernicious( i ) THEN
# found a pernicious number #
print( ( whole( i, 0 ), " " ) );
pernicious count +:= 1
FI
OD;
print( ( newline ) );
# find the pernicious numbers between 888 888 877 and 888 888 888 #
FOR i FROM 888 888 877 TO 888 888 888 DO
IF is pernicious( i ) THEN
print( ( whole( i, 0 ), " " ) )
FI
OD;
print( ( newline ) )
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
ALGOL W
begin % find some pernicious numbers: numbers with a prime population count %
% returns the population count of n %
integer procedure populationCount( integer value n ) ;
begin
integer v, count;
count := 0;
v := abs n;
while v > 0 do begin
if odd( v ) then count := count + 1;
v := v div 2
end while_v_gt_0 ;
count
end populationCount ;
% sets p( 1 :: n ) to a sieve of primes up to n %
procedure Eratosthenes ( logical array p( * ) ; integer value n ) ;
begin
p( 1 ) := false; p( 2 ) := true;
for i := 3 step 2 until n do p( i ) := true;
for i := 4 step 2 until n do p( i ) := false;
for i := 3 step 2 until truncate( sqrt( n ) ) do begin
integer ii; ii := i + i;
if p( i ) then for pr := i * i step ii until n do p( pr ) := false
end for_i ;
end Eratosthenes ;
% returns true if p is pernicious, false otherwise, s must be a sieve %
% of primes upto 32 %
logical procedure isPernicious ( integer value p; logical array s ( * ) ) ; p > 0 and s( populationCount( p ) );
% find the pernicious numbers %
begin
% as we are dealing with 32 bit numbers, the maximum possible %
% population is 32 %
logical array isPrime ( 1 :: 32 );
integer p, pCount;
Eratosthenes( isPrime, 32 );
% show the first 25 pernicious numbers %
pCount := 0;
p := 2; % 0 and 1 aren't pernicious, so start at 2 %
while pCount < 25 do begin
if isPernicious( p, isPrime ) then begin
% have a pernicious number %
pCount := pCount + 1;
writeon( i_w := 1, s_w := 0, " ", p )
end if_pernicious_p ;
p := P + 1
end for_p ;
write();
% find the pernicious numbers between 888 888 877 and 888 888 888 %
for p := 888888877 until 888888888 do begin
if isPernicious( p, isPrime ) then writeon( i_w := 1, s_w := 0, " ", p )
end for_p ;
write();
end
end.
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
AppleScript
on isPrime(n)
if (n < 4) then return (n > 1)
if ((n mod 2 is 0) or (n mod 3 is 0)) then return false
repeat with i from 5 to (n ^ 0.5) div 1 by 6
if ((n mod i is 0) or (n mod (i + 2) is 0)) then return false
end repeat
return true
end isPrime
on isPernicious(n)
-- 8 bits at a time is statistically slightly more efficient than 1 bit at a time.
set popCount to (n mod 4 + 1) div 2 + (n mod 16 + 4) div 8
set n to n div 16
repeat until (n = 0)
set popCount to popCount + (n mod 4 + 1) div 2 + (n mod 16 + 4) div 8
set n to n div 16
end repeat
return isPrime(popCount)
end isPernicious
-- Task code:
on intToText(n)
set output to ""
repeat until (n < 100000000)
set output to text 2 thru 9 of ((100000000 + (n mod 100000000 as integer)) as text) & output
set n to n div 100000000
end repeat
set output to (n as integer as text) & output
return output
end intToText
on join(lst, delim)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to delim
set output to lst as text
set AppleScript's text item delimiters to astid
return output
end join
on task()
set l1 to {}
set n to 0
set counter to 0
repeat until (counter = 25)
if (isPernicious(n)) then
set end of l1 to n
set counter to counter + 1
end if
set n to n + 1
end repeat
set l2 to {}
-- One solution to 8,888,877 and up being too large to be AppleScript repeat indices.
repeat with i from 88888877 to 88888888
set n to 8.0E+8 + i
if (isPernicious(n)) then set end of l2 to intToText(n)
end repeat
return join(l1, " ") & (linefeed & join(l2, " "))
end task
task()
- Output:
"3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36
888888877 888888878 888888880 888888883 888888885 888888886"
Arturo
pernicious?: function [n][
prime? size filter split as.binary n 'x -> x="0"
]
i: 1
found: 0
while [found<25][
if pernicious? i [
prints i
prints " "
found: found + 1
]
i: i + 1
]
print ""
print select 888888877..888888888 => pernicious?
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
AutoHotkey
c := 0
while c < 25
if IsPern(A_Index)
Out1 .= A_Index " ", c++
Loop, 12
if IsPern(n := 888888876 + A_Index)
Out2 .= n " "
MsgBox, % Out1 "`n" Out2
IsPern(x) { ;https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation
static p := {2:1, 3:1, 5:1, 7:1, 11:1, 13:1, 17:1, 19:1, 23:1, 29:1, 31:1, 37:1, 41:1, 43:1, 47:1, 53:1, 59:1, 61:1}
x -= (x >> 1) & 0x5555555555555555
, x := (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
, x := (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
return p[(x * 0x0101010101010101) >> 56]
}
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
AWK
# syntax: GAWK -f PERNICIOUS_NUMBERS.AWK
BEGIN {
pernicious(25)
pernicious(888888877,888888888)
exit(0)
}
function pernicious(x,y, count,n) {
if (y == "") { # print first X pernicious numbers
while (count < x) {
if (is_prime(pop_count(++n)) == 1) {
printf("%d ",n)
count++
}
}
}
else { # print pernicious numbers in X-Y range
for (n=x; n<=y; n++) {
if (is_prime(pop_count(n)) == 1) {
printf("%d ",n)
}
}
}
print("")
}
function dec2bin(n, str) {
while (n) {
if (n%2 == 0) {
str = "0" str
}
else {
str = "1" str
}
n = int(n/2)
}
if (str == "") {
str = "0"
}
return(str)
}
function is_prime(x, i) {
if (x <= 1) {
return(0)
}
for (i=2; i<=int(sqrt(x)); i++) {
if (x % i == 0) {
return(0)
}
}
return(1)
}
function pop_count(n) {
n = dec2bin(n)
return gsub(/1/,"&",n)
}
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
BASIC
BASIC256
n = 1
cont = 0
print "The following are the first 25 pernicious numbers:"
print
do
if isPernicious(n) then
print rjust(string(n), 3);
cont += 1
end if
n += 1
until cont = 25
print : print
print "The pernicious numbers between 888,888,877 and 888,888,888 inclusive are:"
print
for n = 888888877 to 888888888
if isPernicious(n) then print rjust(string(n), 10);
next n
end
function SumBinaryDigits(number)
if number < 0 then number = -number # convert negative numbers to positive
sum = 0
while number > 0
sum += number mod 2
number /= 2
end while
return sum
end function
function isPrime(v)
if v < 2 then return False
if v mod 2 = 0 then return v = 2
if v mod 3 = 0 then return v = 3
d = 5
while d * d <= v
if v mod d = 0 then return False else d += 2
end while
return True
end function
function isPernicious(number)
popcont = SumBinaryDigits(number)
return isPrime(popcont)
end function
- Output:
Same as FreeBASIC entry.
Gambas
Public Sub Main()
Dim n As Integer = 1, count As Integer = 0
Print "The following are the first 25 pernicious numbers:\n"
Do
If isPernicious(n) Then
Print Format$(n, "###");
count += 1
End If
n += 1
Loop Until count = 25
Print "\n\nThe pernicious numbers between 888,888,877 and 888,888,888 inclusive are:\n"
For n = 888888877 To 888888888
If isPernicious(n) Then Print Format$(n, "##########");
Next
Print
End
Public Sub isPrime(ValorEval As Long) As Boolean
If ValorEval < 2 Then Return False
If ValorEval Mod 2 = 0 Then Return ValorEval = 2
If ValorEval Mod 3 = 0 Then Return ValorEval = 3
Dim d As Long = 5
While d * d <= ValorEval
If ValorEval Mod d = 0 Then Return False Else d += 2
Wend
Return True
End Function
Public Function SumBinaryDigits(number As Integer) As Integer
If number < 0 Then number = -number ' convert negative numbers to positive
Dim sum As Integer = 0
While number > 0
sum += number Mod 2
number \= 2
Wend
Return sum
End Function
Public Function isPernicious(number As Integer) As Boolean
Dim popCount As Integer = SumBinaryDigits(number)
Return isPrime(popCount)
End Function
- Output:
Same as FreeBASIC entry.
Yabasic
n = 1
cont = 0
print "The following are the first 25 pernicious numbers:\n"
repeat
if isPernicious(n) then
print n using ("###");
cont = cont + 1
fi
n = n + 1
until cont = 25
print "\n\nThe pernicious numbers between 888,888,877 and 888,888,888 inclusive are:\n"
for n = 888888877 to 888888888
if isPernicious(n) print n using("##########");
next n
print
end
sub SumBinaryDigits(number)
if number < 0 number = -number // convert negative numbers to positive
sum = 0
while number > 0
sum = sum + mod(number, 2)
number = int(number / 2)
wend
return sum
end sub
sub isPrime(v)
if v < 2 return False
if mod(v, 2) = 0 return v = 2
if mod(v, 3) = 0 return v = 3
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
wend
return True
end sub
sub isPernicious(number)
popcont = SumBinaryDigits(number)
return isPrime(popcont)
end sub
- Output:
Same as FreeBASIC entry.
Befunge
Based more or less on the C implementation, although we don't bother supporting n = 0, so we can use a smaller prime bit set that fits inside a signed 32 bit int (most Befunge implementations wouldn't support anything higher).
Also note that the extra spaces in the output are just to ensure it's readable on buggy interpreters that don't include a space after numeric output. They can easily be removed by replacing the comma on line 3 with a dollar.
55*00p1>:"ZOA>/"***7-*>\:2>/\v
>8**`!#^_$@\<(^v^)>/#2^#\<2 2
^+**"X^yYo":+1<_:.48*,00v|: <%
v".D}Tx"$,+55_^#!p00:-1g<v |<
> * + : * * + ^^ ! % 2 $ <^ <^
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
C
#include <stdio.h>
typedef unsigned uint;
uint is_pern(uint n)
{
uint c = 2693408940u; // int with all prime-th bits set
while (n) c >>= 1, n &= (n - 1); // take out lowerest set bit one by one
return c & 1;
}
int main(void)
{
uint i, c;
for (i = c = 0; c < 25; i++)
if (is_pern(i))
printf("%u ", i), ++c;
putchar('\n');
for (i = 888888877u; i <= 888888888u; i++)
if (is_pern(i))
printf("%u ", i);
putchar('\n');
return 0;
}
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
C#
using System;
using System.Linq;
namespace PerniciousNumbers
{
class Program
{
public static int PopulationCount(long n)
{
int cnt = 0;
do
{
if ((n & 1) != 0)
{
cnt++;
}
} while ((n >>= 1) > 0);
return cnt;
}
public static bool isPrime(int x)
{
if (x <= 2 || (x & 1) == 0)
{
return x == 2;
}
var limit = Math.Sqrt(x);
for (int i = 3; i <= limit; i += 2)
{
if (x % i == 0)
{
return false;
}
}
return true;
}
private static IEnumerable<int> Pernicious(int start, int count, int take)
{
return Enumerable.Range(start, count).Where(n => isPrime(PopulationCount(n))).Take(take);
}
static void Main(string[] args)
{
foreach (var n in Pernicious(0, int.MaxValue, 25))
{
Console.Write("{0} ", n);
}
Console.WriteLine();
foreach (var n in Pernicious(888888877, 11, 11))
{
Console.Write("{0} ", n);
}
Console.ReadKey();
}
}
}
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
C++
#include <iostream>
using namespace std;
int main() {
int cnt = 0, cnt2, cnt3, tmp, binary[8];
for (int i = 3; cnt < 25; i++) {
tmp = i;
cnt2 = 0;
cnt3 = 0;
for (int j = 7; j > 0; j--) {
binary[j] = tmp % 2;
tmp /= 2;
}
binary[0] = tmp;
for (int j = 0; j < 8; j++) {
if (binary[j] == 1) {
cnt2++;
}
}
for (int j = 2; j <= (cnt2 / 2); j++) {
if (cnt2 % j == 0) {
cnt3++;
break;
}
}
if (cnt3 == 0 && cnt2 != 1) {
cout << i << endl;
cnt++;
}
}
cout << endl;
int binary2[31];
for (int i = 888888877; i <= 888888888; i++) {
tmp = i;
cnt2 = 0;
cnt3 = 0;
for (int j = 30; j > 0; j--) {
binary2[j] = tmp % 2;
tmp /= 2;
}
binary2[0] = tmp;
for (int j = 0; j < 31; j++) {
if (binary2[j] == 1) {
cnt2++;
}
}
for (int j = 2; j <= (cnt2 / 2); j++) {
if (cnt2 % j == 0) {
cnt3++;
break;
}
}
if (cnt3 == 0 && cnt2 != 1) {
cout << i << endl;
}
}
}
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
Clojure
(defn counting-numbers
([] (counting-numbers 1))
([n] (lazy-seq (cons n (counting-numbers (inc n))))))
(defn divisors [n] (filter #(zero? (mod n %)) (range 1 (inc n))))
(defn prime? [n] (= (divisors n) (list 1 n)))
(defn pernicious? [n]
(prime? (count (filter #(= % \1) (Integer/toString n 2)))))
(println (take 25 (filter pernicious? (counting-numbers))))
(println (filter pernicious? (range 888888877 888888889)))
- Output:
(3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36) (888888877 888888878 888888880 888888883 888888885 888888886)
CLU
% The population count of an integer is never going to be
% higher than the amount of bits in it (max 64)
% so we can get away with a very simple primality test.
is_prime = proc (n: int) returns (bool)
if n<=2 then return(n=2) end
if n//2=0 then return(false) end
for i: int in int$from_to_by(n+2, n/2, 2) do
if n//i=0 then return(false) end
end
return(true)
end is_prime
% Find the population count of a number
pop_count = proc (n: int) returns (int)
c: int := 0
while n > 0 do
c := c + n // 2
n := n / 2
end
return(c)
end pop_count
% Is N pernicious?
pernicious = proc (n: int) returns (bool)
return(is_prime(pop_count(n)))
end pernicious
start_up = proc ()
po: stream := stream$primary_output()
stream$putl(po, "First 25 pernicious numbers: ")
n: int := 1
seen: int := 0
while seen<25 do
if pernicious(n) then
stream$puts(po, int$unparse(n) || " ")
seen := seen + 1
end
n := n + 1
end
stream$putl(po, "\nPernicious numbers between 888,888,877 and 888,888,888:")
for i: int in int$from_to(888888877,888888888) do
if pernicious(i) then
stream$puts(po, int$unparse(i) || " ")
end
end
end start_up
- Output:
First 25 pernicious numbers: 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 Pernicious numbers between 888,888,877 and 888,888,888: 888888877 888888878 888888880 888888883 888888885 888888886
COBOL
IDENTIFICATION DIVISION.
PROGRAM-ID. PERNICIOUS-NUMBERS.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 VARIABLES.
03 AMOUNT PIC 99.
03 CAND PIC 9(9).
03 POPCOUNT PIC 99.
03 POP-N PIC 9(9).
03 FILLER REDEFINES POP-N.
05 FILLER PIC 9(8).
05 FILLER PIC 9.
88 ODD VALUES 1, 3, 5, 7, 9.
03 DSOR PIC 99.
03 DIV-RSLT PIC 99V99.
03 FILLER REDEFINES DIV-RSLT.
05 FILLER PIC 99.
05 FILLER PIC 99.
88 DIVISIBLE VALUE ZERO.
03 PRIME-FLAG PIC X.
88 PRIME VALUE '*'.
01 FORMAT.
03 SIZE-FLAG PIC X.
88 SMALL VALUE 'S'.
88 LARGE VALUE 'L'.
03 SMALL-NUM PIC ZZ9.
03 LARGE-NUM PIC Z(9)9.
03 OUT-STR PIC X(80).
03 OUT-PTR PIC 99.
PROCEDURE DIVISION.
BEGIN.
PERFORM SMALL-PERNICIOUS.
PERFORM LARGE-PERNICIOUS.
STOP RUN.
INIT-OUTPUT-VARS.
MOVE ZERO TO AMOUNT.
MOVE 1 TO OUT-PTR.
MOVE SPACES TO OUT-STR.
SMALL-PERNICIOUS.
PERFORM INIT-OUTPUT-VARS.
MOVE 'S' TO SIZE-FLAG.
PERFORM ADD-PERNICIOUS
VARYING CAND FROM 1 BY 1 UNTIL AMOUNT IS EQUAL TO 25.
DISPLAY OUT-STR.
LARGE-PERNICIOUS.
PERFORM INIT-OUTPUT-VARS.
MOVE 'L' TO SIZE-FLAG.
PERFORM ADD-PERNICIOUS
VARYING CAND FROM 888888877 BY 1
UNTIL CAND IS GREATER THAN 888888888.
DISPLAY OUT-STR.
ADD-NUM.
ADD 1 TO AMOUNT.
IF SMALL,
MOVE CAND TO SMALL-NUM,
STRING SMALL-NUM DELIMITED BY SIZE INTO OUT-STR
WITH POINTER OUT-PTR.
IF LARGE,
MOVE CAND TO LARGE-NUM,
STRING LARGE-NUM DELIMITED BY SIZE INTO OUT-STR
WITH POINTER OUT-PTR.
ADD-PERNICIOUS.
PERFORM FIND-POPCOUNT.
PERFORM CHECK-PRIME.
IF PRIME, PERFORM ADD-NUM.
FIND-POPCOUNT.
MOVE ZERO TO POPCOUNT.
MOVE CAND TO POP-N.
PERFORM COUNT-BIT UNTIL POP-N IS EQUAL TO ZERO.
COUNT-BIT.
IF ODD, ADD 1 TO POPCOUNT.
DIVIDE 2 INTO POP-N.
CHECK-PRIME.
IF POPCOUNT IS LESS THAN 2,
MOVE SPACE TO PRIME-FLAG
ELSE
MOVE '*' TO PRIME-FLAG.
PERFORM CHECK-DSOR VARYING DSOR FROM 2 BY 1
UNTIL NOT PRIME OR DSOR IS NOT LESS THAN POPCOUNT.
CHECK-DSOR.
DIVIDE POPCOUNT BY DSOR GIVING DIV-RSLT.
IF DIVISIBLE, MOVE SPACE TO PRIME-FLAG.
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
Common Lisp
Using primep
from Primality by trial division task.
(format T "~{~a ~}~%"
(loop for n = 1 then (1+ n)
when (primep (logcount n))
collect n into numbers
when (= (length numbers) 25)
return numbers))
(format T "~{~a ~}~%"
(loop for n from 888888877 to 888888888
when (primep (logcount n))
collect n))
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
Cowgol
include "cowgol.coh";
sub prime(n: uint8): (r: uint8) is
if n<2 then
r := 0;
return;
end if;
r := 1;
var d: uint8 := 2;
while d*d <= n loop
if n%d == 0 then
r := 0;
return;
end if;
d := d + 1;
end loop;
end sub;
sub popcount(n: uint32): (count: uint8) is
count := 0;
while n > 0 loop
count := count + (n as uint8 & 1);
n := n >> 1;
end loop;
end sub;
sub pernicious(n: uint32): (r: uint8) is
r := prime(popcount(n));
end sub;
var candidate: uint32 := 0;
var seen: uint8 := 0;
while seen < 25 loop
candidate := candidate + 1;
if pernicious(candidate) != 0 then
print_i32(candidate);
print_char(' ');
seen := seen + 1;
end if;
end loop;
print_nl();
candidate := 888888877;
while candidate < 888888888 loop
if pernicious(candidate) != 0 then
print_i32(candidate);
print_char(' ');
end if;
candidate := candidate + 1;
end loop;
print_nl();
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
D
void main() {
import std.stdio, std.algorithm, std.range, core.bitop;
immutable pernicious = (in uint n) => (2 ^^ n.popcnt) & 0xA08A28AC;
uint.max.iota.filter!pernicious.take(25).writeln;
iota(888_888_877, 888_888_889).filter!pernicious.writeln;
}
- Output:
[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] [888888877, 888888878, 888888880, 888888883, 888888885, 888888886]
Where 0xA08A28AC == 0b_1010_0000__1000_1010__0010_1000__1010_1100
, that is a bit set equivalent to the prime numbers [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31] of the range (0, 31].
This high-level code is fast enough to allow to count all the 1_421_120_880 Pernicious numbers in the unsigned 32 bit range in less than 48 seconds with this line:
uint.max.iota.filter!pernicious.walkLength.writeln;
EasyLang
fastfunc isprim num .
if num < 2
return 0
.
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
func popc n .
while n > 0
r += n mod 2
n = n div 2
.
return r
.
n = 1
while cnt < 25
if isprim popc n = 1
write n & " "
cnt += 1
.
n += 1
.
print ""
n = 1
for n = 888888877 to 888888888
if isprim popc n = 1
write n & " "
.
.
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
EchoLisp
(lib 'sequences)
(define (pernicious? n) (prime? (bit-count n)))
(define pernicious (filter pernicious? [1 .. ]))
(take pernicious 25)
→ (3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36)
(take (filter pernicious? [888888877 .. 888888889]) #:all)
→ (888888877 888888878 888888880 888888883 888888885 888888886)
Eiffel
class
APPLICATION
create
make
feature
make
-- Test of is_pernicious_number.
local
test: LINKED_LIST [INTEGER]
i: INTEGER
do
create test.make
from
i := 1
until
test.count = 25
loop
if is_pernicious_number (i) then
test.extend (i)
end
i := i + 1
end
across
test as t
loop
io.put_string (t.item.out + " ")
end
io.new_line
across
888888877 |..| 888888888 as c
loop
if is_pernicious_number (c.item) then
io.put_string (c.item.out + " ")
end
end
end
is_pernicious_number (n: INTEGER): BOOLEAN
-- Is 'n' a pernicious_number?
require
positiv_input: n > 0
do
Result := is_prime (count_population (n))
end
feature{NONE}
count_population (n: INTEGER): INTEGER
-- Population count of 'n'.
require
positiv_input: n > 0
local
j: INTEGER
math: DOUBLE_MATH
do
create math
j := math.log_2 (n).ceiling + 1
across
0 |..| j as c
loop
if n.bit_test (c.item) then
Result := Result + 1
end
end
end
is_prime (n: INTEGER): BOOLEAN
--Is 'n' a prime number?
require
positiv_input: n > 0
local
i: INTEGER
max: REAL_64
math: DOUBLE_MATH
do
create math
if n = 2 then
Result := True
elseif n <= 1 or n \\ 2 = 0 then
Result := False
else
Result := True
max := math.sqrt (n)
from
i := 3
until
i > max
loop
if n \\ i = 0 then
Result := False
end
i := i + 2
end
end
end
end
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
Elixir
defmodule SieveofEratosthenes do
def init(lim) do
find_primes(2,lim,(2..lim))
end
def find_primes(count,lim,nums) when (count * count) > lim do
nums
end
def find_primes(count,lim,nums) when (count * count) <= lim do
e = Enum.reject(nums,&(rem(&1,count) == 0 and &1 > count))
find_primes(count+1,lim,e)
end
end
defmodule PerniciousNumbers do
def take(n) do
primes = SieveofEratosthenes.init(100)
Stream.iterate(1,&(&1+1))
|> Stream.filter(&(pernicious?(&1,primes)))
|> Enum.take(n)
|> IO.inspect
end
def between(a..b) do
primes = SieveofEratosthenes.init(100)
a..b
|> Stream.filter(&(pernicious?(&1,primes)))
|> Enum.to_list
|> IO.inspect
end
def ones(num) do
num
|> Integer.to_string(2)
|> String.codepoints
|> Enum.count(fn n -> n == "1" end)
end
def pernicious?(n,primes), do: Enum.member?(primes,ones(n))
end
PerniciousNumbers.take(25)
PerniciousNumbers.between(888_888_877..888_888_888)
- Output:
[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36]
[888888877, 888888878, 888888880, 888888883, 888888885, 888888886]
F#
open System
//Taken from https://gist.github.com/rmunn/bc49d32a586cdfa5bcab1c3e7b45d7ac
let bitcount (n : int) =
let count2 = n - ((n >>> 1) &&& 0x55555555)
let count4 = (count2 &&& 0x33333333) + ((count2 >>> 2) &&& 0x33333333)
let count8 = (count4 + (count4 >>> 4)) &&& 0x0f0f0f0f
(count8 * 0x01010101) >>> 24
//Modified from other examples to actually state the 1 is not prime
let isPrime n =
if n < 2 then
false
else
let sqrtn n = int <| sqrt (float n)
seq { 2 .. sqrtn n } |> Seq.exists(fun i -> n % i = 0) |> not
[<EntryPoint>]
let main _ =
[1 .. 100] |> Seq.filter (bitcount >> isPrime) |> Seq.take 25 |> Seq.toList |> printfn "%A"
[888888877 .. 888888888] |> Seq.filter (bitcount >> isPrime) |> Seq.toList |> printfn "%A"
0 // return an integer exit code
- Output:
[3; 5; 6; 7; 9; 10; 11; 12; 13; 14; 17; 18; 19; 20; 21; 22; 24; 25; 26; 28; 31; 33; 34; 35; 36] [888888877; 888888878; 888888880; 888888883; 888888885; 888888886]
Factor
USING: lists lists.lazy math.bitwise math.primes math.ranges
prettyprint sequences ;
: pernicious? ( n -- ? ) bit-count prime? ;
25 0 lfrom [ pernicious? ] lfilter ltake list>array . ! print first 25 pernicious numbers
888,888,877 888,888,888 [a,b] [ pernicious? ] filter . ! print pernicious numbers in range
- Output:
{ 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 } { 888888877 888888878 888888880 888888883 888888885 888888886 }
Forth
: popcount { n -- u }
0
begin
n 0<>
while
n n 1- and to n
1+
repeat ;
\ primality test for 0 <= n <= 63
: prime? ( n -- ? )
1 swap lshift 0x28208a20a08a28ac and 0<> ;
: pernicious? ( n -- ? )
popcount prime? ;
: first_n_pernicious_numbers { n -- }
." First " n . ." pernicious numbers:" cr
1
begin
n 0 >
while
dup pernicious? if
dup .
n 1- to n
then
1+
repeat
drop cr ;
: pernicious_numbers_between { m n -- }
." Pernicious numbers between " m . ." and " n 1 .r ." :" cr
n 1+ m do
i pernicious? if i . then
loop
cr ;
25 first_n_pernicious_numbers
888888877 888888888 pernicious_numbers_between
bye
- Output:
First 25 pernicious numbers: 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 Pernicious numbers between 888888877 and 888888888: 888888877 888888878 888888880 888888883 888888885 888888886
Fortran
program pernicious
implicit none
integer :: i, n
i = 1
n = 0
do
if(isprime(popcnt(i))) then
write(*, "(i0, 1x)", advance = "no") i
n = n + 1
if(n == 25) exit
end if
i = i + 1
end do
write(*,*)
do i = 888888877, 888888888
if(isprime(popcnt(i))) write(*, "(i0, 1x)", advance = "no") i
end do
contains
function popcnt(x)
integer :: popcnt
integer, intent(in) :: x
integer :: i
popcnt = 0
do i = 0, 31
if(btest(x, i)) popcnt = popcnt + 1
end do
end function
function isprime(number)
logical :: isprime
integer, intent(in) :: number
integer :: i
if(number == 2) then
isprime = .true.
else if(number < 2 .or. mod(number,2) == 0) then
isprime = .false.
else
isprime = .true.
do i = 3, int(sqrt(real(number))), 2
if(mod(number,i) == 0) then
isprime = .false.
exit
end if
end do
end if
end function
end program
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
FreeBASIC
' FreeBASIC v1.05.0 win64
Function SumBinaryDigits(number As Integer) As Integer
If number < 0 Then number = -number ' convert negative numbers to positive
Var sum = 0
While number > 0
sum += number Mod 2
number \= 2
Wend
Return sum
End Function
Function IsPrime(number As Integer) As Boolean
If number <= 1 Then
Return false
ElseIf number <= 3 Then
Return true
ElseIf number Mod 2 = 0 OrElse number Mod 3 = 0 Then
Return false
End If
Var i = 5
While i * i <= number
If number Mod i = 0 OrElse number Mod (i + 2) = 0 Then
Return false
End If
i += 6
Wend
Return True
End Function
Function IsPernicious(number As Integer) As Boolean
Dim popCount As Integer = SumBinaryDigits(number)
Return IsPrime(popCount)
End Function
Dim As Integer n = 1, count = 0
Print "The following are the first 25 pernicious numbers :"
Print
Do
If IsPernicious(n) Then
Print Using "###"; n;
count += 1
End If
n += 1
Loop Until count = 25
Print : Print
Print "The pernicious numbers between 888,888,877 and 888,888,888 inclusive are :"
Print
For n = 888888877 To 888888888
If IsPernicious(n) Then Print Using "##########"; n;
Next
Print : Print
Print "Press any key to exit the program"
Sleep
End
- Output:
The following are the first 25 pernicious numbers : 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 The pernicious numbers between 888,888,877 and 888,888,888 inclusive are : 888888877 888888878 888888880 888888883 888888885 888888886
Frink
isPernicious = {|x|
bits = countToDict[integerDigits[x,2]].get[1,0]
return bits > 1 and isPrime[bits]
}
println["First 25: " + first[select[count[1], isPernicious], 25]]
println[select[888_888_877 to 888_888_888, isPernicious]]
- Output:
First 25: [3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] [888888877, 888888878, 888888880, 888888883, 888888885, 888888886]
Fōrmulæ
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in its website.
In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution
Case 1. Display the first 25 pernicious numbers (in decimal)
Case 2. display all pernicious numbers between 888,888,877 and 888,888,888 (inclusive).
Go
package main
import "fmt"
func pernicious(w uint32) bool {
const (
ff = 1<<32 - 1
mask1 = ff / 3
mask3 = ff / 5
maskf = ff / 17
maskp = ff / 255
)
w -= w >> 1 & mask1
w = w&mask3 + w>>2&mask3
w = (w + w>>4) & maskf
return 0xa08a28ac>>(w*maskp>>24)&1 != 0
}
func main() {
for i, n := 0, uint32(1); i < 25; n++ {
if pernicious(n) {
fmt.Printf("%d ", n)
i++
}
}
fmt.Println()
for n := uint32(888888877); n <= 888888888; n++ {
if pernicious(n) {
fmt.Printf("%d ", n)
}
}
fmt.Println()
}
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
Groovy
class example{
static void main(String[] args){
def n=0;
def counter=0;
while(counter<25){
if(print(n)){
counter++;}
n=n+1;
}
println();
def x=888888877;
while(x<888888889){
print(x);
x++;}
}
static def print(def a){
def primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47];
def c=Integer.toBinaryString(a);
String d=c;
def e=0;
for(i in d){if(i=='1'){e++;}}
if(e in primes){printf(a+" ");return 1;}
}
}
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
Haskell
module Pernicious
where
isPernicious :: Integer -> Bool
isPernicious num = isPrime $ toInteger $ length $ filter ( == 1 ) $ toBinary num
isPrime :: Integer -> Bool
isPrime number = divisors number == [1, number]
where
divisors :: Integer -> [Integer]
divisors number = [ m | m <- [1 .. number] , number `mod` m == 0 ]
toBinary :: Integer -> [Integer]
toBinary num = reverse $ map ( `mod` 2 ) ( takeWhile ( /= 0 ) $ iterate ( `div` 2 ) num )
solution1 = take 25 $ filter isPernicious [1 ..]
solution2 = filter isPernicious [888888877 .. 888888888]
- Output:
[3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36] [888888877,888888878,888888880,888888883,888888885,888888886]
Or, in a point-free and applicative style, using unfoldr for the population count:
import Data.Numbers.Primes (isPrime)
import Data.List (unfoldr)
import Data.Tuple (swap)
import Data.Bool (bool)
isPernicious :: Int -> Bool
isPernicious = isPrime . popCount
popCount :: Int -> Int
popCount =
sum . unfoldr ((flip bool Nothing . Just . swap . flip quotRem 2) <*> (0 ==))
main :: IO ()
main =
mapM_
print
[ take 25 $ filter isPernicious [1 ..]
, filter isPernicious [888888877 .. 888888888]
]
- Output:
[3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36] [888888877,888888878,888888880,888888883,888888885,888888886]
Icon and Unicon
Works in both languages:
link "factors"
procedure main(A)
every writes((pernicious(seq())\25||" ") | "\n")
every writes((pernicious(888888877 to 888888888)||" ") | "\n")
end
procedure pernicious(n)
return (isprime(c1bits(n)),n)
end
procedure c1bits(n)
c := 0
while n > 0 do c +:= 1(n%2, n/:=2)
return c
end
- Output:
->pn 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886 ->
J
Implementation:
ispernicious=: 1 p: +/"1@#:
Task (thru taken from the Loops/Downward for task).:
25{.I.ispernicious i.100
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36
thru=: <. + i.@(+*)@-~
(#~ ispernicious) 888888877 thru 888888888
888888877 888888878 888888880 888888883 888888885 888888886
Java
public class Pernicious{
//very simple isPrime since x will be <= Long.SIZE
public static boolean isPrime(int x){
if(x < 2) return false;
for(int i = 2; i < x; i++){
if(x % i == 0) return false;
}
return true;
}
public static int popCount(long x){
return Long.bitCount(x);
}
public static void main(String[] args){
for(long i = 1, n = 0; n < 25; i++){
if(isPrime(popCount(i))){
System.out.print(i + " ");
n++;
}
}
System.out.println();
for(long i = 888888877; i <= 888888888; i++){
if(isPrime(popCount(i))) System.out.print(i + " ");
}
}
}
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
jq
The most interesting detail in the following is perhaps the use of recurse/1 to define the helper function bin, which generates the binary bits.
# is_prime is designed to work with jq 1.4
def is_prime:
if . == 2 then true
else 2 < . and . % 2 == 1 and
. as $in
| (($in + 1) | sqrt) as $m
| (((($m - 1) / 2) | floor) + 1) as $max
| reduce range(1; $max) as $i
(true; if . then ($in % ((2 * $i) + 1)) > 0 else false end)
end;
def popcount:
def bin: recurse( if . == 0 then empty else ./2 | floor end ) % 2;
[bin] | add;
def is_pernicious: popcount | is_prime;
# Emit a stream of "count" pernicious numbers greater than
# or equal to m:
def pernicious(m; count):
if count > 0 then
if m | is_pernicious then m, pernicious(m+1; count -1)
else pernicious(m+1; count)
end
else empty
end;
def task:
# display the first 25 pernicious numbers:
[ pernicious(1;25) ],
# display all pernicious numbers between
# 888,888,877 and 888,888,888 (inclusive).
[ range(888888877; 888888889) | select( is_pernicious ) ]
;
task
- Output:
[3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36] [888888877,888888878,888888880,888888883,888888885,888888886]
Julia
using Primes
ispernicious(n::Integer) = isprime(count_ones(n))
nextpernicious(n::Integer) = begin n += 1; while !ispernicious(n) n += 1 end; return n end
function perniciouses(n::Int)
rst = Vector{Int}(n)
rst[1] = 3
for i in 2:n
rst[i] = nextpernicious(rst[i-1])
end
return rst
end
perniciouses(a::Integer, b::Integer) = filter(ispernicious, a:b)
println("First 25 pernicious numbers: ", join(perniciouses(25), ", "))
println("Perniciouses in [888888877, 888888888]: ", join(perniciouses(888888877, 888888888), ", "))
- Output:
First 25 pernicious numbers: 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36 Perniciouses in [888888877, 888888888]: 888888877, 888888878, 888888880, 888888883, 888888885, 888888886
Kotlin
// version 1.0.5-2
fun isPrime(n: Int): Boolean {
if (n < 2) return false
if (n % 2 == 0) return n == 2
if (n % 3 == 0) return n == 3
var d : Int = 5
while (d * d <= n) {
if (n % d == 0) return false
d += 2
if (n % d == 0) return false
d += 4
}
return true
}
fun getPopulationCount(n: Int): Int {
if (n <= 0) return 0
var nn = n
var sum = 0
while (nn > 0) {
sum += nn % 2
nn /= 2
}
return sum
}
fun isPernicious(n: Int): Boolean = isPrime(getPopulationCount(n))
fun main(args: Array<String>) {
var n = 1
var count = 0
println("The first 25 pernicious numbers are:\n")
do {
if (isPernicious(n)) {
print("$n ")
count++
}
n++
}
while (count < 25)
println("\n")
println("The pernicious numbers between 888,888,877 and 888,888,888 inclusive are:\n")
for (i in 888888877..888888888) {
if (isPernicious(i)) print("$i ")
}
}
- Output:
The first 25 pernicious numbers are: 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 The pernicious numbers between 888,888,877 and 888,888,888 inclusive are: 888888877 888888878 888888880 888888883 888888885 888888886
Ksh
#!/bin/ksh
# Positive integer whose population count is a prime
# # Variables:
#
integer PNUM=25 MINN=888888877 MAXN=888888888
# # Functions:
#
# # Function _dec2bin(n) - return binary representation of decimal n
#
function _dec2bin {
typeset _n ; integer _n=$1
typeset _base ; integer _base=2
typeset _q _r _buff ; integer _q _r
typeset -a _arr _barr
(( _q = _n / _base ))
(( _r = _n % _base ))
_arr+=( ${_r} )
until (( _q == 0 )); do
_n=${_q}
(( _q = _n / _base ))
(( _r = _n % _base ))
_arr+=( ${_r} )
done
_revarr _arr _barr
_buff=${_barr[@]}
echo ${_buff// /}
}
# # Function _revarr(arr, barr) - reverse arr into barr
#
function _revarr {
typeset _arr ; nameref _arr="$1"
typeset _barr ; nameref _barr="$2"
typeset _i ; integer _i
for ((_i=${#_arr[*]}-1; _i>=0; _i--)); do
_barr+=( ${_arr[_i]} )
done
}
# # Function _isprime(n) return 1 for prime, 0 for not prime
#
function _isprime {
typeset _n ; integer _n=$1
typeset _i ; integer _i
(( _n < 2 )) && return 0
for (( _i=2 ; _i*_i<=_n ; _i++ )); do
(( ! ( _n % _i ) )) && return 0
done
return 1
}
# # Function _sumdigits(n) return sum of n's digits
#
function _sumdigits {
typeset _n ; _n=$1
typeset _i _sum ; integer _i _sum=0
for ((_i=0; _i<${#_n}; _i++)); do
(( _sum+=${_n:${_i}:1} ))
done
echo ${_sum}
}
######
# main #
######
integer i sbi n=3 cnt=0
printf "First $PNUM Pernicious numbers:\n"
for ((n = cnt = 0; cnt < PNUM; n++)); do
bi=$(_dec2bin ${n}) # $n as Binary
sbi=${bi//0/} # Strip zeros (i.e. count ones)
_isprime ${#sbi} # One count prime?
(( $? )) && { printf "%4d " ${n} ; ((++cnt)) }
done
printf "\n\nPernicious numbers between %11,d and %11,d inclusive:\n" $MINN $MAXN
for ((i=MINN; i<=MAXN; i++)); do
bi=$(_dec2bin ${i})
sbi=${bi//0/}
_isprime ${#sbi}
(( $? )) && printf "%12,d " ${i}
done
echo
- Output:
First 25 Pernicious numbers:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36Pernicious numbers between 888,888,877 and 888,888,888 inclusive:
888,888,877 888,888,878 888,888,880 888,888,883 888,888,885 888,888,886
Lua
-- Test primality by trial division
function isPrime (x)
if x < 2 then return false end
if x < 4 then return true end
if x % 2 == 0 then return false end
for d = 3, math.sqrt(x), 2 do
if x % d == 0 then return false end
end
return true
end
-- Take decimal number, return binary string
function dec2bin (n)
local bin, bit = ""
while n > 0 do
bit = n % 2
n = math.floor(n / 2)
bin = bit .. bin
end
return bin
end
-- Take decimal number, return population count as number
function popCount (n)
local bin, count = dec2bin(n), 0
for pos = 1, bin:len() do
if bin:sub(pos, pos) == "1" then count = count + 1 end
end
return count
end
-- Print pernicious numbers in range if two arguments provided, or
function pernicious (x, y) -- the first 'x' if only one argument.
if y then
for n = x, y do
if isPrime(popCount(n)) then io.write(n .. " ") end
end
else
local n, count = 0, 0
while count < x do
if isPrime(popCount(n)) then
io.write(n .. " ")
count = count + 1
end
n = n + 1
end
end
print()
end
-- Main procedure
pernicious(25)
pernicious(888888877, 888888888)
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
Maple
ispernicious := proc(n::posint)
return evalb(isprime(rhs(Statistics:-Tally(StringTools:-Explode(convert(convert(n, binary), string)))[-1])));
end proc;
print_pernicious := proc(n::posint)
local k, count, list_num;
count := 0;
list_num := [];
for k while count < n do
if ispernicious(k) then
count := count + 1;
list_num := [op(list_num), k];
end if;
end do;
return list_num;
end proc:
range_pernicious := proc(n::posint, m::posint)
local k, list_num;
list_num := [];
for k from n to m do
if ispernicious(k) then
list_num := [op(list_num), k];
end if;
end do;
return list_num;
end proc:
- Output:
[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] [888888877, 888888878, 888888880, 888888883, 888888885, 888888886]
Mathematica/Wolfram Language
popcount[n_Integer] := IntegerDigits[n, 2] // Total
perniciousQ[n_Integer] := popcount[n] // PrimeQ
perniciouscount = 0;
perniciouslist = {};
i = 0;
While[perniciouscount < 25,
If[perniciousQ[i], AppendTo[perniciouslist, i]; perniciouscount++];
i++]
Print["first 25 pernicious numbers"]
perniciouslist
(*******)
perniciouslist2 = {};
Do[
If[perniciousQ[i], AppendTo[perniciouslist2, i]]
, {i, 888888877, 888888888}]
Print["Pernicious numbers between 888,888,877 and 888,888,888 (inclusive)"]
perniciouslist2
- Output:
first 25 pernicious numbers {3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36} Pernicious numbers between 888,888,877 and 888,888,888 (inclusive) {888888877, 888888878, 888888880, 888888883, 888888885, 888888886}
Alternate Code
test function
perniciousQ[n_Integer] := PrimeQ@Total@IntegerDigits[n, 2]
First 25 pernicious numbers
n = 0; NestWhile[Flatten@{#, If[perniciousQ[++n], n, {}]} &, {}, Length@# < 25 &]
Pernicious numbers betweeen 888888877 and 888888888 inclusive
Cases[Range[888888877, 888888888], _?(perniciousQ@# &)]
Miranda
main :: [sys_message]
main = [Stdout (lay (map show [first25, large]))]
first25 :: [num]
first25 = take 25 (filter pernicious [1..])
large :: [num]
large = filter pernicious [888888877..888888888]
pernicious :: num->bool
pernicious = prime . popcount
popcount :: num->num
popcount 0 = 0
popcount n = n mod 2 + popcount (n div 2)
prime :: num->bool
prime n = n >= 2 & and [n mod d ~= 0 | d<-[2..sqrt n]]
- Output:
[3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36] [888888877,888888878,888888880,888888883,888888885,888888886]
Modula-2
MODULE Pernicious;
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
PROCEDURE IsPrime(x : LONGINT) : BOOLEAN;
VAR i : LONGINT;
BEGIN
IF x<2 THEN RETURN FALSE END;
FOR i:=2 TO x-1 DO
IF x MOD i = 0 THEN RETURN FALSE END
END;
RETURN TRUE
END IsPrime;
PROCEDURE BitCount(x : LONGINT) : LONGINT;
VAR count : LONGINT;
BEGIN
count := 0;
WHILE x>0 DO
x := x BAND (x-1);
INC(count)
END;
RETURN count
END BitCount;
VAR
buf : ARRAY[0..63] OF CHAR;
i,n : LONGINT;
BEGIN
i := 1;
n := 0;
WHILE n<25 DO
IF IsPrime(BitCount(i)) THEN
FormatString("%l ", buf, i);
WriteString(buf);
INC(n)
END;
INC(i)
END;
WriteLn;
FOR i:=888888877 TO 888888888 DO
IF IsPrime(BitCount(i)) THEN
FormatString("%l ", buf, i);
WriteString(buf)
END;
END;
ReadChar
END Pernicious.
Nim
import strutils
proc count(s: string; sub: char): int =
var i = 0
while true:
i = s.find(sub, i)
if i < 0:
break
inc i
inc result
proc popcount(n: int): int = n.toBin(64).count('1')
const primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61}
var p: seq[int]
var i = 0
while p.len < 25:
if popcount(i) in primes: p.add i
inc i
echo p
p = @[]
i = 888_888_877
while i <= 888_888_888:
if popcount(i) in primes: p.add i
inc i
echo p
- Output:
@[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] @[888888877, 888888878, 888888880, 888888883, 888888885, 888888886]
OCaml
let rec popcount n =
if n = 0 then 0 else succ (popcount (n land pred n))
let is_prime n =
let rec test d = d * d > n || n mod d <> 0 && test (d + 2) in
if n < 3 then n = 2 else n land 1 <> 0 && test 3
let is_pernicious n =
is_prime (popcount n)
let () =
Seq.ints 0 |> Seq.filter is_pernicious |> Seq.take 25
|> Seq.iter (Printf.printf " %u") |> print_newline
and () =
Seq.ints 888888877 |> Seq.take 12 |> Seq.filter is_pernicious
|> Seq.iter (Printf.printf " %u") |> print_newline
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
Panda
fun prime(a) type integer->integer
a where count{{a.factor}}==2
fun pernisc(a) type integer->integer
a where sum{{a.radix:2 .char.integer}}.integer.prime
1..36.pernisc
888888877..888888888.pernisc
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
PARI/GP
pern(n)=isprime(hammingweight(n))
select(pern, [1..36])
select(pern,[888888877..888888888])
- Output:
%1 = [3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] %2 = [888888877, 888888878, 888888880, 888888883, 888888885, 888888886]
Pascal
Inspired by Ada, using array of primes to simply add.An if-then takes to long.
Added easy counting of pernicious numbers for full Bit ranges like 32-Bit
program pernicious;
{$IFDEF FPC}
{$OPTIMIZATION ON,Regvar,ASMCSE,CSE,PEEPHOLE}// 3x speed up
{$ENDIF}
uses
sysutils;//only used for time
type
tbArr = array[0..64] of byte;
{
PrimeTil64 : array[0..64] of byte =
(0,0,2,3,0,5,0, 7,0,0,0,11,0,13,0,0,0,17,0,19,0,0,0,23,0,0,0,0,0,29,0,
31,0,0,0,0,0,37,0,0,0,41,0,43,0,0,0,47,0, 0,0,0,0,53,0,0,0,0,0,59,0,
61,0,0,0);
}
const
PrimeTil64 : tbArr =
(0,0,1,1,0,1,0, 1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,
1,0,0,0,0,0, 1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,
1,0,0,0);
function n_beyond_k(n,k: NativeInt):Uint64;
var
i : NativeInt;
Begin
result := 1;
IF 2*k>= n then
k := n-k;
For i := 1 to k do
Begin
result := result *n DIV i;
dec(n);
end;
end;
function popcnt32(n:Uint32):NativeUint;
//https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation
const
K1 = $0101010101010101;
K33 = $3333333333333333;
K55 = $5555555555555555;
KF1 = $0F0F0F0F0F0F0F0F;
begin
n := n- (n shr 1) AND NativeUint(K55);
n := (n AND NativeUint(K33))+ ((n shr 2) AND NativeUint(K33));
n := (n + (n shr 4)) AND NativeUint(KF1);
n := (n*NativeUint(K1)) SHR 24;
popcnt32 := n;
end;
var
bit1cnt,
k : LongWord;
PernCnt : Uint64;
Begin
writeln('the 25 first pernicious numbers');
k:=1;
PernCnt:=0;
repeat
IF PrimeTil64[popCnt32(k)] <> 0 then Begin
inc(PernCnt); write(k,' ');end;
inc(k);
until PernCnt >= 25;
writeln;
writeln('pernicious numbers in [888888877..888888888]');
For k := 888888877 to 888888888 do
IF PrimeTil64[popCnt32(k)] <> 0 then
write(k,' ');
writeln(#13#10);
k := 8;
repeat
PernCnt := 0;
For bit1cnt := 0 to k do
Begin
//i == number of Bits set,n_beyond_k(k,i) == number of arrangements
IF PrimeTil64[bit1cnt] <> 0 then
inc(PernCnt,n_beyond_k(k,bit1cnt));
end;
writeln(PernCnt,' pernicious numbers in [0..2^',k,'-1]');
inc(k,k);
until k>64;
end.
- Output:
the 25 first pernicious numbers 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 pernicious numbers in [888888877..888888888] 888888877 888888878 888888880 888888883 888888885 888888886 148 pernicious numbers in [0..2^8-1] 21416 pernicious numbers in [0..2^16-1] 1421120880 pernicious numbers in [0..2^32-1] 1214766910143514374 pernicious numbers in [0..2^64-1]
Perl
sub is_pernicious {
my $n = shift;
my $c = 2693408940; # primes < 32 as set bits
while ($n) { $c >>= 1; $n &= ($n - 1); }
$c & 1;
}
my ($i, @p) = 0;
while (@p < 25) {
push @p, $i if is_pernicious($i);
$i++;
}
print join ' ', @p;
print "\n";
($i, @p) = (888888877,);
while ($i < 888888888) {
push @p, $i if is_pernicious($i);
$i++;
}
print join ' ', @p;
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
Alternately, generating the same output using a method similar to Pari/GP:
use ntheory qw/is_prime hammingweight/;
my $i = 1;
my @pern = map { $i++ while !is_prime(hammingweight($i)); $i++; } 1..25;
print "@pern\n";
print join(" ", grep { is_prime(hammingweight($_)) } 888888877 .. 888888888), "\n";
Phix
with javascript_semantics function pernicious(integer n) return is_prime(sum(int_to_bits(n,32))) end function sequence s = {} integer n = 1 while length(s)<25 do if pernicious(n) then s &= n end if n += 1 end while pp(s) s = {} for i=888_888_877 to 888_888_888 do if pernicious(i) then s &= i end if end for pp(s)
- Output:
{3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36} {888888877,888888878,888888880,888888883,888888885,888888886}
Picat
go =>
println(take_n(pernicious_number,25,1)),
println([J : J in 888888877..888888888, pernicious_number(J)]),
nl.
% Get the first N numbers that satisfies function F, starting with S
take_n(F,N,S) = L =>
I = S,
C = 0,
L = [],
while(C < N)
if call(F,I) then
L := L ++ [I],
C := C + 1
end,
I := I + 1
end.
pop_count(N) = sum([1: I in N.to_binary_string(), I = '1']).
pernicious_number(N) => prime(pop_count(N)).
- Output:
[3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36] [888888877,888888878,888888880,888888883,888888885,888888886]
PicoLisp
Using 'prime?' from Primality by trial division#PicoLisp.
(de pernicious? (N)
(prime? (cnt = (chop (bin N)) '("1" .))) )
Test:
: (let N 0
(do 25
(until (pernicious? (inc 'N)))
(printsp N) ) )
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 -> 36
: (filter pernicious? (range 888888877 888888888))
-> (888888877 888888878 888888880 888888883 888888885 888888886)
PL/I
pern: procedure options (main);
declare (i, n) fixed binary (31);
n = 3;
do i = 1 to 25, 888888877 to 888888888;
if i = 888888877 then do; n = i ; put skip; end;
do while ( ^is_prime ( tally(bit(n), '1'b) ) );
n = n + 1;
end;
put edit( trim(n), ' ') (a);
n = n + 1;
end;
is_prime: procedure (n) returns (bit(1));
declare n fixed (15);
declare i fixed (10);
if n < 2 then return ('0'b);
if n = 2 then return ('1'b);
if mod(n, 2) = 0 then return ('0'b);
do i = 3 to sqrt(n) by 2;
if mod(n, i) = 0 then return ('0'b);
end;
return ('1'b);
end is_prime;
end pern;
Results:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886 888888889 888888890 888888892 888888897 888888898 888888900
Plain English
To decide if a number is pernicious:
Find a population count of the number.
If the population count is prime, say yes.
Say no.
To find a population count of a number:
Privatize the number.
Loop.
If the number is 0, exit.
Bitwise and the number with the number minus 1.
Bump the population count.
Repeat.
To run:
Start up.
Show the first twenty-five pernicious numbers.
Show the pernicious numbers between 888888877 and 888888888.
Wait for the escape key.
Shut down.
To show the first twenty-five pernicious numbers:
Put 0 into a number.
Put 0 into a pernicious number count.
Loop.
If the pernicious number count is greater than 24, write "" on the console; exit.
If the number is pernicious, show the number; bump the pernicious number count.
Bump the number.
Repeat.
To show a number:
Convert the number to a string.
Write the string then " " on the console without advancing.
To show the pernicious numbers between a number and another number:
Privatize the number.
Subtract 1 from the number.
Loop.
If the number is past the other number, exit.
If the number is pernicious, show the number.
Repeat.
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
PowerShell
function pop-count($n) {
(([Convert]::ToString($n, 2)).toCharArray() | where {$_ -eq '1'}).count
}
function isPrime ($n) {
if ($n -eq 1) {$false}
elseif ($n -eq 2) {$true}
elseif ($n -eq 3) {$true}
else{
$m = [Math]::Floor([Math]::Sqrt($n))
(@(2..$m | where {($_ -lt $n) -and ($n % $_ -eq 0) }).Count -eq 0)
}
}
$i = 0
$num = 1
$arr = while($i -lt 25) {
if((isPrime (pop-count $num))) {
$i++
$num
}
$num++
}
"first 25 pernicious numbers"
"$arr"
""
"pernicious numbers between 888,888,877 and 888,888,888"
"$(888888877..888888888 | where{isprime(pop-count $_)})"
Output:
First 25 pernicious numbers 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 Pernicious numbers between 888,888,877 and 888,888,888 888888877 888888878 888888880 888888883 888888885 888888886
As An Advanced Function
Just an exercise in how to make the input more "PowerShelly".
The PopCount property is available in each of the returned integers.
function Select-PerniciousNumber
{
[CmdletBinding()]
[OutputType([int])]
Param
(
[Parameter(Mandatory=$true,
ValueFromPipeline=$true,
ValueFromPipelineByPropertyName=$true,
Position=0)]
$InputObject
)
Begin
{
function Test-Prime ([int]$n)
{
$n = [Math]::Abs($n)
if ($n -eq 0 -or $n -eq 1) {return $false}
for ($m = 2; $m -le [Math]::Sqrt($n); $m++)
{
if (($n % $m) -eq 0) {return $false}
}
return $true
}
[scriptblock]$popCount = {(([Convert]::ToString($this, 2)).ToCharArray() | Where-Object {$_ -eq '1'}).Count}
}
Process
{
foreach ($object in $InputObject)
{
$object | Add-Member -MemberType ScriptProperty -Name PopCount -Value $popCount -Force -PassThru | ForEach-Object {
if (Test-Prime $_.PopCount)
{
$_
}
}
}
}
}
$start, $end = 0, 999999
$range1 = $start..$end | Select-PerniciousNumber | Select-Object -First 25
"First {0} pernicious numbers:`n{1}`n" -f $range1.Count, ($range1 -join ", ")
$start, $end = 888888877, 888888888
$range2 = $start..$end | Select-PerniciousNumber
"Pernicious numbers between {0} and {1}:`n{2}`n" -f $start, $end, ($range2 -join ", ")
- Output:
First 25 pernicious numbers: 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36 Pernicious numbers between 888888877 and 888888888: 888888877, 888888878, 888888880, 888888883, 888888885, 888888886
PureBasic
EnableExplicit
Procedure.i SumBinaryDigits(Number)
If Number < 0 : number = -number : EndIf; convert negative numbers to positive
Protected sum = 0
While Number > 0
sum + Number % 2
Number / 2
Wend
ProcedureReturn sum
EndProcedure
Procedure.i IsPrime(Number)
If Number <= 1
ProcedureReturn #False
ElseIf Number <= 3
ProcedureReturn #True
ElseIf Number % 2 = 0 Or Number % 3 = 0
ProcedureReturn #False
EndIf
Protected i = 5
While i * i <= Number
If Number % i = 0 Or Number % (i + 2) = 0
ProcedureReturn #False
EndIf
i + 6
Wend
ProcedureReturn #True
EndProcedure
Procedure.i IsPernicious(Number)
Protected popCount = SumBinaryDigits(Number)
ProcedureReturn Bool(IsPrime(popCount))
EndProcedure
Define n = 1, count = 0
If OpenConsole()
PrintN("The following are the first 25 pernicious numbers :")
PrintN("")
Repeat
If IsPernicious(n)
Print(RSet(Str(n), 3))
count + 1
EndIf
n + 1
Until count = 25
PrintN("")
PrintN("")
PrintN("The pernicious numbers between 888,888,877 and 888,888,888 inclusive are : ")
PrintN("")
For n = 888888877 To 888888888
If IsPernicious(n)
Print(RSet(Str(n), 10))
EndIf
Next
PrintN("")
PrintN("")
PrintN("Press any key to close the console")
Repeat: Delay(10) : Until Inkey() <> ""
CloseConsole()
EndIf
- Output:
The following are the first 25 pernicious numbers : 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 The pernicious numbers between 888,888,877 and 888,888,888 inclusive are : 888888877 888888878 888888880 888888883 888888885 888888886
Python
Procedural
>>> def popcount(n): return bin(n).count("1")
>>> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61}
>>> p, i = [], 0
>>> while len(p) < 25:
if popcount(i) in primes: p.append(i)
i += 1
>>> p
[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36]
>>> p, i = [], 888888877
>>> while i <= 888888888:
if popcount(i) in primes: p.append(i)
i += 1
>>> p
[888888877, 888888878, 888888880, 888888883, 888888885, 888888886]
>>>
Functional
'''Pernicious numbers'''
from itertools import count, islice
# isPernicious :: Int -> Bool
def isPernicious(n):
'''True if the population count of n is
a prime number.
'''
return isPrime(popCount(n))
# oeisA052294 :: [Int]
def oeisA052294():
'''A non-finite stream of pernicious numbers.
(Numbers with a prime population count)
'''
return (x for x in count(1) if isPernicious(x))
# popCount :: Int -> Int
def popCount(n):
'''The count of non-zero digits in the binary
representation of the positive integer n.
'''
def go(x):
return divmod(x, 2) if 0 < x else None
return sum(unfoldl(go)(n))
# ------------------------- TEST -------------------------
# main :: IO ()
def main():
'''First 25, and any in the range
[888,888,877..888,888,888]
'''
print(
take(25)(
oeisA052294()
)
)
print([
x for x in enumFromTo(888888877)(888888888)
if isPernicious(x)
])
# ----------------------- GENERIC ------------------------
# enumFromTo :: Int -> Int -> [Int]
def enumFromTo(m):
'''Enumeration of integer values [m..n]'''
def go(n):
return range(m, 1 + n)
return go
# isPrime :: Int -> Bool
def isPrime(n):
'''True if n is prime.'''
if n in (2, 3):
return True
if 2 > n or 0 == n % 2:
return False
if 9 > n:
return True
if 0 == n % 3:
return False
return not any(map(
lambda x: 0 == n % x or 0 == n % (2 + x),
range(5, 1 + int(n ** 0.5), 6)
))
# take :: Int -> [a] -> [a]
# take :: Int -> String -> String
def take(n):
'''The prefix of xs of length n,
or xs itself if n > length xs.
'''
return lambda xs: (
xs[0:n]
if isinstance(xs, (list, tuple))
else list(islice(xs, n))
)
# unfoldl :: (b -> Maybe (b, a)) -> b -> [a]
def unfoldl(f):
'''A lazy (generator) list unfolded from a seed value
by repeated application of f until no residue remains.
Dual to fold/reduce.
f returns either None or just (residue, value).
For a strict output list, wrap the result with list()
'''
def go(v):
residueValue = f(v)
while residueValue:
yield residueValue[1]
residueValue = f(residueValue[0])
return go
# MAIN ---
if __name__ == '__main__':
main()
- Output:
[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] [888888877, 888888878, 888888880, 888888883, 888888885, 888888886]
Quackery
[ $ "rosetta/seive.qky" loadfile
$ "rosetta/popcount.qky" loadfile ] now!
( i.e. using the code at )
( http://rosettacode.org/wiki/Sieve_of_Eratosthenes and )
( http://rosettacode.org/wiki/Population_count )
29 eratosthenes ( Precompute as many primes as are required )
( for the task. 888,888,888 is a 30 bit )
( number less than (2^30)-1 so primes up to )
( 29 will suffice. )
[ 1+ over - times
[ dup i^ +
dup popcount
isprime iff
[ echo sp ]
else drop ]
drop ] is perniciousrange ( n n --> )
25 echopopwith isprime cr
888888877 888888888 perniciousrange cr
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
Racket
#lang racket
(require math/number-theory rnrs/arithmetic/bitwise-6)
(define pernicious? (compose prime? bitwise-bit-count))
(define (dnl . strs)
(for-each displayln strs))
(define (show-sequence seq)
(string-join (for/list ((v (in-values*-sequence seq))) (~a ((if (list? v) car values) v))) ", "))
(dnl
"Task requirements:"
"display the first 25 pernicious numbers."
(show-sequence (in-parallel (sequence-filter pernicious? (in-naturals 1)) (in-range 25)))
"display all pernicious numbers between 888,888,877 and 888,888,888 (inclusive)."
(show-sequence (sequence-filter pernicious? (in-range 888888877 (add1 888888888)))))
(module+ test
(require rackunit)
(check-true (pernicious? 22)))
- Output:
Task requirements: display the first 25 pernicious numbers. 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36 display all pernicious numbers between 888,888,877 and 888,888,888 (inclusive). 888888877, 888888878, 888888880, 888888883, 888888885, 888888886
Raku
(formerly Perl 6)
Straightforward implementation using Raku's is-prime built-in subroutine.
sub is-pernicious(Int $n --> Bool) {
is-prime [+] $n.base(2).comb;
}
say (grep &is-pernicious, 0 .. *)[^25];
say grep &is-pernicious, 888_888_877 .. 888_888_888;
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
REXX
Programming note: to increase the size of the numbers being tested (to greater than 100 decimal digits),
all that is needed is to extend the list of low primes in the 2nd line in the pernicious procedure (below);
the highest prime (Hprime) should exceed the number of decimal digits in 2Hprime.
The program could be easily extended by programmatically generating enough primes to handle much larger numbers.
╔════════════════════════════════════════════════════════════════════════════════════════╗ ╠═════ How the ─── popCount ─── function works (working from the inner─most level): ═════╣ ║ ║ ║ arg(1) obtains the value of the 1st argument passed to the (popCount) function. ║ ║ d2x converts a decimal string ──► heXadecimal (it may have a leading zeroes).║ ║ +0 adds zero to the (above) string, removing any superfluous leading zeroes. ║ ║ translate converts all zeroes to blanks (the 2nd argument defaults to a blank). ║ ║ space removes all blanks from the character string (now only containing '1's). ║ ║ length counts the number of characters in the string. ║ ║ return returns the above value to the invoker. ║ ║ ║ ║ Note that all values in REXX are stored as (eight─bit) characters. ║ ╚════════════════════════════════════════════════════════════════════════════════════════╝
/*REXX program computes and displays a number (and also a range) of pernicious numbers.*/
numeric digits 100 /*be able to handle large numbers. */
parse arg N L H . /*obtain optional arguments from the CL*/
if N=='' | N==',' then N=25 /*N not given? Then use the default. */
if L=='' | L==',' then L=888888877 /*L " " " " " " */
if H=='' | H==',' then H=888888888 /*H " " " " " " */
say 'The 1st ' N " pernicious numbers are:" /*display a nice title for the numbers.*/
say pernicious(1,,N) /*get all pernicious # from 1 ─~─► N. */
say /*display a blank line for a separator.*/
say 'Pernicious numbers between ' L " and " H ' (inclusive) are:'
say pernicious(L,H) /*get all pernicious # from L ───► H. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
pernicious: procedure; parse arg bot,top,lim /*obtain the bot and top numbers, limit*/
p='2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101'
@.=0
do k=1 until _=='' /*examine the list of some low primes.*/
_=word(p, k); @._=1 /*generate an array " " " " */
end /*k*/
$= /*list of pernicious numbers (so far). */
if m=='' then m=999999999 /*Not given? Then use a gihugic limit.*/
if top=='' then top=999999999 /* " " " " " " " */
#=0 /*number of pernicious numbers (so far)*/
do j=bot to top until #==lim /*generate pernicious #s 'til satisfied*/
pc=popCount(j) /*obtain the population count for J. */
if \@.pc then iterate /*if popCount not in @.prime, skip it.*/
$=$ j /*append a pernicious number to list. */
#=#+1 /*bump the pernicious number count. */
end /*j*/
return substr($, 2) /*return the results, sans 1st blank. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
popCount: return length( space( translate( x2b( d2x(arg(1))) +0,, 0), 0)) /*count 1's.*/
output when the default inputs are used:
The 1st 25 pernicious numbers are: 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 Pernicious numbers between 888888877 and 888888888 (inclusive) are: 888888877 888888878 888888880 888888883 888888885 888888886
Ring
Programming note: as written, this program can't handle the large numbers required for the 2nd task requirement (it receives a Numeric Overflow).
# Project : Pernicious numbers
see "The first 25 pernicious numbers:" + nl
nr = 0
for n=1 to 50
sum = 0
str = decimaltobase(n, 2)
for m=1 to len(str)
if str[m] = "1"
sum = sum + 1
ok
next
if isprime(sum)
nr = nr + 1
see "" + n + " "
ok
if nr = 25
exit
ok
next
func decimaltobase(nr, base)
binary = 0
i = 1
while(nr != 0)
remainder = nr % base
nr = floor(nr/base)
binary= binary + (remainder*i)
i = i*10
end
return string(binary)
func isprime num
if (num <= 1) return 0 ok
if (num % 2 = 0 and num != 2) return 0 ok
for i = 3 to floor(num / 2) -1 step 2
if (num % i = 0) return 0 ok
next
return 1
Output:
The first 25 pernicious numbers: 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36
RPL
≪ IF DUP 5 ≤ THEN { 2 3 5 } SWAP POS ELSE IF DUP 2 MOD NOT THEN 2 ELSE DUP √ CEIL → lim ≪ 3 WHILE DUP2 MOD OVER lim ≤ AND REPEAT 2 + END ≫ END MOD END SIGN ≫ 'PRIM?' STO ≪ BIN R→B →STR 0 1 3 PICK SIZE FOR j IF OVER j DUP SUB "1" == THEN 1 + END NEXT SWAP DROP PRIM? ≫ ´PERN?’ STO ≪ { } 1 WHILE OVER SIZE 25 < REPEAT IF DUP PERN? THEN SWAP OVER + SWAP END 1 + END DROP ≫ ´TASK1’ STO ≪ { } 888888877 888888888 FOR n IF n PERN? THEN n + END NEXT ≫ ´TASK2’ STO
- Output:
2: { 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 } 1: { 888888877 888888878 888888880 888888883 888888885 888888886 }
Ruby
require "prime"
class Integer
def popcount
to_s(2).count("1") #Ruby 2.4: digits(2).count(1)
end
def pernicious?
popcount.prime?
end
end
p 1.step.lazy.select(&:pernicious?).take(25).to_a
p ( 888888877..888888888).select(&:pernicious?)
- Output:
[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] [888888877, 888888878, 888888880, 888888883, 888888885, 888888886]
Rust
extern crate aks_test_for_primes;
use std::iter::Filter;
use std::ops::RangeFrom;
use aks_test_for_primes::is_prime;
fn main() {
for i in pernicious().take(25) {
print!("{} ", i);
}
println!();
for i in (888_888_877u64..888_888_888).filter(is_pernicious) {
print!("{} ", i);
}
}
fn pernicious() -> Filter<RangeFrom<u64>, fn(&u64) -> bool> {
(0u64..).filter(is_pernicious as fn(&u64) -> bool)
}
fn is_pernicious(n: &u64) -> bool {
is_prime(n.count_ones())
}
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
S-lang
% Simplistic prime-test from prime-by-trial-division:
define is_prime(n)
{
if (n <= 1) return(0);
if (n == 2) return(1);
if ((n & 1) == 0) return(0);
variable mx = int(sqrt(n)), i;
_for i (3, mx, 1) {
if ((n mod i) == 0)
return(0);
}
return(1);
}
define population(n)
{
variable pc = 0;
do {
if (n & 1) pc++;
n /= 2;
}
while (n);
return(pc);
}
define is_pernicious(n)
{
return(is_prime(population(n)));
}
variable plist = {}, n = 0;
while (length(plist) < 25) {
n++;
if (is_pernicious(n))
list_append(plist, string(n));
}
print(strjoin(list_to_array(plist), " "));
plist = {};
_for n (888888877, 888888888, 1) {
if (is_pernicious(n))
list_append(plist, string(n));
}
print(strjoin(list_to_array(plist), " "));
- Output:
"3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36"
- Output:
"888888877 888888878 888888880 888888883 888888885 888888886"
Scala
def isPernicious( v:Long ) : Boolean = BigInt(v.toBinaryString.toList.filter( _ == '1' ).length).isProbablePrime(16)
// Generate the output
{
val (a,b1,b2) = (25,888888877L,888888888L)
println( Stream.from(2).filter( isPernicious(_) ).take(a).toList.mkString(",") )
println( {for( i <- b1 to b2 if( isPernicious(i) ) ) yield i}.mkString(",") )
}
- Output:
3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36 888888877,888888878,888888880,888888883,888888885,888888886
Seed7
The function popcount
below converts
the integer into a bitset.
The function card
is used to compute the population count of the bitset.
$ include "seed7_05.s7i";
const set of integer: primes is {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61};
const func integer: popcount (in integer: number) is
return card(bitset(number));
const proc: main is func
local
var integer: num is 0;
var integer: count is 0;
begin
for num range 0 to integer.last until count >= 25 do
if popcount(num) in primes then
write(num <& " ");
incr(count);
end if;
end for;
writeln;
for num range 888888877 to 888888888 do
if popcount(num) in primes then
write(num <& " ");
end if;
end for;
writeln;
end func;
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
Sidef
func is_pernicious(n) {
n.sumdigits(2).is_prime
}
say is_pernicious.first(25).join(' ')
say is_pernicious.grep(888_888_877..888_888_888).join(' ')
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
Swift
import Foundation
extension BinaryInteger {
@inlinable
public var isPrime: Bool {
if self == 0 || self == 1 {
return false
} else if self == 2 {
return true
}
let max = Self(ceil((Double(self).squareRoot())))
for i in stride(from: 2, through: max, by: 1) where self % i == 0 {
return false
}
return true
}
}
public func populationCount(n: Int) -> Int {
guard n >= 0 else {
return 0
}
return String(n, radix: 2).lazy.filter({ $0 == "1" }).count
}
let first25 = (1...).lazy.filter({ populationCount(n: $0).isPrime }).prefix(25)
let rng = (888_888_877...888_888_888).lazy.filter({ populationCount(n: $0).isPrime })
print("First 25 Pernicious numbers: \(Array(first25))")
print("Pernicious numbers between 888_888_877...888_888_888: \(Array(rng))")
- Output:
First 25 Pernicious numbers: [3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36] Pernicious numbers between 888_888_877...888_888_888: [888888877, 888888878, 888888880, 888888883, 888888885, 888888886]
Symsyn
primes : 0b0010100000100000100010100010000010100000100010100010100010101100
| the first 25 pernicious numbers
$T | clear string
num_pn | set to zero
2 n | start at 2
5 hi_bit
if num_pn LT 25
call popcount | count ones
if primes bit pop_cnt | if pop_cnt bit of bit vector primes is one
+ num_pn | inc number of pernicious numbers
~ n $S | convert to decimal string
+ ' ' $S | pad a space
+ $S $T | add to string $T
endif
+ pop_cnt | next number (odd) has one more bit than previous (even)
+ n | next number
if primes bit pop_cnt
+ num_pn
~ n $S
+ ' ' $S
+ $S $T
endif
+ n
goif | go back to if
endif
$T [] | display numbers
| pernicious numbers in range 888888877 .. 888888888
$T | clear string
num_pn | set to zero
888888876 n | start at 888888876
29 hi_bit
if n LE 888888888
call popcount | count ones
if primes bit pop_cnt | if pop_cnt bit of bit vector primes is one
+ num_pn | inc number of pernicious numbers
~ n $S | convert to decimal string
+ ' ' $S | pad a space
+ $S $T | add to string $T
endif
+ pop_cnt | next number (odd) has one more bit than previous (even)
+ n | next number
if primes bit pop_cnt
+ num_pn
~ n $S
+ ' ' $S
+ $S $T
endif
+ n
goif | go back to if
endif
$T [] | display numbers
stop
popcount | count ones in bit field
pop_cnt | pop_cnt to zero
1 bit_num | only count even numbers so skip bit 0
if bit_num LE hi_bit
if n bit bit_num
+ pop_cnt
endif
+ bit_num
goif
endif
return
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 37 888888877 888888878 888888880 888888883 888888885 888888886 888888889
Tcl
package require math::numtheory
proc pernicious {n} {
::math::numtheory::isprime [tcl::mathop::+ {*}[split [format %b $n] ""]]
}
for {set n 0;set p {}} {[llength $p] < 25} {incr n} {
if {[pernicious $n]} {lappend p $n}
}
puts [join $p ","]
for {set n 888888877; set p {}} {$n <= 888888888} {incr n} {
if {[pernicious $n]} {lappend p $n}
}
puts [join $p ","]
- Output:
3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36 888888877,888888878,888888880,888888883,888888885,888888886
VBA
Private Function population_count(ByVal number As Long) As Integer
Dim result As Integer
Dim digit As Integer
Do While number > 0
If number Mod 2 = 1 Then
result = result + 1
End If
number = number \ 2
Loop
population_count = result
End Function
Function is_prime(n As Integer) As Boolean
If n < 2 Then
is_prime = False
Exit Function
End If
For i = 2 To Sqr(n)
If n Mod i = 0 Then
is_prime = False
Exit Function
End If
Next i
is_prime = True
End Function
Function pernicious(n As Long)
Dim tmp As Integer
tmp = population_count(n)
pernicious = is_prime(tmp)
End Function
Public Sub main()
Dim count As Integer
Dim n As Long: n = 1
Do While count < 25
If pernicious(n) Then
Debug.Print n;
count = count + 1
End If
n = n + 1
Loop
Debug.Print
For n = 888888877 To 888888888
If pernicious(n) Then
Debug.Print n;
End If
Next n
End Sub
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
VBScript
'check if the number is pernicious
Function IsPernicious(n)
IsPernicious = False
bin_num = Dec2Bin(n)
sum = 0
For h = 1 To Len(bin_num)
sum = sum + CInt(Mid(bin_num,h,1))
Next
If IsPrime(sum) Then
IsPernicious = True
End If
End Function
'prime number validation
Function IsPrime(n)
If n = 2 Then
IsPrime = True
ElseIf n <= 1 Or n Mod 2 = 0 Then
IsPrime = False
Else
IsPrime = True
For i = 3 To Int(Sqr(n)) Step 2
If n Mod i = 0 Then
IsPrime = False
Exit For
End If
Next
End If
End Function
'decimal to binary converter
Function Dec2Bin(n)
q = n
Dec2Bin = ""
Do Until q = 0
Dec2Bin = CStr(q Mod 2) & Dec2Bin
q = Int(q / 2)
Loop
End Function
'display the first 25 pernicious numbers
c = 0
WScript.StdOut.Write "First 25 Pernicious Numbers:"
WScript.StdOut.WriteLine
For k = 1 To 100
If IsPernicious(k) Then
WScript.StdOut.Write k & ", "
c = c + 1
End If
If c = 25 Then
Exit For
End If
Next
WScript.StdOut.WriteBlankLines(2)
'display the pernicious numbers between 888,888,877 to 888,888,888 (inclusive)
WScript.StdOut.Write "Pernicious Numbers between 888,888,877 to 888,888,888 (inclusive):"
WScript.StdOut.WriteLine
For l = 888888877 To 888888888
If IsPernicious(l) Then
WScript.StdOut.Write l & ", "
End If
Next
WScript.StdOut.WriteLine
- Output:
First 25 Pernicious Numbers: 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 31, 33, 34, 35, 36, Pernicious Numbers between 888,888,877 to 888,888,888 (inclusive): 888888877, 888888878, 888888880, 888888883, 888888885, 888888886,
Visual Basic .NET
Module Module1
Function PopulationCount(n As Long) As Integer
Dim cnt = 0
Do
If (n Mod 2) <> 0 Then
cnt += 1
End If
n >>= 1
Loop While n > 0
Return cnt
End Function
Function IsPrime(x As Integer) As Boolean
If x <= 2 OrElse (x Mod 2) = 0 Then
Return x = 2
End If
Dim limit = Math.Sqrt(x)
For i = 3 To limit Step 2
If x Mod i = 0 Then
Return False
End If
Next
Return True
End Function
Function Pernicious(start As Integer, count As Integer, take As Integer) As IEnumerable(Of Integer)
Return Enumerable.Range(start, count).Where(Function(n) IsPrime(PopulationCount(n))).Take(take)
End Function
Sub Main()
For Each n In Pernicious(0, Integer.MaxValue, 25)
Console.Write("{0} ", n)
Next
Console.WriteLine()
For Each n In Pernicious(888888877, 11, 11)
Console.Write("{0} ", n)
Next
Console.WriteLine()
End Sub
End Module
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
Wortel
The following function returns true if it's argument is a pernicious number:
:ispernum ^(@isPrime \@count \=1 @arr &\`![.toString 2])
Task:
!-ispernum 1..36 ; returns [3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36]
!-ispernum 888888877..888888888 ; returns [888888877 888888878 888888880 888888883 888888885 888888886]
Wren
var pernicious = Fn.new { |w|
var ff = 2.pow(32) - 1
var mask1 = (ff / 3).floor
var mask3 = (ff / 5).floor
var maskf = (ff / 17).floor
var maskp = (ff / 255).floor
w = w - (w >> 1 & mask1)
w = (w & mask3) + (w >>2 & mask3)
w = (w + (w >> 4)) & maskf
return 0xa08a28ac >> (w*maskp >> 24) & 1 != 0
}
var i = 0
var n = 1
while (i < 25) {
if (pernicious.call(n)) {
System.write("%(n) ")
i = i + 1
}
n = n + 1
}
System.print()
for (n in 888888877..888888888) {
if (pernicious.call(n)) System.write("%(n) ")
}
System.print()
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
XPL0
func IsPrime(N); \Return 'true' if N is prime
int N, D;
[if N <= 2 then return N = 2;
D:= 2;
while D*D <= N do
[if rem(N/D) = 0 then return false;
D:= D+1;
];
return true;
];
func BitCount(N); \Return number of set bits in N
int N, C;
[C:= 0;
while N do
[C:= C+1;
N:= N & N-1;
];
return C;
];
int N, C;
[N:= 0; C:= 0;
loop [if IsPrime(BitCount(N)) then
[IntOut(0, N); ChOut(0, ^ );
C:= C+1;
if C >= 25 then quit;
];
N:= N+1;
];
CrLf(0);
for N:= 888_888_877 to 888_888_888 do
if IsPrime(BitCount(N)) then
[IntOut(0, N); ChOut(0, ^ )];
CrLf(0);
]
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886
zkl
The largest number of bits is 30.
primes:=T(2,3,5,7,11,13,17,19,23,29,31,37,41);
N:=0; foreach n in ([2..]){
if(n.num1s : primes.holds(_)){
print(n," ");
if((N+=1)==25) break;
}
}
foreach n in ([0d888888877..888888888]){
if (n.num1s : primes.holds(_)) "%,d; ".fmt(n).print();
}
Int.num1s returns the number of 1 bits. eg (3).num1s-->2
- Output:
3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888,888,877; 888,888,878; 888,888,880; 888,888,883; 888,888,885; 888,888,886;
Or in a more functional style:
primes:=T(2,3,5,7,11,13,17,19,23,29,31,37,41);
p:='wrap(n){ primes.holds(n.num1s) };
[1..].filter(25,p).toString(*).println();
[0d888888877..888888888].filter(p).println();
'wrap is syntactic sugar for a closure - it creates a function that wraps local data (variable primes in this case). We assign that function to p.
- Output:
L(3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36) L(888888877,888888878,888888880,888888883,888888885,888888886)
- Programming Tasks
- Prime Numbers
- 11l
- 360 Assembly
- Action!
- Ada
- ALGOL 68
- ALGOL W
- AppleScript
- Arturo
- AutoHotkey
- AWK
- BASIC
- BASIC256
- Gambas
- Yabasic
- Befunge
- C
- C sharp
- C++
- Clojure
- CLU
- COBOL
- Common Lisp
- Cowgol
- D
- EasyLang
- EchoLisp
- Eiffel
- Elixir
- F Sharp
- Factor
- Forth
- Fortran
- FreeBASIC
- Frink
- Fōrmulæ
- Go
- Groovy
- Haskell
- Icon
- Unicon
- J
- Java
- Jq
- Julia
- Kotlin
- Ksh
- Lua
- Maple
- Mathematica
- Wolfram Language
- Miranda
- Modula-2
- Nim
- OCaml
- Panda
- PARI/GP
- Pascal
- Perl
- Ntheory
- Phix
- Picat
- PicoLisp
- PL/I
- Plain English
- PowerShell
- PureBasic
- Python
- Quackery
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- S-lang
- Scala
- Seed7
- Sidef
- Swift
- Symsyn
- Tcl
- Tcllib
- VBA
- VBScript
- Visual Basic .NET
- Wortel
- Wren
- XPL0
- Zkl