A001281 -id:A001281 - cp's OEIS frontend

A378845 Smallest starting x which takes n steps to reach the minimum of a cycle in the 3x-1 iteration.

1, 2, 4, 7, 3, 6, 11, 19, 21, 13, 26, 9, 18, 35, 37, 73, 25, 49, 98, 33, 66, 131, 45, 90, 175, 127, 117, 85, 149, 57, 113, 199, 209, 133, 265, 89, 177, 65, 119, 237, 87, 159, 165, 329, 231, 225, 439, 309, 293, 585, 377, 391, 273, 261, 521, 1042, 671, 695, 485

Offset: 0

Kevin Ryde, Dec 09 2024

nonn

Each step is x -> 3x-1 if x odd, or x -> x/2 if x even (A001281).
The number of steps is A135730(x) so that a(n) = x is the smallest x for which A135730(x) = n.
a(n) <= 2*a(n-1) since x = 2*a(n-1) is a candidate for a(n) by first step x -> x/2.
Even terms are always a(n) = 2*a(n-1) since any smaller even a(n) would imply a smaller a(n-1) after first step x -> x/2.
No term is of the form 12*k+4, since its first step to 6*k+2 is also where the first step from 2*k+1 goes and the latter is a smaller start.
a(n) >= (a(n-1) + 1)/3 is a lower bound since a(n) = x must at least have a first step 3x-1 which reaches somewhere with n-1 further steps, so 3x-1 >= a(n-1).
Equality a(n) = (a(n-1) + 1)/3 = x occurs iff that x is an odd integer and not a cycle minimum, so its first step is to 3x-1 = a(n-1) (as for example at n=11).

Kevin Ryde, Table of n, a(n) for n = 0..1435
Kevin Ryde, C Code

Cf. A001281 (step), A135730 (number of steps).
Cf. A378846 (with halving steps), A378847 (with tripling steps).
Cf. A033491 (in 3x+1).

C
```
/* See links. */
```

A378846 Smallest starting x which takes n halving steps to reach the minimum of a cycle in the 3x-1 iteration.

Original entry on oeis.org

1, 2, 4, 3, 6, 11, 13, 9, 18, 35, 25, 47, 33, 63, 45, 81, 95, 117, 127, 85, 57, 113, 133, 89, 97, 65, 129, 87, 173, 225, 231, 293, 309, 377, 261, 273, 545, 671, 465, 485, 597, 647, 741, 529, 353, 705, 471, 941, 1029, 1241, 837, 577, 385, 257, 513, 343, 229, 153

Offset: 0

Kevin Ryde, Dec 15 2024

nonn

Each step is x -> 3x-1 if x odd, or x -> x/2 if x even (A001281) and here only the halving steps x/2 are counted.
The number of halving steps is A377524(x) so that a(n) = x is the smallest x for which A377524(x) = n.
a(n) <= 2*a(n-1) is an upper bound since x = 2*a(n-1) is a candidate for a(n) by first step x -> x/2.
All even terms are a(n) = 2*a(n-1), since any smaller even a(n) would imply a smaller a(n-1) by first step x -> x/2.
No term is of the form y = 6*k + 2, apart from a(1)=2, since odd x = 2*k+1 takes a tripling step to 3*x-1 = y and x is a smaller start with the same number of halvings as y.

Kevin Ryde, Table of n, a(n) for n = 0..932
Kevin Ryde, C Code (set count type HALF)

Cf. A001281 (step), A377524 (number of halving steps).

Cf. A378845 (with all steps), A378847 (with tripling steps).

C
```
/* See links. */
```

A378847 Smallest starting x which takes n tripling steps to reach the minimum of a cycle in the 3x-1 iteration.

Original entry on oeis.org

1, 3, 15, 13, 9, 37, 25, 33, 45, 57, 145, 97, 65, 87, 159, 165, 225, 273, 391, 261, 647, 465, 741, 529, 353, 471, 921, 837, 865, 577, 385, 257, 343, 229, 153, 407, 543, 721, 481, 321, 855, 1141, 761, 1015, 677, 903, 1209, 1605, 2149, 1433, 1911, 2529, 3397, 2265

Offset: 0

Kevin Ryde, Dec 15 2024

nonn

Each step is x -> 3x-1 if x odd, or x -> x/2 if x even (A001281) and here only the tripling steps 3x-1 are counted.
The number of tripling steps is A378833(x) so that a(n) = x is the smallest x for which A378833(x) = n.
All terms are odd since any even x takes a first step to x/2 which is a smaller start for the same number of tripling steps.
a(n) >= L(n) = (2*a(n-1) + 1)/3 is a lower bound since a(n) = x must at least have a first step 3x-1 and halve to (3x-1)/2, then n-1 further tripling steps, so (3x-1)/2 >= a(n-1).
Equality a(n) = L(n) occurs iff L(n) is an integer and not a cycle minimum.
A large upper bound for n>=1, showing a(n) always exists, is a(n) <= U(n) = (4^(3^n) - 1)*2^n/3^n + 1, since U(n) is a candidate for a(n) by taking n steps of (3x-1)/2 to reach 4^(3^n) which is a power of 2.
Tighter upper bounds on a(n) can be found by taking predecessor steps back from a(n-c) seeking c tripling steps to reach a(n-c) if that's possible (which for instance it's not if a(n-c) == 0 (mod 3)).
Such predecessors are candidates for a(n), but the actual a(n) might have a trajectory which does not go through any previous a(n-c).

			For n=4, a(4) = 9 has 4 tripling steps on its way to 5 which is the minimum of a cycle:
  9 -> 26 -> 13 -> 38 -> 19 -> 56 -> 28 -> 14 -> 7 -> 20 -> 10 -> 5
    ^            ^           ^                      ^
This a(4) = 9 is an example where a(n) is at its lower bound L(n), in this case a(3) = 13 has L(4) = (2*a(3)+1)/3 = 9 which is an integer and not a cycle minimum.

Kevin Ryde, Table of n, a(n) for n = 0..625
Kevin Ryde, C Code (set count type TRIPLE)

Cf. A001281 (step), A378833 (number of triplings).

Cf. A378845 (with all steps), A378846 (with halving steps).

C
```
/* See links. */
```

A194428 Number of iterations of the map n->n/3 if n == 0 (mod 3), n->4n+a if 4n+a == 0 (mod 3) where a = 1 or 2, before reaching the end of the cycle.

Original entry on oeis.org

5, 5, 5, 7, 17, 5, 16, 22, 5, 16, 20, 8, 8, 16, 18, 20, 22, 6, 16, 8, 16, 18, 20, 23, 34, 16, 6, 27, 11, 16, 18, 22, 21, 32, 16, 9, 23, 25, 9, 9, 28, 16, 20, 39, 19, 30, 16, 21, 21, 21, 23, 23, 35, 7, 26, 37, 16, 18, 37, 9, 28, 28, 16, 43, 14, 19, 19, 34, 21, 21, 33, 24

Offset: 1

Michel Lagneau, Aug 23 2011

nonn

The problem is as follows: start with any number n. If n is divisible by 3, divide it by 3, otherwise multiply it by 4 and add 1 or 2 in order to find a new integer divisible by 3. Do we always reach the end of a cycle? It is conjectured that the answer is yes.
On the set of positive integers, the orbit of any number seems to end in the orbit of 1, or of another integer.
This problem has a resemblance with the Collatz problem.

			a(1) = 5 because 1 -> 6 -> 2 -> 9 -> 3 -> 1 with 5 iterations ;
a(2) = 5 because 2 -> 9 -> 3 -> 1-> 6 -> 2  with 5 iterations ;
a(3) = 5 because 3 -> 1 -> 6 -> 2 -> 9 -> 3  with 5 iterations ;
a(4) = 7 because 4 -> 18 -> 6 -> 2 -> 9 -> 3 -> 1 -> 6 with 7 iterations.

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

Cf. A001281.

T:=array(1..2000):for n from 1 to 100 do: T[1]:=n:n0:=n:k:=2:for it from 1 to 50 do: z:=irem(n0,3):if z=0 then n0:=n0/3:T[k]:=n0:k:=k+1:else n0:=4*n0 + 1:if irem(n0,3)=0 then T[k]:=n0:k:=k+1:else n0:=n0+1:T[k]:=n0:k:=k+1:fi:fi:od:U:=convert(T,set):n1:=nops(U): printf(`%d, `, n1):od:

A378833 Number of tripling steps in the 3x-1 trajectory from n to the minimum of its cycle, or -1 if n never reaches a cycle.

Original entry on oeis.org

0, 0, 1, 0, 0, 1, 1, 0, 4, 0, 1, 1, 3, 1, 2, 0, 0, 4, 2, 0, 3, 1, 1, 1, 6, 3, 1, 1, 2, 2, 2, 0, 7, 0, 4, 4, 5, 2, 3, 0, 3, 3, 1, 1, 8, 1, 5, 1, 6, 6, 3, 3, 4, 1, 4, 1, 9, 2, 2, 2, 2, 2, 6, 0, 12, 7, 7, 0, 5, 4, 5, 4, 5, 5, 2, 2, 3, 3, 3, 0, 7, 3, 3, 3, 8, 1, 13

Offset: 1

Kevin Ryde, Dec 08 2024

The 3x-1 iteration is x -> 3x-1 if x odd, or x -> x/2 if x even (A001281).
The cycle minima presently known are 1, 5 and 17.
a(n) = 0 iff n = m*2^k where m is one of the cycle minima.

Kevin Ryde, Table of n, a(n) for n = 1..10000

Cf. A001281 (step), A135730 (total steps), A377524 (halving steps).

a(n) = A135730(n) - A377524(n), if a(n) != -1.

A056957 In repeated iterations of function m->m/2 if m even, m->3m-1 if m odd, a(n) is minimum value achieved if starting from n.

Original entry on oeis.org

1, 1, 1, 1, 5, 1, 5, 1, 5, 5, 1, 1, 5, 5, 1, 1, 17, 5, 5, 5, 17, 1, 17, 1, 17, 5, 5, 5, 1, 1, 17, 1, 17, 17, 5, 5, 17, 5, 1, 5, 17, 17, 1, 1, 17, 17, 5, 1, 17, 17, 5, 5, 1, 5, 17, 5, 1, 1, 1, 1, 17, 17, 5, 1, 1, 17, 17, 17, 1, 5, 1, 5, 17, 17, 5, 5, 1, 1, 1, 5, 5, 17, 17, 17, 1, 1, 1, 1, 5, 17

Offset: 1

Henry Bottomley, Jul 18 2000

nonn

At least for n<10000, the only possible cycles reached include 1,2,1,..., 5,14,7,20,10,5,... and 17,50,25,74,37,110,55,164,82,41,122,61,182,91,272,136,68,34,17,... For n<5 only the first occurs, while for n<17 only the first two occur.

			a(9)=5 since iteration starts: 9, 26, 13, 38, 19, 56, 28, 14, 7, 20, 10, 5, 14, 7, 20, 10, 5, ... and 5 is the smallest value

Cf. A001281. If n is in A039500 then a(n)=1, if n is in A039501 then a(n)=5, if n is in A039502 then a(n)=17. If n is negative then this becomes the 3x+1 problem and the minimum values become those which are most negative (i.e. maximum absolute values) as in A056959.

a(2n) = a(n)

Edited by Bryce Herdt (mathidentity(AT)yahoo.com), Apr 18 2010

A130769 Injection of the sequence of positive integers used in recursive calls (including initial call) in the execution of the Collatz (3n+1) function into the positive integers using the standard power-of-primes encoding (`Goedel-coding').

Original entry on oeis.org

2, 12, 1649253940128607650037732224082865475000, 720, 2032221170141662500000, 7372155480163603867228249918067794802791875000000

Offset: 1

Grant Olney Passmore (grant(AT)math.utexas.edu), Jul 13 2007

nonn

			G(3) = 1649253940128607650037732224082865475000
because given F as described above,
F(3) = (3, 10, 5, 16, 8, 4, 2, 1)
and thus
G(3) = 2^3 * 3^10 * 5^5 * 7^16 * 11^8 * 13^4 * 17^2 * 19
= 1649253940128607650037732224082865475000.

J. Shallit and D. Wilson, The "3x+1" Problem and Finite Automata, Bulletin of the EATCS #46 (1992) pp. 182-185.
R. K. Guy, Unsolved Problems in Number Theory, E16.

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

Cf. A001281, A001281.

;; (main function to call is f-code with n and a list of primes): ; Generate F sequence for the Collatz (3n+1) function (defun F (n) (cond ((= n 1)) (list n)) ((evenp n) (cons n (F (/ n 2)))) (t (cons n (F (1+ (* 3 n))))))) ; The Goedel-coding function. Takes a list of integers and a list of primes and performs the standard powers-of-primes encoding. (defun goedel-code (l p) (cond ((endp l) 1) (t (* (expt (car p) (car l)) (goedel-code (cdr l) (cdr p)))))) ; Encode intermediate values of Collatz function, using a given list of primes (defun G (n) (goedel-code (F n) *list-of-primes*))

Let f(n) be the Collatz (3n+1) function. Let F(n) be the sequence of positive integers m s.t. f(m) is called during the execution of f(n). (So F(1) = (1); F(2) = (2, 1); F(3) = (3, 10, 5, 15, 8, 4, 2, 1); and so on.) Assume that F(n) has k terms. Then, each instance of the sequence, G(n), is generated by encoding the sequence F(n) as a positive integer as follows: G(n) = 2^F(n)0 * 3^F(n)_1 * 5^F(n)_2 * ... * p(k-1)^F(n){k-1} where F(n)_i is the i-th member of the sequence F(n) and p(i) is the i-th prime.

A377945 Numbers k such that the trajectory of k under the `3x-1' map reaches k+1.

Original entry on oeis.org

1, 3, 9, 13, 15, 18, 19, 33, 49, 67, 73, 90, 109, 163, 391, 522, 607, 729, 810, 1093, 1639

Offset: 1

Kevin Ge, Nov 11 2024

The 3x-1 map is x -> 3x-1 if x odd, and x -> x/2 if x even (A001281).

There are no more terms < 10^9.

			13 is a term because its trajectory 13 -> 38 -> 19 -> 56 -> 28 -> 14 -> ... reaches 13 + 1 = 14.

Cf. A001281.

def isok(n):
    temp, loops = n, 0
    while(temp != n + 1 and loops<2):
        temp = temp // 2 if temp % 2 == 0 else 3 * temp - 1
        if(temp == 1 or temp == 5 or temp == 17):
            loops += 1
    return temp == n + 1
print([n for n in range(1, 2000) if isok(n)])

cp's OEIS Frontend

A378845 Smallest starting x which takes n steps to reach the minimum of a cycle in the 3x-1 iteration.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

C

A378846 Smallest starting x which takes n halving steps to reach the minimum of a cycle in the 3x-1 iteration.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

C

A378847 Smallest starting x which takes n tripling steps to reach the minimum of a cycle in the 3x-1 iteration.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

A194428 Number of iterations of the map n->n/3 if n == 0 (mod 3), n->4*n+a if 4*n+a == 0 (mod 3) where a = 1 or 2, before reaching the end of the cycle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A378833 Number of tripling steps in the 3x-1 trajectory from n to the minimum of its cycle, or -1 if n never reaches a cycle.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A056957 In repeated iterations of function m->m/2 if m even, m->3m-1 if m odd, a(n) is minimum value achieved if starting from n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A130769 Injection of the sequence of positive integers used in recursive calls (including initial call) in the execution of the Collatz (3n+1) function into the positive integers using the standard power-of-primes encoding (`Goedel-coding').

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Lisp

Formula

A377945 Numbers k such that the trajectory of k under the `3x-1' map reaches k+1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

A194428 Number of iterations of the map n->n/3 if n == 0 (mod 3), n->4n+a if 4n+a == 0 (mod 3) where a = 1 or 2, before reaching the end of the cycle.