A365495 Square array read by ascending antidiagonals: T(n,k) is the parity of the k-th iterate of the 3x+1 function started at n, with n >= 1 and k >= 0.

1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1

Offset

1

Comments

The 3x+1 function (A014682), denoted by T(x) in the literature, is defined as T(x) = (3x+1)/2 if x is odd, T(x) = x/2 if x is even.

As reported by Kontorovich and Lagarias (2009 and 2010), a result due to Terras and Everett is that the sequence of the first m terms in each row is periodic in n with period 2^m, with each of the 2^m possible binary vectors occurring exactly once (as the first m terms of a row) per period.

For example, for m = 3, the first 3 terms in rows 1..2^3 are respectively [1,0,1], [0,1,0], [1,1,0], [0,0,1], [1,0,0], [0,1,1], [1,1,1] and [0,0,0], and this pattern repeats from row 2^3 + 1 onwards.

As a consequence, Kontorovich and Lagarias note, each integer is uniquely determined by the sequence of the parity of its orbit, i.e., n is uniquely determined by the n-th row of the present array.

Links

Paolo Xausa, Table of n, a(n) for n = 1..11325 (antidiagonals 1..150 of the array, flattened)

C. J. Everett, Iteration of the number-theoretic function f(2n) = n, f(2n + 1) = 3n + 2, Advances in Mathematics, Vol. 25, Issue 1, July 1977, pp. 42-45, and in Jeffrey C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, American Mathematical Society, 2010, pp. 225-230.

Alex V. Kontorovich and Jeffrey C. Lagarias, Stochastic Models for the 3x+1 and 5x+1 Problems, arXiv:0910.1944 [math.NT], 2009, pp. 7-8, and in Jeffrey C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, American Mathematical Society, 2010, pp. 136-137.

Riho Terras, A stopping time problem on the positive integers, Acta Arithmetica 30, 1976, pp. 241-252.

Index entries for sequences related to 3x+1 (or Collatz) problem

Formula

T(n,k) = A365484(n,k) mod 2.

Example

The array begins:
  n\k| 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14  ...
  -----------------------------------------------------
   1 | 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...
   2 | 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
   3 | 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
   4 | 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...
   5 | 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...
   6 | 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...
   7 | 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, ...
   8 | 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
   9 | 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, ...
  10 | 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
  11 | 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, ...
  12 | 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
  13 | 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...
  14 | 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, ...
  15 | 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, ...
  ...

Mathematica

A365495list[dmax_]:=With[{a=Mod[Array[NestList[If[OddQ[#], (3#+1)/2, #/2]&, dmax-#, #]&, dmax, 0], 2]}, Array[Diagonal[a, #]&, dmax, 1-dmax]]; A365495list[20] (* Generates 20 antidiagonals *)

Crossrefs

Cf. A014682, A347283 (equivalent for the Collatz function), A365484, A365992, A371689 (main diagonal).

Sequence in context: A267776 A072792 A254113 * A267037 A200246 A267292

Adjacent sequences: A365492 A365493 A365494 * A365496 A365497 A365498

Keyword

nonn,easy,tabl

Author

Paolo Xausa, Sep 06 2023

Status

approved