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 a 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 always stops, and in one row,
it successively replaces any factor 3 by a factor 2.
Property: The sequence is a permutation of the natural numbers > 0.
Proof: (Start)
The values in columns j in the table's rows i of the form i = f * k + g,
k >= 0, if such columns are present, have the following residues modulo
powers of 2:
j | Op. | Form of i | T(i, j) | Residues | Residues not yet covered
---|-----| ----------|-----------|------------|-------------------------
1 | | 1k + 1 | 4k + 3 | 3 mod 4 | 0, 1, 2 mod 4
2 | /3 | 3k + 1 | 4k + 1 | 1 mod 4 | 0, 2, 4, 6 mod 8
3 | *2 | 3k + 1 | 8k + 2 | 2 mod 8 | 0, 4, 6 mod 8
4 | /3 | 9k + 7 | 8k + 6 | 6 mod 8 | 0, 4, 8, 12 mod 16
5 | *2 | 9k + 7 | 16k + 12 | 12 mod 16 | 0, 4, 8 mod 16
6 | /3 | 27k + 7 | 16k + 4 | 4 mod 16 | 0, 8, 16, 24 mod 32
7 | *2 | 27k + 7 | 32k + 8 | 8 mod 32 | 0, 16, 24 mod 32
8 | /3 | 81k + 61 | 32k + 24 | 24 mod 32 | 0, 16, 32, 48 mod 64
9 | *2 | 81k + 61 | 64k + 48 | 48 mod 64 | 0, 16, 32 mod 64
...| | f*k + g | ... + r | |
In general, f is a power of 3 increasing in every second column,
and g is taken from A066443 (a(0) = 1; a(n) = 9 * a(n-1) - 2
for n > 0). g increases in every fourth column. The residues r
follow the pattern (3, 1, 1, 3) * 2^h, where h increases in
every second column.
The residues in each column and therefore the values are all disjoint,
and with i (and j, k) going to infinity, they cover all natural numbers > 0.
(End)
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: (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 ++;
} # A323232.pl, Georg Fischer Dec. 9 2018
Crossrefs: C.f. A066443, A084101
Keywords: nonn,tabf,easy
Author: Georg Fischer