Wirth Problem 15.12
December 7, 2012
In his 1973 book Systematic Programming: An Introduction, Niklaus Wirth gives the following problem as exercise 15.12:
Develop a program that generates in ascending order the least 100 numbers of the set M, where M is defined as follows:
a) The number 1 is in M.
b) If x is in M, then y = 2 * x + 1 and z = 3 * x + 1 are also in M.
c) No other numbers are in M.
Wirth also gives the first six numbers in the result sequence: 1, 3, 4, 7, 9, 10….
Your task is to write a program that finds the first n numbers in Wirth’s sequence, and use it to solve Wirth’s exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
A Python version.
from heapq import heappop, heappush import itertools def wirth(): Q = [1] last = -1 while Q: x = heappop(Q) if x != last: last = x yield x heappush(Q, 2 * x + 1) heappush(Q, 3 * x + 1) for x in itertools.islice(wirth(), 100): print x,[…] today’s Programming Praxis exercise, our goal is to generate the first 100 terms of a mathematical set […]
My Haskell solution (see http://bonsaicode.wordpress.com/2012/12/07/programming-praxis-wirth-problem-15-12/ for a version with comments):
This puzzle can be solved more efficiently in O(n) using an idea from a previous exercise Hamming numbers
My java solution:
import java.util.*;
public class Problem15_12 {
public static void main(String[] args) {
generate();
}
public static void generate() {
ArrayList al = new ArrayList();
al.add(1);
int index = 0;
int x, y, z;
while(al.size() < 200){
x = al.get(index);
y = 2 * x + 1;
z = 3 * x + 1;
if(! al.contains(y)){
al.add(y);
}
if (! al.contains(z)){
al.add(z);
}
index++;
}
Collections.sort(al);
for(int i = 0; i < 100; i++)
System.out.print(al.get(i) + " ");
System.out.println("");
}
}
[\code]
ans = {1} while len(ans) < 200: for n in list(ans): ans.add(2*n + 1) ans.add(3*n + 1) print sorted(ans)[:100][…] Pages: 1 2 […]
A Clojure solution almost equivalent to the proposed one by using sorted set.
(defn wirth [n] (loop [n n xs (sorted-set 1) ms (sorted-set)] (if (not (pos? n)) ms (let [x (first xs), ys (disj xs x) x1 (inc (* 2 x)), x2 (inc (* 3 x))] (recur (dec n) (conj ys x1 x2) (conj ms x))))))An other one using the algorithm proposed by Cosmin: almost 20x faster
(defn wirth' [n] (loop [n1 0 n2 0 ms [1]] (let [x1 (inc (* 2 (ms n1))), x2 (inc (* 3 (ms n2)))] (cond (>= (count ms) n) ms (< x1 x2) (recur (inc n1) n2 (conj ms x1)) (> x1 x2) (recur n1 (inc n2) (conj ms x2)) :else (recur (inc n1) (inc n2) (conj ms x1))))))A Python solution using generators. This is equivalent to the Haskell solution above.
def merge(a, b): x = a.next() y = b.next() while 1: if x < y: yield x x = a.next() elif x == y: yield x x = a.next() y = b.next() elif x > y: yield y y = b.next() else: raise "Incomparable elements" def lin(a, b, xs): for x in xs: yield a*x + b def seq(): yield 1 for x in merge(lin(2, 1, seq()), lin(3, 1, seq())): yield x print [ x for (i, x) in zip(range(100), seq()) ]Solution in Go that uses a channel to simulate a generator:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
problem_15_12.go
hosted with ❤ by GitHub
That was a neat little puzzle. I ended up working out several ways in both Racket and Python, including a basic recursive solution, a memoized recursive solution, one based on Python generators (which was much cooler until I saw Jan Van lent’s nearly identical solution :), one based on a sieve, and finally one based on priority queues / heaps.
Here’s the post: Numbers of Wirth
Or you can just check out the code here:
– Python version
– Racket version
var m = new SortedDictionary { { 1, 1 } };
var s = 1;
do
{
if (!m.ContainsValue(m[s] * 2 + 1)) m.Add(m.Count + 1, m[s] * 2 + 1);
if (!m.ContainsValue(m[s] * 3 + 1)) m.Add(m.Count + 1, m[s] * 3 + 1);
s++;
} while (m.Count < 100);
var result = m.Values.ToList();
result.Sort();
foreach (var value in result)
Console.Write(value + " ");
Console.ReadKey();
O(n) solution:
#include
int main() {
int w[100];
w[0] = 1;
printf(“1\n”);
int xi = 1;
int yi = 0;
int zi = 0;
while( xi < 100 ) {
int y = w[yi] * 2 + 1;
int z = w[zi] * 3 + 1;
if (y == z) {
w[xi] = y;
yi++;
zi++;
} else if (y < z) {
w[xi] = y;
yi++;
} else {
w[xi] = z;
zi++;
}
printf("%d\n", w[xi]);
xi++;
}
return 0;
}
Python:
def wirth(): M=[1] key = 0 run = True while run==True: x=M[key] M.append(2*x+1) M.append(3*x+1) key=key+1 if len(M)>=99: run=False M.sort() return M print wirth()@Brian: That doesn’t quite work as it doesn’t remove duplicates.
For example 31 = 2 * 15 + 1 = 3 * 10 + 1.
The last number for the first 100 Wirth numbers should be 418 rather than 850.
Scratch that, I made a mistake. If you don’t sort while appending the set M, then you don’t get the first 100 numbers in the series (even though you would get them all eventually).
def wirth(): M=[1] key = 0 run = True while run==True: x=M[key] M.append(2*x+1) M.append(3*x+1) key=key+1 M.sort() if len(M)>=99: run=False return M print wirth()Thanks jpverkamp, I made a change to id and skip dups in the while loop. I won’t post it for the sake of not spamming this comment board with code.
Here my solution to this problem in JavaScript
/*
* Numbers of Wirth
* Solution to https://programmingpraxis.com/2012/12/07/wirth-problem-15-12/2/
*
* Author: Chandrasekhar Thotakura
*/
(function (N) {
‘use strict’;
var wirth = {
queue: [1],
series: [],
insert: function (x) {
var len = this.queue.length, i = 0;
if (len) {
while (i < len && this.queue[i] < x) {
i += 1;
}
}
if (this.queue[i] !== x) {
this.queue.splice(i, 0, x);
}
},
generate: function () {
var head;
while (this.queue.length) {
head = this.queue.shift();
if (this.series.length < N) {
this.series.push(head);
this.insert(2 * head + 1);
this.insert(3 * head + 1);
}
}
}
};
wirth.generate();
return wirth.series;
}(100));
Missed Syntax highlighting and link to gist https://gist.github.com/4261220
/* * Numbers of Wirth * Solution to https://programmingpraxis.com/2012/12/07/wirth-problem-15-12/2/ * * Author: Chandrasekhar Thotakura */ (function (N) { 'use strict'; var wirth = { queue: [1], series: [], insert: function (x) { var len = this.queue.length, i = 0; if (len) { while (i < len && this.queue[i] < x) { i += 1; } } if (this.queue[i] !== x) { this.queue.splice(i, 0, x); } }, generate: function () { var head; while (this.queue.length) { head = this.queue.shift(); if (this.series.length < N) { this.series.push(head); this.insert(2 * head + 1); this.insert(3 * head + 1); } } } }; wirth.generate(); return wirth.series; }(100));Here’s mine in Ruby:
def wirth_list(count) r = [1] # results s = [1] # stack waiting to process begin x = s.shift # grab the bottom item from the stack y = x * 2 + 1 z = x * 3 + 1 index = r.index{|p| (p > y) } || 1 # where will y fall in the results? r = (r << y << z).sort.uniq # add to results and sort s = (s << y << z).sort.uniq # add to stack and sort end until index >= count # the index of the new y is past count, we're done r[0..(count-1)] end puts "#{wirth_list(100)}"Here’s another JavaScript solution:
(function wirth(n) { var M = [1], Y = [], Z = [], i = 0, x; while (M.length < n) { x = M[i++]; Y.push(2 * x + 1); Z.push(3 * x + 1); while (Y[0] && (M.length < n)) { if (Y[0] <= Z[0]) { M.push(Y.shift()); } else { (Z[0] > M[M.length - 1])? M.push(Z.shift()) : Z.shift(); } } } return M; }(100));Haskell is simplest
m = 1 : mv (\x->2*x+1) (\x->3*x+1)
where
mv f1 f2 = map f1 m `merge` map f2 m
xxs@(x:xs) `merge` yys@(y:ys) =
case x`compare`y of
LT -> x:(xs`merge`yys)
EQ -> x:(xs`merge`ys)
GT -> y:(xxs`merge`ys)
Here’s my solution in Ruby:
class MFinder def self.m_list(finish) m_list = [1] until m_list.count > finish for i in m_list y = (2 * i) + 1 z = (3 * i) + 1 m_list += [y] if m_list.count <= finish m_list = m_list.uniq m_list += [z] if m_list.count <= finish m_list = m_list.uniq end end if m_list.count > finish c = m_list.count - finish m_list.pop(c) end return m_list.sort end end puts MFinder.m_list(100)Go implementation of cosmin’s solution: http://play.golang.org/p/kGwF3feDzJ
While not the fastest, here’s a very neat one in Python:
def wirth(n): M = {1} f = lambda x: (2*x + 1, 3*x + 1) while len(M) < n: map(M.add, sum(map(f, M), ())) return sorted(M)[:n]Here’s one using SRFI-41 streams:
(import (srfi :41 streams)) (define (wirth n) (define wirth-merge (stream-lambda (s1 s2) (cond ((stream-null? s1) s2) ((stream-null? s2) s1) (else (let ((x1 (stream-car s1)) (x2 (stream-car s2))) (cond ((= x1 x2) (stream-cons x1 (wirth-merge (stream-cdr s1) (stream-cdr s2)))) ((< x1 x2) (stream-cons x1 (wirth-merge (stream-cdr s1) s2))) (else (stream-cons x2 (wirth-merge (stream-cdr s2) s1))))))))) (define wirth-from (stream-lambda (first) (stream-cons first (wirth-merge (wirth-from (+ 1 (* 2 first))) (wirth-from (+ 1 (* 3 first))))))) (stream->list (stream-take n (wirth-from 1)))) (display (wirth 100)) (newline)C# Array solution . link to gist https://gist.github.com/4446769
//https://programmingpraxis.com/2012/12/07/wirth-problem-15-12/ namespace Wirth_Problem_15._12 { class Program { static int MAX_SIZE = 10000; static byte?[] aWrith = new byte?[MAX_SIZE]; static void Main(string[] args) { for (int i = 0; i < 100; i++) { int nextNumber = GetNext(); aWrith[nextNumber] = 1; aWrith[nextNumber * 2 + 1] = 0; aWrith[nextNumber * 3 + 1] = 0; } for (int i = 0; i < MAX_SIZE; i++) { if (aWrith[i] == 1) { System.Console.Write(String.Format("{0},", i)); } } } static int GetNext() { for (int i = 1; i < MAX_SIZE; i++) { if (aWrith[i] == 0) { return i; } } return 1; } } }