cp's OEIS Frontend

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

%I A363686 #106 Feb 16 2025 08:34:05
%S A363686 5,3,17,23,25,11,65,15,73,59,33,7,185,43,257,95,105,219,97,39,249,363,
%T A363686 385,175,9,123,929,199,57,171,1025,63,297,411,481,487,633,747,129,367,
%U A363686 393,507,1697,583,1849,939,513,287,233,347,1377,423,1529,619,3969,815,265,1403,1441,1479,1593,683,4097
%N A363686 Irregular triangle T(n, k) read by rows which represents a predecessor number system for Collatz sequences (see Comments for precise definition).
%C A363686 Binary tree that contains odd numbers. Predecessors to numbers of Collatz sequences are determined.
%C A363686 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.
%C A363686 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.
%C A363686 Two predecessors are determined for every integer backwards to the procedure for the Collatz problem: a u-predecessor and a d-predecessor.
%C A363686 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.
%C A363686 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.
%C A363686 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.
%C A363686 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.
%C A363686 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.
%C A363686 Example: d-predecessor of 3: 19 (3+16): 19*2*2-1 = 75. 75/3 = 25.
%C A363686 Example: u-predecessor of 17: (17*2-1)/3 = 11.
%C A363686 Example: d-predecessor: 17+32 = 49 is taken. 49*4-1 = 195. 195/3 = 65.
%C A363686 Note: There is a canonical u-predecessor and a d-predecessor for every odd number.
%C A363686 Sketch of a proof of this:
%C A363686 If we look for an odd Collatz predecessor for an odd number m > 1, there are only three cases:
%C A363686 1) m is divisible by 3;
%C A363686 2) m has a u-predecessor, so m*2-1 is divisible by 3;
%C A363686 3) m has a d-predecessor, so m*4-1 is divisible by 3.
%C A363686 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.
%C A363686 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.
%C A363686 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.
%C A363686 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.
%H A363686 Andrä Knispel, <a href="/A363686/b363686.txt">Table of n, a(n) for n = 1..127</a>
%H A363686 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CollatzProblem.html">Collatz Problem</a>
%H A363686 Wikipedia, <a href="http://en.wikipedia.org/wiki/Collatz_conjecture">Collatz conjecture</a>
%H A363686 <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%H A363686 Wikipedia, <a href="https://de.wikipedia.org/wiki/Benutzer:Pacogo7/Notizen_zu_Collatzfolgen">Notizen zu Collatzfolgen</a>
%F A363686 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
%F A363686 Conjecture: Every odd number > 1 is congruent to a(k) mod 2^(A056792(floor(k/2)) for some k.
%e A363686 Triangle begins:
%e A363686     5;
%e A363686     3,  17;
%e A363686    23,  25,  11, 65;
%e A363686    15,  73,  59, 33,  7, 185,  43, 257;
%e A363686    95, 105, 219, 97, 39, 249, 363, 385, 175, 9, 123, 929, 199, 57, 171, 1025;
%e A363686    ...
%e A363686 For n = 2, T(2, 1) = 3 because 3 is an odd Collatz-predecessor of 5.
%o A363686 (MATLAB)
%o A363686 function a = A363686( max_n )
%o A363686     a = 5; r = 8;
%o A363686     for n = 2:max_n
%o A363686         nh = floor(n/2); e = 2^(1 + mod(n, 2)); k = a(nh);
%o A363686         if mod((k*e-1), 3) == 0
%o A363686             k = (k*e-1)/3;
%o A363686         else
%o A363686             k = k + r(nh);
%o A363686             while mod((k*e-1), 3) ~= 0
%o A363686                 k = k + r(nh);
%o A363686             end
%o A363686             k = (k*e-1)/3;
%o A363686         end
%o A363686         r(n) = r(nh)*e; a(n) = k;
%o A363686     end
%o A363686 end % _Thomas Scheuerle_, Jun 23 2023
%o A363686 (PARI)
%o A363686 A056792(n)=n=binary(n); sum(i=1, #n, n[i])+#n-1;
%o A363686 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
%Y A363686 Row lengths give A000079.
%Y A363686 Column 1 gives A283507 starting from its third term.
%Y A363686 Right border gives A052539 starting from its second term.
%Y A363686 Cf. A000265, A056792, A339694.
%K A363686 nonn,tabf
%O A363686 1,1
%A A363686 _Paul Conradi_, Jun 15 2023