A275544 - OEIS

%I #52 Apr 26 2023 09:47:52

%S 1,2,4,8,15,29,56,108,208,400,766,1465,2793,5314,10088,19115,36156,

%T 68290,128817,242720,456884,859269,1614809,3032673,5692145,10678326,

%U 20023239,37531218,70323203,131725663,246674211,461819857,864428716,1617723538,3026965088,5663003895,10593269487,19813600282

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

%C 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   i

%C   0:                                   n

%C   1:                  3n+1                            n/2

%C   2:        9n+4        (3/2)n+1/2         (3/2)n+1          n/4

%C   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   ...

%C   reveals that any n that is part of a cycle has to satisfy an equation of the following form:

%C   (3^(i-p)/2^p - 1)n + x_i = 0     i = 0,1,2,3,...  p = 0,...,i

%C   where x_i are the possible constant terms at iteration i, i.e.,

%C   x_0 = [0],

%C   x_1 = [1,0],

%C   x_2 = [4,1/2,1,0],

%C   x_3 = [13,2,5/2,1/4,4,1/2,1,0],

%C   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   ...

%C (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 This sequence is composed of the numbers of distinct possible constant terms at each iteration i.

%C 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 This sequence is related to A275545, if one sequence is known it is possible to work out the other (see formula).

%C 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 The first 9 terms coincide with the Tetranacci numbers A000078.

%H Markus Sigg, <a href="/A275544/b275544.txt">Table of n, a(n) for n = 0..44</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Collatz_conjecture">Collatz conjecture</a>

%F a(0) = 1; a(n) = 2*a(n-1) - A275545(n), n >= 1.

%e a(3) = 8 since x_3 has 8 members and they are all distinct.

%e a(4) = 15 since x_4 has 16 members but the number 1 appears twice.

%t nmax = 25; s = {0}; a[0] = 1;

%t Do[s = Join[3s + 1, s/2]; Print[n, " ", a[n] = s//Union//Length], {n, nmax}];

%t a /@ Range[0, nmax] (* _Jean-François Alcover_, Nov 16 2019 *)

%o (Python)

%o x = [0]

%o for i in range(n):

%o     x_tmp = []

%o     for s in x:

%o         x_tmp.append(3*s+1)

%o         x_tmp.append(s*0.5)

%o     x = x_tmp

%o     x = list(set(x))

%o     print len(x)

%o (Python)

%o from fractions import Fraction

%o A275544_list, c = [1], [Fraction(0,1)]

%o for _ in range(20):

%o     c = set(e for d in c for e in (3*d+1,d/2))

%o     A275544_list.append(len(c)) # _Chai Wah Wu_, Sep 02 2016

%Y Cf. A208127, A275545.

%K nonn

%O 0,2

%A _Rok Cestnik_, Aug 01 2016

%E a(27)-a(29) corrected and a(30) added by _Chai Wah Wu_, Sep 02 2016

%E a(31)-a(37) from _Hugo Pfoertner_, Apr 23 2023