A064433 -id:A064433 - cp's OEIS frontend

A008908 a(n) = (1 + number of halving and tripling steps to reach 1 in the Collatz (3x+1) problem), or -1 if 1 is never reached.

1, 2, 8, 3, 6, 9, 17, 4, 20, 7, 15, 10, 10, 18, 18, 5, 13, 21, 21, 8, 8, 16, 16, 11, 24, 11, 112, 19, 19, 19, 107, 6, 27, 14, 14, 22, 22, 22, 35, 9, 110, 9, 30, 17, 17, 17, 105, 12, 25, 25, 25, 12, 12, 113, 113, 20, 33, 20, 33, 20, 20, 108, 108, 7, 28, 28, 28, 15, 15, 15, 103

Offset: 1

N. J. A. Sloane, Bill Gosper

The number of steps (iterations of the map A006370) to reach 1 is given by A006577, this sequence counts 1 more. - M. F. Hasler, Nov 05 2017

When Collatz 3N+1 function is seen as an isometry over the dyadics, the halving step necessarily following each tripling is not counted, hence N -> N/2, if even, but N -> (3N+1)/2, if odd. Counting iterations of this map until reaching 1 leads to sequence A064433. - Michael Vielhaber (vielhaber(AT)gmail.com), Nov 18 2009

R. K. Guy, Unsolved Problems in Number Theory, E16.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
Nitrxgen, Collatz Calculator
Wikipedia, Collatz conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006577, A006370, A006667, A075677.

a008908 = length . a070165_row
-- Reinhard Zumkeller, May 11 2013, Aug 30 2012, Jul 19 2011

a:= proc(n) option remember; 1+`if`(n=1, 0,
      a(`if`(n::even, n/2, 3*n+1)))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Jan 29 2021

