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.
Programming Praxis 
[…] 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
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)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; }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.
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 99574Here’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++; } }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.
fg=[1]; bg=[2]; 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 += 1The 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