Permutation Sequence

[franktaw at netscape.net]

I was a bit tired by the time I got around to submitting this.  A 
couple of people have pointed out problems.

First of all, it should read [n/2] appears in the sequence before n, 
not the reverse.

Second, it's been suggested I should use floor(x) instead of [x].  Is 
this in fact the standard for OEIS?  If so, it's widely violated.

It's also been suggested that the full description of the sequence 
should be on the name line, instead of as a formula.  I'm not sure 
about this one, either.

-----Original Message-----
   I just submitted the following sequence, which I find very 
interesting.

 %I A000001
  %S A000001 
1,2,4,8,16,32,5,10,3,6,12,24,48,96,9,18,36,72,144,288,576,1152,33,66,132,
11,22,44,
  
88,176,13,26,52,7,14,28,56,112,224,448,21,42,84,168,336,672,25,50,100,200
,400,20,
  
40,80,160,320,17,34,68,136,272,544,23,46,92,184,368,19,38,76,152,304,608,
1216,2432
 %N A000001 a(n) = [sqrt(a(n-1))] or 2a(n-1)
  %C A000001 One can show (inductively) that n must appear in the 
sequence before [n/2], showing that the sequence is one-to-one; and 
that frac(log_2(log_2(a(n))) is dense in [0,1), from which it follows 
that a(n) is onto.
  %H A000001 <a 
href="http://www.research.att.com/~njas/sequences/Sindx_Per.html#IntegerP

  ermutation">Index entries for sequences that are permutations of the 
natural numbers</a>
  %F A000001 a(1) = 1; if [sqrt(a(n-1))] is already in the sequence, 
a(n)=[sqrt(a(n-1))], otherwise a(n) = 2a(n-1).
 %Y A000001 Cf A000196, A000523.
 %O A000001 1
 %K A000001 ,nice,nonn,
 %A A000001 Frank Adams-Watters (FrankTAW at Netscape.net), Feb 04 2006

  I was quite surprised that this sequence turned out to be a 
permutation of the integers. That it is onto seems obvious, although 
the actual proof is a bit tedious. That it is one-to-one is less 
immmediately obvious, although it turns out to be easier to prove.

  Similar sequences with the ceiling or rounded square root, and/or 
other integer multipliers instead of 2, also seem to produce 
permutations. Essentially the same proof will work for different 
multipliers and for taking the ceiling of the square root; I haven't 
worked out a proof for the rounding case.

 Franklin T. Adams-Watters
 16 W. Michigan Ave.
 Palatine, IL 60067
 847-776-7645

___________________________________________________
Try the New Netscape Mail Today!
Virtually Spam-Free | More Storage | Import Your Contact List
http://mail.netscape.com