Murthy's sequence A073675, etc.

[David Wilson]

Let r >= 1, and for nonnegative integer n >= 0 define

    b(n) = floor(n/r)
    c(n) = floor(n*r)
    a(n) = b(n) if b(n) does not yet appear in the sequence; else c(n).

We can then show that for n >=

    {b(n) < n} is a nondecreasing sequence that includes every nonnegative integer.
    {c(n) >= n} is a strictly increasing sequence.

Now suppose nonnegative integer k does not appear in {a(n)}.  Since every nonnegative integer is in {b(n)}, we have k = b(n) for some n.  But since k = b(n) does not appear in {a(n)} prior to a(n), we have a(n) = b(n) = k by definition.  Hence {a(n)} indeed includes k, showing that every nonnegative integer appears in {a(n)}.

Now suppose a(n) = k.  Let m > n.  If a(m) = a(n), then a(m) appears in {a(n)} prior to a(m).  This would mean that a(m) = c(m) by definition.  Since {c(n)} is strictly increasing, m > n gives c(m) > c(n) >= n > b(n), so c(m) is greater than both c(n) and b(n), which are the only possible values of a(n), hence a(m) != a(n).  This means that element {a(n)} appears at most once in {a(n)}, which establishes that {a(n)} is indeed a permutation of the nonnegative integers.

-----------
We can restrict the domain and range of {a(n)} to the positive integers.  To do this, we use the more complicated definition

    a(n) = b(n) if b(n) >= 1 and b(n) does not yet appear in the sequence; else c(n).

The proof is rather messier, but we arrive the desired result that {a(n)} is a permutation of the positive integers.

------------
Regarding A073675, it is best to start with the definition

    a(2k+1) = 4k+2; a(4k+2) = 2k+1; a(4k) = 4a(k)

and show that this coincides both with the current defintion of A073675 and with {a(n)} for r = 2.  I am sure the proof will go through.

------------
My above proof shows that {a(n)} is a permutation of the nonnegative (positive) integers for any r > 1.  Clearly r = 1 gives a(n) = n, also a permutation.

When r < 1, b(n) is a strictly increasing sequence, so that every element of b(n) is new, giving a(n) = b(n).  However, there will be n where b(n+1) > b(n)+1, so not every nonnegative (positive) integer will appear in {a(n)}.

----------
Not much to say about cycles, except that my instinct is that some choices of r will result in infinite cycles.

  From: Kimberling, Clark 
  To: seqfan at ext.jussieu.fr 
  Sent: Thursday, February 02, 2006 10:18 AM
  Subject: Murthy's sequence A073675, etc.


  Sequence Fans,

  A073675 starts out with 2,1,6,8,10,3,14,...  , the "Rearrangement of natural numbers such that a(k) is the smallest divisor of k not included earlier and if no such divisor exists then the smallest multiple of k not included earlier."

  For any positive real r, define a sequence b(n) by

  b(n) = Floor(n/r) if this number isn't yet in the sequence; else
  b(n) = Floor(r*n) otherwise.

  If r=2, the sequence b also starts out 2,1,6,8,10,3,14,...  Is this also A073675?

  Continuing with r=2, let c be the sequence of numbers k such that k>b(k).  Is c = A036554?

  Let r = sqrt(2), for which the sequence b starts with 1,2,4,5,3,8,9,11,6,7,15,...
  Is this a permutation of the natural numbers?  (For what choices of r is this true?)
  Are the terms in this sequence generated in cycles, such as 3 -> 4 ->5 ->3 
  and 6 -> 8 -> 11 -> 15 -> 10 -> 7 -> 9 -> 6?  What can be said about the lengths of cycles?

  Clark Kimberling 
    

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20060202/584cd8c0/attachment-0001.htm>