

A076227


Number of surviving Collatz residues mod 2^n.


7



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 rclasses versus uniformclasses 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 trianglelike 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



FORMULA

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


EXAMPLE

n=6: Modulo 64, eight residue classes were counted: r=7, 15, 27, 31, 39, 47, 59, 63. See A075476A075483. For other 648=56 rclasses 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.
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,k1). The last value of (n+1,k) is given by n+1 = A056576(k1), or the highest value in column n is given twice only if A022921(k2) = 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);
(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="k1" 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, k1]); t=floor(1+(k1)*log(2)/log(3)); a_n=0; for(i=t, k1, 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



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



