[seqfan] Re: seqs whose |differences| are 1,2,3,4,...

N. J. A. Sloane njas at research.att.com
Thu Mar 11 06:06:52 CET 2010


Franklin,  I had seen your message, but I had not appreciated
what it said!

I've read the message several times, but I admit I don't understand it.

The crucial two paragraphs are these, I believe:

(start)

If this is correct, it provides a negative answer to Conway's question. 
  Given any infinite, one-to-one sequence with the specified difference 
property, we can extend any initial segment to a bijection.  Extend the 
segment to where it reaches a new maximum.  Now (this is a bit vague, 
but is doable) futz around until you can extend to the smallest number 
not yet used and back to another new maximum, then do so.  Repeat this 
for the remainder of the sequence, and you have a bijection.

However, since the sequence Raff describes is the lexicographically 
first one-to-one sequence with the difference property, any sequence we 
generate in this way can be bettered by going further with the 
backtracking heuristic before switching to the algorithm I describe.  
In other words, Raff describes a sequence which is the greatest lower 
bound of all sequences with the desired property.  If it doesn't have 
the property, there is no minimum.

(end)

I don't really follow the algorithm you give in the first
of the two paragraphs.  Could you possibly explain it in more detail?

I am also having trouble following the argument in the second 
paragraph.  Since Raff's sequence is not a permutation,
why should we start with it?

I can see that you are probably right, and that the sequence
we are looking for does not exist, but I would like to
see more details of the argument!


 Best regards
 			 Neil




More information about the SeqFan mailing list