cp's OEIS Frontend

A275544 Number of distinct terms at a given iteration of the Collatz (or 3x+1) map starting with 0.

%I A275544 #61 Jun 02 2025 15:15:47
%S A275544 1,2,4,8,15,29,56,108,208,400,766,1465,2793,5314,10088,19115,36156,
%T A275544 68290,128817,242720,456884,859269,1614809,3032673,5692145,10678326,
%U A275544 20023239,37531218,70323203,131725663,246674211,461819857,864428716,1617723538,3026965088,5663003895,10593269487,19813600282
%N A275544 Number of distinct terms at a given iteration of the Collatz (or 3x+1) map starting with 0.
%C A275544 If one considers an algebraic approach to the Collatz conjecture, the tree of outcomes of the "Half Or Triple Plus One" process starting with a natural number n:
%C A275544   i
%C A275544   0:                                   n
%C A275544   1:                  3n+1                            n/2
%C A275544   2:        9n+4        (3/2)n+1/2         (3/2)n+1          n/4
%C A275544   3: 27n+13 (9/2)n+2 (9/2)n+5/2 (3/4)n+1/4 (9/2)n+4 (3/4)n+1/2 (3/4)n+1 n/8
%C A275544   ...
%C A275544   reveals that any n that is part of a cycle has to satisfy an equation of the following form:
%C A275544   (3^(i-p)/2^p - 1)n + x_i = 0     i = 0,1,2,3,...  p = 0,...,i
%C A275544   where x_i are the possible constant terms at iteration i, i.e.,
%C A275544   x_0 = [0],
%C A275544   x_1 = [1,0],
%C A275544   x_2 = [4,1/2,1,0],
%C A275544   x_3 = [13,2,5/2,1/4,4,1/2,1,0],
%C A275544   x_4 = [40,13/2,7,1,17/2,5/4,7/4,1/8,13,2,5/2,1/4,4,1/2,1,0],
%C A275544   ...
%C A275544 (Note that not all the combinations of members of x_i and numbers p yield an equation that corresponds to n having to belong to a cycle, instead satisfying at least one equation of the form above is a necessary condition for every n that does).
%C A275544 This sequence is composed of the numbers of distinct possible constant terms at each iteration i.
%C A275544 The only constant term at the zeroth iteration is 0. Since at each iteration both half and triple plus one is considered, the halving of 0 always yields another 0, which always has the same progression tree, and therefore each set x_i contains the members of all previous sets x_j where j < i. This is also the reason why the sequence at the beginning resembles powers of 2 A000079, but later falls behind as more and more duplicates arise.
%C A275544 This sequence is related to A275545, if one sequence is known it is possible to work out the other (see formula).
%C A275544 An empirical observation suggests that the same sequence of numbers arises if we analogously consider the 3n-1 problem (the Collatz conjecture can be referred to as the 3n+1 problem).
%C A275544 The first 9 terms coincide with the tetranacci numbers A000078.
%H A275544 Markus Sigg, <a href="/A275544/b275544.txt">Table of n, a(n) for n = 0..44</a>
%H A275544 Wikipedia, <a href="https://en.wikipedia.org/wiki/Collatz_conjecture">Collatz conjecture</a>
%F A275544 a(0) = 1; a(n) = 2*a(n-1) - A275545(n), n >= 1.
%e A275544 a(3) = 8 since x_3 has 8 members and they are all distinct.
%e A275544 a(4) = 15 since x_4 has 16 members but the number 1 appears twice.
%t A275544 nmax = 25; s = {0}; a[0] = 1;
%t A275544 Do[s = Join[3s + 1, s/2]; Print[n, " ", a[n] = s//Union//Length], {n, nmax}];
%t A275544 a /@ Range[0, nmax] (* _Jean-François Alcover_, Nov 16 2019 *)
%o A275544 (Python)
%o A275544 from fractions import Fraction
%o A275544 A275544_list, c = [1], [Fraction(0,1)]
%o A275544 for _ in range(20):
%o A275544     c = set(e for d in c for e in (3*d+1,d/2))
%o A275544     A275544_list.append(len(c)) # _Chai Wah Wu_, Sep 02 2016
%Y A275544 Cf. A208127, A275545.
%K A275544 nonn
%O A275544 0,2
%A A275544 _Rok Cestnik_, Aug 01 2016
%E A275544 a(27)-a(29) corrected and a(30) added by _Chai Wah Wu_, Sep 02 2016
%E A275544 a(31)-a(37) from _Hugo Pfoertner_, Apr 23 2023