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.

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