A208127 -id:A208127 - cp's OEIS frontend

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

1, 2, 4, 8, 15, 29, 56, 108, 208, 400, 766, 1465, 2793, 5314, 10088, 19115, 36156, 68290, 128817, 242720, 456884, 859269, 1614809, 3032673, 5692145, 10678326, 20023239, 37531218, 70323203, 131725663, 246674211, 461819857, 864428716, 1617723538, 3026965088, 5663003895, 10593269487, 19813600282

Offset: 0

Rok Cestnik, Aug 01 2016

nonn

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 has to satisfy an equation of the following form:
  (3^(i-p)/2^p - 1)n + x_i = 0     i = 0,1,2,3,...  p = 0,...,i
  where 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 numbers of distinct possible constant terms at each iteration i.
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.
This sequence is related to A275545, 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).
The first 9 terms coincide with the tetranacci numbers A000078.

			a(3) = 8 since x_3 has 8 members and they are all distinct.
a(4) = 15 since x_4 has 16 members but the number 1 appears twice.

Markus Sigg, Table of n, a(n) for n = 0..44
Wikipedia, Collatz conjecture

Cf. A208127, A275545.

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

from fractions import Fraction
A275544_list, c = [1], [Fraction(0,1)]
for _ in range(20):
    c = set(e for d in c for e in (3*d+1,d/2))
    A275544_list.append(len(c)) # Chai Wah Wu, Sep 02 2016

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

a(27)-a(29) corrected and a(30) added by Chai Wah Wu, Sep 02 2016

a(31)-a(37) from Hugo Pfoertner, Apr 23 2023

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions