A006667 -id:A006667 - cp's OEIS frontend

A062054 Numbers with 4 odd integers in their Collatz (or 3x+1) trajectory.

17, 34, 35, 68, 69, 70, 75, 136, 138, 140, 141, 150, 151, 272, 276, 277, 280, 282, 300, 301, 302, 544, 552, 554, 560, 564, 565, 600, 602, 604, 605, 1088, 1104, 1108, 1109, 1120, 1128, 1130, 1137, 1200, 1204, 1205, 1208, 1210, 2176, 2208, 2216, 2218, 2240

Offset: 1

David W. Wilson

The Collatz (or 3x+1) function is f(x) = x/2 if x is even, 3x+1 if x is odd.
The Collatz trajectory of n is obtained by applying f repeatedly to n until 1 is reached.
A078719(a(n)) = 4; A006667(a(n)) = 3.
Numbers m such that (s0 - 4s1)/2m = 1 where s0 is the sum of the even elements and s1 the sum of the odd elements in the Collatz trajectory of m. - Michel Lagneau, Aug 13 2018
If m is in the sequence then so is 2*m, so one would only have to check odd numbers. - David A. Corneth, Aug 13 2018

			The Collatz trajectory of 17 is (17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1), which contains 4 odd integers. - _Jeffrey R. Goodwin_, Oct 26 2011

J. Shallit and D. Wilson, The "3x+1" Problem and Finite Automata, Bulletin of the EATCS #46 (1992) pp. 182-185.

David A. Corneth, Table of n, a(n) for n = 1..15549 (first 750 terms from Reinhard Zumkeller, terms < 10^15)
J. R. Goodwin, Results on the Collatz Conjecture, Sci. Ann. Comput. Sci. 13 (2003) pp. 1-16.
J. Shallit and D. Wilson, The "3x+1" Problem and Finite Automata, Bulletin of the EATCS #46 (1992) pp. 182-185.
Eric Weisstein's World of Mathematics, Collatz Problem
Wikipedia, Collatz conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem
Index entries for 2-automatic sequences.

Cf. A000079, A006370, A062052, A062053, A062055, A062056, A062057, A062058, A062059, A062060, A092893, A198587.

Column k=4 of A354236.

import Data.List (elemIndices)
a062054 n = a062054_list !! (n-1)
a062054_list = map (+ 1) $ elemIndices 4 a078719_list
-- Reinhard Zumkeller, Oct 08 2011

