|
%I #173 Jan 25 2024 07:08:30
%S 1,1,2,3,7,12,30,85,173,476,961,2652,8045,17637,51033,108950,312455,
%T 663535,1900470,5936673,13472296,39993895,87986917,257978502,
%U 820236724,1899474678,5723030586,12809477536,38036848410,84141805077,248369601964
%N Number of admissible sequences of order j; related to 3x+1 problem and Wagon's constant.
%C 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)).
%C The length of all admissible sequences of order j is A020914(j). - _T. D. Noe_, Sep 11 2006
%C 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
%C 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
%C 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
%C A177789 shows another theorem and algorithm for generating a(n). - _Mike Winkler_, Sep 12 2017
%H T. D. Noe, <a href="/A100982/b100982.txt">Table of n, a(n) for n = 1..500</a>
%H M. Chamberland, <a href="https://web.archive.org/web/20181009015707/http://www.math.grin.edu/~chamberl/papers/3x_survey_cat.pdf">Una actualizacio del problema 3x+1</a>, Butl. Soc. Catalana Mat. 18 (2003) 19-45.
%H M. Chamberland, <a href="https://web.archive.org/web/20190401203406/http://www.math.grin.edu/~chamberl/3x.html">English translation</a>
%H Ruud H.G. van Tol, <a href="/A100982/a100982.svg">Sequence as counts of lattice walks</a>
%H S. Wagon, <a href="http://dx.doi.org/10.1007/BF03023011">The Collatz problem</a>, Math. Intelligencer 7 (1985) 72-76.
%H M. Winkler, <a href="https://www.researchgate.net/publication/265006788_ON_A_STOPPING_TIME_ALGORITHM_OF_THE_3n_1_FUNCTION">On a stopping time algorithm of the 3n + 1 function</a>, 2011.
%H M. Winkler, <a href="http://arxiv.org/abs/1412.0519">On the structure and the behaviour of Collatz 3n + 1 sequences - Finite subsequences and the role of the Fibonacci sequence</a>, arXiv:1412.0519 [math.GM], 2014.
%H M. Winkler, <a href="http://arxiv.org/abs/1504.00212">New results on the stopping time behaviour of the Collatz 3x + 1 function</a>, arXiv:1504.00212 [math.GM], 2015.
%H M. Winkler, <a href="http://arxiv.org/abs/1709.03385">The algorithmic structure of the finite stopping time behavior of the 3x + 1 function</a>, arXiv:1709.03385 [math.GM], 2017.
%F 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.
%F 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)
%F a(n) = Sum_{k=n-1..A056576(n-1)} (k,n). (Theorem 2, cf. example)
%F a(k) = 2*A076227(A020914(k)-1) - A076227(A020914(k)), for k > 0. - _Vladimir M. Zarubin_, Sep 29 2019
%F a(1)=1, a(n) = Sum_{k=0..A020914(n-1)-n-2} A325904(k)*binomial(A020914(n-1)-k-2, n-2) for n>1. - _Benjamin Lombardo_, Oct 18 2019
%e The unique admissible sequence of order 1 is 3/2, 1/2.
%e The unique admissible sequence of order 2 is 3/2, 3/2, 1/2, 1/2.
%e 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.
%e a(13) = 8045 = binomial(floor(5*(13-2)/3), 13-2)
%e - Sum_{i=2..6} binomial(floor((3*(13-i)+0)/2), 13-i)*a(i)
%e - Sum_{i=7..11} binomial(floor((3*(13-i)-1)/2), 13-i)*a(i)
%e - Sum_{i=12..12} binomial(floor((3*(13-i)-2)/2), 13-i)*a(i)
%e = 31824 - 4368*1 - 3003*2 - 715*3 - 495*7 - 120*12 - 28*30 - 21*85 - 5*173 - 4*476 - 1*961 - 0*2652. (Conjecture)
%e From _Mike Winkler_, Sep 12 2017: (Start)
%e The next table shows how Theorem 2 works. No entry is equal to zero.
%e n = 3 4 5 6 7 8 9 10 11 12 .. |A076227(k)=
%e --------------------------------------------------|
%e k = 2 | 1 | 1
%e k = 3 | 1 1 | 2
%e k = 4 | 2 1 | 3
%e k = 5 | 3 1 | 4
%e k = 6 | 3 4 1 | 8
%e k = 7 | 7 5 1 | 13
%e k = 8 | 12 6 1 | 19
%e k = 9 | 12 18 7 1 | 38
%e k = 10 | 30 25 8 1 | 64
%e k = 11 | 30 55 33 9 1 | 128
%e : | : : : : .. | :
%e --------------------------------------------------|---------
%e a(n) = 2 3 7 12 30 85 173 476 961 2652 .. |
%e 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)
%e From _Ruud H.G. van Tol_, Dec 04 2023: (Start)
%e A tree view.
%e n-tree--A098294--ids-----paths-----------------a(n)
%e 0 ._ 0 0 0 -
%e 1 |_ 1 1 10 1
%e 2 |_._ 2 2 1100 1
%e 3 |_|_ 2 3-4 11010 - 11100 2
%e 4 |_|_._ 3 5-7 1101100 - 1111000 3
%e 5 |_|_|_ 3 8-14 11011010 - 11111000 7
%e 6 |_|_|_._ 4 15-26 1101101100-1111110000 12
%e 7 |_|_|_|_._ 5 27-56 ... 30
%e 8 |_|_|_|_|_ 5 57-141 ... 85
%e ...
%e For n>=1, the endpoints are at A098294(n) to the right.
%e (End)
%t (* based on Eric Roosendaal's algorithm *) nn=100; Clear[x,y]; Do[x[i]=0, {i,0,nn+1}]; x[1]=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)*Log[3]<p*Log[2], admis=admis+x[cnt]; x[cnt]=0], {cnt,p+1}]; admis, {p,2,nn}]; DeleteCases[t,0] (* _T. D. Noe_, Sep 11 2006 *)
%o (PARI) /* translation of the above code from _T. D. Noe_ */
%o {limit=100; n=1; x=y=vector(limit+1); x[1]=1; for(b=2, limit, for(c=2, b+1, y[c]=x[c]+x[c-1]); for(c=2, b+1, x[c]=y[c]); a_n=0; for(c=1, b+1, if((b+1-c)*log(3)<b*log(2), a_n=a_n+x[c]; x[c]=0)); if(a_n!=0, print(n" "a_n); n++))} \\ _Mike Winkler_, Feb 28 2015
%o (PARI) /* algorithm for the Conjecture */
%o {limit=53; zn=vector(limit); zn[2]=1; zn[3]=2; zn[4]=3; zn[5]=7; zn[6]=12; f=1; e1=-1; e2=-2; for(n=7, limit, m=floor((n-1)*log(3)/log(2))-(n-1); j=(m+n-2)!/(m!*(n-2)!); if(n>6*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
%o (PARI) /* cf. code for Theorem 2 */
%o {limit=100; /*or limit>100*/ p=q=vector(limit); c=2; w=log(3)/log(2); for(n=3, limit, p[1]=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
%o (PARI) /* algorithm for Theorem 1 */
%o n=20; a=vector(n); log32=log(3)/log(2);
%o {a[1]=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]) );
%o } \\ _Vladimir M. Zarubin_, Sep 25 2015
%o (PARI) /* algorithm for Theorem 2 */
%o {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
%Y Cf. A122790 (Wagon's constant), A076227, A056576, A022921, A098294, A177789.
%K nonn,walk
%O 1,3
%A _Steven Finch_, Jan 13 2005
%E Two more terms from Jules Renucci (jules.renucci(AT)wanadoo.fr), Nov 02 2005
%E More terms from _T. D. Noe_, Sep 11 2006
| 