Hofstadter’s Sequence

February 1, 2013

Before you can write the program, you have to figure out the rule that produces the sequence. The solution is the R sequence given by:

R1 = 1, Rn = Rn−1 + Sn−1

where Sn is the smallest positive integer not present in R0..n or S0..n−1.

At this point in his book Hofstadter is discussing the figure and ground of two sequences, similar to the foreground and background of an image. He characterizes the two sequences given above as a figure-figure sequence, with no ground, because the two sequences are complements of each other.

The program to calculate the R sequence is on the next page.

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

%d bloggers like this: