# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a076227
Showing 1-1 of 1

%I A076227 #112 Jul 19 2024 14:36:49
%S A076227 1,1,1,2,3,4,8,13,19,38,64,128,226,367,734,1295,2114,4228,7495,14990,
%T A076227 27328,46611,93222,168807,286581,573162,1037374,1762293,3524586,
%U A076227 6385637,12771274,23642078,41347483,82694966,151917636,263841377,527682754,967378591,1934757182,3611535862
%N A076227 Number of surviving Collatz residues mod 2^n.
%C A076227 Number of residue classes in which A074473(m) is not constant.
%C A076227 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%.
%C A076227 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
%C A076227 Brown's criterion ensures that the sequence is complete (see formulae). - _Vladimir M. Zarubin_, Aug 11 2019
%H A076227 Tomás Oliveira e Silva, <a href="http://sweet.ua.pt/tos/3x+1.html">Computational verification of the 3x+1 conjecture</a>.
%H A076227 Isaac DeJager, Madeleine Naquin, and Frank Seidl, <a href="https://www.valpo.edu/mathematics-statistics/files/2019/08/Drube2019.pdf">Colored Motzkin Paths of Higher Order</a>, VERUM 2019.
%H A076227 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BrownsCriterion.html">Brown's Criterion</a>
%H A076227 M. Winkler, <a href="http://arxiv.org/abs/1709.03385">The algorithmic structure of the finite stopping time behavior of the 3x + 1 function</a>, arXiv:1709.03385 [math.GM], 2017.
%F A076227 a(n) = Sum_{k=A020915(n+2)..n+1} (n,k). (Theorem, cf. example) - _Mike Winkler_, Sep 12 2017
%F A076227 From _Vladimir M. Zarubin_, Aug 11 2019: (Start)
%F A076227 a(0) = 1, a(1) = 1, and for k > 0,
%F A076227 a(A020914(k)) = 2*a(A020914(k)-1) - A100982(k),
%F A076227 a(A054414(k)) = 2*a(A054414(k)-1). (End)
%F A076227 a(n) = 2^n - 2^n*Sum_{k=0..A156301(n)-1} A186009(k+1)/2^A020914(k). - _Benjamin Lombardo_, Sep 08 2019
%e A076227 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 A074473(64k+r)=9 independently of k.
%e A076227 From _Mike Winkler_, Sep 12 2017: (Start)
%e A076227 The next table shows how the theorem works. No entry is equal to zero.
%e A076227   k =        3  4  5   6   7   8   9  10  11   12 .. | a(n)=
%e A076227 -----------------------------------------------------|
%e A076227   n =  2  |  1                                       |    1
%e A076227   n =  3  |  1  1                                    |    2
%e A076227   n =  4  |     2  1                                 |    3
%e A076227   n =  5  |        3   1                             |    4
%e A076227   n =  6  |        3   4   1                         |    8
%e A076227   n =  7  |            7   5   1                     |   13
%e A076227   n =  8  |               12   6   1                 |   19
%e A076227   n =  9  |               12  18   7   1             |   38
%e A076227   n = 10  |                   30  25   8   1         |   64
%e A076227   n = 11  |                   30  55  33   9    1    |  128
%e A076227   :       |                        :   :   :    : .. |   :
%e A076227 -----------------------------------------------------|------
%e A076227 A100982(k) = 2  3  7  12  30  85 173 476 961 2652 .. |
%e A076227 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)
%o A076227 (C) /* call as follows: uint64_t s=survives(0,1,1,0,bits); */
%o A076227 uint64_t survives(uint64_t r, uint64_t m, uint64_t lm, int p2, int fp2)
%o A076227 {
%o A076227     while(!(m&1) && (m>=lm)) {
%o A076227         if(r&1) { r+=(r+1)>>1; m+=m>>1; }
%o A076227         else { r>>=1; m>>=1; }
%o A076227     }
%o A076227     if(m<lm) { return 0; }
%o A076227     if(p2==fp2) { return 1; }
%o A076227     return survives(r, m<<1, lm<<1, p2+1, fp2)
%o A076227         + survives(r+m, m<<1, lm<<1, p2+1, fp2);
%o A076227 } /* _Phil Carmody_, Sep 08 2011 */
%o A076227 (PARI) /* algorithm for the Theorem */
%o A076227 {limit=30; /*or limit>30*/ 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
%Y A076227 Cf. A006370, A074473, A075476-A075483, A100982, A056576, A022921, A020915, A243115.
%K A076227 nonn
%O A076227 0,4
%A A076227 _Labos Elemer_, Oct 01 2002
%E A076227 New terms to n=39 by _Phil Carmody_, Sep 08 2011

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE