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

Pages: 1 2

### 28 Responses to “Wirth Problem 15.12”

1. Paul said

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,
```
2. […] today’s Programming Praxis exercise, our goal is to generate the first 100 terms of a mathematical set […]

3. My Haskell solution (see http://bonsaicode.wordpress.com/2012/12/07/programming-praxis-wirth-problem-15-12/ for a version with comments):

```import Data.List.Ordered

m :: [Integer]
m = 1 : union (map ((+1) . (*2)) m) (map ((+1) . (*3)) m)
```
4. cosmin said

This puzzle can be solved more efficiently in O(n) using an idea from a previous exercise Hamming numbers

```def wirth_top(n):
wirth = [1]
next_2, next_3 = 0, 0
for i in xrange(1, n):
wirth.append(min(2*wirth[next_2] + 1, 3*wirth[next_3] + 1))
if 2*wirth[next_2] + 1 <= wirth[i]: next_2 += 1
if 3*wirth[next_3] + 1 <= wirth[i]: next_3 += 1
return wirth

print wirth_top(100)
```
5. Hamid said

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]

6. Mark said
```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]
```
7. […] Pages: 1 2 […]

8. kawas44 said

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))))))
```
9. Jan Van lent said

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()) ]
```
10. Solution in Go that uses a channel to simulate a generator:

11. jpverkamp said

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

12. 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();

13. J said

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;

}

14. Brian said

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()
```
15. jpverkamp said

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

16. Brian said

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()
```
17. Brian said

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.

18. greenrobo said

Here my solution to this problem in JavaScript

/*
* Numbers of Wirth
* Solution to http://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));

19. greenrobo said

Missed Syntax highlighting and link to gist https://gist.github.com/4261220

```/*
* Numbers of Wirth
* Solution to http://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));
```
20. splitDiff said

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)}"
```
21. Nathan said

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));
```
22. none said

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)

23. 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)
```
24. Go implementation of cosmin’s solution: http://play.golang.org/p/kGwF3feDzJ

25. Johan said

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]
```
26. Jamie Hope said

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)
```
27. jyoti said

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

```
//http://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;
}

}
}
```