A006666 -id:A006666 - cp's OEIS frontend

A129304 Numbers whose Collatz trajectory does not have the same number of halving steps and the same number of tripling steps as that of any smaller number.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 16, 17, 18, 20, 22, 24, 25, 27, 28, 31, 32, 33, 34, 36, 39, 40, 41, 43, 44, 47, 48, 49, 54, 56, 57, 62, 64, 65, 68, 71, 72, 73, 78, 80, 82, 86, 88, 91, 94, 96, 97, 98, 103, 105, 107, 108, 111, 112, 114, 121, 123, 124, 128, 129, 130

Offset: 1

T. D. Noe, Apr 09 2007

nonn

Note that if k is in this sequence, then 2k is also. The plot shows a very narrow triangle of the possible halving/tripling pairs. As n increases, the width of the triangle grows on its right edge.

			For each integer k, let the ordered pair (h,t) give the numbers of halving and tripling steps in the Collatz trajectory of k. The pairs for k = 1..16 are (0,0), (1,0), (5,2), (2,0), (4,1), (6,2), (11,5), (3,0), (13,6), (5,1), (10,4), (7,2), (7,2), (12,5), (12,5), (4,0). Thus 13 and 15 are not in this sequence because their pairs are the same as for 12 and 14, respectively.

Cf. A006666 (number of halving steps), A006667 (number of tripling steps).

Collatz[n_] := Module[{c1=0,c2=0,m=n}, While[m>1, If[EvenQ[m], c1++; m=m/2, c2++; m=3m+1]]; {c1,c2}]; s={}; t={}; n=0; While[Length[t]<100, n++; c=Collatz[n]; If[ !MemberQ[s,c], AppendTo[s,c]; AppendTo[t,n]]]; t

A176999 An encoding of the Collatz iteration of n.

Original entry on oeis.org

1, 1111010, 11, 11110, 11110101, 1111011101101010, 111, 1111011101101010110, 111101, 11110111011010, 111101011, 111101110, 11110111011010101, 11110111110101010, 1111, 111101110110, 11110111011010101101, 11110111011010111010, 1111011, 1111110, 111101110110101

Offset: 2

T. D. Noe, Apr 30 2010

Working from right to left, the sequence of 0's and 1's in a(n) encode, respectively, the sequence of 3x+1 and x/2 steps in the Collatz iteration of n. This is reverse one's complement of Garner's parity vector. Criswell mentions this encoding.

