Pernicious numbers

From Rosetta Code
Task
Pernicious numbers
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 (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 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

Ada

Uses package Population_Count from Population count#Ada.

<lang 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)
  X := 888_888_877;
  while X <= 888_888_888 loop
     if Prime(Pop_Count(X)) then

Ada.Text_IO.Put(Num'Image(X)); 

     end if;
     X := X + 1;
  end loop;
  Ada.Text_IO.New_Line;

end;</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


AutoHotkey

Works with: AutoHotkey 1.1

<lang 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] }</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

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

Icon and Unicon

Works in both languages: <lang unicon>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</lang>

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 (thru taken from the Loops/Downward for task).

<lang J>ispernicious=: 1 p: +/"1@#:

thru=: <./ + 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


Mathematica

<lang Mathematica>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</lang>

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}


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

Translation of: C

<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>

Racket

<lang 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)))</lang>
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

REXX

Programming note:   to increase the size of the numbers being tested (to greater than 30 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. <lang rexx>/*REXX program displays a number of pernicious numbers and also a range.*/ numeric digits 30 /*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 "  ? " " " " */ if H== | H==',' then H=888888888 /*H "  ? " " " " */ say 'The 1st ' N " pernicious numbers are:" /*display a nice title.*/ say pernicious(1,,N) /*get all pernicious # from 1──►N*/ say /*display a blank line for a sep.*/ 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 done.*/ /*──────────────────────────────────D2B subroutine──────────────────────*/ d2b: return word(strip(x2b(d2x(arg(1))),'L',0) 0,1) /*convert dec──►bin*/ /*──────────────────────────────────PERNICIOUS subroutine───────────────*/ pernicious: procedure; parse arg bot,top,m /*get the bot & top #s, limit*/ _ = 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 !.=0; do k=1 until p=; p=word(_,k); !.p=1; end /*gen low prime array*/ if m== then m=999999999 /*assume an "infinite" limit. */ if top== then top=999999999 /*assume an "infinite" top limit.*/

  1. =0 /*number of pernicious #s so far.*/

$=; do j=bot to top until #==m /*gen pernicious until satisfied.*/ 

    pc=popCount(j)                    /*obtain population count for  J.*/
    if \!.pc  then iterate            /*if popCount ¬ in !.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 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

Ruby

<lang ruby>require "prime"

class Integer 

 def popcount
   to_s(2).count("1")
 end

 def pernicious?
   popcount.prime?
 end

end

bignum = 1 << 64

p (1..bignum).lazy.select(&:pernicious?).take(25).to_a p ( 888888877..888888888).select(&:pernicious?)</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]

Scala

<lang 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(",") )

}</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

Tcl

Library: Tcllib (Package: math::numtheory)

<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 largest number of bits is 30. <lang zkl>var 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()}</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 primes=T(2,3,5,7,11,13,17,19,23,29,31,37,41); fcn p(n){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)
Retrieved from "https://rosettacode.org/wiki/Pernicious_numbers?oldid=241956"