Table[Length[NestWhileList[If[EvenQ[ # ], #/2, 3 # + 1] &, i, # != 1 &]], {i, 75}]

a(n)=my(c=1); while(n>1, n=if(n%2, 3*n+1, n/2); c++); c \\ Charles R Greathouse IV, May 18 2015

def a(n):
    if n==1: return 1
    x=1
    while True:
        if n%2==0: n//=2
        else: n = 3*n + 1
        x+=1
        if n<2: break
    return x
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Apr 15 2017

a(n) = A006577(n) + 1.
a(n) = f(n,1) with f(n,x) = if n=1 then x else f(A006370(n),x+1).
a(A033496(n)) = A159999(A033496(n)). - Reinhard Zumkeller, May 04 2009
a(n) = A006666(n) + A078719(n).
a(n) = length of n-th row in A070165. - Reinhard Zumkeller, May 11 2013

More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001
"Escape clause" added to definition by N. J. A. Sloane, Jun 06 2017
Edited by M. F. Hasler, Nov 05 2017

A064455 a(2n) = 3n, a(2n-1) = n.

Original entry on oeis.org

1, 3, 2, 6, 3, 9, 4, 12, 5, 15, 6, 18, 7, 21, 8, 24, 9, 27, 10, 30, 11, 33, 12, 36, 13, 39, 14, 42, 15, 45, 16, 48, 17, 51, 18, 54, 19, 57, 20, 60, 21, 63, 22, 66, 23, 69, 24, 72, 25, 75, 26, 78, 27, 81, 28, 84, 29, 87, 30, 90, 31, 93, 32, 96, 33, 99, 34, 102, 35, 105, 36, 108

Offset: 1

N. J. A. Sloane, Oct 02 2001

Also number of 1's in n-th row of triangle in A071030. - Hans Havermann, May 26 2002
Number of ON cells at generation n of 1-D CA defined by Rule 54. - N. J. A. Sloane, Aug 09 2014
a(n)*A098557(n) equals the second right hand column of A167556. - Johannes W. Meijer, Nov 12 2009
Given a(1) = 1, for all n > 1, a(n) is the least positive integer not equal to a(n-1) such that the arithmetic mean of the first n terms is an integer. The sequence of arithmetic means of the first 1, 2, 3, ..., terms is 1, 2, 2, 3, 3, 4, 4, ... (A004526 disregarding its first three terms). - Rick L. Shepherd, Aug 20 2013

			a(13) = a(2*7 - 1) = 7, a(14) = a(2*7) = 21.
a(8) = 8-9+10-11+12-13+14-15+16 = 12. - _Bruno Berselli_, Jun 05 2013

Harry J. Smith, Table of n, a(n) for n = 1..1000
A. J. Macfarlane, Generating functions for integer sequences defined by the evolution of cellular automata with even rule numbers, 2016.
S. Wolfram, Statistical mechanics of cellular automata, Rev. Mod. Phys., 55 (1983), 601--644.
Index entries for linear recurrences with constant coefficients, signature (0,2,0,-1)

Interleaving of A000027 and A008585 (without first term).

Cf. A004526, A052928, A064433, A071030, A080512, A098557, A123684, A137501, A167556, A225144, A265888.

maxarg := 75; for n := 1 to maxarg do if n mod 2 = 1 then write((n+1) div 2, " ") else write((n div 2)*3," "); end; end;

a:=[];;  for n in [1..75] do if n mod 2 = 0 then Add(a,3*n/2); else Add(a,(n+1)/2); fi; od; a; # Muniru A Asiru, Oct 28 2018

import Data.List (transpose)
a064455 n = n + if m == 0 then n' else - n'  where (n',m) = divMod n 2
a064455_list = concat $ transpose [[1 ..], [3, 6 ..]]
-- Reinhard Zumkeller, Oct 12 2013

[(1/2)*n*(-1)^n+n+(1/4)*(1-(-1)^n): n in [1..80]]; // Vincenzo Librandi, Aug 10 2014

A064455 := proc(n)
    if type(n,'even') then
        3*n/2 ;
    else
        (n+1)/2 ;
    end if;
end proc: # R. J. Mathar, Aug 03 2015

Table[ If[ EvenQ[n], 3n/2, (n + 1)/2], {n, 1, 70} ]

a(n) = { if (n%2, (n + 1)/2, 3*n/2) } \\ Harry J. Smith, Sep 14 2009

a(n)=if(n<3,2*n-1,((n-1)*(n-2))%(2*n-1)) \\ Jim Singh, Oct 14 2018

def A064455(n): return (3*n - (2*n-1)*(n%2))//2
print([A064455(n) for n in range(1,81)]) # G. C. Greubel, Jan 30 2025

a(n) = (1/2)*n*(-1)^n + n + (1/4)*(1 - (-1)^n). - Stephen Crowley, Aug 10 2009
G.f.: x*(1+3*x) / ( (1-x)^2*(1+x)^2 ). - R. J. Mathar, Mar 30 2011
From Jaroslav Krizek, Mar 22 2011: (Start)
a(n) = n - A123684(n-1) for odd n.
a(n) = n + a(n-1) for even n.
a(n) = A123684(n) + A137501(n).
Abs( a(n) - A123684(n) ) =  A052928(n). (End)
a(n) = Sum_{i=n..2*n} i*(-1)^i. - Bruno Berselli, Jun 05 2013
a(n) = n + floor(n/2)*(-1)^(n mod 2). - Bruno Berselli, Dec 14 2015
a(n) = (n^2-3*n+2) mod (2*n-1) for n>2. - Jim Singh, Oct 31 2018
E.g.f.: (1/2)*(x*cosh(x) + (1+3*x)*sinh(x)). - G. C. Greubel, Jan 30 2025

A070168 Irregular triangle of Terras-modified Collatz problem.

Original entry on oeis.org

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

Offset: 1

Eric W. Weisstein, Apr 23 2002

The row length of this irregular triangle is A006666(n) + 1 = A064433(n+1), n >= 1. - Wolfdieter Lang, Mar 20 2014

			The irregular triangle begins:
n\k   0   1   2   3   4   5   6   8  9 10  11  12  13  14 ...
1:    1
2:    2   1
3:    3   5   8   4   2   1
4:    4   2   1
5:    5   8   4   2   1
6:    6   3   5   8   4   2   1
7:    7  11  17  26  13  20  10   5  8  4   2   1
8:    8   4   2   1
9:    9  14   7  11  17  26  13  20 10  5   8   4   2   1
10:  10   5   8   4   2   1
11:  11  17  26  13  20  10   5   8  4  2   1
12:  12   6   3   5   8   4   2   1
13:  13  20  10   5   8   4   2   1
14:  14   7  11  17  26  13  20  10  5  8   4   2   1
15:  15  23  35  53  80  40  20  10  5  8   4   2   1
...  formatted by _Wolfdieter Lang_, Mar 20 2014
-------------------------------------------------------------

Reinhard Zumkeller, Rows n = 1..250 of triangle, flattened
J. C. Lagarias, The 3x+1 Problem and its Generalizations, Amer. Math. Monthly 92 (1985) 3-23.
R. Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976) 241-252.
Eric Weisstein's World of Mathematics, Collatz Problem
Wikipedia, Collatz conjecture

Cf. A070165 (ordinary Collatz case).

Cf. A014682, A248573, A285098 (row sums).

a070168 n k = a070168_tabf !! (n-1) !! (k-1)
a070168_tabf = map a070168_row [1..]
a070168_row n = (takeWhile (/= 1) $ iterate a014682 n) ++ [1]
a070168_list = concat a070168_tabf
-- Reinhard Zumkeller, Oct 03 2014

f[n_] := If[EvenQ[n], n/2, (3 n + 1)/2];
Table[NestWhileList[f, n, # != 1 &], {n, 1, 30}] // Grid (* Geoffrey Critzer, Oct 18 2014 *)

def a(n):
    if n==1: return [1]
    l=[n, ]
    while True:
        if n%2==0: n//=2
        else: n = (3*n + 1)//2
        l.append(n)
        if n<2: break
    return l
for n in range(1, 16): print(a(n)) # Indranil Ghosh, Apr 15 2017

From Wolfdieter Lang, Mar 20 2014: (Start)
See Lagarias, pp. 4-7, eqs. (2.1), (2.4) with (2.5) and (2.6).
T(n,k) = T^{(k)}(n), with the iterations of the Terras-modified Collatz map: T(n) = n/2 if n is even and otherwise (3*n+1)/2, n >= 1. T^{(0)}(n) = n.
T(n,k) = lambda(n,k)*n + rho(n,k), with lambda(n,k) = (3^X(n,k,-1))/2^k and rho(n,k) = sum(x(n,j)*(3^X(n,k,j))/ 2^(k-j), j=0..(k-1)) with X(n,k,j) = sum(x(n,j+p), p=1.. (k-1-j)) where x(n,j) = T^{(j)}(n) (mod 2). The parity sequence suffices to determine T(n,k).
(End)

Name shortened, tabl changed into tabf, Cf. added by Wolfdieter Lang, Mar 20 2014

A248037 Numbers n such that the ratio of tripling steps to halving steps in the Collatz (3x+1) trajectory of n is greater than all previous ratios.

Original entry on oeis.org

2, 3, 7, 9, 27, 230631, 626331, 837799, 1723519, 3732423, 5649499, 6649279, 8400511, 63728127, 3743559068799, 100759293214567, 104899295810901231

Offset: 1

Derek Orr, Sep 29 2014

Equivalently, numbers n such that A006667(n)/A064433(n) > A006667(m)/A064433(m) for all 0 < m < n.
A006667(n) is the number of tripling steps in the Collatz (3x+1) problem and A064433(n) is the number of halving steps in the Collatz (3x+1) problem.
It is crucial to make A006667(n) the numerator as it can be zero when n = 2^k for some k > 0.
a(n) is odd for all n > 1.
The corresponding ratios are:
0.0000000000000000000000000000... (2)
0.4000000000000000000000000000... (3)
0.4545454545454545454545454545... (7)
0.4615384615384615384615384615... (9)
0.5857142857142857142857142857... (27)
0.5899280575539568345323741007... (230631)
0.5924764890282131661442006269... (626331)
0.5927051671732522796352583586... (837799)
0.5931232091690544412607449856... (1723519)
0.5935828877005347593582887700... (3732423)
0.5937500000000000000000000000... (5649499)
0.5961538461538461538461538461... (6649279)
0.5967365967365967365967365967... (8400511)
0.6030405405405405405405405405... (63728127)
0.6035196687370600414078674948... (3743559068799)
If we define a "tripling step" to also include a "halving step" afterwards (since 3*n+1 converts an odd number n into an even number, so a halving step will always follow), the ratios are still maximum at the a(n) values. However, the ratios themselves are different. The corresponding ratios in this case are:
0.000000000000000000000000000... (2)
0.666666666666666666666666666... (3)
0.833333333333333333333333333... (7)
0.857142857142857142857142857... (9)
1.413793103448275862068965517... (27)
1.438596491228070175438596491... (230631)
1.453846153846153846153846153... (626331)
1.455223880597014925373134328... (837799)
1.457746478873239436619718309... (1723519)
1.460526315789473684210526315... (3732423)
1.461538461538461538461538461... (5649499)
1.476190476190476190476190476... (6649279)
1.479768786127167630057803468... (8400511)
1.519148936170212765957446808... (63728127)
1.656946826758147512864493997... (3743559068799)
From Jon E. Schoenfield, Nov 21 2015: (Start)
Let T and H be the number of tripling steps and halving steps, respectively, in the entire Collatz (3x+1) trajectory of a number n. Since each tripling step increases the value by a factor greater than 3, and each halving step decreases it by a factor of exactly 2, we have n * 3^T / 2^H < 1, from which T/H < log(2)/log(3) - log_3(n)/H, so the ratio T/H cannot exceed log(2)/log(3) = 0.6309297535...
It seems likely that the present sequence is a subsequence of A006877 (which consists of values n whose trajectories are of record length). Taking as values of n the terms from the b-file for A006877, and generating their trajectories to obtain the corresponding values of H(n), it does not seem clear whether log_3(n)/H(n) is converging toward zero or toward some positive limit, perhaps around 0.020 (which would mean T/H < log(2)/log(3) - 0.020, i.e., T/H < 0.611).
The known terms n in A006877 at which log_3(n)/H(n) reaches a record low coincide almost exactly with the known terms of this sequence, the only exception thus far being a(11) = A006877(52) = 5649499, at which log_3(n)/H(n) is only slightly larger than it is at a(10) = A006877(51) = 3732423 (0.03685302 vs. 0.03682956). Given the values of log_3(n)/H(n) for the remaining known terms in A006877, it seems likely that
     a(16) = A006877(110) = 100759293214567
  and that a(17) exceeds A006877(130), which is 46785696846401151.
(End)
Note that a(17)=104899295810901231 has now been found by Eric Roosendaal's distributed project (see link below). - Dmitry Kamenetsky, Sep 23 2016
For n>=14, a(n) must be 7, 15, 27, or 31 (mod 32). This is because all other values provably have a ratio of tripling to halving steps of less than 0.6 (see program by Irvine and Consiglio Jr.). - Dmitry Kamenetsky, Sep 24 2016

Sean A. Irvine and David Consiglio, Jr., C program
Eric Roosendaal, Completeness and Gamma records
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006667, A006877, A008908, A064433.

Tratio(n)=c=0; d=0; while(n!=1,if(n==Mod(0,2),n=n/2;d++); if(n==Mod(1,2)&&n!=1,n=3*n+1;c++));c/d
print1(2,", "); n=2; p=Tratio(2); while(n,t=Tratio(n+1); if(p>=t,n+=2); if(p

Corrected and extended by Sean A. Irvine, Derek Orr, and David Consiglio, Jr., Nov 23 2015
a(16) from David Consiglio, Jr. and Sean A. Irvine, Nov 26 2015
a(17) added by Dmitry Kamenetsky, Sep 23 2016

A064456 A064434(n) = 0.

Original entry on oeis.org

1, 3, 79, 235, 431, 1503, 2943, 6059, 6619, 18911, 54223, 302467995, 1772665631, 2148845167, 5145362667, 129465909327, 212089391807

Offset: 1

Jonathan Ayres (JonathanAyres(AT)btinternet.com), Oct 01 2001

a(18) > 4*10^12. - Donovan Johnson, Jan 19 2011

Also indices n where A079878(n)=1. - R. J. Mathar, Nov 13 2011

Cf. A064433.

: a := 0; for n := 1 to 3000000000 do am := a; a := (am*2 + 1) mod n; if a = 0 then write(n," "); end; end;

More terms from Klaus Brockhaus, Oct 04 2001

Offset corrected and a(15)-a(17) from Donovan Johnson, Jan 19 2011

A076182 a(n) = A006666(n) mod 2.

Original entry on oeis.org

0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Benoit Cloitre, Nov 01 2002

nonn

Cf. A014682, A006513, A006666, A076092.

a(n)=if(n<0,0,s=n; c=0; while(s>1,s=(s%2)*(3*s+1)/2+(1-s%2)*s/2; c++); c)%2

(define (A076182 n) (modulo (A006666 n) 2))
(definec (A006666 n) (if (= 1 n) 0 (+ 1 (A006666 (A014682 n))))) ;; With memoization-macro definec
(define (A014682 n) (if (even? n) (/ n 2) (/ (+ n n n 1) 2)))
;; Antti Karttunen, Aug 13 2017

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

Apparently also the antiparity of A064433. - Ralf Stephan, Nov 16 2004

A174539 Starting numbers n such that the number of halving and tripling steps to reach 1 under the Collatz 3x+1 map is a perfect square.

Original entry on oeis.org

1, 2, 7, 12, 13, 16, 44, 45, 46, 80, 84, 85, 98, 99, 100, 101, 102, 107, 129, 153, 156, 157, 158, 169, 272, 276, 277, 280, 282, 300, 301, 302, 350, 351, 512, 576, 592, 596, 597, 608, 616, 618, 625, 642, 643, 644, 645, 646, 648, 649, 650, 651, 652, 653, 654, 655, 662, 663

Offset: 1

Michel Lagneau, Mar 21 2010

nonn

Numbers n such that A006577(n) is a perfect square.

			44, 45 and 46 are in the sequence because the number of steps as counted in A006577 for each of them is 16 = 4^2, a perfect square.

Index to sequences related to the 3x+1 problem

Cf. A006577, A008908, A064433, A006666, A006667, A033491

with(numtheory):for x from 1 to 200 do traj:=0: n1:=x: x1:=x: for p from 1 to 20 while(irem(x1,2)=0)do p1:=2^p: xx1:=x1: x1:=floor(n1/p1): traj:=traj+1:od:
n:=x1: for q from 1 to 100 while(n<>1)do n1:=3*n+1: traj:=traj+1: x0:=irem(n1,2): for p from 1 to 20 while(x0=0)do p1:=2^p: xx1:=x1: x1:=floor(n1/p1): x0:=n1-p1*x1: traj:=traj+1: od: traj:=traj-1: n:=xx1:od:
if(sqrt(traj))=floor(sqrt(traj)) then print(x):else fi:od:

htsQ[n_]:=With[{len=Length[NestWhileList[If[EvenQ[#],#/2,3#+1]&,n,#!=1&]]-1},IntegerQ[Sqrt[len]]]; Select[Range[700],htsQ] (* Harvey P. Dale, Jan 01 2023 *)

{n: A006577(n) in A000290}.

Unspecific references removed - R. J. Mathar, Mar 31 2010

Corrected and extended by Harvey P. Dale, Jan 01 2023

cp's OEIS Frontend

A008908 a(n) = (1 + number of halving and tripling steps to reach 1 in the Collatz (3x+1) problem), or -1 if 1 is never reached.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A064455 a(2n) = 3n, a(2n-1) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

ARIBAS

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A070168 Irregular triangle of Terras-modified Collatz problem.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Formula

Extensions

A248037 Numbers n such that the ratio of tripling steps to halving steps in the Collatz (3x+1) trajectory of n is greater than all previous ratios.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A064456 A064434(n) = 0.

Views

Author

Keywords

Comments

Crossrefs

Programs

ARIBAS

Extensions

A076182 a(n) = A006666(n) mod 2.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Scheme

Formula

A174539 Starting numbers n such that the number of halving and tripling steps to reach 1 under the Collatz 3x+1 map is a perfect square.