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. 9
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 1: 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

Conjecture 2: There is another easy method of summation for generating a(n) by using the term log(3)/log(2). This has been proved for each n <= 10000. - Mike Winkler, Apr 14 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: (see conjecture 2 above) The encoding (in the A176999 sequence fashion) of integers of equal stopping time leads to two geographies of a "Pascal trihedron", each one with specific properties. The second geography enables (in Aug 2017) the author to prove his 2015 conjecture. - Hubert Schaetzel, Aug 23 2017

Theorem 3: 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 connectedness to 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

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

H. Schaetzel, Collatz conjecture : Geography of the Pascal trihedron, 2017.

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 1)

a(n) = Sum_{k=n-1..A056576(n-1)} (k,n). (theorem 3, 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 1)

The next table shows how theorem 3 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). - Mike Winkler, Sep 12 2017

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) /* algorithm for conjecture 1 */

{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) /* algorithm for conjecture 2 */

{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) /* 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 3 */

{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,changed

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 September 24 17:29 EDT 2017. Contains 292432 sequences.