CloudFlare suffered a massive security issue affecting all of its customers, including Rosetta Code. All passwords not changed since February 19th 2017 have been expired, and session cookie longevity will be reduced until late March.--Michael Mol (talk) 05:15, 25 February 2017 (UTC)

Population count

From Rosetta Code
Task
Population count
You are encouraged to solve this task according to the task description, using any language you may know.

The population count   is the number of   1s   (ones)   in the binary representation of a non-negative integer.

Population count is also known as   pop count,   popcount,   sideways sum,   and   Hamming weight.

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
  • 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 indexed).
  • display the   pop count   of the   1st   thirty powers of   3       (30,   31,   32,   33,   34,   ∙∙∙   329).
  • display the   1st   thirty     evil     numbers.
  • display the   1st   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



Ada[edit]

Specification and implementation of an auxiliary package "Population_Count". The same package is used for Pernicious numbers#Ada

with Interfaces;
 
package Population_Count is
subtype Num is Interfaces.Unsigned_64;
function Pop_Count(N: Num) return Natural;
end Population_Count;
package body Population_Count is
 
function Pop_Count(N: Num) return Natural is
use Interfaces;
K5555: constant Unsigned_64 := 16#5555555555555555#;
K3333: constant Unsigned_64 := 16#3333333333333333#;
K0f0f: constant Unsigned_64 := 16#0f0f0f0f0f0f0f0f#;
K0101: constant Unsigned_64 := 16#0101010101010101#;
X: Unsigned_64 := N;
begin
X := X - (Shift_Right(X, 1) and k5555);
X := (X and k3333) + (Shift_Right(X, 2) and k3333);
X := (X + (Shift_Right(X, 4)) and K0f0f);
X := Shift_Right((x * k0101), 56);
return Natural(X);
end Pop_Count;
 
end Population_Count;

The main program:

with Ada.Text_IO, Population_Count; use Ada.Text_IO; use Population_Count;
 
procedure Test_Pop_Count is
 
X: Num; use type Num;
 
