A290102 -id:A290102 - cp's OEIS frontend

A290100 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 size of the set after the first iteration which has produced 1 as a member.

1, 2, 12, 3, 8, 23, 381, 5, 73, 12, 187, 47, 39, 786, 537, 8, 109, 124, 2020, 23, 19, 381, 267, 81, 7768, 60, 6061, 73, 1238, 1128, 118945, 12, 1120, 187, 141, 234, 190, 3999, 18578, 39, 3394, 28, 2896, 747, 576, 537, 56496, 128, 533, 606, 9757, 109, 95, 12337, 8656, 118, 11306, 2020, 9309, 2309, 1789, 258213, 176262, 19

Offset: 1

Antti Karttunen, Aug 18 2017

nonn

Records are {1, 2, 12, 23, 381, 786, 2020, 7768, 118945, 258213, 2124457, 40495936, 59752379, 65297014, 231177519} at positions {1, 2, 3, 6, 7, 14, 19, 25, 31, 62, 107, 127, 255, 295, 339}. - Michael De Vlieger, Aug 24 2017

			For n=1, the initial set from which we start is {1}, and it already contains 1, so a(1) = 1 as the size of that set is 1.
For n=2, the initial set is {2}, which will become set {1, 7} (because 2/2 = 1 and 3*2+1 = 7), and that set already contains 1, thus a(2) = 2.
For n=3, the initial set is {3}, the next set is 3*3+1 = {10}, from which we get {5, 31} -> {16, 94} -> {8, 47, 49, 283} -> {4, 25, 142, 148, 850} -> {2, 13, 71, 74, 76, 425, 427, 445, 2551} and from that one we get these 12 numbers: {1, 7, 37, 38, 40, 214, 223, 229, 1276, 1282, 1336, 7654}, and because 1 is among these, a(3) = 12.
For n = 12, the iteration proceeds as follows: {12} -> {6, 37} -> {3, 19, 112} -> {10, 56, 58, 337} -> {5, 28, 29, 31, 169, 175, 1012} -> {14, 16, 85, 88, 94, 506, 508, 526, 3037} -> {7, 8, 43, 44, 47, 49, 253, 254, 256, 263, 265, 283, 1519, 1525, 1579, 9112} -> {4, 22, 25, 127, 128, 130, 133, 142, 148, 760, 763, 769, 790, 796, 850, 4556, 4558, 4576, 4738, 27337} -> {2, 11, 13, 64, 65, 67, 71, 74, 76, 380, 382, 385, 391, 395, 398, 400, 425, 427, 445, 2278, 2279, 2281, 2288, 2290, 2308, 2369, 2371, 2389, 2551, 13669, 13675, 13729, 14215, 82012} -> {1, 7, 32, 34, 37, 38, 40, 190, 191, 193, 196, 199, 200, 202, 214, 223, 229, 1139, 1141, 1144, 1145, 1147, 1154, 1156, 1174, 1186, 1195, 1201, 1276, 1282, 1336, 6835, 6838, 6844, 6865, 6871, 6925, 7108, 7114, 7168, 7654, 41006, 41008, 41026, 41188, 42646, 246037}. As this last set contains 1 and has 47 members, a(12) = 47. Note how here in the 7th iteration the term 22 is a child of both 7 (as 3*7+1) and 44 (as 44/2), but as these are sets, not multisets, 22 occurs only once in {4, 22, 25, ...}.

Michael De Vlieger, Table of n, a(n) for n = 1..450 (first 126 terms from Antti Karttunen)
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A127885 (gives the number of iterations needed until 1 is present).

Cf. also A290101, A290102.

Table[Length@ Last@ NestWhileList[Union@ Flatten[# /. {k_ /; OddQ@ k :> 3 k + 1, k_ /; EvenQ@ k :> {k/2, 3 k + 1}}] &, {n}, FreeQ[#, 1] &], {n, 64}] (* Michael De Vlieger, Aug 20 2017 *)

allocatemem(2^31);
A290100(n) = { my(S); S=[n]; while( S[1]!=1, 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
for(n=1,126,write("b290100.txt", n, " ", A290100(n)));

from sympy import flatten
def a(n):
    if n==1: return 1
    L=[n]
    while not 1 in L:
        L=sorted(list(set(flatten([[3*k + 1, k/2] if k%2==0 else 3*k + 1 for k in L]))))
    return len(L)
for i in range(1, 101): print(a(i)) # Indranil Ghosh, Aug 31 2017

a(n) >= A290102(n).

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

Antti Karttunen, Aug 20 2017

nonn

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.

			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.

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

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.

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

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

a(n) <= A102419(n).

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

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula