A075677 -id:A075677 - cp's OEIS frontend

A256598 Irregular triangle where row n contains the odd terms in the Collatz sequence beginning with 2n+1.

1, 3, 5, 1, 5, 1, 7, 11, 17, 13, 5, 1, 9, 7, 11, 17, 13, 5, 1, 11, 17, 13, 5, 1, 13, 5, 1, 15, 23, 35, 53, 5, 1, 17, 13, 5, 1, 19, 29, 11, 17, 13, 5, 1, 21, 1, 23, 35, 53, 5, 1, 25, 19, 29, 11, 17, 13, 5, 1, 27, 41, 31, 47, 71, 107, 161, 121, 91, 137, 103, 155

Offset: 0

Bob Selcoe, Apr 03 2015

The Collatz function is an integer-valued function given by n/2 if n is even and 3n+1 if n is odd. We build a Collatz sequence by beginning with a natural number and iterating the function indefinitely. It is conjectured that all such sequences terminate at 1.
In this triangle, row n is made up of the odd terms of the Collatz sequence beginning with 2n+1. Therefore, it is conjectured that this sequence is well-defined, i.e., that all rows terminate at 1.
The last index k in row n gives the number of iterations required for the Collatz sequence to terminate if even terms are omitted.
T(n,k)/T(n,k+1) is of form: ceiling(T(n,k)*3/2^j) for some j>=1. Therefore, the coefficients in each row may be read as a series of iterated ceilings, where j may vary. For example, row 3 has initial term 7, which is followed by ceiling(7*3/2), ceiling(ceiling(7*3/2)*3/2), ceiling(ceiling(ceiling(7*3/2)*3/2)*3/4), ceiling(ceiling(ceiling(ceiling(7*3/2)*3/2)*3/4)*3/8), ceiling(ceiling(ceiling(ceiling(ceiling(7*3/2)*3/2)*3/4)*3/8)*3/16).
The length of row n is A258145(n) (set to 0 if 1 is not reached after a finite number of steps). - Wolfdieter Lang, Aug 11 2021

			Triangle starts T(0,0):
n\k   0   1   2   3   4    5   6   7   8   9  10 ...
0:    1
1:    3   5   1
2:    5   1
3:    7   11  17  13  5    1
4:    9   7   11  17  13   5   1
5:    11  17  13  5   1
6:    13  5   1
7:    15  23  35  53  5    1
8:    17  13  5   1
9:    19  29  11  17  13   5   1
10:   21  1
11:   23  35  53  5    1
12:   25  19  29  11  17  13   5   1
...
n=13 starts with 27 and takes 41 steps: (27), 41, 31, 47, 71, 107,... 53, 5, 1, (see A372443).
Row 8 is [17, 13, 5, 1] because it is the subsequence of odd terms for the Collatz sequence starting with 17: [17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1].

Eric Weisstein's World of Mathematics, Collatz Problem
Wikipedia, Collatz conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006370, A070165, A075677, A258145.
Cf. A372443 (row 13 up to its first 1).
Cf. also array A372283 showing the same terms in different orientation.

f[n_] := NestWhileList[(3*# + 1)/2^IntegerExponent[3*# + 1, 2] &, 2*n + 1, # > 1 &]; Grid[Table[f[n], {n, 0, 12}]] (* L. Edson Jeffery, Apr 25 2015 *)

row(n) = {my(oddn = 2*n+1, vl = List(oddn), x); while (oddn != 1, x = 3*oddn+1; oddn = x >> valuation(x, 2); listput(vl, oddn)); Vec(vl);}
tabf(nn) = {for (n=0, nn, my(rown = row(n)); for (k=1, #rown, print1(rown[k], ", ")); print;);} \\ Michel Marcus, Oct 04 2019

def Collatz(n):
    A = [n]
    b = A[-1]
    while b != 1:
        if is_even(b):
            A.append(b//2)
        else:
            A.append(3*b+1)
    return A
[y for sublist in [[x for x in Collatz(2*n+1) if is_odd(x)] for n in [0..15]] for y in sublist] # Tom Edgar, Apr 04 2015

T(n,0) = 2n+1 and T(n,k) = A000265(3*T(n,k-1)+1) for k>0. - Tom Edgar, Apr 04 2015

A209308 Denominators of the Akiyama-Tanigawa algorithm applied to 2^(-n), written by antidiagonals.

Original entry on oeis.org

1, 2, 2, 1, 2, 4, 4, 4, 8, 8, 1, 4, 8, 4, 16, 2, 2, 1, 8, 32, 32, 1, 2, 4, 4, 16, 32, 64, 8, 8, 16, 16, 64, 64, 128, 128, 1, 8, 16, 8, 32, 64, 128, 32, 256, 2, 2, 8, 16, 64, 64, 128, 64, 512, 512, 1, 2, 4, 8, 32, 64, 128, 16, 128, 512, 1024

Offset: 0

Paul Curtz, Jan 18 2013

1/2^n and successive rows are
1,       1/2,   1/4,   1/8,  1/16,  1/32,   1/64, 1/128, 1/256,...
1/2,     1/2,   3/8,   1/4,  5/32,  3/32,  7/128,  1/32,...       = A000265/A075101, the Oresme numbers n/2^n. Paul Curtz, Jan 18 2013 and May 11 2016
0,       1/4,   3/8,   3/8,  5/16, 15/64, 21/128,...              = (0 before A069834)/new,
-1/4,   -1/4,     0,   1/4, 25/64, 27/64,...
0,      -1/2,  -3/4, -9/16, -5/32,...
1/2,     1/2, -9/16, -13/8,...
0,      17/8, 51/16,...
-17/8, -17/8,...
0
The first column is A198631/(A006519?), essentially the fractional Euler numbers 1, -1/2, 0, 1/4, 0,...  in A060096.
Numerators b(n): 1, 1, 1, 0, 1, 1, -1, 1, 3, 1, ... .
Coll(n+1) - 2*Coll(n) = -1/2, -5/8, -1/2, -11/32, -7/32, -17/128, -5/64, -23/512, ... = -A075677/new, from Collatz problem.
There are three different Bernoulli numbers:
The first Bernoulli numbers are  1, -1/2, 1/6, 0,... = A027641(n)/A027642(n).
The second Bernoulli numbers are 1,  1/2, 1/6, 0,... = A164555(n)/A027642(n). These are the binomial transform of the first one.
The third Bernoulli numbers are  1,   0,  1/6, 0,... = A176327(n)/A027642(n), the half sum. Via A177427(n) and A191567(n), they yield the Balmer series A061037/A061038.
There are three different fractional Euler numbers:
1) The first are  1, -1/2, 0, 1/4, 0, -1/2,... in A060096(n).
Also Akiyama-Tanigawa algorithm for ( 1, 3/2, 7/4, 15/8, 31/16, 63/32,... = A000225(n+1)/A000079(n) ).
2) The second are 1, 1/2, 0, -1/4, 0,  1/2,... , mentioned by Wolfdieter Lang in A198631(n).
3) The third are  0, 1/2, 0, -1/4, 0,  1/2,... , half difference of 2) and 1).
Also Akiyama-Tanigawa algorithm for ( 0, -1/2, -3/4, -7/8, -15/16, -31/32,... =  A000225(n)/A000079(n) ). See A097110(n).

			Triangle begins:
  1,
  2, 2,
  1, 2,  4,
  4, 4,  8,  8,
  1, 4,  8,  4, 16,
  2, 2,  1,  8, 32, 32,
  1, 2,  4,  4, 16, 32,  64,
  8, 8, 16, 16, 64, 64, 128, 128,
  ...

G. C. Greubel, Table of n, a(n) for n = 0..5049
A. F. Horadam, Oresme Numbers, Fibonacci Quarterly, 12, #3, 1974, pp. 267-271.

Cf. Second Bernoulli numbers A164555(n)/A027642(n) via Akiyama-Tanigawa algorithm for 1/(n+1), A272263.

max = 10; t[0, k_] := 1/2^k; t[n_, k_] := t[n, k] = (k + 1)*(t[n - 1, k] - t[n - 1, k + 1]); denoms = Table[t[n, k] // Denominator, {n, 0, max}, {k, 0, max - n}]; Table[denoms[[n - k + 1, k]], {n, 1, max}, {k, 1, n}] // Flatten (* Jean-François Alcover, Feb 05 2013 *)

A067745 Numerator of ((3n - 2)/(n^(2n - 1)(2n - 1)*4^(n - 1))).

Original entry on oeis.org

1, 1, 7, 5, 13, 1, 19, 11, 25, 7, 31, 17, 37, 5, 43, 23, 49, 13, 55, 29, 61, 1, 67, 35, 73, 19, 79, 41, 85, 11, 91, 47, 97, 25, 103, 53, 109, 7, 115, 59, 121, 31, 127, 65, 133, 17, 139, 71, 145, 37, 151, 77, 157, 5, 163, 83, 169, 43, 175, 89, 181, 23, 187, 95, 193, 49, 199

Offset: 1

Marc LeBrun, Jan 29 2002

Conjecture: Odd part of 3n-2. - Ralf Stephan, Nov 18 2010
Conjecture is true.  Note that gcd(3n-2,2n-1)=1 (because 2(3n-2)-3(2n-1) = -1) and gcd(3n-2,n) = 1 or 2.  If 2^k | (3n-2), then k <= log_2(3n-2) < (n-1)/2 for n >= 11.  So only the cases n <= 10 need to be checked individually. - Robert Israel, May 16 2017
This sequence is equivalent to A165355 where each element is reduced by the highest possible power of two. - Joe Slater, Nov 30 2016
Selecting each odd term gives b(n) = 6n+1 (A016921). A075677 is the even bisection of this sequence, while this sequence is the odd bisection of A075677. - Cory Kalm, Apr 29 2021
Numerator of n/2^n + (n-1)/2^(n-1), two Oresme numbers. - Paul Curtz, Dec 07 2021

Robert Israel, Table of n, a(n) for n = 1..10000
D. S. Mitrinovic and Slavko Simic, Special Functions from Long Ago: 5626, Amer. Math. Monthly 109, (2002), p. 83-84.

Cf. A067746, A165355, A000265, A075677, A016921, A007310 (range).

Cf. A075101.

[Numerator(((3*n - 2)/(n^(2*n - 1)*(2*n - 1)*4^(n - 1)))): n in [1..80]]; // Vincenzo Librandi, Feb 16 2015

f:= n -> (3*n-2)/2^padic:-ordp(3*n-2,2):
map(f, [$1..100]); # Robert Israel, May 16 2017

(* Assuming the above conjecture: *)
a067745[n_] := (3*n - 2)/2^IntegerExponent[3*n - 2, 2]; Table[a067745[n], {n, 67}] (* L. Edson Jeffery, Feb 15 2015 *)

vector(80, n, numerator(((3*n - 2)/(n^(2*n - 1)*(2*n - 1)*4^(n - 1))))) \\ Michel Marcus, Feb 16 2015

Assuming the above conjecture, a(n) = a((8+(3*n-2)*4^k)/12), for all k >= 1. - L. Edson Jeffery, Feb 15 2015
a(n) = A000265(A165355(n-1)). - Joe Slater, Nov 30 2016
a(n) = A000265(3*n-2). - R. J. Mathar, Aug 23 2020
a(n) = A075677(2*n-1). a(2*n) = A075677(n); a(2*n-1) = A016921(n). - Cory Kalm, May 03 2021
Sum_{k=1..n} a(k) ~ n^2. - Amiram Eldar, Aug 26 2024
G.f.: Sum_{k>=1} ((3 + 2*(-1)^(k + 1))*x^(3*2^(k - 1) - (2*(-2)^(k - 1))/3 - 1/3) + (3 - 2*(-1)^(k + 1))*x^(2^(k - 1)*(3 + 2*(-1)^k)/3 - 1/3))/(x^(2^(k + 1)) - 2*x^(2^k) + 1). - Miles Wilson, Jan 12 2025

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

A159885 For n >= 1, let f(2n+1) = (3n+2)/A006519(3n+2) and let f^k be the k-th iteration of f. Then a(n) is the least k such that A000120(f^k(2n+1)) <= A000120(n).

Original entry on oeis.org

2, 1, 2, 6, 1, 1, 2, 3, 3, 1, 1, 4, 1, 1, 2, 8, 2, 3, 3, 39, 1, 1, 1, 4, 3, 1, 1, 2, 1, 1, 2, 8, 5, 2, 2, 41, 3, 2, 3, 5, 5, 1, 1, 1, 1, 1, 1, 42, 2, 1, 4, 6, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 2, 44, 5, 5, 5, 31, 5, 2, 2, 41, 7, 1, 3, 3, 3, 2, 3, 34, 3, 5, 13, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 42, 8, 1, 2, 4, 1

Offset: 1

Vladimir Shevelev, Apr 25 2009, Apr 27 2009

Conjecture: a(n) exists for every n >= 1. It is easy to see that this conjecture is equivalent to the well-known Collatz 3x+1 conjecture.

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

Cf. A006519, A007814, A000120, A159945, A160198, A160266.

A006519(n) = (1<A006519((3*((n-1)/2))+2); \\ Defined only for odd n. Cf. A075677.
A159885(n) = { my(w=hammingweight(n), n = (n+n+1)); for(k=1,oo,n = f(n); if(hammingweight(n) <= w, return(k))); }; \\ Antti Karttunen, Sep 22 2018

Edited by N. J. A. Sloane, May 03 2009

a(25) corrected, sequence extended by R. J. Mathar, May 15 2009

A159945 Let f be defined as in A159885. Then a(n) = max{A000120(f^i(2n+1)): 1 <= i <= A159885(n)}.

Original entry on oeis.org

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

Offset: 1

Vladimir Shevelev, Apr 27 2009

nonn

Problem: find an upper estimate for a(n).

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

Cf. A000120, A006519, A007814, A075677, A159885.

A006519(n) = (1<A006519((3*((n-1)/2))+2); \\ Defined for odd n only. Cf. A075677.
A159945(n) = { my(w=hammingweight(n), m = 0, n = (n+n+1)); for(k=1,oo,n = f(n); m = max(m,hammingweight(n)); if(hammingweight(n) <= w, return(m))); }; \\ Antti Karttunen, Sep 22 2018

More terms from Antti Karttunen, Sep 22 2018

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

A160198 a(n) = min(A122458(n), A159885(n)).

Original entry on oeis.org

2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 3, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 4, 1, 3, 1, 2, 1, 2, 1, 3, 1, 3, 1, 3, 1, 2, 1, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 4, 1, 2

Offset: 1

Vladimir Shevelev, May 04 2009

Let f(2n+1) = A000265(3n+2) be defined as in A159885. Then a(n) is the least number k of iterations such that either f^k(2n+1) < 2n+1 or A000120(f^k(2n+1)) < A000120(2n+1).

Using induction, one can prove that the Collatz (3x+1)-conjecture follows from the finiteness of a(n) for every n. - Vladimir Shevelev, May 05 2009

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

Cf. A000120, A075677, A122458, A159885, A159945, A160267.

A000265 := proc(n) option remember ; local a; a := n ; while a mod 2 = 0 do a := a/2 ; end do; a; end proc:
f := proc(n) local m ; m := (n-1)/2 ; A000265(3*m+2) ; end:
A000120 := proc(n) local d; add(d, d=convert(n,base,2)) ; end proc:
A159885 := proc(n) local k, twon1; k := 0 ; twon1 := 2*n+1 ; while ( A000120(twon1) > A000120(n) ) do twon1 := f(twon1) ; k := k+1 ; end do; k ; end proc:
A122458 := proc(n) local tx1,a; a := 0 ; tx1 := 2*n+1 ; while tx1 >= 2*n+1 do if tx1 mod 2 = 0 then tx1 := tx1/2 ; else tx1 := 3*tx1+1 ; a := a+1 ; fi; end do; a ; end proc:
A160198 := proc(n) min(A159885(n),A122458(n)) ; end: seq(A160198(n),n=1..130) ; # R. J. Mathar, May 15 2009

a[n_] := Module[{u=2n+1, w, k=0}, w = DigitCount[u, 2, 1]; While[u >= 2n+1 && DigitCount[u, 2, 1] >= w, k++; u = (3(u-1)/2+2)/2^IntegerExponent[ (3(u-1)/2+2), 2]]; k];
Array[a, 105] (* Jean-François Alcover, Apr 16 2020, after Antti Karttunen *)

f(n) = ((3*((n-1)/2))+2)/A006519((3*((n-1)/2))+2);  \\ Defined for odd n only. Cf. A075677.
A006519(n) = (1<A160198(n) = { my(u = (n+n+1), w = hammingweight(u), k=0); while((u >= (n+n+1))&&(hammingweight(u) >= w), k++; u = f(u)); (k); }; \\ Antti Karttunen, Sep 22 2018

a(1) corrected and sequence extended by R. J. Mathar, May 15 2009

A173732 a(n) = (A016957(n)/2^A007814(A016957(n)) - 1)/2, with A016957(n) = 6*n+4 and A007814(n) the 2-adic valuation of n.

Original entry on oeis.org

0, 2, 0, 5, 3, 8, 2, 11, 6, 14, 0, 17, 9, 20, 5, 23, 12, 26, 3, 29, 15, 32, 8, 35, 18, 38, 2, 41, 21, 44, 11, 47, 24, 50, 6, 53, 27, 56, 14, 59, 30, 62, 0, 65, 33, 68, 17, 71, 36, 74, 9, 77, 39, 80, 20, 83, 42, 86, 5, 89, 45, 92, 23, 95, 48, 98, 12, 101, 51, 104, 26, 107, 54, 110, 3

Offset: 0

Howard A. Landman, Feb 22 2010

All positive integers eventually reach 1 in the Collatz problem iff all nonnegative integers eventually reach 0 with repeated application of this map, i.e., if for all n, the sequence n, a(n), a(a(n)), a(a(a(n))), ... eventually hits 0.
0 <= a(n) <= (3n+1)/2, with the upper bound being achieved for all odd n.
The positions of the zeros are given by A020988 = (2/3)*(4^n-1). This is because if n = (2/3)*(4^k-1), then m = 2n+1 = (1/3)*(4^(k+1)-1), and 3m+1 = 4^(k+1) is a power of 4. - Howard A. Landman, Mar 14 2010
Subsequence of A025480, a(n) = A025480(3n+1), i.e., A025480 = 0,[0],1,0,[2],1,3,[0],4,2,[5],1,6,[3],7,0,[8],4,9,[2],10,5,[11],1,12,[6],13,3,[14],... with elements of A173732 in brackets. - Paul Tarau, Mar 21 2010
A204418(a(n)) = 1. - Reinhard Zumkeller, Apr 29 2012
Original name: "A compression of the Collatz (or 3x+1) sequence considered as a map from odd numbers to odd numbers." - Michael De Vlieger, Oct 07 2019

			a(0) = 0 because 2n+1 = 1 (the first odd number), 3*1 + 1 = 4, dividing all powers of 2 out of 4 leaves 1, and (1-1)/2 = 0.
a(1) = 2 because 2n+1 = 3, 3*3 + 1 = 10, dividing all powers of 2 out of 10 leaves 5, and (5-1)/2 = 2.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics,Collatz Problem.
Wikipedia, Collatz conjecture.
Index entries for sequences related to 3x+1 (or Collatz) problem.

Cf. A006370, A007494 (range), A007814, A016957, A020988, A025480, A075677.

#include  main() { int k,m,n; for (k = 0; ; k++) { n = 2*k + 1 ; m = 3*n + 1 ; while (!(m & 1)) { m >>= 1 ; } printf("%d,",((m - 1) >> 1)); } }

a173732 n = a173732_list !! n
a173732_list = f $ tail a025480_list where f (x :  :  : xs) = x : f xs
-- Reinhard Zumkeller, Apr 29 2012

Array[(#/2^IntegerExponent[#, 2] - 1)/2 &[6 # + 4] &, 75, 0] (* Michael De Vlieger, Oct 06 2019 *)

odd(n) = n >> valuation(n, 2);
a(n) = (odd(6*n+4) - 1)/2; \\ Amiram Eldar, Aug 26 2024

From Amiram Eldar, Aug 26 2024: (Start)
a(n) = (A075677(n+1) - 1)/2.
Sum_{k=1..n} a(k) ~ n^2 / 2. (End)

Name changed by Michael De Vlieger, Oct 07 2019

A160267 Minimum of A122458(n) and A160266(n).

Original entry on oeis.org

2, 1, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 4, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 5, 1, 1, 1, 17, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 4, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 9, 1, 2, 1, 1, 1, 2, 1, 3, 1, 1, 1, 8, 1, 1, 1, 5, 1, 2, 1, 1, 1, 2, 1

Offset: 1

Vladimir Shevelev, May 07 2009, May 11 2009

nonn

Let f be the operation defined in A159885, namely f(2n+1) = A075677(n+1), and f^k its k-fold iteration.

Then a(n) is the smallest k such that either f^k(2n+1)< 2n+1 or A006694((f^k(2n+1)-1)/2) < A006694(n).

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

Cf. A006694, A075677, A122458, A159885, A159945, A160198, A160266.

f(n) = ((3*((n-1)/2))+2)/A006519((3*((n-1)/2))+2); \\ Defined for odd n only. Cf. A075677.
A006519(n) = (1<A006694(n) = (sumdiv(2*n+1, d, eulerphi(d)/znorder(Mod(2, d))) - 1); \\ From A006694
A160267(n) = { my(w=A006694(n), u = (n+n+1), k=0); while((u >= (n+n+1))&&(A006694((u-1)/2) >= w), k++; u = f(u)); (k); }; \\ Antti Karttunen, Sep 22 2018

a(47) corrected and more terms appended by R. J. Mathar, Aug 08 2010

cp's OEIS Frontend

A256598 Irregular triangle where row n contains the odd terms in the Collatz sequence beginning with 2n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A209308 Denominators of the Akiyama-Tanigawa algorithm applied to 2^(-n), written by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A067745 Numerator of ((3*n - 2)/(n^(2*n - 1)*(2*n - 1)*4^(n - 1))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

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

A159885 For n >= 1, let f(2n+1) = (3n+2)/A006519(3n+2) and let f^k be the k-th iteration of f. Then a(n) is the least k such that A000120(f^k(2n+1)) <= A000120(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A159945 Let f be defined as in A159885. Then a(n) = max{A000120(f^i(2n+1)): 1 <= i <= A159885(n)}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

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

A067745 Numerator of ((3n - 2)/(n^(2n - 1)(2n - 1)*4^(n - 1))).

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.