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.

Posted by programmingpraxis

Filed in Exercises

28 Comments »

28 Responses to “Wirth Problem 15.12”

Paul said

December 7, 2012 at 9:16 AM

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,

Programming Praxis – Wirth Problem 15.12 « Bonsai Code said
December 7, 2012 at 9:48 AM
[…] today’s Programming Praxis exercise, our goal is to generate the first 100 terms of a mathematical set […]
Remco Niemeijer said
December 7, 2012 at 9:49 AM
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)
```

cosmin said

December 7, 2012 at 12:39 PM

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)

Hamid said
December 7, 2012 at 3:48 PM
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]

Mark said

December 7, 2012 at 5:15 PM

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]

Wirth Problem 15.12 | My Blog said
December 7, 2012 at 10:27 PM
[…] Pages: 1 2 […]

kawas44 said

December 8, 2012 at 6:59 PM

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

Jan Van lent said

December 9, 2012 at 3:23 PM

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()) ]

James Cooper (@coopernurse) said

December 10, 2012 at 4:02 PM

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

	package main

	import (
	"log"
	"sort"
	)

	func generateSet(c chan<- int) {
	min := 0
	nums := make([]int, 0)
	nums = append(nums, 1)

	for len(nums) > 0 {
	// get the first num in slice. should be lowest num.
	i := nums[0]

	// have we already seen this number?
	if i > min {
	// nope, yield the number to the channel
	c <- i

	// update min so we'll skip this number if we have
	// a dupe in the nums slice
	min = i

	// add the next two numbers in the set
	nums = append(nums[1:], (2i)+1, (3i)+1)

	// sort
	sort.Ints(nums)
	} else {
	// already seen this number. pop first element off
	// slice and keep going
	nums = append(nums[1:])
	}
	}
	}

	// https://programmingpraxis.com/2012/12/07/wirth-problem-15-12/
	func main() {
	// this solution uses a channel and goroutine as a
	// generator that yields the next value in the set
	c := make(chan int)
	go generateSet(c)

	// print the first 100 numbers in the set
	for i := 0; i < 100; i++ {
	log.Println(i, <-c)
	}
	}

view raw
problem_15_12.go
hosted with ❤ by GitHub

jpverkamp said
December 10, 2012 at 7:58 PM
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
Mohamad Hmb said
December 11, 2012 at 1:18 PM
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();
J said
December 11, 2012 at 7:23 PM
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;

}

Brian said

December 11, 2012 at 8:02 PM

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()

jpverkamp said
December 11, 2012 at 8:04 PM
@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.

Brian said

December 11, 2012 at 8:14 PM

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()

Brian said
December 11, 2012 at 8:15 PM
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.
greenrobo said
December 11, 2012 at 9:01 PM
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));

greenrobo said

December 11, 2012 at 9:07 PM

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));

splitDiff said

December 11, 2012 at 11:29 PM

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)}"

Nathan said

December 12, 2012 at 3:03 AM

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));

none said
December 12, 2012 at 3:44 AM
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)

Sean (@seanoliver) said

December 12, 2012 at 8:37 AM

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)

Glenn Brown said
December 12, 2012 at 4:07 PM
Go implementation of cosmin’s solution: http://play.golang.org/p/kGwF3feDzJ

Johan said

December 13, 2012 at 6:38 AM

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]

Jamie Hope said

December 13, 2012 at 9:57 PM

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)

jyoti said
January 3, 2013 at 8:17 PM

jyoti said

January 3, 2013 at 8:33 PM

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

    }
}

Programming Praxis