Pernicious numbers
A pernicious number is a positive integer whose population count is a prime.
The population count (also known as pop count) is the number of 1's (ones) in the binary representation of an non-negative integer.
For example, (which is 10110 in binary) has a population count of , which is prime and so is a pernicious number.
- Task requirements
- display the first 25 pernicious numbers.
- display all pernicious numbers between 888888877 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.
C
<lang 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;
}</lang>
- 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
<lang parigp>pern(n)=isprime(hammingweight(n)) select(pern, [1..35]) select(pern,[888888877..888888888])</lang>
- 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] %2 = [888888877, 888888878, 888888880, 888888883, 888888885, 888888886]
Perl 6
Straightforward implementation using Perl 6's is-prime built-in subroutine. <lang perl6>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;</lang>
- 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
<lang rexx>/*REXX program displays a number of pernicious numbers and also a range.*/ numeric digits 100 /*be able to handle large numbers*/ parse arg N L H . /*get optional arguments: N, L, H*/ if N== | N==',' then N=25 /*N given? Then use the default.*/ if L== | L==',' then L=888888877 /*L given? Then use the default.*/ if H== | H==',' then H=888888888 /*H given? Then use the default.*/ _=pernicious(1,,N) /*get all pernicious # from 1──◄N*/ say 'The 1st ' N " pernicious numbers are:" /*display a title.*/ say _ /*display a list. */ say /*display a blank line for a sep.*/ _=pernicious(L,H) /*get all pernicious # from L──◄H*/ say 'Pernicious numbers between ' L " and " H ' (inclusive) are:' say _ /*display a list. */ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────D2B subroutine──────────────────────*/ d2b: return word(strip(x2b(d2x(arg(1))),'L',0) 0,1) /*convert dec──►bin*/ /*──────────────────────────────────ISPRIME subroutine──────────────────*/ isPrime: procedure; parse arg x; if x<2 then return 0 /*X is too low.*/
if wordpos(x,'2 3 5 7')\==0 then return 1 /*X is prime. */
if x//2==0 then return 0; if x//3==0 then return 0
do j=5 by 6 until j*j>x; if x// j ==0 then return 0
if x//(j+2)==0 then return 0; end
return 1 /*The X number is prime. */ /*──────────────────────────────────PERNICIOUS subroutine───────────────*/ pernicious: procedure; parse arg bot,top,m /*get the bot & top #s, limit*/ if m== then m=999999999 /*assume an "infinite" limit. */ if top== then top=999999999 /*assume an "infinite" top limit.*/
- =0 /*number of pernicious #s so far.*/
$=; do j=bot to top until #==m /*gen pernicious until satisfied.*/
if \isPrime(popCount(j)) then iterate /*if popCount ¬prime, skip.*/
$=$ j /*append a pernicious # to list.*/
#=#+1 /*bump the pernicious # count. */
end /*j*/ /* [↑] append popCount to a list*/
return substr($,2) /*return results, sans 1st blank.*/ /*──────────────────────────────────POPCOUNT subroutine─────────────────*/ popCount: procedure;_=d2b(abs(arg(1))) /*convert the # passed to binary.*/ return length(_)-length(space(translate(_,,1),0)) /*count the one bits.*/</lang> output   when the default input is 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
Tcl
<lang 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 ","]</lang>
- 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