This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A076227 Number of surviving Collatz residues mod 2^n. 4
 1, 1, 1, 2, 3, 4, 8, 13, 19, 38, 64, 128, 226, 367, 734, 1295, 2114, 4228, 7495, 14990, 27328, 46611, 93222, 168807, 286581, 573162, 1037374, 1762293, 3524586, 6385637, 12771274, 23642078, 41347483, 82694966, 151917636, 263841377, 527682754, 967378591, 1934757182, 3611535862 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS Number of residue classes in which A074473(m) is not constant. The ratio of numbers of inhomogenous r-classes versus uniform-classes enumerated here increases with n and tends to 0. For n large enough ratio < a(16)/65536 = 2114/65536 ~ 3.23%. Theorem: 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 A100982, A056576, A022921, A020915. - Mike Winkler, Sep 12 2017 LINKS Tomás Oliveira e Silva, Computational verification of the 3x+1 conjecture M. Winkler, The algorithmic structure of the finite stopping time behavior of the 3x + 1 function, arXiv:1709.03385 [math.GM], 2017. FORMULA a(n) = Sum_{k=A020915(n+2)..n+1} (n,k). (Theorem, cf. example) - Mike Winkler, Sep 12 2017 EXAMPLE n=6: Modulo 64, eight residue classes were counted: r=7, 15, 27, 31, 39, 47, 59, 63. See A075476-A075483. For other 64-8=56 r-classes u(q)=A074473(64k+q) is constant: in 32 class u(q)=2, in 16 classes u(q)=4, in 4 classes u(q)=7 and in 4 cases u(q)=9. E.g., for r=11, 23, 43, 55 A047473(64k+r)=9 independently of k. From Mike Winkler, Sep 12 2017: (Start) The next table shows how the theorem works. No entry is equal to zero.   k =        3  4  5   6   7   8   9  10  11   12 .. | a(n)= -----------------------------------------------------|   n =  2  |  1                                       |    1   n =  3  |  1  1                                    |    2   n =  4  |     2  1                                 |    3   n =  5  |        3   1                             |    4   n =  6  |        3   4   1                         |    8   n =  7  |            7   5   1                     |   13   n =  8  |               12   6   1                 |   19   n =  9  |               12  18   7   1             |   38   n = 10  |                   30  25   8   1         |   64   n = 11  |                   30  55  33   9    1    |  128   :       |                        :   :   :    : .. |   : -----------------------------------------------------|------ A100982(k)=  2  3  7  12  30  85 173 476 961 2652 .. | The entries (n,k) in this table are generated by the rule (n+1,k) = (n,k) + (n,k-1). The last value of (n+1,k) is given by n+1 = A056576(k-1), or the highest value in column n is given twice only if A022921(k-2) = 2. Then a(n) is equal to the sum of the entries in row n. For k = 7 there is: 1 = 0 + 1, 5 = 1 + 4, 12 = 5 + 7, 12 = 12 + 0. It is a(9) = 12 + 18 + 7 + 1 = 38. The sum of column k is equal to A100982(k). (End) PROG (C) /* call as follows: uint64_t s=survives(0, 1, 1, 0, bits); */ uint64_t survives(uint64_t r, uint64_t m, uint64_t lm, int p2, int fp2) {     while(!(m&1) && (m>=lm)) {         if(r&1) { r+=(r+1)>>1; m+=m>>1; }         else { r>>=1; m>>=1; }     }     if(m30*/ R=matrix(limit, limit); R[2, 1]=0; R[2, 2]=1; for(k=2, limit, if(k>2, print; print1("For n="k-1" in row n: ")); Kappa_k=floor(k*log(3)/log(2)); for(n=k, Kappa_k, R[n+1, k]=R[n, k]+R[n, k-1]); t=floor(1+(k-1)*log(2)/log(3)); a_n=0; for(i=t, k-1, print1(R[k, i]", "); a_n=a_n+R[k, i]); if(k>2, print; print(" and the sum is a(n)="a_n)))} \\ Mike Winkler, Sep 12 2017 CROSSREFS Cf. A006370, A074473, A075476-A075483, A100982, A056576, A022921, A020915. Sequence in context: A068791 A219968 A126042 * A186272 A092075 A091415 Adjacent sequences:  A076224 A076225 A076226 * A076228 A076229 A076230 KEYWORD nonn AUTHOR Labos Elemer, Oct 01 2002 EXTENSIONS New terms to n=39 by Phil Carmody, Sep 08 2011 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 21 22:24 EDT 2019. Contains 323467 sequences. (Running on oeis4.)