Population count

The (last) requirement of this draft task has been changed.

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

For example,

5

(which is 101 in binary) has a population count of

2

.

Evil numbers are non-negative integers that have an even population count;
odious numbers are positive integers that have an odd population count.

Task requirements

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

display the pop count of the 1^st thirty powers of $3$ ( $3^{0},3^{1},3^{2},3^{3},3^{4},\ldots$ ).
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), each set of integers being shown should be properly identified.

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.

C

Works with: GCC

<lang c>#include <stdio.h>

int main() {

 {
   unsigned long long n = 1;
   for (int i = 0; i < 30; i++) {
     // __builtin_popcount() for unsigned int
     // __builtin_popcountl() for unsigned long
     // __builtin_popcountll() for unsigned long long
     printf("%d ", __builtin_popcountll(n));
     n *= 3;
   }
   printf("\n");
 }

 int od[30];
 int ne = 0, no = 0;
 printf("evil  : ");
 for (int n = 0; ne+no < 60; n++) {
   if ((__builtin_popcount(n) & 1) == 0) {
     if (ne < 30) {

printf("%d ", n); ne++;

     }
   } else {
     if (no < 30) {

od[no++] = n;

     }
   }
 }
 printf("\n");
 printf("odious: ");
 for (int i = 0; i < 30; i++) {
   printf("%d ", od[i]);
 }
 printf("\n");

 return 0;

}</lang>

Output:

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

C++

Works with: C++11

<lang cpp>#include <iostream>

include <bitset>
include <climits>

size_t popcount(unsigned long long n) {

 return std::bitset<CHAR_BIT * sizeof n>(n).count();

}

int main() {

 {
   unsigned long long n = 1;
   for (int i = 0; i < 30; i++) {
     std::cout << popcount(n) << " ";
     n *= 3;
   }
   std::cout << std::endl;
 }

 int od[30];
 int ne = 0, no = 0;
 std::cout << "evil  : ";
 for (int n = 0; ne+no < 60; n++) {
   if ((popcount(n) & 1) == 0) {
     if (ne < 30) {

std::cout << n << " "; ne++;

     }
   } else {
     if (no < 30) {

od[no++] = n;

     }
   }
 }
 std::cout << std::endl;
 std::cout << "odious: ";
 for (int i = 0; i < 30; i++) {
   std::cout << od[i] << " ";
 }
 std::cout << std::endl;

 return 0;

}</lang>

Output:

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

This example may be incorrect due to a recent change in the task requirements or a lack of testing. Please verify it and remove this message. If the example does not match the requirements or does not work, replace this message with Template:incorrect or fix the code yourself.

<lang d>void main() {

   import std.stdio, std.algorithm, std.range, core.bitop;

   const pCount = (ulong n) => popcnt(cast(uint)n) + popcnt(n >> 32);
   uint.max.iota.map!(i => pCount(3L ^^ i)).take(30).writeln;
   uint.max.iota.filter!(i => pCount(i) % 2 == 0).take(30).writeln;
   uint.max.iota.filter!(i => pCount(i) % 2).take(30).writeln;

}</lang>

Output:

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

Erlang

<lang erlang>-module(population_count). -export([popcount/1]).

-export([task/0]).

popcount(N) ->

   popcount(N,0).

popcount(0,Acc) ->

   Acc;

popcount(N,Acc) ->

   popcount(N div 2, Acc + N rem 2).

threes(_,0,Acc) ->

   lists:reverse(Acc);

threes(Threes,N,Acc) ->

   threes(Threes * 3, N-1, [popcount(Threes)|Acc]).

threes(N) ->

   threes(1,N,[]).

evil(_,0,Acc) ->

   lists:reverse(Acc);

evil(N,Count,Acc) ->

   case popcount(N) rem 2 of
       0 ->
           evil(N+1,Count-1,[N|Acc]);
       1 ->
           evil(N+1,Count,Acc)
   end.

evil(Count) ->

   evil(0,Count,[]).

odious(_,0,Acc) ->

   lists:reverse(Acc);

odious(N,Count,Acc) ->

   case popcount(N) rem 2 of
       1 ->
           odious(N+1,Count-1,[N|Acc]);
       0 ->
           odious(N+1,Count,Acc)
   end.

odious(Count) ->

   odious(1,Count,[]).

task() ->

   io:format("~p~n",[threes(30)]),
   io:format("Evil:~p~n",[evil(30)]),
   io:format("Odious:~p~n",[odious(30)]).</lang>

Output:

