A001281 -id:A001281 - cp's OEIS frontend

A039500 Iterations of "k->k/2 if k is even, k->3k-1 if k is odd" (A001281) starting at these numbers reach 1.

1, 2, 3, 4, 6, 8, 11, 12, 15, 16, 22, 24, 29, 30, 32, 39, 43, 44, 48, 53, 57, 58, 59, 60, 64, 65, 69, 71, 77, 78, 79, 85, 86, 87, 88, 95, 96, 97, 101, 103, 105, 106, 113, 114, 115, 116, 118, 120, 127, 128, 129, 130, 135, 137, 138, 141, 142, 145, 151, 154, 155, 156

Offset: 1

Christian G. Bower, Feb 15 1999

It appears that lim_{n->oo} a(n)/n = 5/2. - Benoit Cloitre, Jan 29 2006
Equivalent to the Collatz ('3n+1') problem for negative integers. - Dmitry Kamenetsky, Jan 12 2017
There are 327679 terms in this sequence which are less than 1000000. Based on this, I would suggest that the limit of a(n)/n is more likely to be 3 than 5/2. This is also a natural guess; there are three known periodic orbits for this recurrence. - David Speyer, Mar 25 2022

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

Positive integers not in A037084.

Cf. A039501, A039502, A039503, A039504, A039505.

