OEIS/A322469

From tehowiki
Revision as of 09:44, 9 December 2018 by imported>Gfis (Algorithm in the name)
Jump to navigation Jump to search
Name: Permutation of the natural numbers: Start with 3, divide by 3 and multiply by 2 as long as possible, then increase the start value by 4.
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 tries to divide by 3 and multiply by 2,
as long as the number contains a factor 3. 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: tabf,easy
Author: Georg Fischer