[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:
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.
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!
More information about the SeqFan