begin
Put("Pop_Cnt(3**i):"); -- print pop_counts of powers of three
X := 1; -- X=3**0
for I in 1 .. 30 loop
Put(Natural'Image(Pop_Count(X)));
X := X * 3;
end loop;
New_Line;
 
Put("Evil: "); -- print first thirty evil numbers
X := 0;
for I in 1 .. 30 loop
while Pop_Count(X) mod 2 /= 0 loop -- X is not evil
X := X + 1;
end loop;
Put(Num'Image(X));
X := X + 1;
end loop;
New_Line;
 
Put("Odious: "); -- print thirty oudous numbers
X := 1;
for I in 1 .. 30 loop
while Pop_Count(X) mod 2 /= 1 loop -- X is not odious
X := X + 1;
end loop;
Put(Num'Image(X));
X := X + 1;
end loop;
New_Line;
end Test_Pop_Count;
Output:
Pop_Cnt(3**i): 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

ALGOL 68[edit]

# returns the population count (number of bits on) of the non-negative       #
# integer n #
PROC population count = ( LONG INT n )INT:
BEGIN
LONG INT number := n;
INT result := 0;
WHILE number > 0 DO
IF ODD number THEN result +:= 1 FI;
number OVERAB 2
OD;
result
END # population # ;
 
# population count of 3^0, 3^1, 3*2, ..., 3^29 #
LONG INT power of three := 1;
print( ( "3^x pop counts:" ) );
FOR power FROM 0 TO 29 DO
print( ( " ", whole( population count( power of three ), 0 ) ) );
power of three *:= 3
OD;
print( ( newline ) );
# print the first thirty evil numbers (even population count) #
INT evil count := 0;
print( ( "evil numbers  :" ) );
FOR n FROM 0 WHILE evil count < 30 DO
IF NOT ODD population count( n ) THEN
print( ( " ", whole( n, 0 ) ) );
evil count +:= 1
FI
OD;
print( ( newline ) );
# print the first thirty odious numbers (odd population count) #
INT odious count := 0;
print( ( "odious numbers:" ) );
FOR n WHILE odious count < 30 DO
IF ODD population count( n ) THEN
print( ( " ", whole( n, 0 ) ) );
odious count +:= 1
FI
OD;
print( ( newline ) )
 
Output:
3^x pop counts: 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 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
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

AppleScript[edit]

Translation of: JavaScript
-- popCount :: Int -> Int
on popCount(n)
script bitSum
on lambda(a, x)
a + (x as integer)
end lambda
end script
 
foldl(bitSum, 0, characters of showIntAtBase(n, 2))
end popCount
 
 
-- TEST
on run
script powerOfThreePopCount
on lambda(x)
popCount(3 ^ x)
end lambda
end script
 
script popCountisEven
on lambda(x)
popCount(x) mod 2 = 0
end lambda
end script
 
{popCounts:¬
map(powerOfThreePopCount, range(0, 30)), evenThenOdd:¬
partition(popCountisEven, range(0, 59))} ¬
 
end run
 
 
---------------------------------------------------------------------------
 
-- GENERIC FUNCTIONS
 
-- showIntAtBase :: Int -> Int -> String
on showIntAtBase(n, base)
if base > 1 then
if n > 0 then
set m to n mod base
set r to n - m
if r > 0 then
set prefix to showIntAtBase(r div base, base)
else
set prefix to ""
end if
 
if m < 10 then
set baseCode to 48 -- "0"
else
set baseCode to 55 -- "A" - 10
end if
 
prefix & character id (baseCode + m)
else
"0"
end if
else
missing value
end if
end showIntAtBase
 
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to lambda(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
 
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to lambda(item i of xs, i, xs)
end repeat
return lst
end tell
end map
 
-- partition :: predicate -> List -> (Matches, nonMatches)
-- partition :: (a -> Bool) -> [a] -> ([a], [a])
on partition(f, xs)
tell mReturn(f)
set lst to {{}, {}}
repeat with x in xs
set v to contents of x
set end of item ((lambda(v) as integer) + 1) of lst to v
end repeat
end tell
{item 2 of lst, item 1 of lst}
end partition
 
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property lambda : f
end script
end if
end mReturn
 
-- range :: Int -> Int -> [Int]
on range(m, n)
if n < m then
set d to -1
else
set d to 1
end if
set lst to {}
repeat with i from m to n by d
set end of lst to i
end repeat
return lst
end range
Output:
{popCounts:
{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, 25},
evenThenOdd:
{{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}}}

AutoHotkey[edit]

Loop, 30
Out1 .= PopCount(3 ** (A_Index - 1)) " "
Loop, 60
i := A_Index - 1
, PopCount(i) & 0x1 ? Out3 .= i " " : Out2 .= i " "
MsgBox, % "3^x:`t" Out1 "`nEvil:`t" Out2 "`nOdious:`t" Out3
 
PopCount(x) { ;https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation
x -= (x >> 1) & 0x5555555555555555
, x := (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
, x := (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
return (x * 0x0101010101010101) >> 56
}
Output:
3^x:	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[edit]

Works with: GCC
#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;
}
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 


GCC's builtin doesn't exist prior to 3.4, and the LL version is broken in 3.4 to 4.1. In 4.2+, if the platform doesn't have a good popcount instruction or isn't enabled (e.g. not compiled with -march=native), it typically emits unoptimized code which is over 2x slower than the C below. Alternative:

#if defined(__POPCNT__) && defined(__GNUC__) && (__GNUC__> 4 || (__GNUC__== 4 && __GNUC_MINOR__> 1))
#define HAVE_BUILTIN_POPCOUNTLL
#endif
static uint64_t bitcount64(uint64_t b) {
b -= (b >> 1) & 0x5555555555555555;
b = (b & 0x3333333333333333) + ((b >> 2) & 0x3333333333333333);
b = (b + (b >> 4)) & 0x0f0f0f0f0f0f0f0f;
return (b * 0x0101010101010101) >> 56;
}
/* For 32-bit, an 8-bit table may or may not be a little faster */
static uint32_t bitcount32(uint32_t b) {
b -= (b >> 1) & 0x55555555;
b = (b & 0x33333333) + ((b >> 2) & 0x33333333);
b = (b + (b >> 4)) & 0x0f0f0f0f;
return (b * 0x01010101) >> 24;
}

C++[edit]

Works with: C++11
#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;
}
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#[edit]

 
using System;
using System.Linq;
 
namespace PopulationCount
{
class Program
{
private static int PopulationCount(long n)
{
string binaryn = Convert.ToString(n, 2);
return binaryn.ToCharArray().Where(t => t == '1').Count();
}
 
static void Main(string[] args)
{
Console.WriteLine("Population Counts:");
Console.Write("3^n : ");
 
int count = 0;
 
while (count < 30)
{
double n = Math.Pow(3f, (double)count);
int popCount = PopulationCount((long)n);
Console.Write(string.Format("{0} ", popCount));
count++;
}
 
Console.WriteLine();
Console.Write("Evil: ");
 
count = 0;
int i = 0;
 
while (count < 30)
{
int popCount = PopulationCount(i);
 
if (popCount % 2 == 0)
{
count++;
Console.Write(string.Format("{0} ", i));
}
 
i++;
}
 
Console.WriteLine();
Console.Write("Odious: ");
 
count = 0;
i = 0;
 
while (count < 30)
{
int popCount = PopulationCount(i);
 
if (popCount % 2 != 0)
{
count++;
Console.Write(string.Format("{0} ", i));
}
 
i++;
}
 
Console.ReadKey();
}
}
}
 
Output:
Population Counts:
3^n :   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

Common Lisp[edit]

(format T "3^x: ~{~a ~}~%" 
(loop for i below 30
collect (logcount (expt 3 i))))
 
(multiple-value-bind
(evil odious)
(loop for i below 60
if (evenp (logcount i)) collect i into evil
else collect i into odious
finally (return (values evil odious)))
(format T "evil: ~{~a ~}~%" evil)
(format T "odious: ~{~a ~}~%" odious))
Output:
3^x: 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

D[edit]

void main() {
import std.stdio, std.algorithm, std.range, core.bitop;
 
enum pCount = (ulong n) => popcnt(n & uint.max) + popcnt(n >> 32);
writefln("%s\nEvil: %s\nOdious: %s",
uint.max.iota.map!(i => pCount(3L ^^ i)).take(30),
uint.max.iota.filter!(i => pCount(i) % 2 == 0).take(30),
uint.max.iota.filter!(i => pCount(i) % 2).take(30));
}
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]

Elixir[edit]

Translation of: Ruby
defmodule Population do
def count(n) do
Integer.to_string(n,2) |> to_char_list |> Enum.count(&(&1 == ?1))
end
 
def evil?(n), do: n >= 0 and rem(count(n),2) == 0
 
def odious?(n), do: n >= 0 and rem(count(n),2) == 1
end
 
IO.puts "Population count of the first thirty powers of 3:"
IO.inspect Stream.iterate(1, &(&1*3)) |> Enum.take(30) |> Enum.map(&Population.count(&1))
IO.puts "first thirty evil numbers:"
IO.inspect Stream.iterate(0, &(&1+1)) |> Stream.filter(&Population.evil?(&1)) |> Enum.take(30)
IO.puts "first thirty odious numbers:"
IO.inspect Stream.iterate(0, &(&1+1)) |> Stream.filter(&Population.odious?(&1)) |> Enum.take(30)
Output:
Population count of the first thirty 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]
first thirty 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]
first thirty 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]

