A070165 -id:A070165 - cp's OEIS frontend

A135282 Largest k such that 2^k appears in the trajectory of the Collatz 3x+1 sequence started at n.

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

Offset: 1

Masahiko Shin, Dec 02 2007

nonn

Most of the first eighty terms in the sequence are 4, because the trajectories finish with 16 -> 8 -> 4 -> 2 -> 1. - R. J. Mathar, Dec 12 2007
Most of the first ten thousand terms are 4, and there only appear 4, 6, 8, and 10 in the extent, unless n is power of 2. In the other words, it seems that the trajectory of the Collatz 3x + 1 sequence ends with either 16, 64, 256 or 1024. There are few exceptional terms, for example a(10920) = 12, a(10922) = 14. It also seems all terms are even unless n is an odd power of 2. - Masahiko Shin, Mar 16 2010
It is true that all terms are even unless n is an odd power of 2: 2 == -1 mod 3, 2 * 2 == -1 * -1 == 1 mod 3. Therefore only even-indexed powers of 2 are congruent to 1 mod 3 and thus reachable by either a halving step or a "tripling step," whereas the odd-indexed powers of 2 are only reachable by a halving step or as an initial value. - Alonso del Arte, Aug 15 2010

			a(6) = 4 because the sequence is 6, 3, 10, 5, 16, 8, 4, 2, 1; there 16 = 2^4 is the largest power of 2 encountered.

Cf. A007814, A209229, A070165, A232503.

Cf. A006577, A208981.

#include  int main(){ int i, s, f; for(i = 2; i < 10000; i++){ f = 0; s = i; while(s != 1){ if(s % 2 == 0){ s = s/2; f++;} else{ f = 0; s = 3 * s + 1; } } printf("%d,", f); } return 0; } /* Masahiko Shin, Mar 16 2010 */

a135282 = a007814 . head . filter ((== 1) . a209229) . a070165_row
-- Reinhard Zumkeller, Jan 02 2013

A135282 := proc(n) local k,threen1 ; k := 0 : threen1 := n ; while threen1 > 1 do if 2^ilog[2](threen1) = threen1 then k := max(k,ilog[2](threen1)) ; fi ; if threen1 mod 2 = 0 then threen1 := threen1/2 ; else threen1 := 3*threen1+1 ; fi ; od: RETURN(k) ; end: for n from 1 to 80 do printf("%d, ",A135282(n)) ; od: # R. J. Mathar, Dec 12 2007

