OEIS/A322469

Name: Permutation of the natural numbers: Step by 4 and replace factors 3 by 2.

3, 1, 2, 7, 11, 15, 5, 10, 19, 23, 27, 9, 18, 6, 12, 4, 8, 31, 35, 39, 13, 
26, 43, 47, 51, 17, 34, 55, 59, 63, 21, 42, 14, 28, 67, 71, 75, 25, 50, 79, 
83, 87, 29, 58, 91, 95, 99, 33, 66, 22, 44, 103, 107, 111, 37, 74

Offset: 1,1

Comments: The sequence is the flattened form of an irregular table T(i, j)
(c.f. the example below) which has rows í >= 1 consisting of subsequences 
of varying length as defined by the following algorithm: 
    T(i, 1) := 4i - 1; j := 1;
    while T(i, j) divisible by 3 do
        T(i, j + 1) := T(i, j) / 3; 
        T(i, j + 2) := T(i, j + 1) * 2;
        j := j + 2;
    end while
The algorithm successively replaces any factor 3 by a factor 2,
and therefore it always stops. The first rows which are longer 
than any previous row are 1, 7, 61, 547, 4921 ... (A066443).

Property: The sequence is a permutation of the natural numbers > 0.
Proof: (Start)
The values in the columns j of T for row indexes i of the form 
i = e * k + f, k >= 0, if such columns are present, have the following 
residues modulo some power of 2:

 j | Op.  | Form of i    |  T(i, j)     |  Residues  | Residues not yet covered
---+------+ -------------+--------------+------------+-------------------------
 1 |      |  1 * k +  1  |   4 * k +  3 |   3 mod  4 |   0,  1,  2     mod  4
 2 | / 3  |  3 * k +  1  |   4 * k +  1 |   1 mod  4 |   0,  2,  4,  6 mod  8
 3 | * 2  |  3 * k +  1  |   8 * k +  2 |   2 mod  8 |   0,  4,  6     mod  8
 4 | / 3  |  9 * k +  7  |   8 * k +  6 |   6 mod  8 |   0,  4,  8, 12 mod 16
 5 | * 2  |  9 * k +  7  |  16 * k + 12 |  12 mod 16 |   0,  4,  8     mod 16
 6 | / 3  | 27 * k +  7  |  16 * k +  4 |   4 mod 16 |   0,  8, 16, 24 mod 32
 7 | * 2  | 27 * k +  7  |  32 * k +  8 |   8 mod 32 |   0, 16, 24     mod 32
 8 | / 3  | 81 * k + 61  |  32 * k + 24 |  24 mod 32 |   0, 16, 32, 48 mod 64
 9 | * 2  | 81 * k + 61  |  64 * k + 48 |  48 mod 64 |   0, 16, 32     mod 64
...| ...  |  e * k +  f  |   g * k +  m |   m mod  g |   0, ...

The variables in the last, general line can be computed from the
the operations in the algorithm. They are the following:
  e = 3^floor(j / 2)
  f = A066443(floor(j / 4)) with A066443(0) = 0, A066443(n) = 9 * A066443(n-1) - 2 
  g = 2^floor((j + 3) / 2)
  m = 2^floor((j - 1) / 4) * A084101(j + 1 mod 4) with A084101(0..3) = (1, 3, 3, 1)

The residues m in each column and therefore the T(i, j) are all disjoint.
For numbers which contain a sufficiently high power of 3, the length of 
the rows grows beyond any limit, and the numbers containing any power of 2 
will finally be covered 
(End)
The lengths grow slowly; for example, the first number not in a(1..10^7) is 65536.

Example:
  i | j = 1  2  3  4  5  6
----+--------------------
  1 |     3  1  2
  2 |     7
  3 |    11
  4 |    15  5 10
  5 |    19
  6 |    23
  7 |    27  9 18  6 12  4

Prog: 
(PARI) n=1; for(i=1,100, a=4*i-1; print1(a); while(a%3==0, a=a/3;\
print1(" ", a); a=a*2; print1(" ", a)); print;)
(Perl) use integer; my $n = 1; my $i = 1; 
while ($i < 1000) {
  my $an = 4 * $i - 1; print "$n $an\n"; $n ++;
  while ($an % 3 == 0) {
    $an /= 3; print "$n $an\n"; $n ++;
    $an *= 2; print "$n $an\n"; $n ++;
  } $i ++; 
} 

Crossrefs: Cf. A066443, A084101
Keywords: nonn,tabf,easy
Author: Georg Fischer