Erlang[edit]

-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("Powers of 3: ~p~n",[threes(30)]),
io:format("Evil:~p~n",[evil(30)]),
io:format("Odious:~p~n",[odious(30)]).
Output:
61> population_count:task().
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]
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

Fortran[edit]

Works with: Fortran version 95 and later
program population_count
implicit none
 
integer, parameter :: i64 = selected_int_kind(18)
integer(i64) :: x
integer :: i, n
 
x = 1
write(*, "(a8)", advance = "no") "3**i :"
do i = 1, 30
write(*, "(i3)", advance = "no") popcnt(x)
x = x * 3
end do
 
write(*,*)
write(*, "(a8)", advance = "no") "Evil :"
n = 0
x = 0
do while(n < 30)
if(mod(popcnt(x), 2) == 0) then
n = n + 1
write(*, "(i3)", advance = "no") x
end if
x = x + 1
end do
 
write(*,*)
write(*, "(a8)", advance = "no") "Odious :"
n = 0
x = 0
do while(n < 30)
if(mod(popcnt(x), 2) /= 0) then
n = n + 1
write(*, "(i3)", advance = "no") x
end if
x = x + 1
end do
 
contains
 
integer function popcnt(x)
integer(i64), intent(in) :: x
integer :: i
 
popcnt = 0
do i = 0, 63
if(btest(x, i)) popcnt = popcnt + 1
end do
 
end function
end program
Output:
  3**i : 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

Go[edit]

