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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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