Murthy's sequence A073675, etc.

[franktaw at netscape.net]

First of all, the description of A073675 should be changed, replacing "divisor" with "proper divisor" and "multiple" with "proper multiple".
 
Second, this is closely related to A035263: if A035263(n) = 1, A073675(n) = 2n; otherwise A073675(n)=n/2.  And yes, this matches both the definition of A073675 and Clark's definition (with r=2), so those define the same sequence.
 
Clark's definition will give a permutation of the natural numbers for any r >= 1.  If n has not appeared in the sequence previously, it will appear at ceiling(n*r).  Conversely, floor(n*r) is greater floor(m*r) for any m<n, and so greater than any preceding member of the sequence; thus no number can appear twice.
 
If 0 < r < 1, the result will be a Beatty sequence for 1/r, which will thus not include all natural numbers.
 
As for cycles, the answer in general is no.  Taking r = phi^2, starting with 1, we get
1,2,5,13,34,89,... (A001519, a bisection of the Fibonacci sequence).
 
Probabilistically, let probability p = P(b(n) = [n/r]) = P([n/r] > [(n-1)/r] AND f([n/r] != [[n/r]/r])) =
(waving our hands here, there is no guarantee these conditions are independent) 1/r * (1-p).  Solving for p, we get p = 1/(1+r).  Then the expected value E(ln(b(n))) = 1/(1+r)*log(n/r) + 1/(1+r)*log(n*r)  = log(n) + (r-1)/(r+1)*ln(r), (more hand-waving here), so the trajectory from a given starting point can be expected to increase without limit.  (Use of the log is appropriate here, since we are multiplying and dividing to get the next term.)  Nothing definitive here, but I suspect that for a randomly chosen r (i.e., with probability 1), the values whose trajectory is unbounded has density 1.
 
On the other hand, for the particular case r = sqrt(2), the trajectories may all be cycles.  The numbers 23*2^k seem to start cycles of roughly double length at each step (verified through k=4, k=5 is next value not yet in a cycle).  (Probably this is actually ceiling(C*2^k) for some real number C, since the preceding cycles start at 1,2,3,6, and 12.  If so, 0.71777 < C <= 0.71875.)
 
-----Original Message-----
From: Kimberling, Clark ck6 at evansville.edu


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 
  
 
 
___________________________________________________
Try the New Netscape Mail Today!
Virtually Spam-Free | More Storage | Import Your Contact List
http://mail.netscape.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20060202/b47745a7/attachment-0001.htm>