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