login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

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 > 12. This has been proved for each n <= 10000. This algorithm is based on simple integer arithmetic without the use of the expression log(3)/log(2). - Mike Winkler, Apr 02 2015

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) = binomial(floor(5*(n-2)/3), n-2) - Sum_{i=2..n-1} binomial(floor((3*(n-i)+b)/2), n-i)*a(i), where 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]=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=10000; a=vector(limit); a[1]=a[2]=1; a[3]=2; a[4]=3; a[5]=7; a[6]=12; a[7]=30; a[8]=85; a[9]=173; a[10]=476; a[11]=961; a[12]=2652; for(n=12, limit, Sum=0; x=-1; for(k=0, n-11, x=x+(-1)^floor(2*(k-2)/3)); for(i=2, 6, Sum=Sum+binomial(floor((3*(n-i)+x)/2), n-i)*a[i]); for(i=7, 11, Sum=Sum+binomial(floor((3*(n-i)+x-1)/2), n-i)*a[i]); for(h=0, floor((limit-12)/6), v=12; w=5; if((h<58)&&(frac((h-6)/9)==0), w=4); for(k=0, 5, if(h>=k*9+7, v--)); c2=58; for(k=1, floor(n/20), if(frac(k/2)!=0, d=52; e=5, d=61; e=6); c1=c2; c2=c1+d; if((h>=c1)&&(h<c2)&&(frac((h-6+2*k)/9)==0), w=4); for(f=0, e, if(h>=f*9+c1+1, v--))); p=q=0; for(i=v+h*6, v+h*6+w, b=x-2-h; Sum=Sum+binomial(floor((3*(n-i)+b)/2), n-i)*a[i]; a_n=binomial(floor(5*(n-2)/3), n-2)-Sum; r1=r2=0; p++; for(t=0, floor(n/15), c1=5; c2=6; d=0; if(t>c1, r1=2); if(t>c2, r2=2); for(k=2, floor(n/50), if(frac(k/2)==0, d=6, d=7); c1=c1+d; c2=c2+d; if(t>c1, r1=k*2); if(t>c2, r2=k*2)); for(k=t*9-r2, t*9+8-r1, if((n>k*6-t)&&(h==k-2)&&(p==n-k*6+t), print(n" "a_n); a[n]=a_n; q=1; break)); if(q==1, break)); if(q==1, break)); if(q==1, break))); } \\ Mike Winkler, Apr 02 2015

(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, A177789.

Sequence in context: A047749 A134565 * A186009 A034786 A080107 A056156

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 21 13:53 EST 2017. Contains 295001 sequences.