<lang erlang>61> population_count:task(). [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:[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:[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]

ok</lang>

Go

This example may be incorrect due to a recent change in the task requirements or a lack of testing. Please verify it and remove this message. If the example does not match the requirements or does not work, replace this message with Template:incorrect or fix the code yourself.

<lang go>package main

import "fmt"

func pop64(w uint64) int {

   const (
       ff    = 1<<64 - 1
       mask1 = ff / 3
       mask3 = ff / 5
       maskf = ff / 17
       maskp = maskf >> 3 & maskf
   )
   w -= w >> 1 & mask1
   w = w&mask3 + w>>2&mask3
   w = (w + w>>4) & maskf
   return int(w * maskp >> 56)

}

func main() {

   n := uint64(1) // 3^0
   for i := 0; i < 30; i++ {
       fmt.Printf("%d ", pop64(n))
       n *= 3
   }
   fmt.Println()
   var od [30]uint64
   var ne, no int
   for n = 0; ne+no < 60; n++ {
       if pop64(n)&1 == 0 {
           if ne < 30 {
               fmt.Printf("%d ", n)
               ne++
           }
       } else {
           if no < 30 {
               od[no] = n
               no++
           }
       }
   }
   fmt.Println()
   for _, n := range od {
       fmt.Printf("%d ", n)
   }
   fmt.Println()

}</lang>

Output:

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

Haskell

This example may be incorrect due to a recent change in the task requirements or a lack of testing. Please verify it and remove this message. If the example does not match the requirements or does not work, replace this message with Template:incorrect or fix the code yourself.

Works with: GHC version 7.4+

<lang haskell>import Data.Bits (popCount)

main :: IO () main = do

 print $ take 30 $ map popCount $ iterate (* 3) (1 :: Integer)
 print $ take 30 $ filter (even . popCount) ([0..] :: [Integer])
 print $ take 30 $ filter (odd . popCount) ([0..] :: [Integer])</lang>

Output:

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

J

Implementation:

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

Task:

<lang J> pcount 3^i.30x 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

  30{.(#~ 1=2|pcount) i. 100 NB. odd population count (aka "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

  30{.(#~ 0=2|pcount) i. 100 NB. even population count (aka "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</lang>

Java

<lang java>import java.math.BigInteger;

public class PopCount {

   public static void main(String[] args) {

{ // with int System.out.print("32-bit integer: "); int n = 1; for (int i = 0; i < 20; i++) { System.out.printf("%d ", Integer.bitCount(n)); n *= 3; } System.out.println(); } { // with long System.out.print("64-bit integer: "); long n = 1; for (int i = 0; i < 30; i++) { System.out.printf("%d ", Long.bitCount(n)); n *= 3; } System.out.println(); } { // with BigInteger System.out.print("big integer : "); BigInteger n = BigInteger.ONE; BigInteger three = BigInteger.valueOf(3); for (int i = 0; i < 30; i++) { System.out.printf("%d ", n.bitCount()); n = n.multiply(three); } System.out.println(); }

int[] od = new int[30]; int ne = 0, no = 0; System.out.print("evil : "); for (int n = 0; ne+no < 60; n++) { if ((Integer.bitCount(n) & 1) == 0) { if (ne < 30) { System.out.printf("%d ", n); ne++; } } else { if (no < 30) { od[no++] = n; } } } System.out.println(); System.out.print("odious : "); for (int n : od) { System.out.printf("%d ", n); } System.out.println();

}</lang>

Output:

32-bit integer: 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 
64-bit integer: 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 
big integer   : 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   : 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 : 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

PARI/GP

This example is incorrect. Please fix the code and remove this message.

Details:
The output for EVIL numbers is missing zero.

This example may be incorrect due to a recent change in the task requirements or a lack of testing. Please verify it and remove this message. If the example does not match the requirements or does not work, replace this message with Template:incorrect or fix the code yourself.

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

Perl

Translation of: Perl 6

We'll emulate infinite lists with closures.

<lang perl>use strict; use warnings;

sub population_count {

   my $n = shift;
   die "argument can't be negative" if $n < 0;
   my $c;
   for ($c = 0; $n; $n >>= 1) { 
       $c += $n & 1; 
   } 
   $c;

}

print join ' ', map { population_count(3**$_) } 0 .. 30 - 1; print "\n"; sub evil {

   my $i = 0;
   sub { $i++ while population_count($i) % 2; $i++ }

} sub odious {

   my $i = 0;
   sub { $i++ until population_count($i) % 2; $i++ }

}

my ($evil, $odious) = (evil, odious); my (@evil, @odious); for (1 .. 30) {

   push @evil, $evil->();
   push @odious, $odious->();

}

printf "Evil : %s\n", join ' ', @evil; printf "Odious: %s\n", join ' ', @odious;</lang>

Output:

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

Perl 6

This example may be incorrect due to a recent change in the task requirements or a lack of testing. Please verify it and remove this message. If the example does not match the requirements or does not work, replace this message with Template:incorrect or fix the code yourself.

<lang perl6>sub population-count(Int $n where * >= 0) { [+] $n.base(2).comb }

say map &population-count, 3 «**« ^30; say (grep { population-count($_) %% 2 }, 0 .. *)[^30]; say (grep { population-count($_) % 2 }, 0 .. *)[^30];</lang>

Output:

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

That's the convenient way to write it, but the following avoids string processing and is therefore about twice as fast: <lang perl6>sub population-count(Int $n is copy where * >= 0) {

   loop (my $c = 0; $n; $n +>= 1) { 
       $c += $n +& 1; 
   } 
   $c;

}</lang>

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 'popcounts of the powers of' B /*display list with hdr.*/

    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 popcounts of the 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

Tcl

Works with: Tcl version 8.6

<lang tcl>package require Tcl 8.6

proc hammingWeight {n} {

   tcl::mathop::+ {*}[split [format %llb $n] ""]

} for {set n 0;set l {}} {$n<30} {incr n} {

   lappend l [hammingWeight [expr {3**$n}]]

} puts "p3: $l" for {set n 0;set e [set o {}]} {[llength $e]<30||[llength $o]<30} {incr n} {

   lappend [expr {[hammingWeight $n]&1 ? "o" : "e"}] $n

} puts "evil: [lrange $e 0 29]" puts "odious: [lrange $o 0 29]"</lang>

Output:

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