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
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Andreas-Stephan Elsenhans, Numerical verification of the Collatz conjecture for billion digit random numbers, arXiv:2502.16743 [math.NT], 2025.
Tomás Oliveira e Silva, Computational verification of the 3x+1 conjecture.
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(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 A074473(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
KEYWORD
nonn
AUTHOR
Labos Elemer, Oct 01 2002
EXTENSIONS
New terms to n=39 by Phil Carmody, Sep 08 2011
STATUS
approved