login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A076227 Number of surviving Collatz residues mod 2^n. 5
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

Brown's criterion ensures that the sequence is complete (see formulae). - Vladimir M. Zarubin, Aug 11 2019

LINKS

Table of n, a(n) for n=0..39.

Tomás Oliveira e Silva, Computational verification of the 3x+1 conjecture.

Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.

Eric Weisstein's World of Mathematics, Brown's Criterion

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

From Vladimir M. Zarubin, Aug 11 2019: (Start)

a(0) = 1, a(1) = 1, and for k > 0,

a(A020914(k)) = 2*a(A020914(k)-1) - A100982(k),

a(A054414(k)) = 2*a(A054414(k)-1). (End)

a(n) = 2^n - 2^n*Sum_{k=0..A156301(n)-1} A186009(k+1)/2^A020914(k). - Benjamin Lombardo, Sep 08 2019

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(m<lm) { return 0; }

if(p2==fp2) { return 1; }

return survives(r, m<<1, lm<<1, p2+1, fp2)

+ survives(r+m, m<<1, lm<<1, p2+1, fp2);

} /* Phil Carmody, Sep 08 2011 */

(PARI) /* algorithm for the Theorem */

{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

CROSSREFS

Cf. A006370, A074473, A075476-A075483, A100982, A056576, A022921, A020915, A243115.

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 4 20:24 EST 2022. Contains 358568 sequences. (Running on oeis4.)