Population count

Population count 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.

population count, evil numbers, odious numbers

definitions

The population count (also known as pop count)   is the number of 1's (ones) in the binary representation of an non-negative integer.

I.E.:     5   (which is   101   in binary)   has a population count of   2.

Population counts are normally restricted to non-negative integers, which will be the case for this Rosetta Code task.

Evil numbers   are non-negative integers   that have an even number of 1s (ones) in their binary representation of the number.

Odious numbers   are   positive integers   that have an odd   number of 1s (ones) in their binary representation of the number.

task requirements

• write a function (or routine) to return the population count of a non-negative integer.
• all lists below should start with 0 (zero).

• display the pop count of the 1^st thirty powers of 3     (3⁰   3¹   3²   3³   3⁴ ···).
• display the 1^st thirty   evil   numbers.
• display the 1^st thirty   odious   numbers.

• display each list of integers on one line   (which may or may not include a title).

See also

• Sequence A000069 odious numbers on The On-Line Encyclopedia of Integer Sequences.
• Sequence A001969 evil numbers on The On-Line Encyclopedia of Integer Sequences.
• Entry evil number on The Eric Weisstein's World of Mathematics (TM).
• Entry odious number on The Eric Weisstein's World of Mathematics (TM).

PARI/GP

<lang parigp>vector(30,n,hammingweight(3^(n-1))) od=select(n->hammingweight(n)%2,[1..100]); ev=setminus([1..100],od); ev[1..30] od[1..30]</lang>

Output:

%1 = [1, 2, 2, 4, 3, 6, 6, 5, 6, 8, 9, 13, 10, 11, 14, 15, 11, 14, 14, 17, 17, 20, 19, 22, 16, 18, 24, 30, 25, 25]
%2 = [3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58, 60]
%3 = [1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59]

Python

<lang python>>>> def popcount(n): return bin(n).count("1") ... >>> [popcount(3**i) for i in range(30)] [1, 2, 2, 4, 3, 6, 6, 5, 6, 8, 9, 13, 10, 11, 14, 15, 11, 14, 14, 17, 17, 20, 19, 22, 16, 18, 24, 30, 25, 25] >>> evil, odious, i = [], [], 0 >>> while len(evil) < 30 or len(odious) < 30: ... p = popcount(i) ... if p % 2: odious.append(i) ... else: evil.append(i) ... i += 1 ... >>> evil[:30] [0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58] >>> odious[:30] [1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59] >>> </lang>

REXX

<lang rexx>/*REXX program counts the (binary) bits in the binary version of a dec#,*/ /* and also generates a specific number of EVIL and ODIOUS numbers. */ parse arg N B . /*get optional arguments, N and B*/ if N== | N==',' then N=30 /*N given? Then use the default.*/ if B== | B==',' then B= 3 /*B given? Then use the default.*/ numeric digits 3000 /*support most gi-normus numbers.*/ numeric digits max(20,length(B**N)) /*whittle the precision to size. */

                                      /* [↑]  a little calc for sizing.*/

$=; do j=0 for N /*generate N popCounts for powers*/

    $=$ popCount(B**j)                /*get the popCount for a pow of B*/
    end   /*j*/                       /* [↑]  append popCount to a list*/
                                      /* [↓]  display the pop counts.  */

call showList 'powers of' B /*display the list with a header.*/

    do j=0  until  #==N               /*generate  N  evil  numbers.    */
    if popCount(j)//2  then iterate   /*if  odd population count, skip.*/
    #=#+1                             /*bump the  evil  number counter.*/
    $=$ j                             /*append an   evil #   to a list.*/
    end   /*j*/                       /* [↑]  build a list of evil #s. */
                                      /* [↓]  display the evil # list. */

call showList 'evil numbers' /*display the list with a header.*/

    do j=0  until  #==N               /*generate  N  odious  numbers.  */
    if popCount(j)//2==0 then iterate /*if even population count, skip.*/
    #=#+1                             /*bump the odious number counter.*/
    $=$ j                             /*append an  odious #  to a list.*/
    end   /*j*/                       /* [↑]  build a list of odious #s*/
                                      /* [↓]  display the odious# list.*/

call showList 'odious numbers' /*display the list with a header.*/ 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*/ /*──────────────────────────────────POPCOUNT subroutine─────────────────*/ popCount: procedure;_=d2b(abs(arg(1))) /*convert the # passed to binary.*/ return length(_)-length(space(translate(_,,1),0)) /*count the one bits.*/ /*──────────────────────────────────SHOWLIST subroutine─────────────────*/ showlist: say; say 'The 1st' N arg(1)':'; say substr($,2); #=0; $=; return</lang> output   when using the default input:

The 1st 30 powers of 3:
1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25

The 1st 30 evil numbers:
0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58

The 1st 30 odious numbers:
1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59