Wirth Problem 15.12

December 7, 2012

We start with a priority queue that contains only 1. Then the head of the queue is popped and added to the outgoing sequence, and two new items are added to the queue:

(define (wirth n)
  (let ((pq (pq-insert < 1 pq-empty)))
    (let loop ((n n) (pq pq) (ps (list)))
      (if (zero? n) (reverse ps)
        (let* ((p (pq-first pq))
               (pq (pq-rest < pq))
               (pq (if (and (not (pq-empty? pq))
                            (= (pq-first pq) p))
                       (pq-rest < pq) pq)))
          (loop (- n 1)
                (pq-insert < (+ (* 2 p) 1)
                  (pq-insert < (+ (* 3 p) 1) pq))
                (cons p ps)))))))

The only complication arises from numbers like 10*3+1 = 15*2+1 = 31 that appear twice in the sequence. We could change the priority queue to add only distinct items, but instead we leave the library code of the priority queue alone and check each time we pop an item if the next item is the same, in which case we discard it. Here’s the output:

> (wirth 100)
(1 3 4 7 9 10 13 15 19 21 22 27 28 31 39 40 43 45 46 55 57
 58 63 64 67 79 81 82 85 87 91 93 94 111 115 117 118 121 127
 129 130 135 136 139 159 163 165 166 171 172 175 183 187 189
 190 193 202 223 231 235 237 238 243 244 247 255 256 259 261
 262 271 273 274 279 280 283 319 327 331 333 334 343 345 346
 351 352 355 364 367 375 379 381 382 387 388 391 405 406 409
 418)

This is sequence A002977 at oeis.org; the references there indicate it has been studied by Knuth and others. We used the pairing heaps of a previous exercise, but any implementation of priority queues will work. You can run the program at http://programmingpraxis.codepad.org/GLmxhznj.

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:

  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 628 other followers

%d bloggers like this: