login
a(n) = 4*a(n-1) + 1 with a(0) = 3.
31

%I #107 Dec 20 2023 09:50:49

%S 3,13,53,213,853,3413,13653,54613,218453,873813,3495253,13981013,

%T 55924053,223696213,894784853,3579139413,14316557653,57266230613,

%U 229064922453,916259689813,3665038759253,14660155037013,58640620148053,234562480592213,938249922368853

%N a(n) = 4*a(n-1) + 1 with a(0) = 3.

%C Let A be the Hessenberg matrix of order n, defined by: A[1, j] = 1, A[i, i] := 2, (i > 1), A[i, i - 1] = -1, and A[i, j] = 0 otherwise. Then, for n >= 1, a(n - 1) = (-1)^n*charpoly(A, -2). - _Milan Janjic_, Jan 26 2010

%C Numbers whose binary representation is 11 together with n times 01. For example, 213 = 11010101 (2). - _Omar E. Pol_, Nov 22 2012

%C The Collatz-function starting with a(n) will terminate at 1 after 2*n + 7 steps. This is because 3*a(n) + 1 = 5*2^(2n + 1), and the Collatz-function starting with 5 terminates at 1 after 5 additional steps. So for example, a(2) = 53; Collatz sequence starting with 53 follows: 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 (11 steps). - _Bob Selcoe_, Apr 03 2015

%C a(n) is also the sum of the numerator and denominator of the binary fractions 0.1, 0.101, 0.10101, 0.1010101... Thus 0.1 = 1/2 with 1 + 2 = 3, 0.101 = 1/2 + 1/8 = 5/8 with 5 + 8 = 13; 0.10101 = 1/2 + 1/8 + 1/32 = 21/32 with 21 + 32 = 53. - _J. M. Bergot_, Sep 28 2016

%C a(n), for n >= 2, is also the smallest odd number congruent to 5 modulo 8 for which the modified reduced Collatz map given in A324036 has n consecutive extra steps compared to the reduced Collatz map given in A075677. - _Nicolas Vaillant_, Philippe Delarue, _Wolfdieter Lang_, May 09 2019

%H Vincenzo Librandi, <a href="/A072197/b072197.txt">Table of n, a(n) for n = 0..1000</a>

%H Petro Kosobutskyy and Volodymyr Karkulovskyy, <a href="https://doi.org/10.23939/cds2023.01.028">Recurrence and structuring of sequences of transformations 3n+ 1 as arguments for confirmation of the Collatz hypothesis</a>, Comp. Des. Sys., Theor. Practice (2023) Vol. 5, No. 1, 28-33. See p. 29.

%H Petro Kosobutskyy, Anastasiia Yedyharova, and Taras Slobodzyan, <a href="https://doi.org/10.23939/cds2023.01.121">From Newton's binomial and Pascal's triangle to Collatz's problem</a>, Comp. Des. Sys., Theor. Practice (2023) Vol. 5, No. 1, 121-127.

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

%H <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>

%F a(n) = (10*4^n - 1)/3 = 10*A002450(n) + 3. - _Henry Bottomley_, Dec 02 2002

%F a(n) = 5*a(n - 1) - 4*a(n - 2), n > 1. - _Vincenzo Librandi_, Oct 31 2011

%F a(n) = 2^(2*(n + 1)) - (2^(2*n + 1) + 1)/3 = A000302(n + 1) - A007583(n). - _Vladimir Pletser_, Apr 12 2014

%F a(n) = (5*2^(2*n + 1) - 1)/3. - _Bob Selcoe_, Apr 03 2015

%F G.f.: (3-2*x) / ((1-x)*(1-4*x)). - _Colin Barker_, Sep 28 2016

%F a(n) = A020988(n) + A020988(n+1) + 1 = 2*(A002450(n) + A002450(n+1)) + 1. - _Yosu Yurramendi_, Jan 24 2017

%F a(n) = A002450(n+1) + 2^(2*n+1). - _Adam Michael Bere_, May 13 2021

%F a(n) = a(n-1) + 5*2^(2*n-1), for n >= 1, with a(0) = 3. - _Wolfdieter Lang_, Aug 16 2021

%F a(n) = A178415(2, n+1) = A347834(2, n), arrays, for n >= 0. - _Wolfdieter Lang_, Nov 29 2021

%e a(1) = 13 because a(0) = 3 and 4 * 3 + 1 = 13.

%e a(2) = 53 because a(1) = 13 and 4 * 13 + 1 = 53.

%e a(3) = 213 because a(2) = 53 and 4 * 53 + 1 = 213.

%p A072197:=n->(10*4^n - 1)/3: seq(A072197(n), n=0..30); # _Wesley Ivan Hurt_, Sep 29 2016

%t Table[(10(4^n) - 1)/3, {n, 0, 19}] (* _Alonso del Arte_, Nov 22 2012 *)

%t NestList[4#+1&,3,30] (* _Harvey P. Dale_, Mar 09 2019 *)

%o (Magma) [(10*4^n-1)/3: n in [0..30]]; // _Vincenzo Librandi_, Oct 31 2011

%o (PARI) a(n)=10*4^n\3 \\ _Charles R Greathouse IV_, Apr 06 2016

%o (PARI) Vec((3-2*x)/((1-x)*(1-4*x)) + O(x^30)) \\ _Colin Barker_, Sep 28 2016

%Y Cf. A000302, A002066 (first differences), A002450, A007583, A075677, A178415, A324036, A347834.

%K nonn,easy

%O 0,1

%A N. Rathankar (rathankar(AT)yahoo.com), Jul 03 2002

%E More terms from _Henry Bottomley_, Dec 02 2002