col4Q[n_]:=Module[{c=NestWhileList[If[EvenQ[#],#/2,3#+1]&,n,#!=1&]}, Count[c,?OddQ]==4]; Select[Range[2500],col4Q]  (* _Harvey P. Dale, Mar 21 2011 *)

The twelve formulas giving this sequence are listed in Corollary 3.3 in J. R. Goodwin with the following caveats: the value x cannot equal zero in formulas (3.16) and (3.20), one must multiply the formulas by all powers of 2 (2^1, 2^2, ...) to get the evens. - Jeffrey R. Goodwin, Oct 26 2011

A127789 Record indices of 2^h(n)/(3^t(n)*n), where h and t are the number of halving resp. tripling steps in the '3x + 1' problem.

Original entry on oeis.org

1, 3, 7, 9, 505, 559, 745, 993

Offset: 1

Paul Boddington, Apr 04 2007

Original name: In the '3x + 1' problem we would expect a positive integer n to be approximately equal to 2^j / 3^k where j is the number of halving steps and k is the number of '3x + 1' steps required to reach 1. The numbers in this sequence are those for which 2^j / (n*3^k) sets a new record.
Eric Roosendaal calls 2^j / (n*3^k) the residue of n and conjectures that 993 yields the highest residue. - T. D. Noe, Apr 08 2007
It has been verified that the next value, if it exists, is larger than 2^32 ~ 4.3e9. We do not need an "escape clause" (as for A006577, A006666, A006667, ...) in this sequence since the unlikely case of a possibly undefined ratio is irrelevant for the list of records. - M. F. Hasler, May 07 2018

Eric Roosendaal, On the 3x+1 Problem

Cf. A006370 (Collatz map), A014682 (condensed version using (3n+1)/2).

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

(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];print1(n", ")) \\ M. F. Hasler, May 07 2018

New name from M. F. Hasler, May 07 2018

A033958 In the '3x+1' problem, these values for the starting value set new records for number of steps to reach 1.

Original entry on oeis.org

1, 3, 7, 9, 25, 27, 73, 97, 129, 171, 231, 313, 327, 703, 871, 1161, 2463, 2919, 3711, 6171, 10971, 13255, 17647, 23529, 26623, 34239, 35655, 52527, 77031, 106239, 142587, 156159, 216367, 230631, 410011, 511935, 626331, 837799, 1117065, 1501353, 1723519, 2298025, 3064033

Offset: 1

N. J. A. Sloane

Only the 3x+1 steps, not the halving steps, are counted.

D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 400.
G. T. Leavens and M. Vermeulen, 3x+1 search problems, Computers and Mathematics with Applications, 24 (1992), 79-99.

Charles R Greathouse IV, Table of n, a(n) for n = 1..71
Brian Hayes, Computer Recreations: On the ups and downs of hailstone numbers, Scientific American, 250 (No. 1, 1984), pp. 10-16.
Index entries for sequences from "Goedel, Escher, Bach"
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006884, A006885, A006877, A006878, A033492, A033959.

a033958 n = a033958_list !! (n-1)
-- For definition of a033958_list: see A033959.
-- Reinhard Zumkeller, Jan 08 2014

f[ nn_ ] := Module[ {c, n}, c = 0; n = nn; While[ n != 1, If[ Mod[ n, 2 ] == 0, n /= 2, n = 3*n + 1; c++ ] ]; Return[ c ] ] maxx = -1; For[ n = 1, n <= 10^8, n++, Module[ {val}, val = f[ n ]; If[ val > maxx, maxx = val; Print[ n, " ", val ] ] ] ] (* Winston C. Yang (winston(AT)cs.wisc.edu), Aug 27 2000 *)

Positions of records in A006667. - Sean A. Irvine, Jul 22 2020

More terms from Jud McCranie, Jan 26 2000
Corrected with Mathematica code by Winston C. Yang (winston(AT)cs.wisc.edu), Aug 27 2000
a(40)-a(43) from Charles R Greathouse IV, Oct 07 2013

A332453 Starting from sigma(n), number of tripling steps to reach 1 in '3x+1' problem, or -1 if 1 is never reached.

Original entry on oeis.org

0, 2, 0, 5, 2, 2, 0, 5, 2, 6, 2, 5, 5, 2, 2, 39, 6, 11, 1, 1, 0, 6, 2, 5, 39, 1, 1, 5, 5, 6, 0, 39, 2, 41, 2, 33, 6, 5, 5, 4, 1, 2, 4, 1, 11, 6, 2, 39, 10, 4, 6, 7, 41, 5, 6, 5, 1, 4, 5, 1, 39, 2, 2, 15, 1, 6, 3, 39, 2, 6, 6, 43, 6, 10, 39, 3, 2, 1, 1, 4, 34, 39, 1, 5, 41, 8, 5, 4, 4, 5, 5, 1, 0, 6, 5, 39, 7, 45, 11, 7, 7, 41, 2, 12, 2

Offset: 1

Antti Karttunen, Feb 16 2020

nonn

Antti Karttunen, Table of n, a(n) for n = 1..8192
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Index entries for sequences related to 3x+1 (or Collatz) problem
Index entries for sequences related to sigma(n)

Cf. A000203, A006667, A332209, A332452, A332455.

A006667(n) = { my(t=0); while(n>1, if(n%2, t++; n=3*n+1, n>>=1)); (t); };
A332453(n) = A006667(sigma(n));

a(n) = A006667(A000203(n)).

a(n) = A332209(n) - A332452(n).

A332455 Starting from sigma(n)+1, number of tripling steps to reach 1 in '3x+1' problem, or -1 if 1 is never reached.

Original entry on oeis.org

0, 0, 1, 0, 5, 2, 6, 0, 5, 6, 2, 5, 5, 7, 7, 0, 6, 1, 1, 9, 8, 6, 7, 5, 0, 9, 40, 10, 39, 42, 8, 0, 7, 41, 7, 4, 11, 5, 10, 33, 9, 43, 4, 1, 11, 42, 7, 39, 5, 38, 42, 7, 41, 34, 42, 34, 6, 33, 5, 16, 39, 43, 12, 0, 1, 42, 3, 15, 43, 42, 42, 7, 3, 10, 39, 3, 43, 16, 6, 14, 5, 15, 1, 17, 41, 8, 34, 4, 33, 46, 2, 16, 44, 42, 34, 39

Offset: 1

Antti Karttunen, Feb 16 2020

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Index entries for sequences related to 3x+1 (or Collatz) problem
Index entries for sequences related to sigma(n)

Cf. A000203, A006667, A088580, A202274, A332453, A332454.

Cf. also A324294, A332459.

A006667(n) = { my(t=0); while(n>1, if(n%2, t++; n=3*n+1, n>>=1)); (t); };
A332455(n) = A006667(1+sigma(n));

a(n) = A006667(A088580(n)) = A006667(1+sigma(n)).

a(2^n) = 0 for all n >= 0. [Zero occurs at least also at a(25). See A202274]

A166549 The number of halving steps of the Collatz 3x+1 map to reach 1 starting from 2n-1.

Original entry on oeis.org

0, 5, 4, 11, 13, 10, 7, 12, 9, 14, 6, 11, 16, 70, 13, 67, 18, 10, 15, 23, 69, 20, 12, 66, 17, 17, 9, 71, 22, 22, 14, 68, 19, 19, 11, 65, 73, 11, 16, 24, 16, 70, 8, 21, 21, 59, 13, 67, 75, 18, 18, 56, 26, 64, 72, 45, 10, 23, 15, 23, 61, 31, 69, 31, 77, 20, 20, 28, 58, 28, 12, 66, 74, 74, 17

Offset: 1

Jimin Park, Oct 16 2009

nonn

A given term k appears A131450(k) times. - Flávio V. Fernandes, Mar 13 2022

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Index to sequences related to the 3x+1 problem

Cf. A131450, A006577, A075680.

A006370 := proc(n) if type(n,'even') then n/2; else 3*n+1 ; end if; end proc:
A006577 := proc(n) a := 0 ; x := n ; while x > 1 do x := A006370(x) ; a := a+1 ; end do; a ; end proc:
A006667 := proc(n) a := 0 ; x := n ; while x > 1 do if type(x,'even') then x := x/2 ; else x := 3*x+1 ; a := a+1 ; end if; end do; a ; end proc:
A075680 := proc(n) A006667(2*n-1) ; end proc:
A166549 := proc(n) A006577(2*n-1)-A075680(n) ; end: seq(A166549(n),n=1..120) ; # R. J. Mathar, Oct 18 2009
# second Maple program:
b:= proc(n) option remember; `if`(n=1, 0,
      1+b(`if`(n::even, n/2, (3*n+1)/2)))
    end:
a:= n-> b(2*n-1):
seq(a(n), n=1..75);  # Alois P. Heinz, Mar 14 2022

b[n_] := b[n] = If[n == 1, 0, 1 + b[If[EvenQ[n], n/2, (3n+1)/2]]];
a[n_] := b[2n-1];
Table[a[n], {n, 1, 75}] (* Jean-François Alcover, Apr 22 2022, after Alois P. Heinz *)

a(n) = A006577(2n-1) - A075680(n).

Edited and extended by R. J. Mathar, Oct 18 2009

A101229 Perfect inverse "3x+1 conjecture" (See comments for rules).

Original entry on oeis.org

1, 2, 4, 1, 2, 4, 8, 16, 5, 10, 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 196608, 393216, 786432, 1572864, 3145728, 6291456, 12582912, 25165824, 50331648, 100663296, 201326592, 402653184, 805306368

Offset: 1

Alexandre Wajnberg, Jan 22 2005

Perfect inverse "3x+1 conjecture": rule 1: multiply n by 2 to give n' = 2n. rule 2: when n'=(3x+1), do n"= (n'-1)/3 (n" integer) Additional rule: rule 2 is applied once for any number n' (otherwise, the sequence beginning with 1 would be the cycle "1 2 4 1 2 4 1 2 4 1..."); then apply rule 1.
This gives a particular sequence of hailstone numbers which may be considered as a central axis for all the hailstone number sequences. The perfect inverse "3x+1 conjecture" falls rapidly into the sequence 3 6 12 24 48 96... which will never give a number to which apply the 2nd rule.
a(n) for n >= 11 written in base 2: 11, 110, 11000, 110000, ..., i.e.: 2 times 1, (n-11) times 0 (see A003953(n-10)). - Jaroslav Krizek, Aug 17 2009

			The first 4 is followed by 1 because 4 = 3*1 + 1, so rule 2: (4-1)/3 = 1;
the second 4 is followed by 8 because the 2nd rule has already been applied, so rule 1: 4*2 = 8.

R. K. Guy, Collatz's Sequence, Section E16 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 215-218, 1994.

G. C. Greubel, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Collatz Problem
Index entries for linear recurrences with constant coefficients, signature (2).

Cf. A070165, A006577, A006667, A006666, A070167.

R:=PowerSeriesRing(Integers(), 45); Coefficients(R!( x*(17*x^10+27*x^8+7*x^3-1)/(2*x-1) )); // G. C. Greubel, Mar 20 2019

Rest[CoefficientList[Series[x*(17*x^10+27*x^8+7*x^3-1)/(2*x-1), {x, 0, 45}], x]] (* G. C. Greubel, Mar 20 2019 *)
LinearRecurrence[{2},{1,2,4,1,2,4,8,16,5,10,3},40] (* Harvey P. Dale, May 06 2023 *)

my(x='x+O('x^45)); Vec(x*(17*x^10+27*x^8+7*x^3-1)/(2*x-1)) \\ G. C. Greubel, Mar 20 2019

a=(x*(17*x^10+27*x^8+7*x^3-1)/(2*x-1)).series(x, 45).coefficients(x, sparse=False); a[1:] # G. C. Greubel, Mar 20 2019

a(n) = 3*2^(n-11) = 2^(n-11) + 2^(n-10) for n >= 11. - Jaroslav Krizek, Aug 17 2009
From Colin Barker, Apr 28 2013: (Start)
a(n) = 2*a(n-1) for n>11.
G.f.: x*(17*x^10+27*x^8+7*x^3-1) / (2*x-1). (End)

More terms from Joshua Zucker, May 18 2006

Edited by G. C. Greubel, Mar 20 2019

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.

Original entry on oeis.org

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.

cp's OEIS Frontend

A062054 Numbers with 4 odd integers in their Collatz (or 3x+1) trajectory.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A127789 Record indices of 2^h(n)/(3^t(n)*n), where h and t are the number of halving resp. tripling steps in the '3x + 1' problem.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A033958 In the '3x+1' problem, these values for the starting value set new records for number of steps to reach 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

Extensions

A332453 Starting from sigma(n), number of tripling steps to reach 1 in '3x+1' problem, or -1 if 1 is never reached.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A332455 Starting from sigma(n)+1, number of tripling steps to reach 1 in '3x+1' problem, or -1 if 1 is never reached.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A166549 The number of halving steps of the Collatz 3x+1 map to reach 1 starting from 2n-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A101229 Perfect inverse "3x+1 conjecture" (See comments for rules).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI