Pernicious numbers

From Rosetta Code
Revision as of 16:07, 26 March 2014 by rosettacode>Gerard Schildberger (→‎{{header|REXX}}: extended the internal list of low primes in isPrime function, corrected a couple of wrong glyphs used.)
Pernicious numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

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

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>

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: too low.*/ lp='2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67' /*low primes.*/ if wordpos(x,lp)\==0 then return 1 /*X is prime.*/ if x//2==0 then return 0; if x//3==0 then return 0 /*X is¬prime.*/ 

            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.*/

  1. =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 &nbsp 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

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]

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=241940"