How can I generate the nth number in the Godel, Escher, Bach number sequence?

[recon]

I've been reading Godel, Escher and Bach. In Chapter III - Figure and Ground, there is this number sequence:

1 3 7 12 18 26 35 45 56 69 ...

I understand that every number is expressed once, covert or overt, in the sequence above.

For example you can 'find' 2 in the gap between 1 and 3. You can 'find' 4 in the gap between 3 and 7, 5 in the gap between 7 and 12, etc.

Can someone please show me an algorithm that I can use for generating the nth number in this sequence?

 

[philosophking]

Hey, I read that book too. Awesome stuff. I think what Hofstadter was trying to explain there was the different "levels" of sequences--am I correct?

If so, I think you have to take it another level. For example, the "first-level" differences between the numbers are 2, 4, 5, 6, 8, 9, 10, 11, 13,...

But this really doesn't tell you much. But the "second level" differences are 2, 1, 1, 2, 1, 1, 1, 2, ...

Hm. Seems like we may have a pattern. The "second level" differences have a 2, then two 1's, then a 2, then three 1's, then a 2...

I think from this you can set up the pattern. Let me know what you get.

 

[recon]

I get it now. Thanks philosophking. The problem wasn't primarily about looking at different "levels". It was about looking at the "Figure" and "Ground", i.e. the numbers themselves and the gaps between them on the "first level".

 

[GrapesOfWrath]

If so, I think you have to take it another level. For example, the "first-level" differences between the numbers are 2, 4, 5, 6, 8, 9, 10, 11, 13,...

But this really doesn't tell you much. But the "second level" differences are 2, 1, 1, 2, 1, 1, 1, 2, ...

Hm. Seems like we may have a pattern. The "second level" differences have a 2, then two 1's, then a 2, then three 1's, then a 2...

I think from this you can set up the pattern. Let me know what you get.

2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2,
ok so far
1, 1, 1, 1, 1, 1, 2
hmm...

 

[philosophking]

Grapes, are you trying to disprove me or confirm my results? I'm confused :P

 

[GrapesOfWrath]

Your results (2, 1, 1, 2, 1, 1, 1, 2, ) are OK, I just extended them. The first level differences are just the numbers that were "left out" of the first sequence, the second level differences have a 2 whenever the first level differences skips over a element of the original sequence.

 

[HenriqueAndrade]

The algorithm

I think I made the algorithm:

function GEB(){
i := 1;
p := 0;
L.[p] := 1;
while(true){
temp = true;
while(temp) {
if (temp = search(i,L))
i++;
}
L[p+1] := L[p] + i;
p++;
i++;
}
}



function search(x,L){

for (i=1, i<=n, i++){ // n is the number of elements of array L
if (L == x){
return true;
}
}
return false;
}


Is it correct?

 

[3trQN]

Take it up another level:

A = 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2

B = 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1

C = 1 2 3 ...

Now that's even easier, Its just like Pulse Width Modulation, the period of the off pulse increases with n.

Now define a function for each level, and plug each function into the other.

So operating on the integers A (1,2,3..) a function mapping to B and then likewise for A, its easier to program the algo if you break it down like that i think.

The first function would not be recursive like the rest though. i.e. F(n) : C -> B and G(b) : B -> A and G(a) : A -> X

G(x) can be applied recursivley as G(G(G(G(...))) etc...i think.