Collatz[n_] := If[EvenQ[n], n/2, 3*n + 1]; Log[2, Table[NestWhile[Collatz, n, ! IntegerQ[Log[2, #]] &], {n, 100}]] (* T. D. Noe, Mar 05 2012 *)

a(n) = A006577(n) - A208981(n) (after Alonso del Arte's comment in A208981), if A006577(n) is not -1. - Omar E. Pol, Apr 10 2022

Edited and extended by R. J. Mathar, Dec 12 2007

More terms from Masahiko Shin, Mar 16 2010

A033479 3x+1 sequence beginning at 9.

Original entry on oeis.org

9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1

Offset: 0

Jeff Burch

			9 is odd, so the next term is 3*9 + 1 = 28.
28 is even, so the next term is 28/2 = 14.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for sequences related to 3x+1 (or Collatz) problem
Index entries for linear recurrences with constant coefficients, signature (0,0,1).

Cf. A070165.

Row 9 of A347270.

NestList[If[EvenQ[#], #/2, 3# + 1] &, 9, 100] (* Harvey P. Dale, Dec 16 2012 *)

Vec((9 + 28*x + 14*x^2 - 2*x^3 - 6*x^4 - 3*x^5 + 27*x^6 - 5*x^7 + 41*x^8 - 8*x^9 - 4*x^10 - 12*x^11 - 6*x^12 - 3*x^13 - 35*x^14 - 4*x^15 - 2*x^16 - x^17 - 14*x^18 - 7*x^19) / ((1 - x)*(1 + x + x^2)) + O(x^80)) \\ Colin Barker, Oct 04 2019

from itertools import accumulate
def f(x, _): return x//2 if x%2 == 0 else 3*x+1
print(list(accumulate([9]*92, f))) # Michael S. Branicky, Sep 28 2021

def collatz(n: Int): Int = (n % 2) match {
  case 0 => n / 2
  case 1 => 3 * n + 1
}
import scala.collection.mutable.ListBuffer
val start = 9; var curr = start; var trajectory = new ListBuffer[Int]()
for (_ <- 1 to 100) {
  trajectory += curr; curr = collatz(curr)
}
trajectory // Alonso del Arte, Jun 02 2019

From Colin Barker, Oct 04 2019: (Start)
G.f.: (9 + 28*x + 14*x^2 - 2*x^3 - 6*x^4 - 3*x^5 + 27*x^6 - 5*x^7 + 41*x^8 - 8*x^9 - 4*x^10 - 12*x^11 - 6*x^12 - 3*x^13 - 35*x^14 - 4*x^15 - 2*x^16 - x^17 - 14*x^18 - 7*x^19) / ((1 - x)*(1 + x + x^2)).
a(n) = a(n-3) for n>19.
(End)

A060445 "Dropping time" in 3x+1 problem starting at 2n+1 (number of steps to reach a lower number than starting value). Also called glide(2n+1).

Original entry on oeis.org

0, 6, 3, 11, 3, 8, 3, 11, 3, 6, 3, 8, 3, 96, 3, 91, 3, 6, 3, 13, 3, 8, 3, 88, 3, 6, 3, 8, 3, 11, 3, 88, 3, 6, 3, 83, 3, 8, 3, 13, 3, 6, 3, 8, 3, 73, 3, 13, 3, 6, 3, 68, 3, 8, 3, 50, 3, 6, 3, 8, 3, 13, 3, 24, 3, 6, 3, 11, 3, 8, 3, 11, 3, 6, 3, 8, 3, 65, 3, 34, 3, 6, 3, 47, 3, 8, 3, 13, 3, 6, 3, 8, 3

Offset: 0

N. J. A. Sloane, Apr 07 2001

If the starting value is even then of course the next step in the trajectory is smaller (cf. A102419).

The dropping time can be made arbitrarily large: If the starting value is of form n(2^m)-1 and m > 1, the next value is 3n(2^m)-3+1. That divided by 2 is 3n(2^(m-1))-1. It is bigger than the starting value and of the same form - substitute 3n -> n and m-1 -> m, so recursively get an increasing subsequence of m odd values. The dropping time is obviously longer than that. This holds even if Collatz conjecture were refuted. For example, m=5, n=3 -> 95, 286, 143, 430, 215, 646, 323, 970, 485, 1456, 728, 364, 182, 91. So the subsequence in reduced Collatz variant is 95, 143, 215, 323, 485. - Juhani Heino, Jul 21 2017

			3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2, taking 6 steps, so a(1) = 6.

T. D. Noe, Table of n, a(n) for n = 0..10000
Jason Holt, Plot of first 1 billion terms, log scale on x axis
Jason Holt, Plot of first 10 billion terms, log scale on x axis
Eric Roosendaal, On the 3x + 1 problem
Index entries for sequences related to 3x+1 (or Collatz) problem

A060565 gives the first lower number that is reached. Cf. A060412-A060415, A217934.
See A074473, A102419 for other versions of this sequence.
Cf. A122437 (allowable dropping times), A122442 (least k having dropping time A122437(n)).
Cf. A070165.

a060445 0 = 0
a060445 n = length $ takeWhile (>= n') $ a070165_row n'
            where n' = 2 * n + 1
-- Reinhard Zumkeller, Mar 11 2013

nxt[n_]:=If[OddQ[n],3n+1,n/2]; Join[{0},Table[Length[NestWhileList[nxt, n,#>=n&]]-1, {n,3,191,2}]]  (* Harvey P. Dale, Apr 23 2011 *)

def a(n):
    if n<1: return 0
    n=2*n + 1
    N=n
    x=0
    while True:
        if n%2==0: n//=2
        else: n = 3*n + 1
        x+=1
        if nIndranil Ghosh, Apr 22 2017

More terms from Jason Earls, Apr 08 2001 and from Michel ten Voorde Apr 09 2001

Still more terms from Larry Reeves (larryr(AT)acm.org), Apr 12 2001

A208981 Number of iterations required to reach a power of 2 in the 3x+1 sequence starting at n.

Original entry on oeis.org

0, 0, 3, 0, 1, 4, 12, 0, 15, 2, 10, 5, 5, 13, 13, 0, 8, 16, 16, 3, 1, 11, 11, 6, 19, 6, 107, 14, 14, 14, 102, 0, 22, 9, 9, 17, 17, 17, 30, 4, 105, 2, 25, 12, 12, 12, 100, 7, 20, 20, 20, 7, 7, 108, 108, 15, 28, 15, 28, 15, 15, 103, 103, 0, 23, 23, 23, 10, 10, 10

Offset: 1

L. Edson Jeffery, Mar 04 2012

The original name was: Number of iterations of the Collatz recursion required to reach a power of 2.
The statement that all paths must eventually reach a power of 2 is equivalent to the Collatz conjecture.
A006577(n) - a(n) gives the exponent for the first power of 2 reached in the Collatz trajectory of n. - Alonso del Arte, Mar 05 2012
Number of nonpowers of 2 in the 3x+1 sequence starting at n. - Omar E. Pol, Sep 05 2021

			a(7) = 12 because the Collatz trajectory for 7 is 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ... which reached 16 = 2^4 in 12 steps.

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

Row sums of A347519.
Cf. A006577 (and references therein).
Cf. A347270 (gives all 3x+1 sequences).
Cf. A070165, A010120, A057716, A135282, A209229.

a208981 = length . takeWhile ((== 0) . a209229) . a070165_row
-- Reinhard Zumkeller, Jan 02 2013

a:= proc(n) option remember; `if`(n=2^ilog2(n), 0,
      1+a(`if`(n::odd, 3*n+1, n/2)))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Sep 05 2021

Collatz[n_?OddQ] := 3*n + 1; Collatz[n_?EvenQ] := n/2; Table[-1 + Length[NestWhileList[Collatz, n, Not[IntegerQ[Log[2, #]]] &]], {n, 50}] (* Alonso del Arte, Mar 04 2012 *)

ispow2(n)=n>>=valuation(n,2); n==1
a(n)=my(s); while(!ispow2(n), n=if(n%2, 3*n+1, n/2); s++); s \\ Charles R Greathouse IV, Jul 31 2016

For x>0 an integer, define f_0(x)=x, and for r=1,2,..., f_r(x)=f_{r-1}(x)/2 if f_{r-1}(x) is even, else f_r(x)=3*f_{r-1}(x)+1. Then a(n) = min(k such that f_k(n) is equal to a power of 2).

a(n) = A006577(n) - A135282(n) (after Alonso del Arte's comment), if A006577(n) is not -1. - Omar E. Pol, Apr 10 2022

Name clarified by Omar E. Pol, Apr 10 2022

A257480 S(n) = (3 + (3/2)^v(1 + F(4n - 3))(1 + F(4n - 3)))/6, n >= 1, where F(x) = (3x + 1)/2^v(3*x + 1) for x odd, and v(y) denotes the 2-adic valuation of y.

Original entry on oeis.org

1, 1, 5, 2, 4, 1, 8, 5, 7, 5, 41, 5, 10, 2, 17, 14, 13, 4, 32, 8, 16, 1, 26, 14, 19, 8, 68, 11, 22, 5, 35, 41, 25, 7, 59, 14, 28, 5, 44, 23, 31, 41, 365, 17, 34, 5, 53, 41, 37, 10, 86, 20, 40, 2, 62, 32, 43, 17, 149

Offset: 1

L. Edson Jeffery, Apr 26 2015

nonn

In the following, let F^(k)(x) denote k-fold iteration of F and defined by the recurrence F^(k)(x) = F(F^(k-1)(x)), k > 0, with initial condition F^(0)(x) = x, and let S^(k)(n) denote k-fold iteration of S and defined by the recurrence S^(k)(n) = S(S^(k-1)(n)), k > 0, with initial condition S^(0)(n) = n, where F and S are as defined above.
Theorem 1: For each x, there exists a j>0 such that F^(j)(x) == 1 (mod 4).
Theorem 2: S(n) = m if and only if S(4*n-2) = m.
Conjecture 1: For each n, there exists a k such that S^(k)(n) = 1.
Theorem 3: Conjecture 1 is equivalent to the 3x+1 conjecture.
Theorem 4: The sequence {log(S(n))/log(n)}_{n>1} is bounded with least upper bound equal to log(3)/log(2).
[I have proved Theorems 1--4 (along with several lemmas) and am trying to finish typesetting the draft containing the proofs but had been too ill to finish that work until now. The draft also contains the derivation of the function S from properties of the known function F (A075677). When that paper is completed (hopefully within two weeks) I will then upload it to the links section and delete this comment.]

K. H. Metzger, Untersuchungen zum (3n+1)-Algorithmus, Teil II: Die Konstruktion des Zahlenbaums, PM (Praxis der Mathematik in der Schule) 42, 2000, 27-32.

I. Korec and Štefan Znám, A Note on the 3x+1 Problem, Amer. Math. Monthly 94, 1987, pp. 771-772.
J. C. Lagarias, The 3x + 1 Problem and Its Generalizations, Amer. Math. Monthly 92, 1985, pp. 3-23.
J. C. Lagarias, The 3x+1 Problem: An Annotated Bibliography (1963-2000), arXiv:math/0309224 [math.NT], 2003-2011.
J. C. Lagarias, The 3x+1 Problem: an annotated bibliography, II (2000-2009), arXiv:math/0608208 [math.NT], 2006-2012.

Cf. A006370, A070165, A075677, A256598.
Cf. A241957, A254067, A254311, A257499, A257791 (all used in the proof of Thm 4).
Cf. A253676 (iteration of S terminating at the first occurrence of 1, assuming the 3x+1 conjecture).
Cf. A253720, A254068, A254070, A254131, A254312, A255138, A255168, A258415.

v[x_] := IntegerExponent[x, 2]; f[x_] := (3*x + 1)/2^v[3*x + 1]; s[n_] := (3 + (3/2)^v[1 + f[4*n - 3]]*(1 + f[4*n - 3]))/6; Table[s[n], {n, 59}]

a(n) = my(x=3*n-2, v=valuation(x, 2)); x>>=v; v=valuation(x+1, 2); (((x>>v)+1)*3^(v-1)+1)/2; \\ Ruud H.G. van Tol, Jul 30 2023

A070167 a(n) is the smallest starting value that produces a Collatz sequence in which n occurs.

Original entry on oeis.org

1, 2, 3, 3, 3, 6, 7, 3, 9, 3, 7, 12, 7, 9, 15, 3, 7, 18, 19, 7, 21, 7, 15, 24, 25, 7, 27, 9, 19, 30, 27, 21, 33, 7, 15, 36, 37, 25, 39, 7, 27, 42, 43, 19, 45, 15, 27, 48, 43, 33, 51, 7, 15, 54, 55, 37, 57, 19, 39, 60, 27, 27, 63, 21, 43, 66, 39, 45, 69, 15, 27, 72, 73, 43, 75, 25

Offset: 1

Eric W. Weisstein, Apr 23 2002

nonn

a(n) <= n. - Robert G. Wilson v, Jan 14 2015

T. D. Noe, Table of n, a(n) for n=1..10000
Eric Weisstein's World of Mathematics, Collatz Sequence
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006667, A070165.

Cf. A010120, A054646.

import Data.List (findIndex)
import Data.Maybe (fromJust)
a070167 n = fromJust (findIndex (elem n) a070165_tabf) + 1
-- Reinhard Zumkeller, Jan 02 2013

Collatz[n_] := NestWhileList[If[EvenQ[#], #/2, 3 # + 1] &, n, # > 1 &]; nn = 100; t = Table[0, {nn}]; n = 0; zeros = nn; While[zeros > 0, n++; c = Collatz[n]; Do[If[i <= nn && t[[i]] == 0, t[[i]] = n; zeros--], {i, c}]]; t (* T. D. Noe, Dec 03 2012 *)

A235795 Triangle read by rows T(n,k) in which row n gives the trajectory of n in Collatz problem including the trajectory [1, 4, 2, 1] for n = 1.

Original entry on oeis.org

1, 4, 2, 1, 2, 1, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 5, 16, 8, 4, 2, 1, 6, 3, 10, 5, 16, 8, 4, 2, 1, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 8, 4, 2, 1, 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 10, 5, 16, 8, 4, 2, 1, 11, 34, 17, 52, 26, 13

Offset: 1

Omar E. Pol, Jan 15 2014

Also [1, 4, 2] together with A070165.

			The irregular triangle begins:
1,4,2,1;
2,1;
3,10,5,16,8,4,2,1;
4,2,1;
5,16,8,4,2,1;
6,3,10,5,16,8,4,2,1;
7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1;
8,4,2,1;
9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1;
10,5,16,8,4,2,1;
11,34,17,52,26,13,40,20,10,5,16,8,4,2,1;
12,6,3,10,5,16,8,4,2,1;
13,40,20,10,5,16,8,4,2,1;
14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1;
...

Michael De Vlieger, Table of n, a(n) for n = 1..11449 (rows 1..250, flattened)
Index entries for sequences related to 3x+1 (or Collatz) problem
Index entries for sequences related to Benford's law

Cf. A000079, A014682, A006370, A070165, A235800, A235801, A347270 (all 3x+1 sequences).

Prepend[Array[NestWhileList[If[EvenQ[#], #/2, 3 # + 1] &, #, # > 1 &] &, 10, 2], NestWhileList[If[EvenQ[#], #/2, 3 # + 1] &, 1, # > 1 &, {2, 1}]] // Flatten (* Michael De Vlieger, Oct 27 2021 *)

f(n) = if (n%2, 3*n+1, n/2); \\ A014682
row(n) = {my(list=List()); listput(list, n); until(n==1, n = f(n); listput(list, n)); Vec(list);} \\ Michel Marcus, Sep 10 2021

A159999 Number of numbers not greater than n occurring in Collatz (3x+1) trajectory starting with n.

Original entry on oeis.org

1, 2, 3, 3, 4, 6, 5, 4, 7, 6, 7, 9, 7, 10, 7, 5, 9, 14, 11, 8, 6, 12, 9, 11, 14, 10, 10, 16, 14, 11, 10, 6, 17, 12, 9, 20, 18, 17, 18, 9, 13, 8, 20, 16, 14, 12, 13, 12, 20, 21, 18, 12, 10, 18, 15, 20, 24, 19, 22, 16, 14, 17, 15, 7, 23, 25, 22, 15, 13, 12, 16, 23

Offset: 1

Reinhard Zumkeller, May 04 2009

If the Collatz conjecture is true, there are no cycles in the 3x+1 trajectory and the difference between the counts here and those of A076228 is that the start value is counted here but not there; then a(n) = 1+A076228(n) [discovered by sequencedb.net]. - R. J. Mathar, Jun 24 2021

			a(9) = #{1,2,4,5,7,8,9} = 7, as
9-28-14-7-22-11-34-17-52-26-13-40-20-10-5-16-8-[4-2-1]*
9-..-..-7-..-..-..-..-..-..-..-..-..-..-5-..-8-[4-2-1]*.

Cf. A033496, A008908, A070165, A214614.

a159999 n = length $ takeWhile (<= n) $ sort $ a070165_row n
-- Reinhard Zumkeller, Sep 01 2012

Collatz[n_] := NestWhileList[If[EvenQ[#], #/2, 3 # + 1] &, n, # > 1 &]; f[n_] := Module[{c = Collatz[n]}, Length[Select[c, # <= n &]]]; Table[ f[n], {n, 100}] (* T. D. Noe, Mar 07 2013 *)

a(n) < n for n>6;
a(A033496(n)) = A008908(A033496(n)).
a(n) = f(n,n,1) with f(n,m,x) = if m=1 then x else f(n, A006370(m), if A006370(m)a(n) = n - A246436(n); row lengths of triangle A214614. - Reinhard Zumkeller, Sep 01 2014

A220237 Triangle read by rows: sorted terms of Collatz trajectories.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 4, 5, 8, 10, 16, 1, 2, 4, 1, 2, 4, 5, 8, 16, 1, 2, 3, 4, 5, 6, 8, 10, 16, 1, 2, 4, 5, 7, 8, 10, 11, 13, 16, 17, 20, 22, 26, 34, 40, 52, 1, 2, 4, 8, 1, 2, 4, 5, 7, 8, 9, 10, 11, 13, 14, 16, 17, 20, 22, 26, 28, 34, 40, 52, 1, 2, 4, 5, 8, 10, 16

Offset: 1

Reinhard Zumkeller, Jan 03 2013

n-th row = sorted list of {A070165(n,k): k = 1..A006577(n)};

T(n,1) = 1 if Collatz conjecture is true.

			The table begins:
.   1:  [1]
.   2:  [1,2]
.   3:  [1,2,3,4,5,8,10,16]
.   4:  [1,2,4]
.   5:  [1,2,4,5,8,16]
.   6:  [1,2,3,4,5,6,8,10,16]
.   7:  [1,2,4,5,7,8,10,11,13,16,17,20,22,26,34,40,52]
.   8:  [1,2,4,8]
.   9:  [1,2,4,5,7,8,9,10,11,13,14,16,17,20,22,26,28,34,40,52]
.  10:  [1,2,4,5,8,10,16]
.  11:  [1,2,4,5,8,10,11,13,16,17,20,26,34,40,52]
.  12:  [1,2,3,4,5,6,8,10,12,16] .

Reinhard Zumkeller, Rows n = 1..120 of triangle, flattened
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006577 (row lengths), A025586(right edge), A033493 (row sums).

import Data.List (sort)
a220237 n k = a220237_tabf !! (n-1) !! (k-1)
a220237_row n = a220237_tabf !! (n-1)
a220237_tabf = map sort a070165_tabf

T:= proc(n) option remember; `if`(n=1, 1,
      sort([n, T(`if`(n::even, n/2, 3*n+1))])[])
    end:
seq(T(n), n=1..10);  # Alois P. Heinz, Oct 16 2021

Flatten[Table[Sort[NestWhileList[If[EvenQ[#],#/2,3#+1]&,n,#>1&]],{n,12}]] (* Harvey P. Dale, Jan 28 2013 *)

A235800 Length of n-th vertical line segment from left to right in a diagram of a two-dimensional version of the 3x+1 (or Collatz) problem.

Original entry on oeis.org

3, 1, 7, 2, 11, 3, 15, 4, 19, 5, 23, 6, 27, 7, 31, 8, 35, 9, 39, 10, 43, 11, 47, 12, 51, 13, 55, 14, 59, 15, 63, 16, 67, 17, 71, 18, 75, 19, 79, 20, 83, 21, 87, 22, 91, 23, 95, 24, 99, 25, 103, 26, 107, 27, 111, 28, 115, 29, 119, 30, 123, 31, 127, 32

Offset: 1

Omar E. Pol, Jan 15 2014

nonn

In the diagram every cycle is represented by a directed graph.
After (3x + 1) the next step is (3y + 1).
After (x/2) the next step is (y/2).
A235801(n) gives the length of n-th horizontal line segment in the same diagram.
Also A004767 and A000027 interleaved.

			The first part of the diagram in the first quadrant looks like this:
. . . . . . . . . . . . . . . . . . . . . . . .
.              _ _|_ _|_ _|_ _|_ _|_ _|_ _|_ _.
.             |   |   |   |   |   |   |   |_|_.
.             |   |   |   |   |   |   |  _ _|_.
.             |   |   |   |   |   |   |_|_ _|_.
.             |   |   |   |   |   |  _ _|_ _|_.
.             |   |   |   |   |   |_|_ _|_ _|_.
.          _ _|_ _|_ _|_ _|_ _|_ _ _|_ _|_ _|_.
.         |   |   |   |   |   |_|_ _|_ _|_ _|_.
.         |   |   |   |   |  _ _|_ _|_ _|_ _|_.
.         |   |   |   |   |_|_ _|_ _|_ _|_ _|_.
.         |   |   |   |  _ _|_ _|_ _|_ _|_ _|_.
.         |   |   |   |_|_ _|_ _|_ _|_ _|_ _| .
.      _ _|_ _|_ _|_ _ _|_ _|_ _|_ _|_ _|     .
.     |   |   |   |_|_ _|_ _|_ _|_ _|         .
.     |   |   |  _ _|_ _|_ _|_ _|             .
.     |   |   |_|_ _|_ _|_ _|                 .
.     |   |  _ _|_ _|_ _|                     .
.     |   |_|_ _|_ _|                         .
.  _ _|_ _ _|_ _|                             .
. |   |_|_ _|                                 .
. |  _ _|                                     .
. |_|                                         .
. . . . . . . . . . . . . . . . . . . . . . . .
. 3,1,7,2,11...
From _Omar E. Pol_, Aug 25 2021: (Start)
The above diagram is the skeleton of a piping model of the 3x+1 or Collatz problem as shown below:
The model consists of pipes, 90-degree elbows and three types of pumps that propel the fluid through the pipes.
The corner of the infinite diagram looks like this:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
                            | |         | |         | |         | |  _ _ _  .
                            | |         | |         | |         | | |     |_.
                            | |         | |         | |         | | |  12  _.
                            | |         | |         | |        _| |_|_ v _| .
                            | |         | |         | |       |  ^  |_|_|_ _.
                            | |         | |         | |       |  11  _ _ _ _.
                            | |         | |         | |  _ _ _|_ _ _| | |   .
                 _ _ _ _ _ _|_|_ _ _ _ _|_|_ _ _ _ _|_|_|     |_ _ _ _|_|_ _.
                |  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _   10  _ _ _ _ _ _ _.
                | |         | |         | |        _| |_|_ v _|       | |   .
                | |         | |         | |       |  ^  |_| |_ _ _ _ _| |_ _.
                | |         | |         | |       |  9   _| |_ _ _ _ _| |_ _.
                | |         | |         | |  _ _ _|_ _ _| | |         | |   .
                | |         | |         | | |     |_ _ _ _| |_ _ _ _ _|_|_ _.
                | |         | |         | | |  8   _ _ _ _| |_ _ _ _ _ _ _ _.
                | |         | |        _| |_|_ v _|       | |         | |   .
                | |         | |       |  ^  |_| |_ _ _ _ _| |_ _ _ _ _|_|_ _.
                | |         | |       |  7   _| |_ _ _ _ _| |_ _ _ _ _ _ _ _.
                | |         | |  _ _ _|_ _ _| | |         | |         | |   .
                | |         | | |     |_ _ _ _| |_ _ _ _ _| |_ _ _ _ _| |   .
                | |         | | |  6   _ _ _ _| |_ _ _ _ _| |_ _ _ _ _ _|   .
                | |        _| |_|_ v _|       | |         | |               .
                | |       |  ^  |_|_|_ _ _ _ _|_|_ _ _ _ _| |               .
                | |       |  5   _ _ _ _ _ _ _ _ _ _ _ _ _ _|               .
                | |  _ _ _|_ _ _| | |         | |                           .
     _ _ _ _ _ _|_|_|     |_ _ _ _|_|_ _ _ _ _| |                           .
    |  _ _ _ _ _ _ _   4   _ _ _ _ _ _ _ _ _ _ _|                           .
    | |        _| |_|_ v _|       | |                                       .
    | |       |  ^  |_| |_ _ _ _ _| |                                       .
    | |       |  3   _| |_ _ _ _ _ _|                                       .
    | |  _ _ _|_ _ _| | |                                                   .
    | | |     |_ _ _ _| |                                                   .
    | | |  2   _ _ _ _ _|                                                   .
   _| |_|_ v _|                                                             .
  |  ^  |_| |                                                               .
  |  1   _ _|                                                               .
  |_ _ _|                                                                   .
.                                                                           .
On the main diagonal of the diagram appear the pumps labeled with the positive integers (A000027).
The pumps labeled with the numbers 2, 6, 8, 12, 14, 18, 20, 24, ... (the nonzero terms of A047238) receive the fluid from the EAST and propel it in a SOUTH direction. The fluid then passes through a 90-degree elbow and then heads WEST.
The pumps labeled with the numbers 4, 10, 16, 22, 28, 34, 40, ... (A016957) are of the type "TEE" as they have two side inlets and one outlet. These receive the fluid from the EAST and from the WEST and propel it in a SOUTH direction. The fluid then passes through a 90-degree elbow and then heads WEST.
The pumps labeled with the numbers 1, 3, 5, 7, 9, 11, 13, ... (A005408) receive the fluid from the EAST and propel it in the NORTH direction. The fluid then passes through a 90-degree elbow and then heads EAST.
Starting from the n-th pump we have that the fluid makes a path equivalent to the trayectory of the 3x+1 sequence starting at n. (End)

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Index entries for sequences related to 3x+1 (or Collatz) problem
Index entries for linear recurrences with constant coefficients, signature (0,2,0,-1).

Cf. A347270 (all 3x+1 sequences).
Cf. Companion of A235801.
Cf. A000027, A004767, A005408, A006370, A014682, A016957, A047238, A070165, A193356, A235795.

LinearRecurrence[{0,2,0,-1},{3,1,7,2},70] (* Harvey P. Dale, Sep 29 2016 *)

from _future_ import division
A235800_list = [4*(n//2) + 3 if n % 2 else n//2 for n in range(1,10**4)] # Chai Wah Wu, Sep 26 2016

a(n) = A006370(n) - A193356(n).
From Chai Wah Wu, Sep 26 2016: (Start)
a(n) = 2*a(n-2) - a(n-4) for n > 4.
G.f.: x*(x^2 + x + 3)/((x - 1)^2*(x + 1)^2). (End)

Previous Showing 11-20 of 121 results. Next

cp's OEIS Frontend

A135282 Largest k such that 2^k appears in the trajectory of the Collatz 3x+1 sequence started at n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Haskell

Maple

Mathematica

Formula

Extensions

A033479 3x+1 sequence beginning at 9.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Scala

Formula

A060445 "Dropping time" in 3x+1 problem starting at 2n+1 (number of steps to reach a lower number than starting value). Also called glide(2n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Extensions

A208981 Number of iterations required to reach a power of 2 in the 3x+1 sequence starting at n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A257480 S(n) = (3 + (3/2)^v(1 + F(4*n - 3))*(1 + F(4*n - 3)))/6, n >= 1, where F(x) = (3*x + 1)/2^v(3*x + 1) for x odd, and v(y) denotes the 2-adic valuation of y.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

A070167 a(n) is the smallest starting value that produces a Collatz sequence in which n occurs.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

A235795 Triangle read by rows T(n,k) in which row n gives the trajectory of n in Collatz problem including the trajectory [1, 4, 2, 1] for n = 1.

Views

A257480 S(n) = (3 + (3/2)^v(1 + F(4n - 3))(1 + F(4n - 3)))/6, n >= 1, where F(x) = (3x + 1)/2^v(3*x + 1) for x odd, and v(y) denotes the 2-adic valuation of y.