login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A277109 Starting from 2^n+1, the length of the longest sequence of consecutive numbers which all take the same number of steps to reach 1 in the Collatz (or '3x+1') problem. 7

%I

%S 1,1,1,1,1,1,3,1,3,1,3,1,1,1,3,1,3,7,15,30,1,1,3,7,15,26,26,1,1,1,3,1,

%T 3,1,3,1,1,1,3,1,3,7,15,1,1,1,3,1,3,1,3,1,1,1,3,1,3,7,15,1,1,3,7,15,

%U 26,1,3,7,15,31,63,26,30,26,26,26,26,30,46,26,26,26,26,1,1,1,3,7,15,1,3,1

%N Starting from 2^n+1, the length of the longest sequence of consecutive numbers which all take the same number of steps to reach 1 in the Collatz (or '3x+1') problem.

%C a(500) was found by Guo-Gang Gao (see links).

%C Interestingly, this sequence has many sets of consecutive terms that are increasing powers of 2 minus 1. For example: a(291) to a(307), a(447) to a(467), and a(603) to a(625). It is not clear why this is the case.

%C The largest value known in this sequence is a(1812) = 2^26-1 = 67108863.

%C Conjecture: If a(n) = 2^k - 1 for some k > 1, then a(n-1) = 2^(k-1) - 1. Conjecture holds for n <= 1812.

%C From _Hartmut F. W. Hoft_, Aug 16 2018: (Start)

%C The conjecture is true. Let the lengths of the Collatz runs equal q for all numbers 2^n + 1, 2^n + 2, 2^n + 3, 2^n + 4, ..., 2^n + 2^k - 2, 2^n + 2^k - 1. Then dividing the 2^(k-1) - 1 even numbers by two gives rise to the sequence 2^(n-1) + 1, 2^(n-1) + 2, ..., 2^(n-1) + 2^(k-1) - 1 of numbers for which the lengths of the Collatz runs equals q-1. Furthermore, let the length of the Collatz run of 2^n + 2^k be r != q then the length of the Collatz run of 2^(n-1) + 2^(k-1) is r-1 != q-1, i.e., a(n-1) = 2^(k-1) - 1.

%C Conjecture: Let a(k), ..., a(k+m), m >= 0, be a subsequence of this sequence such that a(k)=a(k+m+1)=1 and a(k+i) > 1, 1 <= i <= m. Then the lengths of the Collatz runs of a(k+i), 0 <= i <= m, increase by 1. In addition, there is an initial segment of increasing numbers a(k), ..., a(k+j), for some 0 <= j <= m, in each such subsequence having the form 2^i - 1, 0 < i <= j. (End)

%H Dmitry Kamenetsky, <a href="/A277109/b277109.txt">Table of n, a(n) for n = 0..1812</a>

%H Dmitry Kamenetsky, <a href="/A277109/a277109_1.c.txt">C program to compute the sequence</a>

%H Guo-Gang Gao, <a href="http://dx.doi.org/10.1016/0012-365X(93)90240-T">On consecutive numbers of the same height in the Collatz problem</a>, Discrete Mathematics, Volume 112, pages 261-267, 1993.

%H Pureferret, <a href="https://math.stackexchange.com/questions/470782/longest-known-sequence-of-identical-consecutive-collatz-sequence-lengths/">Longest known sequence of identical consecutive Collatz sequence lengths</a>, Mathematics StackExchange, 2013.

%H Carlos Rivera, <a href="http://primepuzzles.net/puzzles/puzz_847.htm">Puzzle 847: Consecutive primes with the same Collatz length</a>, The Prime Puzzles and Problems Connection.

%H Carlos Rivera, <a href="http://primepuzzles.net/puzzles/puzz_851.htm">Puzzle 851: Puzzle 847 revisited</a>, The Prime Puzzles and Problems Connection.

%e a(6) = 3, because 2^6+1, 2^6+2 and 2^6+3 all take 27 steps to reach 1.

%e From _Hartmut F. W. Hoft_, Aug 16 2018: (Start)

%e Two examples for the conjecture (L(n) denotes the length of the Collatz run):

%e n a(n) L(n) n a(n) L(n)

%e 64 26 483 20 1 72

%e ------------------ ------------------

%e 65 1 559 21 1 166

%e 66 3 560 22 3 167

%e 67 7 561 23 7 168

%e 68 15 562 24 15 169

%e 69 31 563 ------------------

%e 70 63 564 25 26 170

%e ------------------ 26 26 171

%e 71 26 565 ------------------

%e 72 30 566 27 1 247

%e 73 26 567

%e 74 26 568

%e 75 26 569

%e 76 26 570

%e 77 30 571

%e 78 46 572

%e 79 26 573

%e 80 26 574

%e 81 26 575

%e 82 26 576

%e ------------------

%e 83 1 626

%e The "power of 2 minus 1" initial section of any such subsequence of a(n) is always increasing. However, there is no apparent ordering in the second section when that is present. (End)

%t f[n_] := Length[NestWhileList[If[EvenQ@ #, #/2, 3 # + 1] &, n, # != 1 &]] - 1; Table[k = 1; While[f[2^n + k] == f[2^n + k + 1], k++]; k, {n, 120}] (* _Michael De Vlieger_, Oct 03 2016 *)

%o nbsteps(n)= s=n; c=0; while(s>1, s=if(s%2, 3*s+1, s/2); c++); c;

%o a(n) = {my(ns = 2^n+1); my(nbs = nbsteps(ns)); while(nbsteps(ns+1) == nbs, ns++); ns - 2^n;} \\ _Michel Marcus_, Oct 30 2016

%Y Cf. A006577, A078441, A179118, A277684.

%K nonn

%O 0,7

%A _Dmitry Kamenetsky_, Sep 30 2016

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 24 01:41 EDT 2021. Contains 346269 sequences. (Running on oeis4.)