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.

About these ads

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

    https://gist.github.com/4251470

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

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

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

    }

  13. 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()
    
  14. 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.

  15. 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()
    
  16. 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.

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

  18. 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));
    
  19. 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)}"
    
  20. 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));
    
  21. 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)

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

  24. 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]
    
  25. 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)
    
  26. 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;
            }
    
        }
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 576 other followers

%d bloggers like this: