cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A127885 a(n) = minimal number of steps to get from n to 1, where a step is x -> 3x+1 if x is odd, or x -> either x/2 or 3x+1 if x is even; or -1 if 1 is never reached.

Original entry on oeis.org

0, 1, 7, 2, 5, 8, 16, 3, 11, 6, 14, 9, 9, 17, 17, 4, 12, 12, 20, 7, 7, 15, 15, 10, 23, 10, 23, 10, 18, 18, 31, 5, 18, 13, 13, 13, 13, 21, 26, 8, 21, 8, 21, 16, 16, 16, 29, 11, 16, 16, 24, 11, 11, 24, 24, 11, 24, 19, 24, 19, 19, 32, 32, 6, 19, 19, 27, 14, 14, 14, 27, 14, 27, 14, 14, 22, 22, 27, 27, 9, 22, 22, 22, 9, 9, 22, 22, 17, 22, 17, 30, 17, 17, 30, 30, 12, 30, 17, 17, 17
Offset: 1

Views

Author

David Applegate and N. J. A. Sloane, Feb 04 2007

Keywords

Comments

In contrast to the "3x+1" problem (see A006577), here you are free to choose either step if x is even.
See A125731 for the number of steps in the reverse direction, from 1 to n.

Examples

			Several early values use the path:
6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.
The first path where choosing 3x+1 for even x helps is:
9 -> 28 -> 85 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1.

References

  • M. J. Halm, Sequences (Re)discovered, Mpossibilities 81 (Aug. 2002), p. 1.

Links

Crossrefs

