Ruud H.G. van Tol on Sun, 11 Feb 2024 21:06:10 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

[Collatz] how to best derive x and T^n(x) from a parity vector



An example parity vector is [1,1,0,1,1,0,0].

This represents: T^7(x) = (3^4 * x + 85) / 2^7.

__|__1___1___0_____1_____1_____0______0_
x*| 3/2 9/4 9/8 27/16 81/32 81/64 81/128
0+| 1/2 5/4 5/8 23/16 85/32 85/64 85/128


T(x) = { if(x%2, 3*x+1, x)/2 }

y = T^7(x) = (3^4 * x + 85) / 2^7.
(and y <= x)

81 * x + 85 = 128 * y <=>
81 * x = 128 * (y-1) + 43 <=>
81 * x % 128 = 43 (and x >= 43)

Because of how the parity vector is built,
if its length is >= 4, then x = 3 (mod 4).

So we can try (43, 47, 51, 55, 59, ...) and find that x = 59 works:

(81 * 59 + 85) / 128 = 38

which means that 38 is the first successor that is smaller than or equal to 59.
which then leads to:

59 + i * 2^7 -> 38 + i * 3^4 (for i >= 0)
(59 -> 38, 187 -> 119, ...)

My question: is there a "better" (pari-oriented) way to derive 59 from the parity structure?

-- Ruud


P.S. The first few parity formulas:

0     |  2 + i * 2^1 ->  1 + i * 3^0  (2->1, 4->2, 6->3, ...)
10    |  1 + i * 2^2 ->  1 + i * 3^1  (1->1, 5->4, 9->7, ...)
1100  |  3 + i * 2^4 ->  2 + i * 3^2  (3->2, 19->11, 35->20, ...)
11010 | 11 + i * 2^5 -> 10 + i * 3^3  (11->10, 43->37, 75->64, ...)
11100 | 23 + i * 2^5 -> 20 + i * 3^3  (23->20, 55->47, 87->74, ...)

See also https://oeis.org/A368514/a368514.svg