A349414 - OEIS

%I #173 Aug 10 2023 13:12:58

%S 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,

%T 13,-20,14,-7,15,-23,16,-8,17,-26,18,-9,19,-29,20,-10,21,-32,22,-11,

%U 23,-35,24,-12,25,-38,26,-13,27,-41,28,-14,29,-44,30,-15,31,-47,32

%N a(n) = A324245(n) - n.

%C 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".

%C From _Ruud H.G. van Tol_, Dec 09 2021: (Start)

%C 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,

%C   | 8m + 1  3   5  7 |

%C   | m |r:0  1   2  3 |

%C   +---+--------------+

%C   | 0 |  0  1  -2  2 |

%C   | 1 | -1  3  -5  4 |

%C   | 2 | -2  5  -8  6 |

%C   | 3 | -3  7 -11  8 |

%C   ...

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

%C Example for m = 1, r = 0: (8m+1) = 9; a(floor(9/2)) = a(4) = -1, which leads to (9 + 2*-1) = 7.

%C 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".

%C 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.

%C (End)

%H Antti Karttunen, <a href="/A349414/b349414.txt">Table of n, a(n) for n = 0..20000</a>

%H Nicolas Vaillant and Philippe Delarue, <a href="https://web.archive.org/web/20220317020641/http://nini-software.fr/site/uploads/arithmetics/collatz/Intrinsic%203x+1%20V2.01.pdf">The hidden face of the 3x+1 problem. Part I: Intrinsic algorithm</a>, April 26 2019.

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (-1,-1,-1,1,1,1,1).

%F a(n) = A324245(n) - n.

%F a(n) = (n+1)/2 if n is odd,

%F a(n) = -1*n/4 if n == 0 (mod 4),

%F a(n) = (n-2)/4 - n if n == 2 (mod 4).

%F Let r = n mod 4 and m = n div 4.

%F r=0: a(n) = -1*m   = a(n-4)-1

%F r=1: a(n) =  2*m+1 = a(n-4)+2 = a(n-2)+1

%F r=2: a(n) = -3*m-2 = a(n-4)-3

%F r=3: a(n) =  2*m+2 = a(n-4)+2 = a(n-2)+1

%F The moving sum over 4 elements gives the sequence /1,0,-2,-1/.

%F From _Wesley Ivan Hurt_, Nov 16 2021: (Start)

%F a(n) = (1 - 3*(-1)^n - 4*n*(-1)^n + 2*(1+n)*cos(n*Pi/2))/8.

%F G.f.: x*(1 - x + x^2 + x^4)/((1-x)*(1 + x + x^2 + x^3)^2). (End)

%F From _Stefano Spezia_, Nov 17 2021: (Start)

%F 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.

%F E.g.f.: (cos(x) + (2*x - 1)*cosh(x) - x*sin(x) - 2*(x - 1)*sinh(x))/4. (End)

%F a(n) >= - n. - _Ruud H.G. van Tol_, Dec 09 2021

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

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

%t LinearRecurrence[{-1,-1,-1,1,1,1,1},{0,1,-2,2,-1,3,-5},64] (* _Stefano Spezia_, Nov 17 2021 *)

%o (PARI)

%o A324245(n) = if(n%2, (1+3*n)/2, if(!(n%4), 3*(n/4), (n-2)/4));

%o A349414(n) = (A324245(n)-n); \\ _Antti Karttunen_, Dec 09 2021

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

%K sign,easy

%O 0,3

%A _Ruud H.G. van Tol_, Nov 16 2021