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

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

[…] Pages: 1 2 […]

A Clojure solution almost equivalent to the proposed one by using sorted set.

An other one using the algorithm proposed by Cosmin: almost 20x faster

A Python solution using generators. This is equivalent to the Haskell solution above.

Solution in Go that uses a channel to simulate a generator:

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:

@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).

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

Here’s mine in Ruby:

Here’s another JavaScript solution:

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:

Go implementation of cosmin’s solution: http://play.golang.org/p/kGwF3feDzJ

While not the fastest, here’s a very neat one in Python:

Here’s one using SRFI-41 streams:

C# Array solution . link to gist https://gist.github.com/4446769