cp's OEIS Frontend

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.

%I A290102 #22 Apr 23 2021 01:30:52
%S A290102 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,
%T A290102 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,
%U A290102 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
%N 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.
%H A290102 Antti Karttunen, <a href="/A290102/b290102.txt">Table of n, a(n) for n = 1..10000</a>
%H A290102 <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%F A290102 a(n) <= A290100(n).
%e A290102 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.
%t A290102 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 *)
%o A290102 (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.
%o A290102 (Python)
%o A290102 from sympy import flatten
%o A290102 def ok(n, L):
%o A290102     return any(i < n for i in L)
%o A290102 def a(n):
%o A290102     if n==1: return 1
%o A290102     L=[n]
%o A290102     while not ok(n, L):
%o A290102         L=set(flatten([[3*k + 1, k//2] if k%2==0 else 3*k + 1 for k in L]))
%o A290102     return len(L)
%o A290102 print([a(n) for n in range(1, 121)]) # _Indranil Ghosh_, Aug 22 2017
%Y A290102 Cf. A127885, A290100, A007395 (even bisection).
%Y A290102 Cf. A290101 (number of iterations needed until a set with smaller member than n is produced).
%K A290102 nonn
%O A290102 1,2
%A A290102 _Antti Karttunen_, Aug 20 2017