A075680 -id:A075680 - cp's OEIS frontend

A007583 a(n) = (2^(2*n + 1) + 1)/3.

1, 3, 11, 43, 171, 683, 2731, 10923, 43691, 174763, 699051, 2796203, 11184811, 44739243, 178956971, 715827883, 2863311531, 11453246123, 45812984491, 183251937963, 733007751851, 2932031007403, 11728124029611, 46912496118443, 187649984473771, 750599937895083

Offset: 0

Simon Plouffe

Let u(k), v(k), w(k) be the 3 sequences defined by u(1)=1, v(1)=0, w(1)=0 and u(k+1)=u(k)+v(k)-w(k), v(k+1)=u(k)-v(k)+w(k), w(k+1)=-u(k)+v(k)+w(k); let M(k)=Max(u(k),v(k),w(k)); then a(n)=M(2n)=M(2n-1). - Benoit Cloitre, Mar 25 2002
Also the number of words of length 2n generated by the two letters s and t that reduce to the identity 1 by using the relations ssssss=1, tt=1 and stst=1. The generators s and t along with the three relations generate the dihedral group D6=C2xD3. - Jamaine Paddyfoot (jay_paddyfoot(AT)hotmail.com) and John W. Layman, Jul 08 2002
Binomial transform of A025192. - Paul Barry, Apr 11 2003
Number of walks of length 2n+1 between two adjacent vertices in the cycle graph C_6. Example: a(1)=3 because in the cycle ABCDEF we have three walks of length 3 between A and B: ABAB, ABCB and AFAB. - Emeric Deutsch, Apr 01 2004
Numbers of the form 1 + Sum_{i=1..m} 2^(2*i-1). - Artur Jasinski, Feb 09 2007
Prime numbers of the form 1+Sum[2^(2n-1)] are in A000979. Numbers x such that 1+Sum[2^(2n-1)] is prime for n=1,2,...,x is A127936. - Artur Jasinski, Feb 09 2007
Related to A024493(6n+1), A131708(6n+3), A024495(6n+5). - Paul Curtz, Mar 27 2008
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-6, (i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)=(-1)^(n-1)*charpoly(A,2). - Milan Janjic, Feb 21 2010
Number of toothpicks in the toothpick structure of A139250 after 2^n stages. - Omar E. Pol, Feb 28 2011
Numbers whose binary representation is "10" repeated (n-1) times with "11" appended on the end, n >= 1. For example 171 = 10101011 (2). - Omar E. Pol, Nov 22 2012
a(n) is the smallest number for which A072219(a(n)) = 2*n+1. - Ramasamy Chandramouli, Dec 22 2012
An Engel expansion of 2 to the base b := 4/3 as defined in A181565, with the associated series expansion 2 = b + b^2/3 + b^3/(3*11) + b^4/(3*11*43) + .... Cf. A007051. - Peter Bala, Oct 29 2013
The positive integer solution (x,y) of 3*x - 2^n*y = 1, n>=0, with smallest x is (a(n/2), 2) if n is even and (a((n-1)/2), 1) if n is odd. - Wolfdieter Lang, Feb 15 2014
The smallest positive number that requires at least n additions and subtractions of powers of 2 to be formed. See Puzzling StackExchange link. - Alexander Cooke Jul 16 2023

H. W. Gould, Combinatorial Identities, Morgantown, 1972, (1.77), page 10.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..170
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Cecilia Bebeacua, Toufik Mansour, Alexander Postnikov, and Simone Severini, On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
Greg Bell, Austin Lawson, Neil Pritchard, and Dan Yasaki, On locally infinite Cayley graphs of the integers, arXiv preprint arXiv:1711.00809 [math.GT], 2017. See lambda_2.
Phillip G. Bradford, Efficient Exact Paths For Dyck and semi-Dyck Labeled Path Reachability, arXiv:1802.05239 [cs.DS], 2018.
John R. Britnell and Mark Wildon, Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in types A, B and D, arXiv:1507.04803 [math.CO], 2015.
Ernesto Estrada and José A. de la Pena, From Integer Sequences to Block Designs via Counting Walks in Graphs, arXiv preprint arXiv:1302.1176 [math.CO], 2013.
Ernesto Estrada and José A. de la Pena, Integer sequences from walks in graphs, Notes on Number Theory and Discrete Mathematics, Vol. 19, 2013, No. 3, 78-84.
Hannah Golab, Pattern avoidance in Cayley permutations, Master's Thesis, Northern Arizona Univ. (2024). See p. 35.
Sungpyo Hong and Jin Ho Kwak, Regular fourfold coverings with respect to the identity automorphism, J. Graph Theory, 17 (1993), 621-627.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 893
Dmitry Kamenetsky, A magic grasshopper, Puzzling StackExchange, 2023.
Wolfdieter Lang, On Collatz' Words, Sequences and Trees, arXiv preprint arXiv:1404.2710 [math.NT], 2014 and J. Int. Seq. 17 (2014) # 14.11.7.
Mircea Merca, A Note on Cosine Power Sums J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.
Nathan Mihm, Optimal Addition-Subtraction Chains, Bachelor Honors Thesis, Univ. Minnesota-Twin Cities (2025). See p. 5.
Quynh Nguyen, Jean Pedersen, and Hien T. Vu, New Integer Sequences Arising From 3-Period Folding Numbers, Vol. 19 (2016), Article 16.3.1.
Eric Weisstein's World of Mathematics, Repunit
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Cf. also A006054, A006356, A005578, A075680.
Partial sums of A081294.
Cf. A002450, A004171, A007051, A083065, A083066, A083884.
Cf. A000978, A000979, A124400, A124401, A127936, A127955, A127956, A127957, A127958.
Cf. location of records in A007302.

List([0..25], n-> (2^(2*n+1) + 1)/3); # G. C. Greubel, Dec 25 2019

a007583 = (`div` 3) . (+ 1) . a004171
-- Reinhard Zumkeller, Jan 09 2013

[(2^(2*n+1) + 1)/3: n in [0..30] ]; // Vincenzo Librandi, Apr 28 2011

a[0]:=1:for n from 1 to 50 do a[n]:=4*a[n-1]-1 od: seq(a[n], n=0..23); # Zerinvary Lajos, Feb 22 2008, with correction by K. Spage, Aug 20 2014
A007583 := proc(n)
    (2^(2*n+1)+1)/3 ;
end proc: # R. J. Mathar, Feb 19 2015

(* From Michael De Vlieger, Aug 22 2016 *)
Table[(2^(2n+1) + 1)/3, {n, 0, 23}]
Table[1 + 2Sum[4^k, {k, 0, n-1}], {n, 0, 23}]
NestList[4# -1 &, 1, 23]
Table[Sum[Binomial[n+k, 2k]/2^(k-n), {k, 0, n}], {n, 0, 23}]
CoefficientList[Series[(1-2x)/(1-5x+4x^2), {x, 0, 23}], x] (* End *)

a(n)=sum(k=-n\3,n\3,binomial(2*n+1,n+1+3*k))

a=1; for(n=1,23, print1(a,", "); a=bitor(a,3*a)) \\ K. Spage, Aug 20 2014

Vec((1-2*x)/(1-5*x+4*x^2) + O(x^30)) \\ Altug Alkan, Dec 08 2015

apply( {A007583(n)=2<<(2*n)\/3}, [0..25]) \\ M. F. Hasler, Nov 30 2021

[(2^(2*n+1) + 1)/3 for n in (0..25)] # G. C. Greubel, Dec 25 2019

a(n) = 2*A002450(n) + 1.
From Wolfdieter Lang, Apr 24 2001: (Start)
a(n) = Sum_{m = 0..n} A060920(n, m) = A002450(n+1) - 2*A002450(n).
G.f.: (1-2*x)/(1-5*x+4*x^2). (End)
a(n) = Sum_{k = 0..n} binomial(n+k, 2*k)/2^(k - n).
a(n) = 4*a(n-1) - 1, n > 0.
From Paul Barry, Mar 17 2003: (Start)
a(n) = 1 + 2*Sum_{k = 0..n-1} 4^k;
a(n) = A001045(2n+1). (End)
a(n) = A020988(n-1) + 1 = A039301(n+1) - 1 = A083584(n-1) + 2. - Ralf Stephan, Jun 14 2003
a(0) = 1; a(n+1) = a(n) * 4 - 1. - Regis Decamps (decamps(AT)users.sf.net), Feb 04 2004 (correction to lead index by K. Spage, Aug 20 2014)
a(n) = Sum_{i + j + k = n; 0 <= i, j, k <= n} (n+k)!/i!/j!/(2*k)!. - Benoit Cloitre, Mar 25 2004
a(n) = 5*a(n-1) - 4*a(n-2). - Emeric Deutsch, Apr 01 2004
a(n) = 4^n - A001045(2*n). - Paul Barry, Apr 17 2004
a(n) = 2*(A001045(n))^2 + (A001045(n+1))^2. - Paul Barry, Jul 15 2004
a(n) = left and right terms in M^n * [1 1 1] where M = the 3X3 matrix [1 1 1 / 1 3 1 / 1 1 1]. M^n * [1 1 1] = [a(n) A002450(n+1) a(n)] E.g. a(3) = 43 since M^n * [1 1 1] = [43 85 43] = [a(3) A002450(4) a(3)]. - Gary W. Adamson, Dec 18 2004
a(n) = A072197(n) - A020988(n). - Creighton Dement, Dec 31 2004
a(n) = A139250(2^n). - Omar E. Pol, Feb 28 2011
a(n) = A193652(2*n+1). - Reinhard Zumkeller, Aug 08 2011
a(n) = Sum_{k = -floor(n/3)..floor(n/3)} binomial(2*n, n+3*k)/2. - Mircea Merca, Jan 28 2012
a(n) = 2^(2*(n+1)) - A072197(n). - Vladimir Pletser, Apr 12 2014
a(n) == 2*n + 1 (mod 3). Indeed, from Regis Decamps' formula (Feb 04 2004) we have a(i+1) - a(i) == -1 (mod 3), i= 0, 1, ..., n - 1. Summing, we have a(n) - 1 == -n (mod 3), and the formula follows. - Vladimir Shevelev, May 20 2015
For n > 0 a(n) = A133494(0) + 2 * (A133494(n) + Sum_{x = 1..n - 1}Sum_{k = 0..x - 1}(binomial(x - 1, k)*(A133494(k+1) + A133494(n-x+k)))). - J. Conrad, Dec 06 2015
a(n) = Sum_{k = 0..2n} (-2)^k == 1 + Sum_{k = 1..n} 2^(2k-1). - Bob Selcoe, Aug 21 2016
E.g.f.: (1 + 2*exp(3*x))*exp(x)/3. - Ilya Gutkovskiy, Aug 21 2016
A075680(a(n)) = 1, for n > 0. - Ralf Stephan, Jun 17 2025

A006667 Number of tripling steps to reach 1 from n in '3x+1' problem, or -1 if 1 is never reached.

Original entry on oeis.org

0, 0, 2, 0, 1, 2, 5, 0, 6, 1, 4, 2, 2, 5, 5, 0, 3, 6, 6, 1, 1, 4, 4, 2, 7, 2, 41, 5, 5, 5, 39, 0, 8, 3, 3, 6, 6, 6, 11, 1, 40, 1, 9, 4, 4, 4, 38, 2, 7, 7, 7, 2, 2, 41, 41, 5, 10, 5, 10, 5, 5, 39, 39, 0, 8, 8, 8, 3, 3, 3, 37, 6, 42, 6, 3, 6, 6, 11, 11, 1, 6, 40, 40, 1, 1, 9, 9, 4, 9, 4, 33, 4, 4, 38

Offset: 1

N. J. A. Sloane and Bill Gosper

A075680, which gives the values for odd n, isolates the essential behavior of this sequence. - T. D. Noe, Jun 01 2006

A033959 and A033958 give record values and where they occur. - Reinhard Zumkeller, Jan 08 2014

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 204, Problem 22.
R. K. Guy, Unsolved Problems in Number Theory, E16.
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 = 1..10000
J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
Eric Weisstein's World of Mathematics, Collatz Problem.
Wikipedia, Collatz conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem

Equals A078719(n)-1.

Cf. A000079, A000265, A006370, A006577, A006666 (halving steps), A092893, A127789, A139391, A209229.

a006667 = length . filter odd . takeWhile (> 2) . (iterate a006370)
a006667_list = map a006667 [1..]
-- Reinhard Zumkeller, Oct 08 2011

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

Table[Count[Differences[NestWhileList[If[EvenQ[#],#/2,3#+1]&,n,#>1&]], ?Positive], {n,100}] (* _Harvey P. Dale, Nov 14 2011 *)

for(n=2,100,s=n; t=0; while(s!=1,if(s%2==0,s=s/2,s=(3*s+1)/2; t++); if(s==1,print1(t,","); ); ))

def a(n):
    if n==1: return 0
    x=0
    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 14 2017

a(1) = 0, a(n) = a(n/2) if n is even, a(n) = a(3n+1)+1 if n>1 is odd. The Collatz conjecture is that this defines a(n) for all n >= 1.
a(n) = A078719(n) - 1; a(A000079(n))=0; a(A062052(n))=1; a(A062053(n))=2; a(A062054(n))=3; a(A062055(n))=4; a(A062056(n))=5; a(A062057(n))=6; a(A062058(n))=7; a(A062059(n))=8; a(A062060(n))=9. - Reinhard Zumkeller, Oct 08 2011
a(n*2^k) = a(n), for all k >= 0. - L. Edson Jeffery, Aug 11 2014
a(n) = floor(log(2^A006666(n)/n)/log(3)). - Joe Slater, Aug 30 2017
a(n) = a(A085062(n)) + A007814(n+1) for n >= 2. - Alan Michael Gómez Calderón, Feb 07 2025
From  Alan Michael Gómez Calderón, Mar 31 2025: (Start)
a(n) = a(A139391(n)) + (n mod 2) for n >= 2;
a(n) = a(A139391(A000265(n))) - A209229(n) + 1 for n >= 2;
a(n) = a(A000265(A139391(n))) + (n mod 2) for n >= 2. (End)

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

A075677 Reduced Collatz function R applied to the odd integers: a(n) = R(2n-1), where R(k) = (3k+1)/2^r, with r as large as possible.

Original entry on oeis.org

1, 5, 1, 11, 7, 17, 5, 23, 13, 29, 1, 35, 19, 41, 11, 47, 25, 53, 7, 59, 31, 65, 17, 71, 37, 77, 5, 83, 43, 89, 23, 95, 49, 101, 13, 107, 55, 113, 29, 119, 61, 125, 1, 131, 67, 137, 35, 143, 73, 149, 19, 155, 79, 161, 41, 167, 85, 173, 11, 179, 91, 185, 47, 191, 97, 197

Offset: 1

T. D. Noe, Sep 25 2002

The even-indexed terms a(2i+2) = 6i+5 = A016969(i), i >= 0 [Comment corrected by Bob Selcoe, Apr 06 2015]. The odd-indexed terms are the same as A067745. Note that this sequence is A016789 with all factors of 2 removed from each term. Also note that a(4i-1) = a(i). No multiple of 3 is in this sequence. See A075680 for the number of iterations of R required to yield 1.
From Bob Selcoe, Apr 06 2015: (Start)
All numbers in this sequence appear infinitely often.
From Eq. 1 and Eq. 2 in Formulas: Eq. 1 is used with 1/3 of the numbers in this sequence, Eq. 2 is used with 2/3 of the numbers.
(End)
Empirical: For arbitrary m, Sum_{n=2..A007583(m)} (a(n) - a(n-1)) = 0. - Fred Daniel Kline, Nov 23 2015
From Wolfdieter Lang, Dec 07 2021: (Start)
Only positive numbers congruent to 1 or 5 modulo 6 appear.
i) For the sequence entry with value A016921(m), for m >= 0, that is, a value from {1, 7, 13, ...}, the indices n are given by the row of array A178415(2*m+1, k), for k >= 1.
ii) For the sequence entry with value A007528(m), for m >= 1, that is, a value from {5, 11, 17, ...}, the indices n are given by the row of array A178415(2*m, k), for k >= 1.
See also the array A347834 with permuted row numbers and columns k >= 0. (End)

			a(11) = 1 because 21 is the 11th odd number and R(21) = 64/64 = 1.
From _Wolfdieter Lang_, Dec 07 2021: (Start)
i) 1 (mod 6) entry 1 = A016921(0) appears for n = A178415(1, k) = A347834(1, k-1) (the arrays), for k >= 1, that is, for {1, 5, 21, ..} = A002450.
ii) 5 (mod 6) entry 11 = A007528(2) appears for n = A178415(4, k) = A347835(3, k-1) (the arrays), for k >= 1, that is, for {7, 29, 117, ..} = A072261. (End)

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section E16, pp. 330-336.
Victor Klee and Stan Wagon, Old and new unsolved problems in plane geometry and number theory, The Mathematical Association of America, 1991, p. 225, C(2n+1) = a(n+1), n >= 0.
Jeffrey C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010; see p. 57, also (90-9), p. 306.

T. D. Noe, Table of n, a(n) for n = 1..1000
Marc Chamberland, Una actualizacio del problema 3x + 1, Butl. Soc. Catalana Mat. (18), 19-45, 2003.
Jeffrey C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
Fabian S. Reid, The Visual Pattern in the Collatz Conjecture and Proof of No Non-Trivial Cycles, arXiv:2105.07955 [math.GM], 2021.
Eric Weisstein's World of Mathematics, Collatz Problem.
Index entries for sequences related to 3x+1 (or Collatz) problem.

Cf. A000265, A000302, A002450, A007528, A016789, A016921, A016969, A065677, A072197, A072261, A075680, A081294, A178415, A191669, A329480, A347834.
Cf. A006370, A014682 (for non-reduced Collatz maps), A087230 (A371093), A371094.
Odd bisection of A139391.
Even bisection of A067745, which is also the odd bisection of this sequence.
After the initial 1, the second leftmost column of A256598.
Row 2 of A372283.

a075677 = a000265 . subtract 2 . (* 6) -- Reinhard Zumkeller, Jan 08 2014

f:=proc(n) local t1;
if n=1 then RETURN(1) else
t1:=3*n+1;
while t1 mod 2 = 0 do t1:=t1/2; od;
RETURN(t1); fi;
end;
# N. J. A. Sloane, Jan 21 2011

nextOddK[n_] := Module[{m=3n+1}, While[EvenQ[m], m=m/2]; m]; (* assumes odd n *) Table[nextOddK[n], {n, 1, 200, 2}]
v[x_] := IntegerExponent[x, 2]; f[x_] := (3*x + 1)/2^v[3*x + 1]; Table[f[2*n - 1], {n, 66}] (* L. Edson Jeffery, May 06 2015 *)

a(n)=n+=2*n-1;n>>valuation(n,2) \\ Charles R Greathouse IV, Jul 05 2013

from sympy import divisors
def a(n):
    return max(d for d in divisors(n) if d % 2)
print([a(6*n - 2) for n in range(1, 101)]) # Indranil Ghosh, Apr 15 2017, after formula by Reinhard Zumkeller

a(n) = A000265(6*n-2) = A000265(3*n-1). - Reinhard Zumkeller, Jan 08 2014
From Bob Selcoe, Apr 05 2015: (Start)
For all n>=1 and for every k, there exists j>=0 dependent upon n and k such that either:
Eq. 1: a(n) = (3n-1)/2^(2j+1) when k = ((4^(j+1)-1)/3) mod 2^(2j+3). Alternatively: a(n) = A016789(n-1)/A081294(j+1) when k = A002450(j+1) mod A081294(j+2). Example: n=51; k=101 == 5 mod 32, j=1. a(51) = 152/8 = 19.
  or
Eq. 2: a(n) = (3n-1)/4^j when k = (5*2^(2j+1) - 1)/3 mod 4^(j+1). Alternatively: a(n) = A016789(n-1)/A000302(j) when k = A072197(j) mod A000302(j+1). Example: n=91; k=181 == 53 mod 64, j=2. a(91) = 272/16 = 17.
(End) [Definition corrected by William S. Hilton, Jul 29 2017]
a(n) = a(n + g*2^r) - 6*g, n > -g*2^r. Examples: n=59; a(59)=11, r=5. g=-1: 11 = a(27) = 5 - (-1)*6; g=1: 11 = a(91) = 17 - 1*6; g=2: 11 = a(123) = 23 - 2*6; g=3: 11 = a(155) = 29 - 3*6; etc. - Bob Selcoe, Apr 06 2015
a(n) = a((1 + (3*n - 1)*4^(k-1))/3), k>=1 (cf. A191669). - L. Edson Jeffery, Oct 05 2015
a(n) = a(4n-1). - Bob Selcoe, Aug 03 2017
a(n) = A139391(2n-1). - Antti Karttunen, May 06 2024
Sum_{k=1..n} a(k) ~ n^2. - Amiram Eldar, Aug 26 2024
G.f.: Sum_{k>=1} ((3 + 2*(-1)^k)*x^(3*2^(k - 1) - (-2)^k/3 + 1/3) + (3 - 2*(-1)^k)*x^(2^(k - 1) - (-2)^k/3 + 1/3))/(x^(2^k) - 1)^2. - Miles Wilson, Oct 26 2024

A122458 "Dropping time" of the reduced Collatz iteration starting with 2n+1.

Original entry on oeis.org

0, 2, 1, 4, 1, 3, 1, 4, 1, 2, 1, 3, 1, 37, 1, 35, 1, 2, 1, 5, 1, 3, 1, 34, 1, 2, 1, 3, 1, 4, 1, 34, 1, 2, 1, 32, 1, 3, 1, 5, 1, 2, 1, 3, 1, 28, 1, 5, 1, 2, 1, 26, 1, 3, 1, 19, 1, 2, 1, 3, 1, 5, 1, 9, 1, 2, 1, 4, 1, 3, 1, 4, 1, 2, 1, 3, 1, 25, 1, 13, 1, 2, 1, 18, 1, 3, 1, 5, 1, 2, 1, 3, 1, 4, 1, 8, 1, 2, 1, 5

Offset: 0

T. D. Noe, Sep 08 2006

nonn

We count only the 3x+1 steps of the usual Collatz iteration. We stop counting when the iteration produces a number less than the initial 2n+1. For a fixed dropping time k, let N(k)=A100982(k) and P(k)=2^(A020914(k)-1). There are exactly N(k) odd numbers less than P(k) with dropping time k. Moreover, the sequence is periodic: if d is one of the N(k) odd numbers, then k=a(d)=a(d+i*P(k)) for all i>=0. This periodicity makes it easy to compute the average dropping time of the reduced Collatz iteration: Sum_{k>0} k*N(k)/P(k) = 3.492651852186... (A122791).

			a(3)=4 because, starting with 7, the iteration produces 11,17,13,5 and the last term is less than 7.
n = 13: the fr trajectory for 2*13+1 = 27 is 41, 31, 47, 71, 107, 161, 121, 91, 137, 103, 155, 233, 175, 263, 395, 593, 445, 167, 251, 377, 283, 425, 319, 479, 719, 1079, 1619, 2429, 911, 1367, 2051, 3077, 577, 433, 325, 61, 23, 35, 53, 5, 1 with 41 terms (without 27), hence fr^[37] = 23 < 27  and  a(13) = 37. - _Wolfdieter Lang_, Feb 20 2019

Victor Klee and Stan Wagon, Old and New Unsolved Problems in Plane Geometry and Number Theory, Mathematical Association of America (1991) pp. 225-229, 308-309. [called on p. 225 stopping time for 2n+1 and the function C(2*n+1) = A075677(n+1), n >= 0. - Wolfdieter Lang, Feb 20 2019]

T. D. Noe, Table of n, a(n) for n = 0..10000

Cf. A000265, A060445, A075677 (one step of the reduced Collatz iteration), A075680.

Cf. A087113 (indices of 1's), A017077 (indices of 2's), A122791 (limit mean).

nextOddK[n_]:=Module[{m=3n+1}, While[EvenQ[m], m=m/2]; m]; dt[n_]:=Module[{m=n, cnt=0}, If[n>1, While[m=nextOddK[m]; cnt++; m>n]]; cnt]; Table[dt[n],{n,1,301,2}]

a(n) is the least k for which fr^[k](n) < 2*n + 1, for n >= 1 and k >= 1, where fr(n) = A075677(n+1) = A000265(3*n+2). No k satisfies this for n = 0: a(0) := 0 by convention. The dropping time a(n) is finite, for n >= 1, if the Collatz conjecture is true. - Wolfdieter Lang, Feb 20 2019

a(1+i*8) = 2, for i>=0, because A100982(2) = 1 is odd, and A020914(2) = 4 gives P(2) = 2^(4-1) = 8. - Ruud H.G. van Tol, Dec 19 2021

A372283 Array read by upward antidiagonals: A(n, k) = R(A(n-1, k)) for n > 1, k >= 1; A(1, k) = 2*k-1, where Reduced Collatz function R(n) gives the odd part of 3n+1.

Original entry on oeis.org

1, 1, 3, 1, 5, 5, 1, 1, 1, 7, 1, 1, 1, 11, 9, 1, 1, 1, 17, 7, 11, 1, 1, 1, 13, 11, 17, 13, 1, 1, 1, 5, 17, 13, 5, 15, 1, 1, 1, 1, 13, 5, 1, 23, 17, 1, 1, 1, 1, 5, 1, 1, 35, 13, 19, 1, 1, 1, 1, 1, 1, 1, 53, 5, 29, 21, 1, 1, 1, 1, 1, 1, 1, 5, 1, 11, 1, 23, 1, 1, 1, 1, 1, 1, 1, 1, 1, 17, 1, 35, 25

Offset: 1

Antti Karttunen, Apr 28 2024

Collatz conjecture is equal to the claim that in each column 1 will eventually appear. See also arrays A372287 and A372288.

			Array begins:
n\k| 1  2  3   4   5   6   7   8   9  10  11  12  13   14  15   16  17  18
---+-----------------------------------------------------------------------
1  | 1, 3, 5,  7,  9, 11, 13, 15, 17, 19, 21, 23, 25,  27, 29,  31, 33, 35,
2  | 1, 5, 1, 11,  7, 17,  5, 23, 13, 29,  1, 35, 19,  41, 11,  47, 25, 53,
3  | 1, 1, 1, 17, 11, 13,  1, 35,  5, 11,  1, 53, 29,  31, 17,  71, 19,  5,
4  | 1, 1, 1, 13, 17,  5,  1, 53,  1, 17,  1,  5, 11,  47, 13, 107, 29,  1,
5  | 1, 1, 1,  5, 13,  1,  1,  5,  1, 13,  1,  1, 17,  71,  5, 161, 11,  1,
6  | 1, 1, 1,  1,  5,  1,  1,  1,  1,  5,  1,  1, 13, 107,  1, 121, 17,  1,
7  | 1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  5, 161,  1,  91, 13,  1,
8  | 1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 121,  1, 137,  5,  1,
9  | 1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  91,  1, 103,  1,  1,
10 | 1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 137,  1, 155,  1,  1,
11 | 1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 103,  1, 233,  1,  1,
12 | 1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 155,  1, 175,  1,  1,
13 | 1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 233,  1, 263,  1,  1,
14 | 1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 175,  1, 395,  1,  1,
15 | 1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 263,  1, 593,  1,  1,
16 | 1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 395,  1, 445,  1,  1,

Cf. A005408 (row 1), A075677 (row 2), A372443 (column 14).
Cf. A258145 (A075680), A371093.
Arrays derived from this one or related to:
  A372282,
  A372287 the column index of A(n, k) in array A257852,
  A372361 terms xored with binary words of the same length, either of the form 10101...0101 or 110101...0101, depending on whether the binary length is odd or even,
  A372360 binary weights of A372361.
Cf. also array A371095 (giving every fourth column, 1, 5, 9, ...) and irregular array A256598 which gives the terms of each column, but only down to the first 1.

With[{dmax = 15}, Table[#[[k, n-k+1]], {n, dmax}, {k, n}] & [Array[NestList[(3*# + 1)/2^IntegerExponent[3*# + 1, 2] &, 2*# - 1, dmax - #] &, dmax]]] (* Paolo Xausa, Apr 29 2024 *)

up_to = 91;
R(n) = { n = 1+3*n; n>>valuation(n, 2); };
A372283sq(n,k) = if(1==n,2*k-1,R(A372283sq(n-1,k)));
A372283list(up_to) = { my(v = vector(up_to), i=0); for(a=1,oo, for(col=1,a, i++; if(i > up_to, return(v)); v[i] = A372283sq((a-(col-1)),col))); (v); };
v372283 = A372283list(up_to);
A372283(n) = v372283[n];

For n > 1, A(n, k) = R(A372282(n-1, k)), where R(n) = (3*n+1)/2^A371093(n).

For all k >= 1, A(A258145(k-1), k) = 1 [which is the topmost 1 in each column].

A286380 a(n) = the minimum number of iterations of the reduced Collatz function R required to yield 1. The function R (A139391) is defined as R(k) = (3k+1)/2^r, with r as large as possible.

Original entry on oeis.org

0, 1, 2, 1, 1, 3, 5, 1, 6, 2, 4, 3, 2, 6, 5, 1, 3, 7, 6, 2, 1, 5, 4, 3, 7, 3, 41, 6, 5, 6, 39, 1, 8, 4, 3, 7, 6, 7, 11, 2, 40, 2, 9, 5, 4, 5, 38, 3, 7, 8, 7, 3, 2, 42, 41, 6, 10, 6, 10, 6, 5, 40, 39, 1, 8, 9, 8, 4, 3, 4, 37, 7, 42, 7, 3, 7, 6, 12, 11, 2, 6, 41, 40, 2, 1, 10, 9, 5, 9, 5, 33, 5, 4, 39, 38, 3, 43, 8, 7, 8, 7, 8, 31, 3, 12, 3, 36, 42, 41, 42, 24

Offset: 1

Antti Karttunen, May 08 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A075680 (the odd bisection).

Cf. A078719, A139391.

(define (A286380 n) (if (= 1 n) 0 (+ 1 (A286380 (A139391 n)))))

a(1) = 0; for n > 1, a(n) = 1 + a(A139391(n)).
Other identities. For all n >= 1:
a(n) + A000035(n) = A078719(n).

A075684 For odd numbers 2n-1, the maximum number produced by iterating the reduced Collatz function R defined as R(k) = (3k+1)/2^r, with r as large as possible.

Original entry on oeis.org

1, 5, 5, 17, 17, 17, 13, 53, 17, 29, 21, 53, 29, 3077, 29, 3077, 33, 53, 37, 101, 3077, 65, 45, 3077, 49, 77, 53, 3077, 65, 101, 61, 3077, 65, 101, 69, 3077, 3077, 113, 77, 269, 81, 3077, 85, 197, 101, 3077, 93, 3077, 3077, 149, 101, 3077, 269, 3077, 3077, 3077

Offset: 1

T. D. Noe, Sep 25 2002

See A075677 for the function R applied to the odd numbers once. See A075680 for the number of iterations required to yield 1. Sequence A006884, with the number 2 removed, gives the odd numbers that produce new record maxima. The maxima of the current sequence are related to A006885: if m is a maximum of the usual Collatz iteration, then (m-1)/3 is the maximum for the reduced Collatz iteration.

			a(4) = 17 because 7 is the fourth odd number and 17 is the largest number in the iteration: R(7)=11, R(11)=17, R(17)=13, R(13)=5, R(5)=1.

T. D. Noe, Table of n, a(n) for n = 1..5000

Cf. A006884, A006885, A075677, A075680.

nextOddK[n_] := Module[{m=3n+1}, While[EvenQ[m], m=m/2]; m]; (* assumes odd n *) Table[m=n; maxK=n; If[n>1, While[m=nextOddK[m]; maxK=Max[m, maxK]; m!=1]]; maxK, {n, 1, 200, 2}]

A033959 Record number of steps to reach 1 in '3x+1' problem, corresponding to starting values in A033958.

Original entry on oeis.org

0, 2, 5, 6, 7, 41, 42, 43, 44, 45, 46, 47, 52, 62, 65, 66, 76, 79, 87, 96, 98, 101, 102, 103, 113, 114, 119, 125, 129, 130, 138, 141, 142, 164, 166, 174, 189, 195, 196, 197, 207, 208, 209, 217, 222, 228, 248, 256, 257, 258, 263, 278, 357, 358, 359, 362, 370

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.

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, A033958.

Cf. A075680.

a033959 n = a033959_list !! (n-1)
(a033959_list, a033958_list) = unzip $ (0, 1) : f 1 1 where
   f i x | y > x     = (y, 2 * i - 1) : f (i + 1) y
         | otherwise = f (i + 1) x
         where y = a075680 i
-- Reinhard Zumkeller, Jan 08 2014

A033959 := proc(n) local a,L; L := 0; a := n; while a <> 1 do if a mod 2 = 0 then a := a/2; else a := 3*a+1; L := L+1; fi; od: RETURN(L); end;

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 ] ] ] ]

More terms from Winston C. Yang (winston(AT)cs.wisc.edu), Aug 27 2000
More terms from Larry Reeves (larryr(AT)acm.org), Sep 27 2000
Offset corrected by Reinhard Zumkeller, Jan 08 2014

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

A214850 3x+1 groups: irregular triangle read by rows: row n gives all the numbers p <= A075684(n)+1 such that {T(2n+1,k) /pZ} is a multiplicative finite group, where T(2n+1,k) is the reduced trajectory of the Collatz problem whose elements are all odd.

Original entry on oeis.org

2, 4, 2, 4, 6, 2, 4, 6, 8, 12, 18, 2, 4, 8, 2, 4, 6, 2, 4, 6, 8, 12, 2, 4, 8, 2, 4, 6, 8, 12, 2, 4, 6, 12, 2, 4, 8, 10, 20, 22, 2, 4, 6, 8, 2, 4, 6, 12, 18, 2, 4, 8, 16, 2, 4, 6, 2, 4, 6, 8, 12, 16, 18, 24, 2, 4, 2, 4, 6, 2, 4, 6, 8, 12, 18, 2, 4, 8, 2, 4, 6

Offset: 1

Michel Lagneau, Mar 08 2013

We introduce the structure of a finite group in order to give a possible way to classify the Collatz trajectories.
We see that the study of the classification of the trajectories is dependent on the values p.
The principle of the algorithm is to compute all the products T(2n+1,i)/pZ * T(2n+1,j)/pZ and also the inverse of each element such that if x is in the group, then there exist x' in the group with x*x' = 1.
Rows of triangle:
{2, 4},
{2, 4, 6},
{2, 4, 6, 8, 12, 18},
{2, 4, 8},
{2, 4, 6},
{2, 4, 6, 8, 12},
{2, 4, 8},
{2, 4, 6, 8, 12}, ...

			Row 18 gives 6 groups with p = {2, 4, 6, 8, 12, 18}. The Collatz trajectory T(37,k) = {37, 7, 11, 17, 13, 5, 1}, and if we choose, for example, p=18, we obtain G(37) = {T(37,k)/18Z} = {7, 11, 17, 13, 5, 1} which (as subset of Z/18Z) is a multiplicative group of order 6.
For example 5, or 11, generates the cyclic group:
5^1 == 5, 5^2 == 7, 5^3 == 17, 5^4 == 13, 5^5 == 11, 5^6 == 1 (mod 18).
Other subgroups are {1}, {1, 17} and {1, 7, 13}.

Michel Lagneau, Rows n = 1..400 of irregular triangle, flattened

Cf. A075680, A075684.

c:=0:
for n from 3 by 2 to 800 do:
       x:=2:lst:={n}:lst1:={}:x := n:
          for k from 1 to 120 while (x > 1) do:
             a := 0:
             if type(x, 'even') then
             x := x/2:lst:=lst union {x}:a:=a+1:
            else
            x := 3*x+1 :lst:=lst union {x}:a:=a+1:
            fi:
       od:
        n1:=nops(lst):
          for u from 1 to n1 do:
             if irem(lst[u], 2)=1 then
             lst1:=lst1 union {lst[u]}:
            else
           fi:
         od:
         m1:= max( op(lst1)):n1:=nops(lst1):
            for p from 2 by 2 to m1+1 do:
            lst2:={}:
               for q from 1 to n1 do:
               lst2:=lst2 union {irem(lst1[q], p)}:
              od:
              lst3:={}:n2:=nops(lst2):kkk:=0:
                for i from 1 to n2 do:jjj:=0:
                    for j from 1 to n2 do:
                       z:=irem(lst2[i]*lst2[j], p):lst3:=lst3 union{z}:
                       if z=1 then jjj:=1:else fi
                    od:
                    if jjj=0 then kkk:=1:else fi:
                 od:
                 n3:=nops(lst3):iii:=0:
                     for b from 1 to n3 while(iii=0 and n2=n3 and kkk=0)
                 do:
                      if lst2[b]<>lst3[b] then
                      iii:=1:else
                      fi:
                    od:
                    if iii=0  and n2=n3 and kkk=0 then c:=c+1:
                    printf ( "%d %d \n",c,p):
                    else
                    fi:
                od:
                 x:=2:
              od:

cp's OEIS Frontend

A007583 a(n) = (2^(2*n + 1) + 1)/3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Sage

Formula

A006667 Number of tripling steps to reach 1 from n in '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

A075677 Reduced Collatz function R applied to the odd integers: a(n) = R(2n-1), where R(k) = (3k+1)/2^r, with r as large as possible.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A122458 "Dropping time" of the reduced Collatz iteration starting with 2n+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A372283 Array read by upward antidiagonals: A(n, k) = R(A(n-1, k)) for n > 1, k >= 1; A(1, k) = 2*k-1, where Reduced Collatz function R(n) gives the odd part of 3n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A286380 a(n) = the minimum number of iterations of the reduced Collatz function R required to yield 1. The function R (A139391) is defined as R(k) = (3k+1)/2^r, with r as large as possible.

Views

Author