Population count
The population count is the number of 1's (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, (which is 101 in binary) has a population count of .
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 1st thirty powers of ().
- 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
- Sequence A000069 odious numbers on The On-Line Encyclopedia of Integer Sequences.
- Sequence A001969 evil numbers on The On-Line Encyclopedia of Integer Sequences.
Ada
Specifiction and implementation of an auxiliary package "Population_Count". The same package is used for Pernicious numbers#Ada
<lang ada>with Interfaces;
package Population_Count is
subtype Num is Interfaces.Unsigned_64; function Pop_Count(N: Num) return Natural;
end Population_Count;</lang>
<lang Ada>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;</lang>
The main program:
<lang Ada>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;</lang>
- 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
AutoHotkey
<lang AutoHotkey>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 }</lang>
- 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
<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++
<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
Common Lisp
<lang lisp>(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))</lang>
- 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
<lang d>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));
}</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]
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("Powers of 3: ~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(). 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</lang>
Go
<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() {
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()
}</lang>
- 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
Haskell
<lang haskell>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])</lang>
- 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
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
Julia
<lang Julia>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]</lang>
Mathematica
<lang Mathematica>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</lang>
- 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}
PARI/GP
<lang parigp>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]</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 = [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]
Perl
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
<lang perl6>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];</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
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>
Racket
<lang racket>#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"))</lang>
- 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
<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
Ruby
Demonstrating lazy enumerators. <lang ruby>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(' ')</lang>
- 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
Seed7
The function popcount
below converts
the integer into a bitset.
The function card
is used to compute the population count of the bitset.
<lang seed7>$ 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;
</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
Tcl
<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
zkl
Ints have the 1s count as a property. <lang zkl>n:=1; do(30){print(n.num1s,","); n*=3} println();
println("evil: ",(0).walker(*).tweak(fcn(n){
if(n.num1s.isOdd)Void.Skip else n}).walk(30).concat(","))
println("odious: ",(0).walker(*).tweak(fcn(n){
if(n.num1s.isEven)Void.Skip else n}).walk(30).concat(","))</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