Method of WP example popcount_3. Probably fastest on machines with fast integer multiplication for data with lots of 1 bits.

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() {
fmt.Println("Pop counts, powers of 3:")
n := uint64(1) // 3^0
for i := 0; i < 30; i++ {
fmt.Printf("%d ", pop64(n))
n *= 3
}
fmt.Println()
fmt.Println("Evil numbers:")
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()
fmt.Println("Odious numbers:")
for _, n := range od {
fmt.Printf("%d ", n)
}
fmt.Println()
}
Output:
Pop counts, 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 
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 
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

Method of WP example popcount_4. Simpler and often faster for data with mostly 0 bits.

func pop64(w uint64) (c int) {
for w != 0 {
w &= w - 1
c++
}
return
}

Haskell[edit]

Works with: GHC version 7.4+
import Data.Bits (popCount)
 
printPops :: (Show a, Integral a) => String -> [a] -> IO ()
printPops title counts = putStrLn $ title ++ show (take 30 counts)
 
main :: IO ()
main = do
printPops "popcount " $ map popCount $ iterate (*3) (1 :: Integer)
printPops "evil " $ filter (even . popCount) ([0..] :: [Integer])
printPops "odious " $ filter ( odd . popCount) ([0..] :: [Integer])
Output:
popcount [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]

J[edit]

Implementation:

countPopln=: +/"1@#:
isOdd=: 1 = 2&|
isEven=: 0 = 2&|


Task:

   countPopln 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{.(#~ [email protected]) 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{.(#~ [email protected]) 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

Java[edit]

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();
}
}
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 

JavaScript[edit]

ES6[edit]

(() => {
'use strict';
 
// popCount :: Int -> Int
const popCount = n =>
n.toString(2)
.split('')
.reduce((a, x) => a + (x === '1' ? 1 : 0), 0);
 
// range :: Int -> Int -> [Int]
const range = (m, n) =>
Array.from({
length: Math.floor(n - m) + 1
}, (_, i) => m + i);
 
 
// until :: (a -> Bool) -> (a -> a) -> a -> a
const until = (p, f, x) => {
let v = x;
while (!p(v)) v = f(v);
return v;
}
 
 
// { popCounts : [Int], evenThenOdd : ([Int], [Int]) }
return {
popCounts: range(0, 30)
.map(x => popCount(Math.pow(3, x))),
 
evenThenOdd: until(
m => m.evod[0].length >= 30 && m.evod[1].length >= 30,
m => ({
x: m.x + 1,
evod: popCount(m.x) % 2 === 0 ? (
[m.evod[0].concat(m.x), m.evod[1]]
) : [m.evod[0], m.evod[1].concat(m.x)]
}), {
x: 0,
evod: [
[],
[]
]
}
).evod
};
})();
Output:
{"popCounts":[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, 25],
"evenThenOdd":[
[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]]}

jq[edit]

Works with: jq version 1.4
def popcount: 
def bin: recurse( if . == 0 then empty else ./2 | floor end ) % 2;
[bin] | add;
 
def firstN(count; condition):
if count > 0 then
if condition then ., (1+.| firstN(count-1; condition))
else (1+.) | firstN(count; condition)
end
else empty
end;
 
def task:
def pow(n): . as $m | reduce range(0;n) as $i (1; . * $m);
 
"The pop count of the first thirty powers of 3:",
[range(0;30) as $n | 3 | pow($n) | popcount],
 
"The first thirty evil numbers:",
[0 | firstN(30; (popcount % 2) == 0)],
 
"The first thirty odious numbers:",
[0 | firstN(30; (popcount % 2) == 1)]
;
 
task
Output:
$ jq -n -r -c -f Population_count.jq
The pop count of the first thirty 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 first thirty 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 first thirty 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]

Julia[edit]

julia> popcount(n) = sum(digits(n,2)) ; show([popcount(3^n) for n =0:29])
[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]
 
julia> println("evil numbers:") ; show(filter(x->iseven(popcount(x)), [0:59]))
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]
 
julia> println("odious numbers:") ; show(filter(x->isodd(popcount(x)), [0:59]))
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]

Kotlin[edit]

// version 1.0.6
 
fun popCount(n: Long) = when {
n < 0L -> throw IllegalArgumentException("n must be non-negative")
else -> java.lang.Long.bitCount(n)
}
 
