A Permutation Based On Largest Odd Divisor

[David Wilson]

Yes this sequence is a permutation of the positive integers.

(1) The sequence contains only positive integers.

By definition, each element is a positive integer.

(2) The sequence contains at most one instance of each positive
integer.

By definition, each element is distinct from all previous elements.

(3) Each positive integer is in the sequence.

Suppose some positive integer is not in the sequence.  Then there is
some least positive integer k that is not in the sequence.  This means
every j < k appears in the sequence, that is, there exists i with a(i) = j.
Let m = MAX(j < k, i(j)).  Then every j < k appears in the sequence
between a(1) and a(m).  Because k is not in the sequence, k must be the
least excluded element from a(m+1) onward.  Choose 2^n > m. Then
k is the least excluded element at a(2^n).  The largest odd divisor of
2^n is 1, so a(2^n) is the first (least) excluded element, and a(2^n) = k.
But then k is in the sequence, a contradiction.

----- Original Message ----- 
From: "Hans Havermann" <pxp at rogers.com>
To: <ham>; <seqfan at ext.jussieu.fr>
Sent: Friday, December 24, 2004 10:05 PM
Subject: Re: A Permutation Based On Largest Odd Divisor


> Leroy Quet:
> 
>> %S A101319
>>  1, 2, 3, 6, 7, 12, 8, 4, 5, 14, 17, 28, 18, 21, 35, 50, 40, 15, 30, 
>> 31, 51, 72, 23, 43, 66, 56, 20, 16, 9, 27, 54, 55, 87, 120, 38, 45, 
>> 79, 115, 153, 192, 13, ...
>> %N A101319
>>  a(1) = 1; a(n) = (largest odd divisor of a(n-1))th lowest positive 
>> integer not yet in the sequence.
> 
>> Is this a permutation of the positive integers?
> 
> Just to note that in the first 50000 terms, the maximum term is 697616 
> at index 48568 and the smallest terms not yet encountered are: {225, 
> 234, 302, 393, 439, 452, 497, 547, 602, ...}
>