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