login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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. 15
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
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.
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(k) = 2*A076227(A020914(k)-1) - A076227(A020914(k)), for k > 0. - Vladimir M. Zarubin, Sep 29 2019
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
Cf. A122790 (Wagon's constant), A076227, A056576, A022921, A098294, A177789.
Sequence in context: A047749 A134565 A300749 * A186009 A299295 A305752
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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 04:58 EDT 2024. Contains 370952 sequences. (Running on oeis4.)