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