# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a100982
Showing 1-1 of 1

%I A100982 #187 Aug 13 2024 22:54:59
%S A100982 1,1,2,3,7,12,30,85,173,476,961,2652,8045,17637,51033,108950,312455,
%T A100982 663535,1900470,5936673,13472296,39993895,87986917,257978502,
%U A100982 820236724,1899474678,5723030586,12809477536,38036848410,84141805077,248369601964
%N A100982 Number of admissible sequences of order j; related to 3x+1 problem and Wagon's constant.
%C A100982 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 A100982 The length of all admissible sequences of order j is A020914(j). - _T. D. Noe_, Sep 11 2006
%C A100982 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 A100982 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 A100982 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 A100982 A177789 shows another theorem and algorithm for generating a(n). - _Mike Winkler_, Sep 12 2017
%H A100982 T. D. Noe, <a href="/A100982/b100982.txt">Table of n, a(n) for n = 1..500</a>
%H A100982 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 A100982 M. Chamberland, <a href="https://web.archive.org/web/20190401203406/http://www.math.grin.edu/~chamberl/3x.html">English translation</a>
%H A100982 Ruud H.G. van Tol, <a href="/A100982/a100982.svg">Sequence as counts of lattice walks</a>
%H A100982 Ruud H.G. van Tol, <a href="/A100982/a100982.txt">A100982 Musings</a>
%H A100982 Stan Wagon, <a href="http://dx.doi.org/10.1007/BF03023011">The Collatz problem</a>, Math. Intelligencer 7 (1985) 72-76.
%H A100982 Mike 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 A100982 Mike 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 A100982 Mike 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 A100982 Mike 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 A100982 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 A100982 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 A100982 a(n) = Sum_{k=n-1..A056576(n-1)} (k,n). (Theorem 2, cf. example)
%F A100982 a(k) = 2*A076227(A020914(k)-1) - A076227(A020914(k)), for k > 0. - _Vladimir M. Zarubin_, Sep 29 2019
%F A100982 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 A100982 The unique admissible sequence of order 1 is 3/2, 1/2.
%e A100982 The unique admissible sequence of order 2 is 3/2, 3/2, 1/2, 1/2.
%e A100982 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 A100982 a(13) = 8045 = binomial(floor(5*(13-2)/3), 13-2)
%e A100982 - Sum_{i=2..6} binomial(floor((3*(13-i)+0)/2), 13-i)*a(i)
%e A100982 - Sum_{i=7..11} binomial(floor((3*(13-i)-1)/2), 13-i)*a(i)
%e A100982 - Sum_{i=12..12} binomial(floor((3*(13-i)-2)/2), 13-i)*a(i)
%e A100982 = 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 A100982 From _Mike Winkler_, Sep 12 2017: (Start)
%e A100982 The next table shows how Theorem 2 works. No entry is equal to zero.
%e A100982 n =       3  4  5   6   7   8   9  10  11   12 .. |A076227(k)=
%e A100982 --------------------------------------------------|
%e A100982 k =  2 |  1                                       |     1
%e A100982 k =  3 |  1  1                                    |     2
%e A100982 k =  4 |     2  1                                 |     3
%e A100982 k =  5 |        3   1                             |     4
%e A100982 k =  6 |        3   4   1                         |     8
%e A100982 k =  7 |            7   5   1                     |    13
%e A100982 k =  8 |               12   6   1                 |    19
%e A100982 k =  9 |               12  18   7   1             |    38
%e A100982 k = 10 |                   30  25   8   1         |    64
%e A100982 k = 11 |                   30  55  33   9    1    |   128
%e A100982 :      |                        :   :   :    : .. |    :
%e A100982 --------------------------------------------------|---------
%e A100982 a(n) =    2  3  7  12  30  85 173 476 961 2652 .. |
%e A100982 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 A100982 From _Ruud H.G. van Tol_, Dec 04 2023: (Start)
%e A100982 A tree view.
%e A100982 n-tree--A098294--ids-----paths-----------------a(n)
%e A100982 0 ._          0  0       0                       -
%e A100982 1 |_          1  1       10                      1
%e A100982 2 |_._        2  2       1100                    1
%e A100982 3 |_|_        2  3-4     11010     -   11100     2
%e A100982 4 |_|_._      3  5-7     1101100   -  1111000    3
%e A100982 5 |_|_|_      3  8-14    11011010  - 11111000    7
%e A100982 6 |_|_|_._    4  15-26   1101101100-1111110000  12
%e A100982 7 |_|_|_|_._  5  27-56   ...                    30
%e A100982 8 |_|_|_|_|_  5  57-141  ...                    85
%e A100982 ...
%e A100982 For n>=1, the endpoints are at A098294(n) to the right.
%e A100982 (End)
%t A100982 (* 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 A100982 (PARI) /* translation of the above code from _T. D. Noe_ */
%o A100982 {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 A100982 (PARI) /* algorithm for the Conjecture */
%o A100982 {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 A100982 (PARI) /* cf. code for Theorem 2 */
%o A100982 {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 A100982 (PARI) /* algorithm for Theorem 1 */
%o A100982 n=20; a=vector(n); log32=log(3)/log(2);
%o A100982 {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 A100982 } \\ _Vladimir M. Zarubin_, Sep 25 2015
%o A100982 (PARI) /* algorithm for Theorem 2 */
%o A100982 {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 A100982 Cf. A122790 (Wagon's constant), A076227, A056576, A022921, A098294, A177789.
%Y A100982 Cf. A060941, A293946.
%K A100982 nonn,walk
%O A100982 1,3
%A A100982 _Steven Finch_, Jan 13 2005
%E A100982 Two more terms from Jules Renucci (jules.renucci(AT)wanadoo.fr), Nov 02 2005
%E A100982 More terms from _T. D. Noe_, Sep 11 2006

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE