A349414 a(n) = A324245(n) - n.

0, 1, -2, 2, -1, 3, -5, 4, -2, 5, -8, 6, -3, 7, -11, 8, -4, 9, -14, 10, -5, 11, -17, 12, -6, 13, -20, 14, -7, 15, -23, 16, -8, 17, -26, 18, -9, 19, -29, 20, -10, 21, -32, 22, -11, 23, -35, 24, -12, 25, -38, 26, -13, 27, -41, 28, -14, 29, -44, 30, -15, 31, -47, 32

Offset: 0

Author

Ruud H.G. van Tol, Nov 16 2021

Keywords

• sign
• easy

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)

Examples

			a(1) = 1 -> a(1+1) = -2 -> a(1+1-2) = a(0) = 0, which represents 3 -> 5 -> 1.
		

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).

Crossrefs

Cf. A047472, A173732, A324245, A344583, A246425.

Programs

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 *)

PARI

A324245(n) = if(n%2, (1+3*n)/2, if(!(n%4), 3*(n/4), (n-2)/4));
A349414(n) = (A324245(n)-n); \\ Antti Karttunen, Dec 09 2021

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