Hofstadter’s Sequence

February 1, 2013

On page 73 of his book Gödel, Escher, Bach: An Eternal Golden Braid, Douglas Hofstadter asks you to think about the following sequence:

1, 3, 7, 12, 18, 26, 35, 45, 56, 69, …

Hofstadter leaves you to figure out the rule that produces the sequence, though he does give some hints in the surrounding text.

Your task is to write a program that produces the first n elements of Hofstadter’s sequence. 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 3

17 Responses to “Hofstadter’s Sequence”

  1. [...] today’s Programming Praxis exercise, our goal is to write a program that generates the Hofstadter sequence. [...]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2013/02/01/programming-praxis-hofstadters-sequence/ for a version with comments):

    import Data.List
    
    hofstadter :: [Integer]
    hofstadter = unfoldr (\(r:s:ss) -> Just (r, r+s:delete (r+s) ss)) [1..]
    
  3. Hamid said

    Java solution here

  4. Here is a java solution that only stores the Hofstader’s sequence instead of both sequences.

    public class Hofstadters {

    Vector<Integer> hof = new Vector<Integer>();

    final int MAX = 20;
    int nextS;
    int hofCheckIndex;

    public Hofstadters(){
    hof.add(1);
    nextS = 2;
    hofCheckIndex = 1;

    for(int i = 1; i < MAX; i++) fillHof();

    System.out.println("Hof index: " + MAX + " Hof number: " + hof.lastElement());
    }

    public void fillHof(){
    hof.add(hof.lastElement() + nextS);
    if(++nextS == hof.elementAt(hofCheckIndex)){
    nextS++;
    hofCheckIndex++;
    }
    }

  5. Mike said

    Python generator

    import itertools as it
    
    def hofstadter_gen():
        hs = set()
        h = 0
        for s in it.filterfalse(hs.__contains__, it.count(1)):
            h += s
            yield h
            hs.add(h)
    
  6. dwjref said

    C# solution

    public List Hofstadters(int n)
    {
    	List results = new List(n);
    	int counter = 0;
    	while (results.Count < n)
    		if (results.Contains(++counter) == false)
    				results.Add(results.Count == 0 ? counter : results[results.Count - 1] + counter);
    	
    	return results;
    }
    
  7. Richard Wagenknecht said

    C# 2, not as elegant.

    List sequenceNumbers = new List();
    int i = 1;

    while (i < 100)
    {
    if (sequenceNumbers.IndexOf(i + sequenceNumbers.LastOrDefault()) == -1)
    {
    sequenceNumbers.Add(i + sequenceNumbers.LastOrDefault());
    ++i;
    }

    while (sequenceNumbers.IndexOf(i) != -1)
    {
    ++i;
    }
    }

  8. Here is Python code with some optimization – we store available numbers (S sequence members) as tuples (min, max) and pops first available. This significantly reduces number of items stored in list.

    class Availables(object):
        def __init__(self):
            self.vals = []
            self.max = 0
            
        def append(self, low_value, high_value):
            if self.max >= low_value:
                raise Exception("Too low value")
            
            if low_value > high_value:
                return
            
            self.vals.append((low_value, high_value))
            self.max = high_value
        
        def pop(self):
            if len(self.vals) == 0:
                return None
            
            low, high = self.vals[0]
            if low == high:
                del self.vals[0]
            else:
                self.vals[0] = low + 1, high
            
            return low
        
        def __len__(self):
            return len(self.vals)
    
    def hofstadter():
        n = 1
        avail = Availables()
        while True:
            yield n
            if len(avail) == 0:
                incr = n + 1
                start = n + 2
            else:
                incr = avail.pop()
                start = n + 1
            avail.append(start, n + incr - 1)
            n += incr
    
    from itertools import islice
    list(islice(hofstadter(), 100000, 100005)) # Get numbers from 100000-th to 100004-th
    
    # Result is: [5028615179L, 5028715611L, 5028816044L, 5028916478L, 5029016913L], length of available number tuples list at 100004-th number is 99574
    
  9. wwh said

    Here’s my racket solution.

    (define (hof length (current 1) (last 0) (s empty))
    (cond
    ((> current length) “done”)
    ((equal? current 1) (printf “1~%”) (hof length (+ current 1)))
    ((equal? current 2) (printf “3~%”) (hof length (+ current 1)))
    ((equal? current 3) (printf “7~%”) (hof length (+ current 1) 7 (list 5 6)))
    (else
    (let ((this-hof (+ last (car s))))
    (printf “~a~%” (+ last (car s)))
    (hof
    length
    (+ current 1)
    (+ last (car s))
    (append (cdr s) (build-list (- this-hof last 1)
    (lambda (x) (+ x last 1)))))))))

  10. dead_ant said

    Even less pretty but faster C# version. Idea is to enumerate S elements and skip previously found R elements. Got lazy to optimize further. On my i7 finds 1M numbers in about 35ms.

    static IEnumerable<int> Hofstadter(int n) {
        var init = new[] { 1, 3, 7 }; // first few elements are pre-set
        var Rs = new Queue<int>(); // queue to store found elements of R
        Rs.Enqueue(7); // pushing first value
        var counter = 0;
        var s = 5; // first unused element of S
        var curR = 7;
    
        while (true) {
            if (counter < 3) { yield return init[counter++]; continue; }
            var nextR = Rs.Dequeue();
            do {
                Rs.Enqueue(s + curR);
                curR = s++ + curR;
                if (counter++ >= n)
                    yield break;
                yield return curR;
            } while (s != nextR);
            s++;
        }
    }
    
  11. Jonathan said

    Really interesting problem. I had a crack for a few hours (eheh…) and came up with a solution in Common Lisp on my blog.

    The solution works for n = 5, but interestingly, it also works for n = 1 (where it finds one solution; 1), and n = 0 (where it finds no solutions).

  12. Keith said

    I hacked this out in Perl, and after the fact found it very similar to beardedone85’s Java solution
    sub hofstadters_sequence{
    my $n = shift;
    my @R = (1); #Given
    my $S = 2; #Given
    my $r_index = 1;

    for(my $i = 1; $i < $n; $i++){
    #Step 1, first calculate the next R
    push(@R, $R[$i-1] + $S);
    #Step 2, calculate next S
    if($S == $R[$r_index] – 1){
    $S = $R[$r_index] + 1;
    $r_index++;
    }
    else{$S++;}
    }

    return \@R;
    }

  13. Scott said

    import java.util.Vector;

    public class HofstadtersSequence{

    public static void main(String[] args){
    Vector S = new Vector();
    int N = 1000000, R = 2, n = 0;
    int lastSkiped = 1;
    S.add(1L);

    while(N>n++){
    System.out.println(S.lastElement()+” “+R);
    S.add(S.lastElement()+R++);
    if(R == S.get(lastSkiped)){
    R++;
    lastSkiped++;
    }
    }
    System.out.println(S.lastElement()+” “+R);
    }
    }

  14. paddy3118 said

    Hofstadter mentions many sequences in his book. This particular one is also known as one of the “Hofstadter Figure-Figure sequences”.

  15. Alcriss said

    int sum = 0, shadow = 1, count = 2, ng = 1;

    for (int i = 1; i <= count – ng; i++)
    {
    sum = sum + shadow;
    Console.Write(" " + sum + ", ");
    shadow = shadow + 1;
    if (i == count)
    {
    count = count + 1;
    shadow = shadow + 1;
    i = 0;
    }
    else if (sum == 150)
    {
    goto End;
    }
    ng = 0;
    }
    End:
    Console.ReadLine();

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

%d bloggers like this: