Paul Conradi - cp's OEIS frontend

User: Paul Conradi

Paul Conradi has authored 1 sequences.

A363686 Irregular triangle T(n, k) read by rows which represents a predecessor number system for Collatz sequences (see Comments for precise definition).

5, 3, 17, 23, 25, 11, 65, 15, 73, 59, 33, 7, 185, 43, 257, 95, 105, 219, 97, 39, 249, 363, 385, 175, 9, 123, 929, 199, 57, 171, 1025, 63, 297, 411, 481, 487, 633, 747, 129, 367, 393, 507, 1697, 583, 1849, 939, 513, 287, 233, 347, 1377, 423, 1529, 619, 3969, 815, 265, 1403, 1441, 1479, 1593, 683, 4097

Offset: 1

Paul Conradi, Jun 15 2023

Binary tree that contains odd numbers. Predecessors to numbers of Collatz sequences are determined.
The variables u and d are used here to distinguish between one and two consecutive even numbers in a Collatz sequence: If there is one even number between two odd numbers in the Collatz sequence, then this is a u-evolution; if there are two even numbers, then this is a d-evolution: 3 is a u-predecessor of 5, 17 is a d-predecessor of 13.
Each integer is assigned to a mod residue class from A000079. The offset 5 receives the modulo 8. Later the u-number gets the doubled modulo, the d-number gets the quadrupled modulo. These attached modulo are used to increase the base in the design for predecessors if necessary. The exponent results from the sequence A119476 starting with the second term.
Two predecessors are determined for every integer backwards to the procedure for the Collatz problem: a u-predecessor and a d-predecessor.
The main rule is that we calculate u = (m*2-1)/3 and d = (m*4-1)/3. If this calculation does not result in an integer, we add to m its associated modulus n: m' = m + n.
First step: 5*2 = 10, next: 10-1 = 9, next: 9/3 = 3. As described above, 3 is a u-predecessor of 5. To determine the d-predecessor, 5 is already used, so we have to add the modulus 8: 5+8 = 13. The d-predecessor to 13 has to use the factor 4. So 13*4 = 52 and 52-1 = 51 and 51/3 is 17. 17 is the d-predecessor of 5.
So 5 has the two generating predecessors 3 and 17. As described above, the following attached modulo now result: 3 mod 16 and 17 mod 32.
For numbers m divisible by 3, the predecessor is formed with the next element of the residue class. In the same way - as described above - if (m*2-1)/3 or (m*4-1)/3 doesn't work, the predecessor is formed with the next element m' of the residue class.
Example: u-predecessor of 3: 3 has no predecessor. 19 (3+16) does not work for u-formation, because 2*19-1 = 37 is not divisible by 3. So the predecessor of 35 (3+16+16) is formed. It is 23, because 35*2-1 = 69 and 69/3 = 23.
Example: d-predecessor of 3: 19 (3+16): 19*2*2-1 = 75. 75/3 = 25.
Example: u-predecessor of 17: (17*2-1)/3 = 11.
Example: d-predecessor: 17+32 = 49 is taken. 49*4-1 = 195. 195/3 = 65.
Note: There is a canonical u-predecessor and a d-predecessor for every odd number.
Sketch of a proof of this:
If we look for an odd Collatz predecessor for an odd number m > 1, there are only three cases:
1) m is divisible by 3;
2) m has a u-predecessor, so m*2-1 is divisible by 3;
3) m has a d-predecessor, so m*4-1 is divisible by 3.
The addition (m' = m + 2^n) of m to a power of 2 forces these cases to alternate, so there is no other possibility at all. This follows from modular arithmetic.
Note: If we start the corresponding Collatz sequence with a number T(n, k), then there are at least n odd numbers in this Collatz sequence.
Conjecture: With the associated residue classes, this sequence forms a complete decomposition of the odd integers. In other words: If we form the complete residue classes to each number from this sequence, then all odd numbers > 1 occur once.
Remark: Even if it can be shown that every odd integer can be transformed by a Collatz sequence into a number equivalent to 5 mod 8, this does not mean that the sequence already ends immediately in the 4-2-1 cycle. For example, T(4, 2) = 73 is transformed into 125, but then jumps up again to T(14, k) = 47.

			Triangle begins:
    5;
    3,  17;
   23,  25,  11, 65;
   15,  73,  59, 33,  7, 185,  43, 257;
   95, 105, 219, 97, 39, 249, 363, 385, 175, 9, 123, 929, 199, 57, 171, 1025;
   ...
For n = 2, T(2, 1) = 3 because 3 is an odd Collatz-predecessor of 5.

Andrä Knispel, Table of n, a(n) for n = 1..127
Eric Weisstein's World of Mathematics, Collatz Problem
Wikipedia, Collatz conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem
Wikipedia, Notizen zu Collatzfolgen

Row lengths give A000079.
Column 1 gives A283507 starting from its third term.
Right border gives A052539 starting from its second term.
Cf. A000265, A056792, A339694.

function a = A363686( max_n )
    a = 5; r = 8;
    for n = 2:max_n
        nh = floor(n/2); e = 2^(1 + mod(n, 2)); k = a(nh);
        if mod((k*e-1), 3) == 0
            k = (k*e-1)/3;
        else
            k = k + r(nh);
            while mod((k*e-1), 3) ~= 0
                k = k + r(nh);
            end
            k = (k*e-1)/3;
        end
        r(n) = r(nh)*e; a(n) = k;
    end
end % Thomas Scheuerle, Jun 23 2023

A056792(n)=n=binary(n); sum(i=1, #n, n[i])+#n-1;
a(n)=if(n==1, return(5), for(x=0, 2, my(k=a(floor(n/2))+x*2^(A056792(floor(n/2))+2)); if((k*2^(1+(n%2))-1)%3==0, return((k*2^(1+(n%2))-1)/3)))) \\ Thomas Scheuerle, Jun 23 2023

For n > 1 holds: (3*a(n) + 1)/2^(1 + mod(n,2)) - a(floor(n/2)) = r*2^(A056792(floor(n/2)) + 2) with for r the least integer from the set {0, 1, 2}. - Thomas Scheuerle, Jun 23 2023

Conjecture: Every odd number > 1 is congruent to a(k) mod 2^(A056792(floor(k/2)) for some k.

cp's OEIS Frontend

User: Paul Conradi

A363686 Irregular triangle T(n, k) read by rows which represents a predecessor number system for Collatz sequences (see Comments for precise definition).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

PARI

Formula