colln[n_]:= NestWhile[If[EvenQ[#], #/2, 3#-1] &, n, FreeQ[{1, 5, 17}, #] &]; Select[Range[156], colln[#] == 1 &] (* Jayanta Basu, Jun 06 2013 *)

A037084 Positive integers not going to 1 under iterations of the map in A001281: n->3n-1 if n odd, n->n/2 if n even.

Original entry on oeis.org

5, 7, 9, 10, 13, 14, 17, 18, 19, 20, 21, 23, 25, 26, 27, 28, 31, 33, 34, 35, 36, 37, 38, 40, 41, 42, 45, 46, 47, 49, 50, 51, 52, 54, 55, 56, 61, 62, 63, 66, 67, 68, 70, 72, 73, 74, 75, 76, 80, 81, 82, 83, 84, 89, 90, 91, 92, 93, 94, 98, 99, 100, 102

Offset: 1

Robert W. Craigen (craigen(AT)fresno.edu)

Up to at least 100000000, every number reaches 1, 5 or 17.
Conjecture : for any x, the iterated process "x ->3x-1" if x is odd or "x ->x/2" if x is even leads to one of the following three cycles: (1, 2), (5, 14, 7, 20, 10), (41, 122, 61, 182, 91, 272, 136, 68, 34, 17, 50, 25, 74, 37, 110, 55, 164, 82). - Benoit Cloitre, May 14 2002
Complement (in N*) of A039500 ; union of A039501 and A039502 (conjectured). - M. F. Hasler, Nov 26 2007
Equivalent to the Collatz ('3n+1') problem for negative integers. - Dmitry Kamenetsky, Jan 12 2017

			Iterations of f starting at 3 are 3,8,4,2,1 - thus 3 is not in the sequence.
Iterations starting at 5 are 5,14,7,20,10,5 -periodic and 1 is not among these values, so 5 is in the sequence.

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

Cf. A001281, A039500-A039505.

Cf. A006370, A006577 (Collatz problem: 3n+1).

colln[n_]:= NestWhile[If[EvenQ[#], #/2, 3#-1] &, n, FreeQ[{1, 5, 17}, #] &]; Select[Range[102], colln[#] != 1 &] (* Jayanta Basu, Jun 06 2013 *)

A037084( end=999, n=0 /*starting value -1 */)={ for( i=n,end, n=i; while( n > 17 || n > 5 && n < 17, if( n%2, n=3*n-1, n>>=1)); if( n > 4, print1(i", ")))} \\ M. F. Hasler, Nov 26 2007

More terms from Christian G. Bower, Feb 15 1999

Edited by M. F. Hasler, Nov 26 2007

A135730 Number of steps to reach the minimum of the final cycle under iterations of the map A001281: x->3x-1 if x odd, x/2 otherwise.

Original entry on oeis.org

0, 1, 4, 2, 0, 5, 3, 3, 11, 1, 6, 6, 9, 4, 9, 4, 0, 12, 7, 2, 8, 7, 3, 7, 16, 10, 5, 5, 10, 10, 6, 5, 19, 1, 13, 13, 14, 8, 13, 3, 9, 9, 8, 8, 22, 4, 16, 8, 17, 17, 11, 11, 16, 6, 12, 6, 29, 11, 11, 11, 7, 7, 19, 6, 37, 20, 20, 2, 19, 14, 19, 14, 15, 15, 9, 9, 14, 14, 14, 4

Offset: 1

M. F. Hasler, Nov 26 2007

Under iterations of the map A001281, the orbit of any positive integer seems to end in one of 3 possible cycles, having 1, 5, resp. 17 as smallest element. This sequence gives the number of iterations needed to reach one of these values. Another sequence that could be considered is the number of iterations needed to reach /any/ element of the final cycle.
From N. J. A. Sloane, Sep 04 2015: (Start)
The same sequence arises as follows: Start at 2n-1 and repeatedly apply the map (see A261671): subtract 1 and divide by 2 if the result is odd, otherwise multiply by 3; a(n) is the number of steps to reach one of 1, 9, or 33.
It is conjectured that the trajectory of any odd number will eventually reach 1, 9, or 33, and so enter one of the loops (1,3), (9, 27, 13, 39, 19), or (33, 99, 49, 147, 73, 219, 109, 327, 163, 81, 243, 121, 363, 181, 543, 271, 135, 67). (End)

N. J. A. Sloane, Table of n, a(n) for n = 1..10001

Cf. A001281, A037084, A039500-A039505, A135727-A135729. A006370, A006577 (Collatz 3x+1 problem).
Cf. also A261671.
See A261673 and A261674 for records.

A135730(n)=local(c=0);while( n>17 || n != 17 && n != 5 && n != 1, c++; if( n%2, n=3*n-1,n>>=1));c

A135727 Maximal value in orbit of n under the map A001281(x)=3x-1 if x odd, x/2 if x even.

Original entry on oeis.org

0, 2, 2, 8, 4, 20, 8, 20, 8, 56, 20, 32, 12, 56, 20, 44, 16, 272, 56, 56, 20, 272, 32, 272, 24, 272, 56, 80, 28, 128, 44, 272, 32, 488, 272, 104, 56, 272, 56, 128, 40, 272, 272, 128, 44, 272, 272, 140, 48, 488, 272

Offset: 0

M. F. Hasler, Nov 26 2007

nonn

On the set of positive integers, the orbit of any number under A001281 seems to end in the orbit of 2, of 20 or of 272, which are the respective maxima of these cycles. Since any odd number increases under the map A001281, all elements of this sequence are even.

Cf. A001281, A037084, A039500-A039505, A135728-A135730. A006370, A006577.

A135727(n)=local(m=n);if(n, while( n != 272 & n != 20 & n != 2, if( n%2, n=3*n-1; m=max(n,m), n>>=1)));m

A039501 Iterations of "n->n/2 if n even, n->3n-1 if n odd" (A001281) starting at these numbers reach 5.

Original entry on oeis.org

5, 7, 9, 10, 13, 14, 18, 19, 20, 26, 27, 28, 35, 36, 38, 40, 47, 51, 52, 54, 56, 63, 70, 72, 75, 76, 80, 81, 89, 93, 94, 102, 104, 107, 108, 112, 119, 121, 125, 126, 133, 139, 140, 143, 144, 149, 150, 152, 159, 160, 161, 162, 167, 177, 178, 181, 186, 187, 188, 191

Offset: 1

Christian G. Bower, Feb 15 1999

Cf. A037084, A039500-A039505.

it5Q[n_]:=Last[NestWhileList[If[EvenQ[#],#/2,3#-1]&,n,#!=5&,1,100]]==5; Select[Range[200],it5Q] (* Harvey P. Dale, May 09 2012 *)

A039502 Iterations of "n->n/2 if n even, n->3n-1 if n odd" (A001281) starting at these numbers reach 17.

Original entry on oeis.org

17, 21, 23, 25, 31, 33, 34, 37, 41, 42, 45, 46, 49, 50, 55, 61, 62, 66, 67, 68, 73, 74, 82, 83, 84, 90, 91, 92, 98, 99, 100, 109, 110, 111, 117, 122, 123, 124, 131, 132, 134, 136, 146, 147, 148, 153, 163, 164, 165, 166, 168, 175, 179, 180, 182, 184, 185, 195, 196

Offset: 1

Christian G. Bower, Feb 15 1999

Cf. A037084, A039500-A039505.

colln[n_]:= NestWhile[If[EvenQ[#], #/2, 3#-1] &, n, FreeQ[{1, 5, 17}, #] &]; Select[Range[196], colln[#] == 17 &] (* Jayanta Basu, Jun 06 2013 *)

A135728 Record indices of A135727(n) = max{ A001281^k(n);k=0,1,2,3... } (3x-1 problem).

Original entry on oeis.org

0, 1, 3, 5, 9, 17, 33, 65, 129, 153, 321, 1425, 1601, 1889, 3393, 4097, 6929, 8193, 10497, 11025, 18273, 28161, 74585, 85265, 149345, 337761, 558341, 839429, 1022105, 1467393, 7932689, 8612097, 23911397, 58882625, 75567105, 293056017

Offset: 1

M. F. Hasler, Nov 26 2007

nonn

This gives indices n for which A135727(n) is larger than all preceding values of that sequence. As in A135727(n), we include the fixed point 0 in the domain of A001281. Obviously, many but not all entries are of the form 2^k+1 and not all of such numbers are in the sequence (e.g. 257, 1025, 2049 are missing). Is there a simple way of characterizing the exceptions?

Cf. A001281, A037084, A039500-A039505, A135727-A135730. A006370, A006577.

A135728(Nmax=10^4)=local(m=-1);for(n=0,Nmax,if(m+0A135727(n)),print1(n",")))

a(19)-a(36) from Donovan Johnson, Nov 06 2010

A135729 Record indices of A135727(n)/n = max{ A001281^k(n);k=0,1,2,3... }/n (3x-1 problem).

Original entry on oeis.org

1, 3, 5, 9, 17, 65, 129, 153, 321, 1889, 4097, 10497, 11025, 28161, 149345, 558341, 1467393, 75567105, 299480577, 344371457, 677585217, 788620517, 1951587609, 2672464025, 15958182629, 52002133905, 187559691777, 213121397657

Offset: 1

M. F. Hasler, Nov 26 2007

nonn

This subsequence of A135728 gives indices n for which A135727(n)/n (ratio of maximal value to starting value) is larger than for all preceding indices. Obviously, we cannot consider the index n=0 here.

Cf. A001281, A037084, A039500-A039505, A135727-A135730. A006370, A006577.

A135729(Nmax=10^5)=local(m=0);for(n=1,Nmax,if(m+0A135727(n)/n),print1(n",")))

a(15)-a(28) from Donovan Johnson, Nov 06 2010

A006370 The Collatz or 3x+1 map: a(n) = n/2 if n is even, 3n + 1 if n is odd.

Original entry on oeis.org

0, 4, 1, 10, 2, 16, 3, 22, 4, 28, 5, 34, 6, 40, 7, 46, 8, 52, 9, 58, 10, 64, 11, 70, 12, 76, 13, 82, 14, 88, 15, 94, 16, 100, 17, 106, 18, 112, 19, 118, 20, 124, 21, 130, 22, 136, 23, 142, 24, 148, 25, 154, 26, 160, 27, 166, 28, 172, 29, 178, 30, 184, 31, 190, 32, 196, 33

Offset: 0

N. J. A. Sloane

The 3x+1 or Collatz problem is as follows: start with any number n. If n is even, divide it by 2, otherwise multiply it by 3 and add 1. Do we always reach 1? This is an unsolved problem. It is conjectured that the answer is yes.
The Krasikov-Lagarias paper shows that at least N^0.84 of the positive numbers < N fall into the 4-2-1 cycle of the 3x+1 problem. This is far short of what we think is true, that all positive numbers fall into this cycle, but it is a step. - Richard C. Schroeppel, May 01 2002
Also A001477 and A016957 interleaved. - Omar E. Pol, Jan 16 2014, updated Nov 07 2017
a(n) is the image of a(2*n) under the 3*x+1 map. - L. Edson Jeffery, Aug 17 2014
The positions of powers of 2 in this sequence are given in A160967. - Federico Provvedi, Oct 06 2021
If displayed as a rectangular array with six columns, the columns are A008585, A350521, A016777, A082286, A016789, A350522 (see example). - Omar E. Pol, Jan 03 2022

			G.f. = 4*x + x^2 + 10*x^3 + 2*x^4 + 16*x^5 + 3*x^6 + 22*x^7 + 4*x^8 + 28*x^9 + ...
From _Omar E. Pol_, Jan 03 2022: (Start)
Written as a rectangular array with six columns read by rows the sequence begins:
   0,   4,  1,  10,  2,  16;
   3,  22,  4,  28,  5,  34;
   6,  40,  7,  46,  8,  52;
   9,  58, 10,  64, 11,  70;
  12,  76, 13,  82, 14,  88;
  15,  94, 16, 100, 17, 106;
  18, 112, 19, 118, 20, 124;
  21, 130, 22, 136, 23, 142;
  24, 148, 25, 154, 26, 160;
  27, 166, 28, 172, 29, 178;
  30, 184, 31, 190, 32, 196;
...
(End)

R. K. Guy, Unsolved Problems in Number Theory, E16.
J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..1000
Darrell Cox, The 3n + 1 Problem: A Probabilistic Approach, Journal of Integer Sequences, Vol. 15 (2012), #12.5.2.
David Eisenbud and Brady Haran, UNCRACKABLE? The Collatz Conjecture, Numberphile Video, 2016.
I. Krasikov and J. C. Lagarias, Bounds for the 3x+1 Problem using Difference Inequalities, arXiv:math/0205002 [math.NT], 2002.
J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
J. C. Lagarias, The set of rational cycles for the 3x+1 problem, Acta Arithmetica, LVI (1990), pp. 33-53.
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.
Jeffrey C. Lagarias, The 3x+1 Problem: An Overview, arXiv:2111.02635 [math.NT], 2021.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
E. Roosendaal, On the 3x+1 problem.
S. Schreiber & N. J. A. Sloane, Correspondence, 1980.
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 linear recurrences with constant coefficients, signature (0,2,0,-1).

Cf. A139391, A016945, A005408, A016825, A082286, A070165.
A006577 gives number of steps to reach 1.
Cf. A001281, A047374.
Column k=1 of A347270, n >= 1.

a006370 n | m /= 0    = 3 * n + 1
          | otherwise = n' where (n',m) = divMod n 2
-- Reinhard Zumkeller, Oct 07 2011

[(1/4)*(7*n+2-(-1)^n*(5*n+2)): n in [1..70]]; // Vincenzo Librandi, Dec 20 2016

f := n-> if n mod 2 = 0 then n/2 else 3*n+1; fi;
A006370:=(4+z+2*z**2)/(z-1)**2/(1+z)**2; # Simon Plouffe in his 1992 dissertation; uses offset 0

f[n_]:=If[EvenQ[n],n/2,3n+1];Table[f[n],{n,50}] (* Geoffrey Critzer, Jun 29 2013 *)
LinearRecurrence[{0,2,0,-1},{4,1,10,2},70] (* Harvey P. Dale, Jul 19 2016 *)

for(n=1,100,print1((1/4)*(7*n+2-(-1)^n*(5*n+2)),","))

A006370(n)=if(n%2,3*n+1,n/2) \\ Michael B. Porter, May 29 2010

def A006370(n):
    q, r = divmod(n, 2)
    return 3*n+1 if r else q # Chai Wah Wu, Jan 04 2015

G.f.: (4*x+x^2+2*x^3) / (1-x^2)^2.
a(n) = (1/4)*(7*n+2-(-1)^n*(5*n+2)). - Benoit Cloitre, May 12 2002
a(n) = ((n mod 2)*2 + 1)*n/(2 - (n mod 2)) + (n mod 2). - Reinhard Zumkeller, Sep 12 2002
a(n) = A014682(n+1) * A000034(n). - R. J. Mathar, Mar 09 2009
a(n) = a(a(2*n)) = -A001281(-n) for all n in Z. - Michael Somos, Nov 10 2016
E.g.f.: (2 + x)*sinh(x)/2 + 3*x*cosh(x). - Ilya Gutkovskiy, Dec 20 2016
From Federico Provvedi, Aug 17 2021: (Start)
Dirichlet g.f.: (1-2^(-s))*zeta(s) + (3-5*2^(-s))*zeta(s-1).
a(n) = ( a(n+2k) + a(n-2k) ) / 2, for every integer k. (End)
a(n) + a(n+1) = A047374(n+1). - Leo Ortega, Aug 22 2025

More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001

Zero prepended and new Name from N. J. A. Sloane at the suggestion of M. F. Hasler, Nov 06 2017

A138750 a(n) = ceiling(n/2) if n == 2 (mod 3), a(n) = 2n otherwise.

Original entry on oeis.org

0, 2, 1, 6, 8, 3, 12, 14, 4, 18, 20, 6, 24, 26, 7, 30, 32, 9, 36, 38, 10, 42, 44, 12, 48, 50, 13, 54, 56, 15, 60, 62, 16, 66, 68, 18, 72, 74, 19, 78, 80, 21, 84, 86, 22, 90, 92, 24, 96, 98, 25, 102, 104, 27, 108, 110, 28, 114, 116, 30, 120, 122, 31, 126, 128, 33, 132, 134, 34

Offset: 0

M. F. Hasler, Mar 28 2008

This map is inspired by A124123, which hides in fact a variation of the Collatz problem, defined on the set of primes and working mod 3 instead of mod 2. See A138751 for more information.
The use of ceiling() is here equivalent to round().
The main reason for defining this function is to write A124123 as complement of A007918(A138750(A000040)), and to express the recursion function occurring there in terms of this map.
It might have been more natural to define this map as a(n) = 2n if n == 1 (mod 3), a(n) = ceiling(n/2) otherwise, which is equivalent for all primes > 3 (which are either == 1 or == 2 (mod 3)) and would have "better" properties regarding the analysis of orbits of all integers under this map.
However, for the prime n=3 it does make a difference, and in order to reproduce the map occurring in A124123, we had to adopt the present convention.

			a(0) = 2*0 = 0, a(1) = 2*1 = 2, a(3) = 2*3 = 6, a(4) = 2*4 = 8, ... since these indices are not congruent to 2 (mod 3).
a(2) = ceiling(2/2) = 1, a(5) = ceiling(5/2) = 3, a(8) = ceiling(8/2) = 4, a(11) = ceiling(11/2) = 6, ... since these indices are congruent to 2 (mod 3).

Index entries for linear recurrences with constant coefficients, signature (0,0,1,0,0,1,0,0,-1).
Index entries for sequences related to 3x+1 (or Collatz) problem.

Cf. A001281, A124123, A138751, A138752, A138753, A008588 (trisection), A016933 (trisection), A032766 (trisection)

Table[If[Mod[n,3]==2,Ceiling[n/2],2n],{n,0,70}] (* or *) LinearRecurrence[{0,0,1,0,0,1,0,0,-1},{0,2,1,6,8,3,12,14,4},70] (* Harvey P. Dale, Nov 20 2013 *)

A138750(n) = if( n%3==2, ceil(n/2), 2*n )

G.f.: x*(2 + x + 6*x^2 + 6*x^3 + 2*x^4 + 6*x^5 + 4*x^6) / ( (1+x)*(x^2-x+1)*(x-1)^2*(1+x+x^2)^2 ). - R. J. Mathar, Oct 16 2013
a(n) = a(n-3) + a(n-6) - a(n-9); a(0)=0, a(1)=2, a(2)=1, a(3)=6, a(4)=8, a(5)=3, a(6)=12, a(7)=14, a(8)=4. - Harvey P. Dale, Nov 20 2013
Sum_{n>=1} (-1)^n/a(n) = log(3)/2 - log(2)/3 = log(27/4)/6. - Amiram Eldar, Jul 26 2024

cp's OEIS Frontend

A039500 Iterations of "k->k/2 if k is even, k->3k-1 if k is odd" (A001281) starting at these numbers reach 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A037084 Positive integers not going to 1 under iterations of the map in A001281: n->3n-1 if n odd, n->n/2 if n even.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A135730 Number of steps to reach the minimum of the final cycle under iterations of the map A001281: x->3x-1 if x odd, x/2 otherwise.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A135727 Maximal value in orbit of n under the map A001281(x)=3x-1 if x odd, x/2 if x even.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A039501 Iterations of "n->n/2 if n even, n->3n-1 if n odd" (A001281) starting at these numbers reach 5.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A039502 Iterations of "n->n/2 if n even, n->3n-1 if n odd" (A001281) starting at these numbers reach 17.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A135728 Record indices of A135727(n) = max{ A001281^k(n);k=0,1,2,3... } (3x-1 problem).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Extensions

A135729 Record indices of A135727(n)/n = max{ A001281^k(n);k=0,1,2,3... }/n (3x-1 problem).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Extensions

A006370 The Collatz or 3x+1 map: a(n) = n/2 if n is even, 3n + 1 if n is odd.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs