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)).
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
Ruud H.G. van Tol, Sequence as counts of lattice walks
Ruud H.G. van Tol, A100982 Musings
Stan Wagon, The Collatz problem, Math. Intelligencer 7 (1985) 72-76.
Mike Winkler, On a stopping time algorithm of the 3n + 1 function, 2011.
Mike 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.
Mike Winkler, New results on the stopping time behaviour of the Collatz 3x + 1 function, arXiv:1504.00212 [math.GM], 2015.
Mike 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)
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
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)
From Ruud H.G. van Tol, Dec 04 2023: (Start)
A tree view.
n-tree--A098294--ids-----paths-----------------a(n)
0 ._ 0 0 0 -
1 |_ 1 1 10 1
2 |_._ 2 2 1100 1
3 |_|_ 2 3-4 11010 - 11100 2
4 |_|_._ 3 5-7 1101100 - 1111000 3
5 |_|_|_ 3 8-14 11011010 - 11111000 7
6 |_|_|_._ 4 15-26 1101101100-1111110000 12
7 |_|_|_|_._ 5 27-56 ... 30
8 |_|_|_|_|_ 5 57-141 ... 85
...
For n>=1, the endpoints are at A098294(n) to the right.
(End)
MATHEMATICA
(* 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 *)
PROG
(PARI) /* translation of the above code from T. D. Noe */
{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
(PARI) /* algorithm for the Conjecture */
{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
(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[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
(PARI) /* algorithm for Theorem 1 */
n=20; a=vector(n); log32=log(3)/log(2);
{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]) );
} \\ 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
KEYWORD
nonn,walk
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