OFFSET

1,1

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

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

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}]]

PROG

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

(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

(Haskell)

a261723 n = a261723_list !! (n-1)

a261723_list = concat $ transpose [tail a052548_list, tail a000051_list]

-- Reinhard Zumkeller, Sep 05 2015

CROSSREFS

KEYWORD

easy,nonn

AUTHOR

Alonso del Arte, Aug 29 2015

EXTENSIONS

Two incorrect terms corrected by Colin Barker, Aug 31 2015

STATUS

approved