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
D
<lang 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;
}</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]
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: <lang d>uint.max.iota.filter!pernicious.walkLength.writeln;</lang>
Go
<lang 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()
}</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
J
Implementation:
<lang J>ispernicious=: 1 p: +/"1@#:
thru=: [ + 1 i.@+ -~</lang>
Task:
<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
888888877 + I. ispernicious 888888877 thru 888888888
888888877 888888878 888888880 888888883 888888885 888888886</lang>
Java
<lang 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 + " "); } }
}</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
<lang perl>sub is_pernicious {
my $n = shift; my $c = 2693408940; 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;</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
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
Python
<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} >>> 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]
>>> </lang>
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
zkl
The GNU bignum library counts the number of 1s in a number so use that. The largest number of bits is 30. <lang zkl>var BN=Import("zklBigNum"); var primes=T(2,3,5,7,11,13,17,19,23,29,31,37,41); N:=0;foreach n in ([2..]){
if (BN(n).num1s() : primes.holds(_)) { print(n," "); if((N+=1) == 25) break; }
} foreach n in ([0d888888877..888888888]){
if (BN(n).num1s() : primes.holds(_)) "%,d; ".fmt(n).print()}</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 888,888,877; 888,888,878; 888,888,880; 888,888,883; 888,888,885; 888,888,886;
Or in a more functional style <lang zkl>var BN=Import("zklBigNum"); var primes=T(2,3,5,7,11,13,17,19,23,29,31,37,41); fcn p(n){BN(n).num1s() : primes.holds(_)} [1..].filter(25,p).toString(*).println(); [0d888888877..888888888].filter(p).println();</lang>
- 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)