A275544 -id:A275544 - cp's OEIS frontend

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

0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 34, 67, 137, 272, 540, 1061, 2074, 4022, 7763, 14914, 28556, 54499, 103729, 196945, 373201, 705964, 1333413, 2515298, 4739834, 8926089

Offset: 0

Rok Cestnik, Aug 01 2016

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:
  i
  0:                                   n
  1:                  3n+1                            n/2
  2:        9n+4        (3/2)n+1/2         (3/2)n+1          n/4
  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
  ...
  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.,
  x_0 = [0],
  x_1 = [1,0],
  x_2 = [4,1/2,1,0],
  x_3 = [13,2,5/2,1/4,4,1/2,1,0],
  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],
  ...
(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).
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).
This sequence is related to A275544, if one sequence is known it is possible to work out the other (see formula).
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).

			a(3) = 0 since all the members of x_3 are distinct.
a(4) = 1 since in x_4 the number 1 appears twice (there is 1 duplicate).

Wikipedia, Collatz conjecture

Cf. A275544.

nmax = 25; s = {0}; b[0] = 1;
Do[s = Join[3 s + 1, s/2]; Print[n]; b[n] = s // Union // Length, {n, 1, nmax}];
a[n_] := If[n == 0, 0, 2 b[n - 1] - b[n]];
a /@ Range[0, nmax] (* Jean-François Alcover, Nov 16 2019 *)

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

x = [0]
n = 20
for i in range(n):
    x_tmp = []
    for s in x:
        x_tmp.append(3*s+1)
        x_tmp.append(s*0.5)
    x = x_tmp
    length_tmp = len(x)
    x = list(set(x))
    print(length_tmp-len(x))

a(n) = 2*A275544(n-1) - A275544(n), for n>=1.

A362757 The number of integers in the set f^n({0}), where f is a variant of the Collatz function that replaces any element x in the argument set with both x/2 and 3*x+1.

Original entry on oeis.org

1, 2, 3, 5, 7, 10, 15, 22, 33, 48, 72, 103, 153, 221, 326, 477, 705, 1036, 1526, 2243, 3310, 4872, 7179, 10582, 15620, 23039, 33995, 50151, 73999, 109170, 161092, 237629, 350590, 517254, 763167, 1126070, 1661607, 2451715, 3617809, 5338044, 7876246, 11621318, 17147409, 25300982, 37331656, 55082911, 81275003

Offset: 0

Markus Sigg, May 02 2023

nonn

a(n) is the number of integers in set A(n), where A(0) = {0} and A(n+1) = {x/2 : x in A(n)} union {3x+1 : x in A(n)}.
Non-integer numbers do not have integer offsprings. Consequently, they can be dropped when calculating terms of the sequence.
Apparently the limit of a(n)/a(n-1) is approximately equal to 1.47551 (see plot of a(n-1)/a(n) ~= 0.677732). An explanation of this limit would be desirable. - Hugo Pfoertner, May 06 2023

			a(3) = 5 is the number of integers in the set {0, 1/4, 1/2, 1, 2, 5/2, 4, 13}.

Markus Sigg, Table of n, a(n) for n = 0..70
Hugo Pfoertner, Plot of ratio a(n-1)/a(n), using Plot 2.

Cf. A208127, A275544.

a362757(maxn) = {
  my(A = Set([0]));
  print1(1);
  for(n = 1, maxn,
    A = setunion([t >> 1 | t <- A, bitnegimply(1,t)], [3*t+1 | t <- A]);
    print1(",", #A);
  );
};

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula