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.

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

Author

Antti Karttunen, Aug 20 2017

Keywords

• nonn

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

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

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