Permutation Sequence

[franktaw at netscape.net]

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