Question is from here.

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.

Solution:
Using this formula:

First 20 (n = 20) elements of this sequence:

import java.util.ArrayList;

public class Hofstadters_Sequence {
	static ArrayList s = new ArrayList();
	static ArrayList r = new ArrayList();

	public static void main(String[] args) {
		generate(20);
	}

	private static void generate(int n){
		int sum = 0, j = 2;
		//R(1) = 1
		s.add(1);
		//S(1) = 2
		r.add(2);
		
		while(s.size() < n) {
			//R(n) = R(n-1) + S(n-1)
			sum = s.get(s.size() - 1) + r.get(r.size() - 1);
			s.add(sum);
			//finding next element of S sequence
			for (int i = j; ; i++) {
				if(!s.contains(i) && !r.contains(i)){
					r.add(i);
					j = i;
					break;
				}
			}
		}
		//printing both sequences
		System.out.println("s: " + s);
		System.out.println("r: " + r);
	}
}

Output:

s: [1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260]
r: [2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25]