OEIS/A322469: Difference between revisions

From tehowiki
Jump to navigation Jump to search
imported>Gfis
Algorithm in the name
imported>Gfis
m Gfis moved page OEIS/Div3Mult2 Sequence to OEIS/A322469 without leaving a redirect
 
(3 intermediate revisions by the same user not shown)
Line 10: Line 10:
  (c.f. the example below) which has rows í >= 1 consisting of subsequences  
  (c.f. the example below) which has rows í >= 1 consisting of subsequences  
  of varying length as defined by the following algorithm:  
  of varying length as defined by the following algorithm:  
     T(i, 1) := 4i - 1; j := 1;
     T(i, 1) := 4 * i - 1; j := 1;
     while T(i, j) divisible by 3 do
     while T(i, j) divisible by 3 do
         T(i, j + 1) := T(i, j) / 3;  
         T(i, j + 1) := T(i, j) / 3;  
Line 42: Line 42:
  the operations in the algorithm. They are the following:
  the operations in the algorithm. They are the following:
   e = 3^floor(j / 2)
   e = 3^floor(j / 2)
   f = A066443(floor(j / 4)) with A066443(0) = 0, A066443(n) = 9 * A066443(n-1) - 2  
   f = A066443(floor(j / 4)) with A066443(0) = 0, A066443(n) = 9 * A066443(n - 1) - 2  
   g = 2^floor((j + 3) / 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)
   m = 2^floor((j - 1) / 4) * A084101(j + 1 mod 4) with A084101(0..3) = (1, 3, 3, 1)
Line 48: Line 48:
  The residues m in each column and therefore the T(i, j) are all disjoint.
  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  
  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  
  the rows in T grows beyond any limit, and the numbers containing any power of 2  
  will finally be covered  
  will finally be covered.
  (End)
  (End)
  The lengths grow slowly; for example, the first number not in a(1..10^7) is 65536.
  All numbers > 0 up to and including 2^(2*j + 1) appear in the rows in T up to and including
A066443(j). For example, 4096 and 8192 are the trailing elements in row 398581 = A066443(6).


  Example:
  Example:
   i | j = 1  2  3  4  5  6
The table T(i, j) begins:
  ----+--------------------
   i\j     1  2  3  4  5  6  7
   1 |    3  1  2
   1 |    3  1  2
   2 |    7
   2 |    7
Line 62: Line 63:
   5 |    19
   5 |    19
   6 |    23
   6 |    23
   7 |    27  9 18  6 12  4
   7 |    27  9 18  6 12  4 8


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


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

Latest revision as of 21:07, 3 August 2019

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) := 4 * i - 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 in T grows beyond any limit, and the numbers containing any power of 2 
will finally be covered.
(End)
All numbers > 0 up to and including 2^(2*j + 1) appear in the rows in T up to and including
A066443(j). For example, 4096 and 8192 are the trailing elements in row 398581 = A066443(6).
Example:
The table T(i, j) begins:
  i\j     1  2  3  4  5  6  7
  1 |     3  1  2
  2 |     7
  3 |    11
  4 |    15  5 10
  5 |    19
  6 |    23
  7 |    27  9 18  6 12  4  8
Prog: 
(PARI) n=1; for(i=1,1000, 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