login
This site is supported by donations 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. 8
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. For details see LINKS, FORMULA, EXAMPLE, PROG. This algorithm is based on simple integer arithmetic without the use of the expression log(3)/log(2). - Mike Winkler, Apr 02 2015

Conjecture 2: Hubert Schaetzel found another easy method of summation for generating a(n). Based on Schaetzel's results, Mike Winkler devised an algorithm which generates a(n) for each n>2. This algorithm computes very fast, but uses the expression log(3)/log(2). This has been proved for each n<=10000. For details see LINKS, EXAMPLE, PROG. - Mike Winkler, Apr 14 2015

Theorem: 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

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

H. Schaetzel, Pascal trihedron and Collatz algorithm, 2015.

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.

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)

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)

The next table shows how the algorithm of conjecture 2 works for n=1..16.

  n : 1 2 3 4 5  6  7  8   9  10  11   12   13    14    15     16

  1 : 1 1 1 1 1  1  1  1   1   1   1    1    1     1     1      1

  2 :     1 2 3  4  5  6   7   8   9   10   11    12    13     14

  3 :         3  7 12 18  25  33  42   52   63    75    88    102

  4 :              12 30  55  88 130  182  245   320   408    510

  5 :                 30  85 173 303  485  730  1050  1458   1968

  6 :                        173 476  961 1691  2741  4199   6167

  7 :                                 961 2652  5393  9592  15759

  8 :                                     2652  8045 17637  33396

  9 :                                                17637  51033

a(n): 1 1 2 3 7 12 30 85 173 476 961 2652 8045 17637 51033 108950

The entries of column n were build by summation with the entries of column n-1. For n=11 there is: 8 + 1 = 9, 33 + 9 = 42, 88 + 42 = 130, 173 + 130 = 303, 173 + 303 = 476. Then a(n) is equal to the sum of entries in column n from row 1..9. There is a(11) = 1 + 9 + 42 + 130 + 303 + 476 = 961.

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) /* based on Eric Roosendaal's algorithm */

{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) /* Mike Winkler's algorithm */

{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) /* based on Hubert Schaetzel's algorithm */

{limit=10000; 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)

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

CROSSREFS

Cf. A122790 (Wagon's constant).

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 July 22 03:22 EDT 2017. Contains 289648 sequences.