This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A100982 Number of admissible sequences of order j; related to 3x+1 problem and Wagon's constant. 12
 1, 1, 2, 3, 7, 12, 30, 85, 173, 476, 961, 2652, 8045, 17637, 51033, 108950, 312455, 663535, 1900470, 5936673, 13472296, 39993895, 87986917, 257978502, 820236724, 1899474678, 5723030586, 12809477536, 38036848410, 84141805077, 248369601964 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS Eric Roosendaal counted all admissible sequences up to order j=1000 (2005). Note: there is a typo in both Wagon and Chamberland in the definition of Wagon's constant 9.477955... The expression floor(1 + 2*i + i*log_2(3)) should be replaced by floor(1 + i + i*log_2(3)). The length of all admissible sequences of order j is A020914(j). - T. D. Noe, Sep 11 2006 Conjecture: a(n) is given for each n > 3 by a formula using a(2)..a(n-1). This allows us to create an iterative algorithm which generates a(n) for each n > 6. This has been proved for each n <= 53. For higher values of n the algorithm must be slightly modified. - Mike Winkler, Jan 03 2018 Theorem 1: a(k) is given for each k > 1 by a formula using a(1)..a(k-1). Namely, a(1)=1 and a(k+1) = Sum_{m=1..k} (-1)^(m-1)*binomial(floor((k-m+1)*(log(3)/log(2))) + m - 1, m)*a(k-m+1)) for k >= 1. - Vladimir M. Zarubin, Sep 25 2015 Theorem 2: a(n) can be generated for each n > 2 algorithmically in a Pascal's triangle-like manner from the two starting values 0 and 1. This result is based on the fact that the Collatz residues (mod 2^k) can be evolved according to a binary tree. There is a direct connection with A076227, A056576 and A022921. - Mike Winkler, Sep 12 2017 A177789 shows another theorem and algorithm for generating a(n). - Mike Winkler, Sep 12 2017 LINKS T. D. Noe, Table of n, a(n) for n = 1..500 M. Chamberland, Una actualizacio del problema 3x+1, Butl. Soc. Catalana Mat. 18 (2003) 19-45. M. Chamberland, English translation S. Wagon, The Collatz problem, Math. Intelligencer 7 (1985) 72-76. M. Winkler, On a stopping time algorithm of the 3n + 1 function, 2011. M. Winkler, On the structure and the behaviour of Collatz 3n + 1 sequences - Finite subsequences and the role of the Fibonacci sequence, arXiv:1412.0519 [math.GM], 2014. M. Winkler, New results on the stopping time behaviour of the Collatz 3x + 1 function, arXiv:1504.00212 [math.GM], 2015. M. Winkler, The algorithmic structure of the finite stopping time behavior of the 3x + 1 function, arXiv:1709.03385 [math.GM], 2017. FORMULA A sequence s(k), where k=1, 2, ..., n, is *admissible* if it satisfies s(k)=3/2 exactly j times, s(k)=1/2 exactly n-j times, s(1)*s(2)*...*s(n) < 1 but s(1)*s(2)*...*s(m) > 1 for all 1 < m < n. a(n) = (m+n-2)!/(m!*(n-2)!) - Sum_{i=2..n-1} binomial(floor((3*(n-i)+b)/2), n-i)*a(i), where m = floor((n-1)*log_2(3))-(n-1) and b assumes different integer values within the sum at intervals of 5 or 6 terms. (Conjecture) a(n) = Sum_{k=n-1..A056576(n-1)} (k,n). (Theorem 2, cf. example) EXAMPLE The unique admissible sequence of order 1 is 3/2, 1/2. The unique admissible sequence of order 2 is 3/2, 3/2, 1/2, 1/2. The two admissible sequences of order 3 are 3/2, 3/2, 3/2, 1/2, 1/2 and 3/2, 3/2, 1/2, 3/2, 1/2. a(13) = 8045 = binomial(floor(5*(13-2)/3), 13-2) - Sum_{i=2..6} binomial(floor((3*(13-i)+0)/2), 13-i)*a(i) - Sum_{i=7..11} binomial(floor((3*(13-i)-1)/2), 13-i)*a(i) - Sum_{i=12..12} binomial(floor((3*(13-i)-2)/2), 13-i)*a(i) = 31824 - 4368*1 - 3003*2 - 715*3 - 495*7 - 120*12 - 28*30 - 21*85 - 5*173 - 4*476 - 1*961 - 0*2652. (Conjecture) From Mike Winkler, Sep 12 2017: (Start) The next table shows how Theorem 2 works. No entry is equal to zero. n =       3  4  5   6   7   8   9  10  11   12 .. |A076227(k)= --------------------------------------------------| k =  2 |  1                                       |     1 k =  3 |  1  1                                    |     2 k =  4 |     2  1                                 |     3 k =  5 |        3   1                             |     4 k =  6 |        3   4   1                         |     8 k =  7 |            7   5   1                     |    13 k =  8 |               12   6   1                 |    19 k =  9 |               12  18   7   1             |    38 k = 10 |                   30  25   8   1         |    64 k = 11 |                   30  55  33   9    1    |   128 :      |                        :   :   :    : .. |    : --------------------------------------------------|--------- a(n) =    2  3  7  12  30  85 173 476 961 2652 .. | The entries (k,n) in this table are generated by the rule (k+1,n) = (k,n) + (k,n-1). The last value of (k+1,n) is given by k+1 = A056576(n-1), or the highest value in column n is given twice only if A022921(n-2) = 2. Then a(n) is equal to the sum of the entries in column n. For n = 7 there is 1 = 0 + 1, 5 = 1 + 4, 12 = 5 + 7, 12 = 12 + 0. Therefore a(7) = 1 + 5 + 12 + 12 = 30. The sum of row k is equal to A076227(k). (End) MATHEMATICA (* based on Eric Roosendaal's algorithm *) nn=100; Clear[x, y]; Do[x[i]=0, {i, 0, nn+1}]; x=1; t=Table[Do[y[cnt]=x[cnt]+x[cnt-1], {cnt, p+1}]; Do[x[cnt]=y[cnt], {cnt, p+1}]; admis=0; Do[If[(p+1-cnt)*Log6*f, if(frac(n/2)==0, e=e1, e=e2)); if(frac((n-6 )/12)==0, f++; e1=e1+2); if(frac((n-12)/12)==0, f++; e2=e2+2); Sum=a=b=0; c=1; d=5; until(c>=n-1, for(i=2+a*5+b, 1+d+a*5, if(i>11 && frac((i+2)/6)==0, b++); delta=e-a; Sum=Sum+binomial(floor((3*(n-i)+delta)/2), n-i)*zn[i]; c++); a++; for(k=3, 50, if(n>=k*6 && a==k-1, d=k+3))); zn[n]=j-Sum; print(n" "zn[n]))} \\ Mike Winkler, Jan 03 2018 (PARI) /* cf. code for Theorem 2 */ {limit=100; /*or limit>100*/ p=q=vector(limit); c=2; w=log(3)/log(2); for(n=3, limit, p=Sum=1; for(i=2, c, p[i]=p[i-1]+q[i]; Sum=Sum+p[i]); a_n=Sum; print(n" "a_n); for(i=1, c, q[i]=p[i]); d=floor(n*w)-floor((n-1)*w); if(d==2, c++)); } \\ Mike Winkler, Apr 14 2015 (PARI) /* algorithm for Theorem 1 */ n=20; a=vector(n); log32=log(3)/log(2); {a=1; for ( k=1, n-1, a[k+1]=sum( m=1, k, (-1)^(m-1)*binomial( floor( (k-m+1)*log32)+m-1, m)*a[k-m+1] ); print(k" "a[k]) ); } \\ Vladimir M. Zarubin, Sep 25 2015 (PARI) /* algorithm for Theorem 2 */ {limit=30; /*or limit>30*/ R=matrix(limit, limit); R[2, 1]=0; R[2, 2]=1; for(n=2, limit, print; print1("For n="n" in column n: "); Kappa_n=floor(n*log(3)/log(2)); a_n=0; for(k=n, Kappa_n, R[k+1, n]=R[k, n]+R[k, n-1]; print1(R[k+1, n]", "); a_n=a_n+R[k+1, n]); print; print(" and the sum is a(n)="a_n))} \\ Mike Winkler, Sep 12 2017 CROSSREFS Cf. A122790 (Wagon's constant), A076227, A056576, A022921, A177789. Sequence in context: A047749 A134565 A300749 * A186009 A299295 A305752 Adjacent sequences:  A100979 A100980 A100981 * A100983 A100984 A100985 KEYWORD nonn AUTHOR Steven Finch, Jan 13 2005 EXTENSIONS Two more terms from Jules Renucci (jules.renucci(AT)wanadoo.fr), Nov 02 2005 More terms from T. D. Noe, Sep 11 2006 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 21 23:47 EDT 2019. Contains 323472 sequences. (Running on oeis4.)