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