fun main(args: Array<String>) {
println("The population count of the first 30 powers of 3 are:")
var pow3 = 1L
for (i in 1..30) {
print("${popCount(pow3)} ")
pow3 *= 3L
}
println("\n")
println("The first thirty evil numbers are:")
var count = 0
var i = 0
while (true) {
val pc = popCount(i.toLong())
if (pc % 2 == 0) {
print("$i ")
if (++count == 30) break
}
i++
}
println("\n")
println("The first thirty odious numbers are:")
count = 0
i = 1
while (true) {
val pc = popCount(i.toLong())
if (pc % 2 == 1) {
print("$i ")
if (++count == 30) break
}
i++
}
println()
}
Output:
The population count of the first 30 powers of 3 are:
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 first thirty evil numbers are:
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 first thirty odious numbers are:
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

Lua[edit]

-- Take decimal number, return binary string
function dec2bin (n)
local bin, bit = ""
while n > 0 do
bit = n % 2
n = math.floor(n / 2)
bin = bit .. bin
end
return bin
end
 
-- Take decimal number, return population count as number
function popCount (n)
local bin, count = dec2bin(n), 0
for pos = 1, bin:len() do
if bin:sub(pos, pos) == "1" then count = count + 1 end
end
return count
end
 
-- Implement task requirements
function firstThirty (mode)
local numStr, count, n, remainder = "", 0, 0
if mode == "Evil" then remainder = 0 else remainder = 1 end
while count < 30 do
if mode == "3^x" then
numStr = numStr .. popCount(3 ^ count) .. " "
count = count + 1
else
if popCount(n) % 2 == remainder then
numStr = numStr .. n .. " "
count = count + 1
end
n = n + 1
end
end
print(mode .. ":" , numStr)
end
 
-- Main procedure
firstThirty("3^x")
firstThirty("Evil")
firstThirty("Odious")
Output:
3^x:    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

Mathematica[edit]

popcount[n_Integer] := IntegerDigits[n, 2] // Total
Print["population count of powers of 3"]
popcount[#] & /@ (3^Range[0, 30])
(*******)
evilQ[n_Integer] := popcount[n] // EvenQ
evilcount = 0;
evillist = {};
i = 0;
While[evilcount < 30,
If[evilQ[i], AppendTo[evillist, i]; evilcount++];
i++
]
Print["first thirty evil numbers"]
evillist
(*******)
odiousQ[n_Integer] := popcount[n] // OddQ
odiouscount = 0;
odiouslist = {};
i = 0;
While[odiouscount < 30,
If[odiousQ[i], AppendTo[odiouslist, i]; odiouscount++];
i++
]
Print["first thirty odious numbers"]
odiouslist
Output:
population count of 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, 25}
first thirty 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}
first thirty 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}

Oforth[edit]

: popcount(n)
0 while ( n ) [ n isOdd + n bitRight(1) ->n ] ;
 
