A261723 Interleave 2^n + 2 and 2^n + 1.

4, 3, 6, 5, 10, 9, 18, 17, 34, 33, 66, 65, 130, 129, 258, 257, 514, 513, 1026, 1025, 2050, 2049, 4098, 4097, 8194, 8193, 16386, 16385, 32770, 32769, 65538, 65537, 131074, 131073, 262146, 262145, 524290, 524289, 1048578, 1048577, 2097154, 2097153, 4194306, 4194305, 8388610, 8388609

Offset: 1

Author

Alonso del Arte, Aug 29 2015

Keywords

• easy
• nonn

Comments

There is only one fundamental difference between the x + 1 problem and the 3x + 1 problem, that being one of definition: if x is odd, then the next value is x + 1 rather than 3x + 1. But there are also important differences between the two problems, such as that with the x + 1 problem it is easy to prove that every positive integer x reaches 1 after a finite number of iterations.

As with the 3x + 1 problem, the minimum necessary number of iterations is obvious: given an arbitrary positive n, it will take at least floor(log_2(n)) iterations to reach 1, especially if n is a power of 2 to begin with.

But with the x + 1 problem, it is almost as easy to determine the maximum number of iterations needed to reach 1: 2*ceiling(log_2(n)). This is the case when n is one of the odd numbers in this sequence, in which case there are no consecutive halving steps prior to reaching 4.

If an initial 1 and 2 are added to this sequence, the complete x + 1 trajectory of any number in this sequence can be obtained by reading backwards from that number.

A061313(n) = number of steps to reach 1 when starting with n. - Reinhard Zumkeller, Sep 05 2015

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (0,3,0,-2).

Crossrefs

Cf. A000051, A052548, A061313.

Programs

Haskell

a261723 n = a261723_list !! (n-1)
a261723_list = concat $ transpose [tail a052548_list, tail a000051_list]
-- Reinhard Zumkeller, Sep 05 2015

Magma

&cat[[2^n+2, 2^n+1]: n in [1..30]]; // Vincenzo Librandi, Aug 31 2015

Maple

A261723:=n->(2^((n+1)/2)+2)*(1-(-1)^n)/2+(2^(n/2)+1)*(1+(-1)^n)/2: seq(A261723(n), n=1..60); # Wesley Ivan Hurt, Sep 06 2015

Mathematica

Flatten[Table[{2^n + 2, 2^n + 1}, {n, 25}]]

PARI

Vec(-x*(4*x^3+6*x^2-3*x-4)/((x-1)*(x+1)*(2*x^2-1)) + O(x^100)) \\ Colin Barker, Aug 31 2015

Formula

a(2n - 1) = 2^n + 2, a(2n) = 2^n + 1.

a(1) = 4, a(2n) = 2a(n - 1), a(2n + 1) = a(n - 1) - 1.

a(1) = 4, a(n) = a(n - 1) - 1 if a(n - 1) is even, a(n) = 2a(n - 1) if a(n - 1) is odd.

a(n) = 3*a(n-2) - 2*a(n-4) for n > 4. - Colin Barker, Aug 31 2015

G.f.: -x*(4*x^3+6*x^2-3*x-4) / ((x-1)*(x+1)*(2*x^2-1)). - Colin Barker, Aug 31 2015

a(n) = (2^((n+1)/2)+2)*(1-(-1)^n)/2+(2^(n/2)+1)*(1+(-1)^n)/2. - Wesley Ivan Hurt, Sep 06 2015

E.g.f.: sqrt(2)*sinh(sqrt(2)*x) + cosh(sqrt(2)*x) + 2*sinh(x) + cosh(x) - 2. - Robert Israel, Sep 06 2015

Extensions

Two incorrect terms corrected by Colin Barker, Aug 31 2015