cp's OEIS Frontend

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.

%I A277109 #87 Sep 04 2025 05:21:22
%S A277109 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 A277109 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 A277109 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 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.
%C A277109 a(500) was found by Guo-Gang Gao (see links).
%C A277109 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 A277109 The largest value known in this sequence is a(3951) = 2^47-1 = 140737488355327.
%C A277109 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 A277109 From _Hartmut F. W. Hoft_, Aug 16 2018: (Start)
%C A277109 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 A277109 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 A277109 Karl Frinkle, <a href="/A277109/b277109.txt">Table of n, a(n) for n = 0..3951</a> (terms 0..1812 from Dmitry Kamenetsky).
%H A277109 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 A277109 Dmitry Kamenetsky, <a href="/A277109/a277109_1.c.txt">C program to compute the sequence</a>.
%H A277109 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 A277109 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 A277109 Carlos Rivera, <a href="http://primepuzzles.net/puzzles/puzz_851.htm">Puzzle 851: Puzzle 847 revisited</a>, The Prime Puzzles and Problems Connection.
%e A277109 a(6) = 3, because 2^6+1, 2^6+2 and 2^6+3 all take 27 steps to reach 1.
%e A277109 From _Hartmut F. W. Hoft_, Aug 16 2018: (Start)
%e A277109 Two examples for the conjecture (L(n) denotes the length of the Collatz run):
%e A277109 n      a(n)    L(n)          n      a(n)    L(n)
%e A277109 64     26      483           20      1       72
%e A277109 ------------------           ------------------
%e A277109 65      1      559           21      1      166
%e A277109 66      3      560           22      3      167
%e A277109 67      7      561           23      7      168
%e A277109 68     15      562           24     15      169
%e A277109 69     31      563           ------------------
%e A277109 70     63      564           25     26      170
%e A277109 ------------------           26     26      171
%e A277109 71     26      565           ------------------
%e A277109 72     30      566           27      1      247
%e A277109 73     26      567
%e A277109 74     26      568
%e A277109 75     26      569
%e A277109 76     26      570
%e A277109 77     30      571
%e A277109 78     46      572
%e A277109 79     26      573
%e A277109 80     26      574
%e A277109 81     26      575
%e A277109 82     26      576
%e A277109 ------------------
%e A277109 83      1      626
%e A277109 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 A277109 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 A277109 (PARI) nbsteps(n)= s=n; c=0; while(s>1, s=if(s%2, 3*s+1, s/2); c++); c;
%o A277109 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 A277109 Cf. A006577, A078441, A179118, A277684.
%K A277109 nonn,changed
%O A277109 0,7
%A A277109 _Dmitry Kamenetsky_, Sep 30 2016