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.
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:
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; } } }