: test
| i count |
30 seq map(#[ 3 swap 1- pow ]) map(#popcount) println
 
0 ->count
0 while( count 30 <> ) [ dup popcount isEven ifTrue: [ dup . count 1+ ->count ] 1+ ] drop printcr
 
0 ->count
0 while( count 30 <> ) [ dup popcount isOdd ifTrue: [ dup . count 1+ ->count ] 1+ ] drop ;
Output:
>test
[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 ok

PARI/GP[edit]

vector(30,n,hammingweight(3^(n-1)))
od=select(n->hammingweight(n)%2,[0..100]); ev=setminus([0..100],od);
ev[1..30]
od[1..30]
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 = [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]
%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]

Pascal[edit]

Works with: freepascal

Like Ada a unit is used.

unit popcount;
{$IFDEF FPC}
{$MODE DELPHI}
{$OPTIMIZATION ON,ASMCSE,CSE,PEEPHOLE}
{$Smartlink OFF}
{$ENDIF}
 
interface
function popcnt(n:Uint64):integer;overload;
function popcnt(n:Uint32):integer;overload;
function popcnt(n:Uint16):integer;overload;
function popcnt(n:Uint8):integer;overload;
 
implementation
const
//K1 = $0101010101010101;
K33 = $3333333333333333;
K55 = $5555555555555555;
KF1 = $0F0F0F0F0F0F0F0F;
KF2 = $00FF00FF00FF00FF;
KF4 = $0000FFFF0000FFFF;
KF8 = $00000000FFFFFFFF;
{
function popcnt64(n:Uint64):integer;
begin
n := n- (n shr 1) AND K55;
n := (n AND K33)+ ((n shr 2) AND K33);
n := (n + (n shr 4)) AND KF1;
n := (n*k1) SHR 56;
result := n;
end;
}

function popcnt(n:Uint64):integer;overload;
// on Intel Haswell 2x faster for fpc 32-Bit
begin
n := (n AND K55)+((n shr 1) AND K55);
n := (n AND K33)+((n shr 2) AND K33);
n := (n AND KF1)+((n shr 4) AND KF1);
n := (n AND KF2)+((n shr 8) AND KF2);
n := (n AND KF4)+((n shr 16) AND KF4);
n := (n AND KF8)+ (n shr 32);
result := n;
end;
 
function popcnt(n:Uint32):integer;overload;
var
c,b : NativeUint;
begin
b := n;
c := (b shr 1) AND NativeUint(K55); b := (b AND NativeUint(K55))+C;
c := ((b shr 2) AND NativeUint(K33));b := (b AND NativeUint(K33))+C;
c:= ((b shr 4) AND NativeUint(KF1)); b := (b AND NativeUint(KF1))+c;
c := ((b shr 8) AND NativeUint(KF2));b := (b AND NativeUint(KF2))+c;
c := b shr 16; b := (b AND NativeUint(KF4))+ C;
result := b;
end;
 
function popcnt(n:Uint16):integer;overload;
var
c,b : NativeUint;
begin
b := n;
c := (b shr 1) AND NativeUint(K55); b := (b AND NativeUint(K55))+C;
c :=((b shr 2) AND NativeUint(K33)); b := (b AND NativeUint(K33))+C;
c:= ((b shr 4) AND NativeUint(KF1)); b := (b AND NativeUint(KF1))+c;
c := b shr 8; b := (b AND NativeUint(KF2))+c;
result := b;
end;
 
function popcnt(n:Uint8):integer;overload;
var
c,b : NativeUint;
begin
b := n;
c := (b shr 1) AND NativeUint(K55); b := (b AND NativeUint(K55))+C;
c :=((b shr 2) AND NativeUint(K33));b := (b AND NativeUint(K33))+C;
c:= b shr 4;
result := (b AND NativeUint(KF1))+c;
end;
 
Begin
End.

The program

program pcntTest;
uses
sysutils,popCount;
 
function Odious(n:Uint32):boolean;inline;
Begin
Odious := boolean(PopCnt(n) AND 1)
end;
 
function EvilNumber(n:Uint32):boolean;inline;
begin
EvilNumber := boolean(NOT(PopCnt(n)) AND 1);
end;
 
var
s : String;
i : Uint64;
k : LongWord;
Begin
s :='PopCnt 3^i  :';
i:= 1;
For k := 1 to 30 do
Begin
s := s+InttoStr(PopCnt(i)) +' ';
i := 3*i;
end;
writeln(s);writeln;
 
s:='Evil numbers  :';i := 0;k := 0;
repeat
IF EvilNumber(i) then
Begin
inc(k);s := s+InttoStr(i) +' ';
end;
inc(i);
until k = 30;
writeln(s);writeln;s:='';
 
 
s:='Odious numbers :';i := 0;k := 0;
repeat
IF Odious(i) then
Begin
inc(k);s := s+InttoStr(i) +' ';
end;
inc(i);
until k = 30;
writeln(s);
end.
Output
PopCnt 3^i     :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 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
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

Perl[edit]

Translation of: Perl 6

We'll emulate infinite lists with closures.

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


A faster population count can be done with pack/unpack:

say unpack("%b*",pack "J*", 1234567); # J = UV

Various modules can also perform a population count, with the first of these being faster than the pack/unpack builtins. The first three easily support bigints, the last will with some adjustment.

use ntheory qw/hammingweight/;
say hammingweight(1234567);
 
use Math::GMPz qw/Rmpz_popcount/;
say Rmpz_popcount(Math::GMPz->new(1234567));
 
use Math::BigInt;
say 0 + (Math::BigInt->new(1234567)->as_bin() =~ tr/1//);
 
use Bit::Vector;
say Bit::Vector->new_Dec(64,1234567)->Norm;

Perl 6[edit]

sub population-count(Int $n where * >= 0) { [+] $n.base(2).comb }
 
say map &population-count, 3 «**« ^30;
say "Evil: ", (grep { population-count($_) %% 2 }, 0 .. *)[^30];
say "Odious: ", (grep { population-count($_) % 2 }, 0 .. *)[^30];
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

That's the convenient way to write it, but the following avoids string processing and is therefore about twice as fast:

sub population-count(Int $n is copy where * >= 0) { 
loop (my $c = 0; $n; $n +>= 1) {
$c += $n +& 1;
}
$c;
}

PowerShell[edit]

 
function pop-count($n) {
(([Convert]::ToString($n, 2)).toCharArray() | where {$_ -eq '1'}).count
}
"pop_count 3^n: $(1..29 | foreach -Begin {$n = 1; (pop-count $n)} -Process {$n = 3*$n; (pop-count $n)} )"
"even pop_count: $($m = $n = 0; while($m -lt 30) {if(0 -eq ((pop-count $n)%2)) {$m += 1; $n}; $n += 1} )"
"odd pop_count: $($m = $n = 0; while($m -lt 30) {if(1 -eq ((pop-count $n)%2)) {$m += 1; $n}; $n += 1} )"
 

Output:

pop_count 3^n: 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
even pop_count: 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
odd pop_count: 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[edit]

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

Racket[edit]

#lang racket
;; Positive version from "popcount_4" in:
;; https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation
;; negative version follows R6RS definition documented in:
;; http://docs.racket-lang.org/r6rs/r6rs-lib-std/r6rs-lib-Z-H-12.html?q=bitwise-bit#node_idx_1074
(define (population-count n)
(if (negative? n)
(bitwise-not (population-count (bitwise-not n)))
(let inr ((x n) (rv 0))
(if (= x 0) rv (inr (bitwise-and x (sub1 x)) (add1 rv))))))
 
(define (evil? x)
(and (not (negative? x))
(even? (population-count x))))
 
(define (odious? x)
(and (positive? x)
(odd? (population-count x))))
 
(define tasks
(list
"display the pop count of the 1st thirty powers of 3 (3^0, 3^1, 3^2, 3^3, 3^4, ...)."
(for/list ((i (in-range 30))) (population-count (expt 3 i)))
"display the 1st thirty evil numbers."
(for/list ((_ (in-range 30)) (e (sequence-filter evil? (in-naturals)))) e)
"display the 1st thirty odious numbers."
(for/list ((_ (in-range 30)) (o (sequence-filter odious? (in-naturals)))) o)))
 
(for-each displayln tasks)
 
(module+ test
(require rackunit)
(check-equal?
(for/list ((p (sequence-map population-count (in-range 16)))) p)
'(0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4))
(check-true (evil? 0) "0 has just *got* to be evil")
(check-true (evil? #b011011011) "six bits... truly evil")
(check-false (evil? #b1011011011) "seven bits, that's odd!")
(check-true (odious? 1) "the least odious number")
(check-true (odious? #b1011011011) "seven (which is odd) bits")
(check-false (odious? #b011011011) "six bits... is evil"))
Output:
display the pop count of the 1st thirty powers of 3 (3^0, 3^1, 3^2, 3^3, 3^4, ...).
(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)
display the 1st thirty 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)
display the 1st thirty 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)

REXX[edit]

/*REXX program counts the (binary) bits in the binary version of a decimal number,  and */
/*───────────────────────── also generates a specific number of EVIL and ODIOUS numbers.*/
parse arg N B . /*get optional arguments from the C.L. */
if N=='' | N=="," then N=30 /*N not specified? Then use default. */
if B=='' | B=="," then B= 3 /*B " " " " " */
numeric digits 3000 /*be able to handle gihugeic numbers.*/
numeric digits max(20, length(B**N)) /*whittle the precision down to size.*/
/* [↑] a little calculation for sizing*/
$=; do j=0 for N /*generate N popCounts for some powers.*/
$=$ popCount(B**j) /*get the popCount for a power of B. */
end /*j*/ /* [↑] append popCount to the $ list. */
/* [↓] display popcounts of "3" powers*/
call showList 'popcounts of the powers of' B /*display the list with a header/title.*/
do j=0 until #==N /*generate N evil numbers. */
if popCount(j) // 2 then iterate /*if odd population count, skip it. */
#=#+1 /*bump the evil number counter. */
$=$ j /*append an evil number to a list.*/
end /*j*/ /* [↑] build a list of evil numbers. */
/* [↓] display the evil number 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, then skip. */
#=#+1 /*bump the odious number counter. */
$=$ j /*append an odious number to a list. */
end /*j*/ /* [↑] build a list of odious numbers.*/
/* [↓] display the odious number list.*/
call showList 'odious numbers' /*display the $ list with a header. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
d2b: return word( strip( x2b( d2x( arg(1) ) ), 'L', 0) 0, 1) /*dec ──► bin.*/
popCount: return length( space( translate( d2b(arg(1) ), , 0), 0) ) /*count ones. */
showList: say; say 'The 1st' N arg(1)':'; say substr($, 2); #=0; $=; return

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

Ruby[edit]

Demonstrating lazy enumerators.

class Integer
 
def popcount
self.to_s(2).count("1")
end
 
def evil?
self >= 0 && popcount.even?
end
 
def odious?
self > 0 && popcount.odd?
end
 
end
 
inf = 1.0 / 0.0 # Infinity
puts "Powers of 3:", (0...30).map{|n| (3**n).popcount}.join(' ')
puts "Evil:" , (0..inf).lazy.select(&:evil? ).first(30).join(' ')
puts "Odious:", (0..inf).lazy.select(&:odious?).first(30).join(' ')
Output:

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

Rust[edit]

 
fn main() {
let mut num = 1u64;
let mut vec = Vec::new();
for _ in 0..30 {
vec.push(num.count_ones());
num *= 3;
}
println!("pop count of 3^0, 3^1 ... 3^29:\n{:?}",vec);
let mut even = Vec::new();
let mut odd = Vec::new();
num = 1;
while even.len() < 30 || odd.len() < 30 {
match 0 == num.count_ones()%2 {
true if even.len() < 30 => even.push(num),
false if odd.len() < 30 => odd.push(num),
_ => {}
}
num += 1;
}
println!("\nFirst 30 even pop count:\n{:?}",even);
println!("\nFirst 30 odd pop count:\n{:?}",odd);
}
 
Output:
pop count of 3^0, 3^1 ... 3^29:
[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]

First 30 even pop count:
[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]

First 30 odd pop count:
[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]

Seed7[edit]

The function popcount below converts the integer into a bitset. The function card is used to compute the population count of the bitset.

$ include "seed7_05.s7i";
 
const func integer: popcount (in integer: n) is
return card(bitset conv n);
 
const proc: main is func
local
var integer: count is 0;
var integer: num is 0;
begin
for count range 0 to 29 do
write(popcount(3 ** count) <& " ");
end for;
writeln;
write("evil: ");
for count range 1 to 30 do
while odd(popcount(num)) do
incr(num);
end while;
write(num <& " ");
incr(num);
end for;
writeln;
write("odious: ");
num := 0;
for count range 1 to 30 do
while not odd(popcount(num)) do
incr(num);
end while;
write(num <& " ");
incr(num);
end for;
writeln;
end func;
 
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 

Sidef[edit]

func population_count(n) { n.as_bin.count('1') };
say "#{0..29 «**« 3 «call« population_count}";
 
var numbers = 60.of { |i|
[i-1, population_count(i-1)];
};
 
say "Evil: #{numbers.grep{_[1].is_even}.map{_[0]}}";
say "Odious: #{numbers.grep{_[1].is_odd}.map{_[0]}}";
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

Tcl[edit]

Works with: Tcl version 8.6
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]"
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

UNIX Shell[edit]

Works with: bash
popcount() {
local -i n=$1
(( n < 0 )) && return 1
local ones=0
while (( n > 0 )); do
(( ones += n%2 ))
(( n /= 2 ))
done
echo $ones
}
 
popcount_3s=()
n=1
for (( i=0; i<30; i++ )); do
popcount_3s+=( $(popcount $n) )
(( n *= 3 ))
done
echo "powers of 3 popcounts: ${popcount_3s[*]}"
 
evil=()
odious=()
n=0
while (( ${#evil[@]} < 30 || ${#odious[@]} < 30 )); do
p=$( popcount $n )
if (( $p%2 == 0 )); then
evil+=( $n )
else
odious+=( $n )
fi
(( n++ ))
done
echo "evil nums: ${evil[*]:0:30}"
echo "odious nums: ${odious[*]:0:30}"
Output:
powers of 3 popcounts: 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 nums:   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 nums: 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

zkl[edit]

Ints have the 1s count as a property.

n:=1; do(30){ print(n.num1s,","); n*=3 } println();
 
println("evil: ",[0..].filter(30,fcn(n){ n.num1s.isEven }).concat(","));
 
// now, as an iterator aka lazy:
println("odious: ",(0).walker(*).tweak( // 0,1,2,3,4... iterator
fcn(n){ if(n.num1s.isEven) Void.Skip else n }).walk(30).concat(","));
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