## Hofstadter’s Sequence

### February 1, 2013

Our solution follows the definition exactly:

`(define (hofstadter n)`

(let ((k 5))

(let loop ((n (- n 2)) (rs (list 3 1)) (ss (list 4 2)))

(if (zero? n) (reverse rs)

(loop (- n 1)

(cons (+ (car rs) (car ss)) rs)

(let next ((n k))

(cond ((member n rs) (next (+ n 1)))

((member n ss) (next (+ n 1)))

(else (set! k (+ n 1))

(cons n ss)))))))))

We precompute the first two elements of each sequence. Then the recursion computes the next *r* in the obvious way, then computes the next integer not yet a member of either list in the *next* loop, saving it in the *s* list. You can run the program at http://programmingpraxis.codepad.org/YhdKy2aR.

This works fine when *n* is small, but is ridiculously slow when *n* is large, because each item added to the sequences causes rescanning of the previous sequences. A005228 gives this gorgeous Haskell program for calculating the sequence:

`hofstadter = 1 : figure 1 [2..] where`

figure n (x:xs) = n' : figure n' (delete n' xs) where n' = n + x

```
```

`hofstadterNth n = hofstadter !! (n-1)`

You can run the program at http://programmingpraxis.codepad.org/0eJy4jur.

With our new stream library we can render that in Scheme like this:

`(define-stream (figure n xs)`

(let ((n-prime (+ n (stream-car xs))))

(stream-cons n-prime

(figure n-prime

(stream-filter

(lambda (x) (not (= x n-prime)))

(stream-cdr xs))))))

```
```(define hofstadter

(stream-cons 1

(figure 1

(stream-from 2))))

`(define (hofstadter-nth n)`

(stream-ref hofstadter (- n 1)))

That works perfectly well, but it’s not as fast as Haskell because Scheme streams are bolted-on to the language instead of built-in, and are very slow. You can run the program at http://programmingpraxis.codepad.org/XzHqlaHb.

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

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

[…] 1 2 […]

[…] Question is from here. […]

Java solution here

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++;

}

}

Python generator

C# solution

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;

}

}

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.

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)))))))))

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.

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

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;

}

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

}

}

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

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

An interesting Haskell solution

ffs = 1 : zipWith (+) ffs ffs’

where ffs’ = 2 : zipWith (+) ffs’ ffs”

ffs” = [2..] >>= twoOnes

twoOnes n = 2 : replicate n 1

An easy Python solution. Finds first n numbers in sequence by distributing every number in either fg or bg starting from i.

fg=[1]; bg=[2]; c=0; i=3; n=10

while(len(fg) c and fg[c]+bg[c] == i:

fg.append(i)

c += 1

else:

bg.append(i)

i += 1

The weird len(bg) > c comparison can be ommited if we give some more information to background (bg) and foreground (fg) since we can easily see that background is growing strictly faster:

fg=[1, 3]; bg=[2, 4]; c=1; i=5; n=10

while(len(fg) < n):

if fg[c]+bg[c] == i:

fg.append(i)

c += 1

else:

bg.append(i)

i += 1

Wow sorry for the double post but WP really mangled the code. I hope it’s better now.

An easy Python solution. Finds first n numbers in sequence by distributing every number in either fg or bg starting from i.

The weird len(bg) > c comparison can be ommited if we give some more information to background (bg) and foreground (fg) since we can easily see that background is growing strictly faster: