cp's OEIS Frontend

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

%I A275545 #39 Aug 01 2025 19:10:55
%S A275545 0,0,0,0,1,1,2,4,8,16,34,67,137,272,540,1061,2074,4022,7763,14914,
%T A275545 28556,54499,103729,196945,373201,705964,1333413,2515298,4739834,
%U A275545 8926089
%N A275545 Number of new duplicate terms at a given iteration of the Collatz (or 3x+1) map starting with 0.
%C A275545 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 A275545   i
%C A275545   0:                                   n
%C A275545   1:                  3n+1                            n/2
%C A275545   2:        9n+4        (3/2)n+1/2         (3/2)n+1          n/4
%C A275545   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 A275545   ...
%C A275545   reveals that any n that is part of a cycle satisfies an equation of the form (3^(i-p)/2^p - 1)n + x_i = 0, i = 0,1,2,3,..., p = 0..i, where the x_i are the possible constant terms at iteration i, i.e.,
%C A275545   x_0 = [0],
%C A275545   x_1 = [1,0],
%C A275545   x_2 = [4,1/2,1,0],
%C A275545   x_3 = [13,2,5/2,1/4,4,1/2,1,0],
%C A275545   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 A275545   ...
%C A275545 (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 A275545 This sequence is composed of the number of new duplicates of possible constant terms at each iteration i. "New duplicates" refers to two identical constant terms appearing in the current iteration i, that have not appeared in any previous one j < i (because every duplicate in x_i yields two duplicates in x_(i+1), these are not counted).
%C A275545 This sequence is related to A275544, if one sequence is known it is possible to work out the other (see formula).
%C A275545 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).
%H A275545 Wikipedia, <a href="https://en.wikipedia.org/wiki/Collatz_conjecture">Collatz conjecture</a>
%F A275545 a(n) = 2*A275544(n-1) - A275544(n), for n>=1.
%e A275545 a(3) = 0 since all the members of x_3 are distinct.
%e A275545 a(4) = 1 since in x_4 the number 1 appears twice (there is 1 duplicate).
%t A275545 nmax = 25; s = {0}; b[0] = 1;
%t A275545 Do[s = Join[3 s + 1, s/2]; Print[n]; b[n] = s // Union // Length, {n, 1, nmax}];
%t A275545 a[n_] := If[n == 0, 0, 2 b[n - 1] - b[n]];
%t A275545 a /@ Range[0, nmax] (* _Jean-François Alcover_, Nov 16 2019 *)
%o A275545 (Python)
%o A275545 x = [0]
%o A275545 n = 20
%o A275545 for i in range(n):
%o A275545     x_tmp = []
%o A275545     for s in x:
%o A275545         x_tmp.append(3*s+1)
%o A275545         x_tmp.append(s*0.5)
%o A275545     x = x_tmp
%o A275545     length_tmp = len(x)
%o A275545     x = list(set(x))
%o A275545     print(length_tmp-len(x))
%o A275545 (PARI) first(n)=my(v=vector(n),u=[0],t); for(i=1,n, t=2*#u; u=Set(concat(vector(#u,j,3*u[j]+1),u/2)); v[i]=t-#u); concat(0, v) \\ _Charles R Greathouse IV_, Aug 05 2016
%Y A275545 Cf. A275544.
%K A275545 nonn,more
%O A275545 0,7
%A A275545 _Rok Cestnik_, Aug 01 2016