Talk:Hofstadter Figure-Figure sequences

No max n

That statement is there to explicitly exclude solutions that used a fixed sized array, say of a 1000 elements and an empty array, then moved elements between the two arrays.

Mind you, an algorithm that started with fixed array sizes and doubled their sizes as necessary would be OK. --Paddy3118 08:37, 22 October 2011 (UTC)

S(n)

The sequence S(n) is further defined as the sequence of positive integers not present in R(n).

I think this should be S(n) is defined as the nth integer in the sequence of positive integers not present in R(n). If S(n) is itself a sequence then R(n) would be a sequence, but the example R(n) values suggest that R is a sequence and R(n) is an integer from that sequence. --Rdm 16:34, 22 October 2011 (UTC)

Hmm. You're right, but then I can't help but think that S(n) can stand for both an integer given a particular value of n, or the sequence when thinking of n as being an arbitrary value? It seems to me that it can be either or both, but either way, would you go further and say that you could not determine the meaning of the sentence?

I'm inclined to leave it as-is. --Paddy3118 17:44, 22 October 2011 (UTC)

In the general case, yes, we might use S(n) to refer to a sequence. However, for this to be accurate, n needs to be an unbound value. And in that particular sentence, we are talking about n having a specific value (which is used in R(n)). Anyways, from my point of view the phrasing is confusing (and opens up questions like: is it possible for S(n) to contain values for some value of n which are not present in later values of n? And rather than delve into the issues that I would need to tackle to determine whether or not this could be a relevant topic, I would rather the notation be self consistent). --Rdm 17:56, 22 October 2011 (UTC)

Not really, this aspect of the definition is present in the references too. I suspect that it may be a part of the original description cited as: D. Hofstadter, "Gödel, Escher, Bach", p. 73, but I don't have it to hand at the moment to check. When I first saw their definition I found it confusing at first too, but that is what made it interesting when trying to code it.

When I had finished the Python version I checked it with tables of the first 1000 values refered to from Sloane: here for R and here for S, although the table for S has an off-by-one error. --Paddy3118 18:31, 22 October 2011 (UTC)

Another ref. with a similar definition: CRC concise encyclopedia of mathematics By Eric W. Weisstein pp 1385. --Paddy3118 18:40, 22 October 2011 (UTC)

Ok, well, I think that's sloppy use of terminology, but I suppose that if they are not considering any possibilities involving sequences of sequences that the sloppiness becomes invisible. --Rdm 19:08, 23 October 2011 (UTC)

It is pretty common to say "S(n)" while meaning "sequence S with n denoting its index", and it's unambiguous. For one thing, the very first sentence already said "sequence of positive integers", which is pretty impossible to be misunderstood as "sequence of sequences of integers". This is how human discuss math using a natural language, there's no need to exercise a context-free parser here. --Ledrug 20:11, 23 October 2011 (UTC)

That's not the issue. S(n) would still be an integer sequence if S was a sequence of sequences. To resolve this conudrum, we have to incorporate the statement giving the first few values of S as a part of the definition. They are specified, of course (but if they had been omitted, then S(2) and R(3) would have been ambiguously defined). --Rdm 11:32, 24 October 2011 (UTC)