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

Pages: 1 2 3

### 20 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
if low == high:
del self.vals
else:
self.vals = 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;
i = 0;
}
else if (sum == 150)
{
goto End;
}
ng = 0;
}
End:

17. Patrick Herrmann said

ffs = 1 : zipWith (+) ffs ffs’
where ffs’ = 2 : zipWith (+) ffs’ ffs”
ffs” = [2..] >>= twoOnes
twoOnes n = 2 : replicate n 1

18. Daniel said

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

fg=; bg=; 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

19. Daniel said

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.

```fg=; bg=; c=0; i=3; n=10
while(len(fg) < n):
if len(bg) > 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
```