OFFSET
0,3
COMMENTS
This uses a modified Collatz-Terras map, called f in the Vaillant and Delarue link. Odd k = 2*n+1; a(0) = 0 represents 1 "is done".
From Ruud H.G. van Tol, Dec 09 2021: (Start)
a(n) is given by cases according as r = n mod 4 is 0,1,2,3 so that the sequence can be taken as an array with row m = floor(n/4) and column r,
| 8m + 1 3 5 7 |
| m |r:0 1 2 3 |
+---+--------------+
| 0 | 0 1 -2 2 |
| 1 | -1 3 -5 4 |
| 2 | -2 5 -8 6 |
| 3 | -3 7 -11 8 |
...
All positive integers eventually reach 1 in the Collatz problem iff all nonnegative integers eventually reach 0 with repeated application of this map, i.e., if for all n, the sequence n, n+a(n), n+a(n+a(n)), n+a(n+a(n+a(n))), ... eventually hits 0 (by hitting any a(n) == -n).
Example for m = 1, r = 0: (8m+1) = 9; a(floor(9/2)) = a(4) = -1, which leads to (9 + 2*-1) = 7.
Notice that the "(8m+5) -> (8m+5-1) / 4 = (2k+1)" operation of the values for r == 2, is "shedding bits", similar to what division-by-2 does. Any trailing '101' of the odd is transformed to '1', so it is not performing a Collatz step itself, but it is "escaping the column".
a(n) = A246425(n) if r is in (0,1,3) (A047472). The values for r == 2 are (n' - n + a(n')), with n' derived as (n' = n; n' = floor(n' / 4) while (n' mod 4 == 2)). Example for 8m+5 == 53: n = (53 - 1) / 2 = 26; n' = ((26 -2)/4 -2)/4 = 1; A246425(26) = 1 - 26 + a(1) = -25 + 1 = -24.
(End)
LINKS
Antti Karttunen, Table of n, a(n) for n = 0..20000
Nicolas Vaillant and Philippe Delarue, The hidden face of the 3x+1 problem. Part I: Intrinsic algorithm, April 26 2019.
Index entries for linear recurrences with constant coefficients, signature (-1,-1,-1,1,1,1,1).
FORMULA
a(n) = A324245(n) - n.
a(n) = (n+1)/2 if n is odd,
a(n) = -1*n/4 if n == 0 (mod 4),
a(n) = (n-2)/4 - n if n == 2 (mod 4).
Let r = n mod 4 and m = n div 4.
r=0: a(n) = -1*m = a(n-4)-1
r=1: a(n) = 2*m+1 = a(n-4)+2 = a(n-2)+1
r=2: a(n) = -3*m-2 = a(n-4)-3
r=3: a(n) = 2*m+2 = a(n-4)+2 = a(n-2)+1
The moving sum over 4 elements gives the sequence /1,0,-2,-1/.
From Wesley Ivan Hurt, Nov 16 2021: (Start)
a(n) = (1 - 3*(-1)^n - 4*n*(-1)^n + 2*(1+n)*cos(n*Pi/2))/8.
G.f.: x*(1 - x + x^2 + x^4)/((1-x)*(1 + x + x^2 + x^3)^2). (End)
From Stefano Spezia, Nov 17 2021: (Start)
a(n) = - a(n-1) - a(n-2) - a(n-3) + a(n-4) + a(n-5) + a(n-6) + a(n-7) for n > 6.
E.g.f.: (cos(x) + (2*x - 1)*cosh(x) - x*sin(x) - 2*(x - 1)*sinh(x))/4. (End)
a(n) >= - n. - Ruud H.G. van Tol, Dec 09 2021
EXAMPLE
a(1) = 1 -> a(1+1) = -2 -> a(1+1-2) = a(0) = 0, which represents 3 -> 5 -> 1.
MATHEMATICA
Table[(1 - 3 (-1)^n - 4 n (-1)^n + 2 (1 + n) Cos[n*Pi/2])/8, {n, 0, 100}] (* Wesley Ivan Hurt, Nov 16 2021 *)
LinearRecurrence[{-1, -1, -1, 1, 1, 1, 1}, {0, 1, -2, 2, -1, 3, -5}, 64] (* Stefano Spezia, Nov 17 2021 *)
PROG
(PARI)
A324245(n) = if(n%2, (1+3*n)/2, if(!(n%4), 3*(n/4), (n-2)/4));
CROSSREFS
KEYWORD
sign,easy
AUTHOR
Ruud H.G. van Tol, Nov 16 2021
STATUS
approved