A127886 gives the difference between A006577 and this sequence.
Cf. A006577, A125731, A127887, A125195, A125686, A125719, A261870.
Cf. A290100 (size of the final set when using Alekseyev's algorithm).
Cf. also A257265.

Programs

  • Maple
    # Code from David Applegate: Be careful - the function takes an iteration limit and returns the limit if it wasn't able to determine the answer (that is, if A127885(n,lim) == lim, all you know is that the value is >= lim). To use it, do manual iteration on the limit.
A127885 := proc(n,lim) local d,d2; options remember;
if (n = 1) then return 0; end if;
if (lim <= 0) then return 0; end if;
if (n > 2 ^ lim) then return lim; end if;
if (n mod 2 = 0) then
d := A127885(n/2,lim-1);
d2 := A127885(3*n+1,d);
if (d2 < d) then d := d2; end if;
else
d := A127885(3*n+1,lim-1);
end if;
return 1+d;
end proc;
  • Mathematica
    Table[-1 + Length@ NestWhileList[Flatten[# /. {k_ /; OddQ@ k :> 3 k + 1, k_ /; EvenQ@ k :> {k/2, 3 k + 1}}] &, {n}, FreeQ[#, 1] &], {n, 126}] (* Michael De Vlieger, Aug 20 2017 *)
  • PARI
    { A127885(n) = my(S,k); S=[n]; k=0; while( S[1]!=1, k++; S=vecsort( concat(apply(x->3*x+1,S), apply(x->x\2, select(x->x%2==0,S) )),,8);  ); k } /* Max Alekseyev, Sep 03 2015 */

Formula

a(1) = 0; and for n > 1, if n is odd, a(n) = 1 + a(3n+1), and if n is even, a(n) = 1 + min(a(3n+1),a(n/2)). [But with a similar caveat as in A257265] - Antti Karttunen, Aug 20 2017

Extensions

Escape clause added to definition by N. J. A. Sloane, Aug 20 2017

A290101 a(n) = dropping time for the modified Collatz problem, where x -> 3x+1 if x is odd, and x -> either x/2 or 3x+1 if x is even (minimal number of any such steps to reach a lower number than the starting value n); a(1) = 0 by convention.

Original entry on oeis.org

0, 1, 6, 1, 3, 1, 11, 1, 3, 1, 8, 1, 3, 1, 11, 1, 3, 1, 6, 1, 3, 1, 8, 1, 3, 1, 16, 1, 3, 1, 19, 1, 3, 1, 6, 1, 3, 1, 11, 1, 3, 1, 8, 1, 3, 1, 16, 1, 3, 1, 6, 1, 3, 1, 8, 1, 3, 1, 11, 1, 3, 1, 19, 1, 3, 1, 6, 1, 3, 1, 13, 1, 3, 1, 8, 1, 3, 1, 13, 1, 3, 1, 6, 1, 3, 1, 8, 1, 3, 1, 11, 1, 3, 1, 13, 1, 3, 1, 6, 1, 3, 1, 16, 1, 3, 1, 8, 1, 3
Offset: 1

Views

Author

Antti Karttunen, Aug 20 2017

Keywords

Comments

In contrast to the "3x+1" problem (see A006577, A102419), here you are free to choose either step if x is even. The sequence counts the minimum number of optimally chosen steps which leads to a value smaller than the value we started from.

Examples

			Starting from n = 27, the following is a shortest path leading to a value smaller than 27: 27 -> 82 -> 41 -> 124 -> 373 -> 1120 -> 560 -> 280 -> 140 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20. It has 16 steps, thus a(27) = 16. Note the 3x+1 step from 124 to 373 which is not allowed in the ordinary Collatz problem.

Links

Crossrefs

Cf. A127885, A290100, A290102, A000012 (even bisection).
Differs from A102419 for the first time at n=27, where a(27) = 16, while A102419(27) = 96.

Programs

  • PARI
    A290101(n) = { if(1==n,return(0)); my(S, k); S=[n]; k=0; while( S[1]>=n, k++; S=vecsort( concat(apply(x->3*x+1, S), apply(x->x\2, select(x->x%2==0, S) )), , 8);  ); k } \\ After Max Alekseyev's code for A127885
  • Python
    from sympy import flatten
def ok(n, L):
    return any(i < n for i in L)
def a(n):
    if n==1: return 0
    L=[n]
    i = 0
    while not ok(n, L):
        L=set(flatten([[3*k + 1, k//2] if k%2==0 else 3*k + 1 for k in L]))
        i+=1
    return i
print([a(n) for n in range(1, 121)]) # Indranil Ghosh, Aug 31 2017

Formula

a(n) <= A102419(n).
a(n) <= A127885(n) [apart from any hypothetical -1's in A127885].

A290102 Start from the singleton set S = {n}, and generate on each iteration a new set where each odd number k is replaced by 3k+1, and each even number k is replaced by 3k+1 and k/2. a(n) is the size of the set after the first iteration which has produced a number smaller than n. a(1) = 1 by convention.

Original entry on oeis.org

1, 2, 9, 2, 3, 2, 52, 2, 3, 2, 18, 2, 3, 2, 49, 2, 3, 2, 9, 2, 3, 2, 18, 2, 3, 2, 395, 2, 3, 2, 1108, 2, 3, 2, 9, 2, 3, 2, 52, 2, 3, 2, 18, 2, 3, 2, 360, 2, 3, 2, 9, 2, 3, 2, 18, 2, 3, 2, 57, 2, 3, 2, 1116, 2, 3, 2, 9, 2, 3, 2, 115, 2, 3, 2, 18, 2, 3, 2, 109, 2, 3, 2, 9, 2, 3, 2, 18, 2, 3, 2, 56, 2, 3, 2, 105, 2, 3, 2, 9, 2, 3, 2, 368, 2, 3, 2, 18
Offset: 1

Views

Author

Antti Karttunen, Aug 20 2017

Keywords

Examples

			For n=3, the initial set is {3}, the next set is 3*3+1 = {10}, from which we get (by applying both x/2 and 3x+1 to 10): {5, 31}, and then on we get -> {16, 94} -> {8, 47, 49, 283} -> {4, 25, 142, 148, 850} -> {2, 13, 71, 74, 76, 425, 427, 445, 2551}, which set already has a member less than 3, and has 9 members in total, thus a(3) = 9.

Links

Crossrefs

Cf. A127885, A290100, A007395 (even bisection).
Cf. A290101 (number of iterations needed until a set with smaller member than n is produced).

Programs

  • Mathematica
    Table[-2 Boole[n == 1] + Length@ Last@ NestWhileList[Union@ Flatten[# /. {k_ /; OddQ@ k :> 3 k + 1, k_ /; EvenQ@ k :> {k/2, 3 k + 1}}] &, {n}, AllTrue[#, # > n &] &, {2, 1}], {n, 107}] (* Michael De Vlieger, Aug 20 2017 *)
  • PARI
    A290102(n) = { if(1==n,return(1)); my(S, k); S=[n]; k=0; while( S[1]>=n, k++; S=vecsort( concat(apply(x->3*x+1, S), apply(x->x\2, select(x->x%2==0, S) )), , 8);  ); length(S); } \\ After Max Alekseyev's code for A127885, see also A290101.
  • Python
    from sympy import flatten
def ok(n, L):
    return any(i < n for i in L)
def a(n):
    if n==1: return 1
    L=[n]
    while not ok(n, L):
        L=set(flatten([[3*k + 1, k//2] if k%2==0 else 3*k + 1 for k in L]))
    return len(L)
print([a(n) for n in range(1, 121)]) # Indranil Ghosh, Aug 22 2017

Formula

a(n) <= A290100(n).

A291213 Start from the singleton set S = {n}, and unless 1 is already a member of S, generate on each iteration a new set where each odd number k is replaced by 3k+1, and each even number k is replaced by 3k+1 and k/2. a(n) is the total size of the set from the singleton through after the first iteration which has produced 1 as a member, inclusive.

Original entry on oeis.org

1, 3, 36, 6, 20, 72, 1168, 11, 216, 35, 576, 143, 111, 2422, 1657, 19, 336, 378, 6253, 66, 51, 1167, 820, 241, 24096, 180, 18805, 215, 3833, 3488, 368905, 31, 3460, 575, 426, 716, 576, 12387, 57556, 110, 10513, 83, 8948, 2303, 1782, 1656, 175195, 387, 1647
Offset: 1

Views

Author

Michael De Vlieger, Aug 26 2017

Keywords

Comments

See comments at A290100.
A290100(n) is the size of the set at the last iteration, while this sequence is the sum of sizes of all generations including the last iteration.
A290100(n)/A291213(n) < 29/90 for n = {6, 67, 81, 92, 102, 153, 155, 165, 198, 201, 202, 204, 205, 217, 228, 235, 264, 265, 289, 299, 308, 309, 349, 353, 360, 396, 408, 434, ...}, with n = 6 the greatest observed difference. - Michael De Vlieger, Aug 30 2017

Examples

			For n = 5:
Generation   Set
1 (1 term)   5
2 (1 term)   16
3 (2 terms)  8, 49
4 (3 terms)  4, 25, 148
5 (5 terms)  2, 13, 74, 76, 445
6 (8 terms)  1, 7, 37, 38, 40, 223, 229, 1336
thus a(5) = 20 and A290100(5) = 8.

Links

Crossrefs

Cf. A006577, A127885, A127886, A290100.

Programs

  • Mathematica
    Table[Length@ Flatten@ NestWhileList[Union@ Flatten[# /. {k_ /; OddQ@ k :> 3 k + 1, k_ /; EvenQ@ k :> {k/2, 3 k + 1}}] &, {n}, FreeQ[#, 1] &], {n, 49}]
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.