Conference rusure::math

140.0. "n separated by n numbers" by HARE::STAN () Fri Aug 24 1984 17:35

Here is another interesting sequence I learned about at Dave Roselle's talk:

Start with a sequence beginning with two 0's.  Place a 1 next to them and
then skip 1 space and place a second 1.  Then place a 2 in the first
unoccupied position in the sequence.  Skip 2 spaces and place another 2.
So far we have:

	0 0 1 2 1 * 2 * * *

where "*" denotes an as-yet unoccupied position.  Then place a 3 in the
first (leftmost) unoccupied position and skip 3 spaces and place another 3.
Then place a 4, skip 4 spaces, and place another 4.  This gives

	0 0 1 2 1 3 2 4 * 3 * * 4 * * *    .

It can be proven that you can always continue to do this (i.e. when you go
to place your second "k" you will never find that that position is already
occupied.)  You get the following sequence:

	0 0 1 2 1 3 2 4 5 3 6 7 4 8 5 9 ...

Furthermore, it can be proven that the leftmost position of the number n
occurs in position [(n+1)(1+sqrt(5))/2] where the brackets denote the
floor function.

--------------------
A related problem where little is known is this: Start with 1 and at each
stage, find the leftmost position in which you can place the next number, k,
skip k positions, then place a second k, skip k positions, and then place
a third k.  For example, this process begins with

	1 * 1 2 1 * 2 3 4 2 5 3 * 4 * 3 5 * 4 * * *

where "*" denotes an as-yet unoccupied position.  Note that if you can't
place all three k's, then you have chosen the wrong initial position and
you should go on to the next one.  For example, 2 could not have been placed
in the 2nd position above since this would have required a second 2 to be
placed at position 5, but a 1 is already at position 5.  So 2 got placed
at the next available position (position 4).  The following questions
are still open:

(a) does position 2 ever get filled in by some number?

(b) find a formula for the leftmost position for the integer n.

Regarding the "harder problem".

Le Computer shows that position 2 is not filled by any number less than 32000.
It's a safe bet that it's never filled.

The left-most position of the number n is given (very roughly) by n*2.215.
An analysis giving the exact value of this constant (as n approaches infinity)
shouldn't be very difficult.

If the problem "places the pattern" 0,n,2*n, then a generalization is to place
the pattern 0,f1(n),f2(n),...,fm(n), where each f(n) is a strictly increasing
function of n.  I suspect the generalized problem leaves at most a finite number
of "holes".