|
| |
|
|
A363686
|
|
Irregular triangle T(n, k) read by rows which represents a predecessor number system for Collatz sequences (see Comments for precise definition).
|
|
1
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
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.
|
|
|
EXAMPLE
|
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.
|
|
|
PROG
|
(MATLAB)
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
(PARI)
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
|
|
|
CROSSREFS
|
Column 1 gives A283507 starting from its third term.
Right border gives A052539 starting from its second term.
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