The length of a(n) is A006577(n). The number of 1's in a(n) is A006666(n). The number of 0's in a(n) is A006667(n). The number of terms having length k is A005186(k).

			a(5)=11110 because the Collatz iteration for 5 is a 3x+1 step (0) followed by 4 x/2 steps (four 1's).

T. D. Noe, Table of n, a(n) for n = 2..10000
Evans A. Criswell, The Collatz Problem (3x+1)
Lynn E. Garner, On heights in the Collatz 3n+1 problem, Discrete Math, 55 (1985), 57-64.

Cf. A006577, A006666, A006667, A005186.

Cf. A220145, A260592.

encode[n_]:=Module[{m=n,p,lst={}}, While[m>1, p=Mod[m,2]; AppendTo[lst,1-p]; If[p==0, m=m/2, m=3m+1]]; FromDigits[Reverse[lst]]]; Table[encode[n], {n,2,26}]

A212653 Number of steps to reach 1 in the Collatz (3x+1) problem starting with 3^n + 1.

Original entry on oeis.org

1, 2, 6, 18, 110, 21, 95, 32, 75, 74, 42, 134, 133, 132, 131, 143, 204, 128, 189, 139, 94, 93, 260, 427, 90, 257, 393, 330, 254, 253, 389, 388, 387, 461, 460, 459, 458, 457, 456, 455, 454, 453, 452, 500, 499, 449, 497, 496, 751, 494, 493, 492, 747, 490, 745

Offset: 0

Michel Lagneau, Feb 14 2013

nonn

It is interesting to note that the quantity 3^k + 1 appears in the formula: A006577(n + 2^A006666(n)) = A006577(n) + A006577(1 + 3^A006667(n)) where A006577 is the n number of halving and tripling steps to reach 1 in '3x+1' problem, A006666 is the number of halving steps to reach 1 and A006667 the number of tripling steps to reach 1.

For example with n = 19, A006577(19 + 2^14) = A006577(19) + A006577(1 + 3^6) => 115 = 20 + 95.

			a(2) = 6 because 3^2 + 1 = 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 with 6 iterations.

Harvey P. Dale, Table of n, a(n) for n = 0..1000
Wikipedia, Collatz conjecture

Cf. A006577, A006666, A006667, A034472, A003462, A075487.

f[n_] := Module[{a=3^n+1, k=0}, While[a!=1, k++; If[EvenQ[a], a=a/2, a=a*3+1]]; k]; Table[f[n], {n, 100}]
Table[Length[NestWhileList[If[EvenQ[#],#/2,3#+1]&,3^n+1,#!=1&]]-1,{n,0,60}] (* Harvey P. Dale, Sep 26 2015 *)

a(n) = A075487(n) - 1.

A220071 Difference between number of halving steps and number of tripling steps needed to reach 1 in '3x+1' problem.

Original entry on oeis.org

0, 1, 3, 2, 3, 4, 6, 3, 7, 4, 6, 5, 5, 7, 7, 4, 6, 8, 8, 5, 5, 7, 7, 6, 9, 6, 29, 8, 8, 8, 28, 5, 10, 7, 7, 9, 9, 9, 12, 6, 29, 6, 11, 8, 8, 8, 28, 7, 10, 10, 10, 7, 7, 30, 30, 9, 12, 9, 12, 9, 9, 29, 29, 6, 11, 11, 11, 8, 8, 8, 28, 10, 31, 10, 8, 10, 10, 13

Offset: 1

Jayanta Basu, Feb 19 2013

nonn

This sequence can also be defined as: a(1) = 0; thereafter a(2*k) = a(k) + 1, a(2*k+1) = a(6*k+4) - 1. - Gionata Neri, Jul 17 2016

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A006577, A006666, A006667, A014682.

a:= proc(n) option remember; `if`(n<2, 0,
      `if`(irem(n, 2)=0, 1+a(n/2), a((3*n+1)/2)))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Feb 19 2013

coll[n_] := NestWhileList[If[EvenQ[#], #/2, 3 # + 1] &, n, # > 1 &]; Table[(x = Count[coll[n], ?EvenQ]) - (Length[coll[n]] - x - 1), {n, 78}] (* _Jayanta Basu, Aug 15 2013 *)

a(n) = A006666(n) - A006667(n).

a(n) = a(A085062(n)) + 1 for n >= 2. - Alan Michael Gómez Calderón, Jan 26 2025

More terms from Alois P. Heinz, Feb 19 2013

A304174 Decimal expansion of 2^61/(3^32*993), the conjectured maximal residue in the Collatz 3x+1 problem.

Original entry on oeis.org

1, 2, 5, 3, 1, 4, 2, 1, 4, 4, 3, 9, 5, 0, 6, 8, 0, 5, 0, 1, 6, 5, 4, 9, 5, 2, 9, 7, 8, 3, 9, 0, 4, 6, 1, 4, 2, 4, 8, 6, 1, 5, 3, 6, 5, 9, 7, 3, 9, 6, 5, 1, 3, 6, 9, 2, 7, 6, 3, 0, 4, 6, 5, 5, 5, 7, 3, 6, 7, 5, 8, 6, 4, 8, 9, 7, 4, 7, 8, 3, 0, 0, 8, 7, 8, 4, 0, 1, 1, 2, 8, 5, 4, 9, 9, 7, 5, 3, 1, 3, 5, 3, 6, 7, 7, 4, 7, 9, 1, 5, 6, 1, 6, 0, 2, 5, 5, 1, 8, 5, 9, 2, 4, 3, 8, 4, 5, 7, 7, 8

Offset: 1

M. F. Hasler (following an idea of Michel Lagneau), May 07 2018

The residue of n in the 3x+1 problem is defined as the ratio 2^h(n)/(3^t(n)*n), where h = A006666 is the number of halving steps, and t = A006667 is the number of tripling steps. It is conjectured that n = 993 yields the highest possible residue. See e.g. the Roosendaal page, and A127789 for indices of record residues.

			res(993) = 1.253142144395068050165495297839461424861536597396513692763...

Paolo Xausa, Table of n, a(n) for n = 1..10000
Eric Roosendaal, On the 3x + 1 problem, last modified on April 6, 2018.
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006370 (Collatz map), A014682 (condensed version), A127789 (indices of record residues).

Cf. A006666 (halving steps), A006667 (tripling steps), A006577 (total).

First[RealDigits[2^61/(3^32*993), 10, 100]] (* Paolo Xausa, Mar 10 2024 *)

2^61/(3^32*993.) \\ Or, to find this value experimentally:
(c(n,c=[0,0])=while(n>1,bittest(n,0)&&c[1]++&&(n=n*3+1)&&next;n\=2;c[2]++);c); m=1;for(n=1,oo,m<<(t=c(n))[2]>n*3^t[1]||next;m=n*3^t[1]/2^t[2];printf("res(%d) = %f\n",n,1./m )) \\ M. F. Hasler, May 07 2018

res(993) = 2^61/(3^32*993).

A186008 Irregular triangle T(n,k) read by rows, in which row n has the pattern of conjectured dropping times in the Collatz iteration.

Original entry on oeis.org

2, 4, 16, 12, 32, 8, 52, 128, 40, 56, 84, 136, 160, 180, 256, 60, 80, 136, 220, 288, 296, 448, 528, 636, 688, 712, 1024, 152, 232, 384, 648, 704, 788, 856, 1000, 1204, 1416, 1472, 1556, 1592, 1624, 1800, 1972, 2008, 2120, 2356, 2360, 2676, 2744, 2888, 2912, 3064, 3328, 3444, 3680, 3832, 4096

Offset: 1

T. D. Noe, Feb 09 2011

Consider A126241, the sequence of dropping times in the Collatz iteration. Only zero and the numbers in A020914 can be dropping times. The dropping times in A126241 have a definite pattern. For example, 1 appears at positions n = 2 + 2*i, for i=0,1,2,3,... Similarly, 2 appears at positions n = 5 + 4*i; 4 appears at n = 3 + 16*i; 5 appears at n = 11 + {12,32}*i; and 7 appears at 7 + {8, 52, 128}*i. In general, if we let s=A020914(r) be the r-th possible stopping time, then A126241(n) = s for n = A122442(r) + T(r)*i, where T(r) is the r-th row of this triangle.  The length of row n is A186009(n). The n-th row ends with 2^A020914(n).
The frequency of the r-th dropping time s=A020914(r) can be computed as A186009(r)/2^s. The first few frequencies are 1/2, 1/4, 1/16, 1/16, 3/128, 7/256, 3/256, 15/2048, and 85/8192.
The term "stopping time" is sometimes used instead of "dropping time", but the former usually refers to A006666.
This sequence is closely related to A177789.

			The triangle begins
2
4
16
12, 32
8, 52, 128
40, 56, 84, 136, 160, 180, 256
60, 80, 136, 220, 288, 296, 448, 528, 636, 688, 712, 1024

J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010. See pp. 33, 35ff.

Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A014682, A126241, A006666, A186009.

A287798 Least k such that A006667(k)/A006577(k) = 1/n.

Original entry on oeis.org

159, 6, 5, 10, 20, 40, 80, 160, 320, 640, 1280, 2560, 5120, 10240, 20480, 40960, 81920, 163840, 327680, 655360, 1310720, 2621440, 5242880, 10485760, 20971520, 41943040, 83886080, 167772160, 335544320, 671088640, 1342177280, 2684354560, 5368709120, 10737418240

Offset: 3

Michel Lagneau, Jun 01 2017

A006667: number of tripling steps to reach 1 in '3x+1' problem.
A006577: number of halving and tripling steps to reach 1 in '3x+1' problem.
a(n) = {159, 6} union {A020714}.

			a(3) = 159 because A006667(159)/A006577(159) = 18/54 = 1/3.

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

Cf. A006577, A006666, A006667. Essentially the same as A020714, A084215, A146523 and A257113.

nn:=10^12:
for n from 3 to 35 do:
ii:=0:
for k from 2 to 10^6 while(ii=0) do:
  m:=k:s1:=0:s2:=0:
   for i from 1 to nn while(m<>1) do:
    if irem(m,2)=0
     then
     s2:=s2+1:m:=m/2:
     else
     s1:=s1+1:m:=3*m+1:
    fi:
   od:
    if n*s1=s1+s2
     then
     ii:=1: printf(`%d, `,k):
     else
    fi:
od:od:

f[u_]:=Module[{a=u,k=0},While[a!=1,k++;If[EvenQ[a],a=a/2,a=a*3+1]];k];Table[f[u],{u,10^7}];g[v_]:=Count[Differences[NestWhileList[If[EvenQ[#],#/2,3#+1]&,v,#>1&]],_?Positive];Table[g[v],{v,10^7}];Do[k=3;While[g[k]/f[k]!=1/n,k++];Print[n," ",k],{n,3,35}]

a(n) = if(n < 5, [0,0,159,6][n], 5<<(n-5)) \\ David A. Corneth, Jun 01 2017

Vec(x^3*(159 - 312*x - 7*x^2) / (1 - 2*x) + O(x^50)) \\ Colin Barker, Jun 01 2017

For n >= 5, a(n) = 5*2^n/32. - David A. Corneth, Jun 01 2017
From Colin Barker, Jun 01 2017: (Start)
G.f.: x^3*(159 - 312*x - 7*x^2) / (1 - 2*x).
a(n) = 2*a(n-1) for n>5.
(End)

A351850 a(n) is the number of iterations of the computation of the A351849 tag system when started from the word encoding n, or -1 if the number of iterations is infinite.

Original entry on oeis.org

0, 2, 24, 6, 20, 30, 128, 14, 152, 30, 120, 42, 64, 142, 300, 30, 108, 170, 236, 50, 84, 142, 284, 66, 300, 90, 40656, 170, 216, 330, 40524, 62, 384, 142, 260, 206, 264, 274, 996, 90, 40628, 126, 596, 186, 256, 330, 40492, 114, 388, 350, 520, 142, 224, 40710

Offset: 1

Paolo Xausa, Feb 22 2022

nonn

If x is even, the A351849 tag system evolves from the word encoding x to the word encoding x/2 in x iterations; if x is odd, x+1 iterations are required to produce the word encoding (3x+1)/2.

See A351849 for additional comments, links and examples.

			When started from 1111 (the word encoding the number 4), the system evolves as 1111 -> 1123 -> 2323 -> 231 -> 11 -> 23 -> 1, reaching the word 1 after 6 steps. a(4) is therefore 6.

Paolo Xausa, Table of n, a(n) for n = 1..10000
Liesbeth De Mol, Tag systems and Collatz-like functions, Theoretical Computer Science, Volume 390, Issue 1, 2008, pp. 92-101.
Index entries for sequences related to 3x+1 (or Collatz) problem.

Cf. A006666, A070168, A285098, A351849.

(* First program, based on the tag system definition *)
t[s_]:=StringDrop[s,2]<>StringReplace[StringTake[s,1],{"1"->"23","2"->"1","3"->"111"}];
nterms=100;Table[Length[NestWhileList[t,StringRepeat["1",n],#!="1"&]]-1,{n,nterms}]
(* Second program, more efficient, based on formula *)
c[x_]:=If[OddQ[x],(3x+1)/2,x/2];
nterms=100;Table[Total[Map[If[OddQ[#],#+1,#]&,NestWhileList[c,n,#>1&]]]-2,{n,nterms}]

def A351850(n):
    s, steps = "1" * n, 0
    while s != "1":
        if s[0] == "1": s += "23"
        elif s[0] == "2": s += "1"
        else: s += "111"
        s = s[2:]
        steps += 1
    return steps
nterms = 100
print([A351850(n) for n in range(1, nterms + 1)])

a(n) = (Sum_{k=0..A006666(n)} 2*floor((A070168(n,k)+1)/2)) - 2.

A377524 Number of steps for n to reach the minimum of its final cycle under iterations of the map (A123684): x->(3x-1)/2 if x odd, x/2 otherwise; or -1 if this never happens.

Original entry on oeis.org

0, 1, 3, 2, 0, 4, 2, 3, 7, 1, 5, 5, 6, 3, 7, 4, 0, 8, 5, 2, 5, 6, 2, 6, 10, 7, 4, 4, 8, 8, 4, 5, 12, 1, 9, 9, 9, 6, 10, 3, 6, 6, 7, 7, 14, 3, 11, 7, 11, 11, 8, 8, 12, 5, 8, 5, 20, 9, 9, 9, 5, 5, 13, 6, 25, 13, 13, 2, 14, 10, 14, 10, 10, 10, 7, 7, 11, 11, 11, 4

Offset: 1

Kevin Ge, Oct 28 2024

nonn

The currently known cycle minimums are 1, 5, 17 and there are no known a(n) = -1 (trajectory never reaches a cycle).

This sequence is one way to extend A006666 (number of Collatz (3x+1)/2 steps) to the negative numbers.

			For n = 5, a(5) = 0 because 5 is already the minimum of its "final cycle".
For n = 12, a(12) = 6 because 12 takes 6 iterations to reach the minimum of its "final cycle": 12 -> 6 -> 3 -> 8 -> 4 -> 2 -> 1.

Cf. A123684 ((3x-1)/2 map), A135730 (all steps).

Cf. A006666 (for (3x+1)/2).

function three_x_minus_one_delay(n::Int)
    count = 0
    while (n != 1 && n != 5 && n != 17)
        if (isodd(n))
            n += n << 1 - 1
        end
        n >>= 1
        count += 1
    end
    return count
end

A179627 a(n) = length of Collatz sequence starting with n-th prime.

Original entry on oeis.org

2, 6, 5, 12, 11, 8, 10, 15, 12, 14, 68, 16, 70, 21, 67, 10, 23, 15, 20, 66, 74, 25, 71, 22, 76, 19, 57, 65, 73, 11, 32, 21, 59, 29, 18, 13, 26, 18, 45, 23, 23, 15, 31, 77, 20, 77, 28, 47, 12, 25, 55, 36, 17, 44, 79, 52, 22, 30, 14, 30, 41, 76, 27, 57, 84, 27, 19, 73, 81, 24, 81

Offset: 1

Roland Schroeder (florola(AT)gmx.de), Jul 21 2010

nonn

			For n=4 the a(n)=12 because the fourth prime is 7 and if you start with 7, the 12th term of syracuse-sequence is 1. The syracuse-sequence starting with 7 has the dimension 12.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Collatz Problem
Wikipedia, Collatz conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem

a179627 = (+ 1) . a006666 . a000040  -- Reinhard Zumkeller, Apr 03 2012

a(n) = A006666(A000040(n)) + 1. [Reinhard Zumkeller, Apr 03 2012]

Offset fixed by Reinhard Zumkeller, Apr 03 2012

cp's OEIS Frontend

A129304 Numbers whose Collatz trajectory does not have the same number of halving steps and the same number of tripling steps as that of any smaller number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A176999 An encoding of the Collatz iteration of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A212653 Number of steps to reach 1 in the Collatz (3x+1) problem starting with 3^n + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A220071 Difference between number of halving steps and number of tripling steps needed to reach 1 in '3x+1' problem.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A304174 Decimal expansion of 2^61/(3^32*993), the conjectured maximal residue in the Collatz 3x+1 problem.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A186008 Irregular triangle T(n,k) read by rows, in which row n has the pattern of conjectured dropping times in the Collatz iteration.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A287798 Least k such that A006667(k)/A006577(k) = 1/n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A351850 a(n) is the number of iterations of the computation of the A351849 tag system when started from the word encoding n, or -1 if the number of iterations is infinite.