login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A275545 Number of new duplicate terms at a given iteration of the Collatz (or 3x+1) map starting with 0. 1
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,7

COMMENTS

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).

LINKS

Table of n, a(n) for n=0..29.

Wikipedia, Collatz conjecture

FORMULA

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

EXAMPLE

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).

MATHEMATICA

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 *)

PROG

(Python)

x = [0]

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)

(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

CROSSREFS

Cf. A275544.

Sequence in context: A084636 A161869 A210541 * A273972 A275443 A288170

Adjacent sequences:  A275542 A275543 A275544 * A275546 A275547 A275548

KEYWORD

nonn,more

AUTHOR

Rok Cestnik, Aug 01 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 4 15:50 EDT 2020. Contains 336202 sequences. (Running on oeis4.)