A277109 - OEIS

%I #71 Jan 14 2024 12:28:23

%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 (PARI) 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