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

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. [...]

```import Data.List

hofstadter = unfoldr (\(r:s:ss) -> Just (r, r+s:delete (r+s) ss)) [1..]
```
3. [...] Question is from here. [...]

4. Hamid said

Java solution here

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

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

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

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(){
if(++nextS == hof.elementAt(hofCheckIndex)){
nextS++;
hofCheckIndex++;
}
}

6. Mike said

Python generator

```import itertools as it

hs = set()
h = 0
for s in it.filterfalse(hs.__contains__, it.count(1)):
h += s
yield h
```
7. 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;
}
```
8. 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)
{
++i;
}

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

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

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

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++;
}
}
```
12. 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).

13. Keith said

I hacked this out in Perl, and after the fact found it very similar to beardedone85′s Java solution
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;
}

14. Scott said

import java.util.Vector;

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

while(N>n++){
System.out.println(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”.

16. Alcriss said

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

for (int i = 1; i <= count – ng; i++)
{
Console.Write(" " + sum + ", ");
if (i == count)
{
count = count + 1;