cp's OEIS Frontend

Conjecture (now Lemma 1): The sequence is a permutation of the odd natural numbers.

Proof from Max Alekseyev, Apr 29 2015:

Reformulating the conjecture, we need to prove that for any integer m >= 0, the equation (1 + 2^n*(6*k - 3 + 2*(-1)^n))/3 = 2*m + 1 has a unique solution in integers n,k >= 1. Simplifying a bit, we have

(1) 2^n*(6*k - 3 + 2*(-1)^n) = 6*m + 2.

Since the factor (6*k - 3 + 2*(-1)^n) is odd, n is uniquely defined by n = A007814(6*m+2). Since 6*m+2 is even, we have n>=1. Dividing (1) by 2^n and rearranging, we further get

(2) 6*k = (6*m + 2)/2^n + 3 - 2*(-1)^n.

To prove the uniqueness of k, it remains to prove that the r.h.s of (2) is divisible by 6. To that end, the value of n implies that (6*m + 2)/2^n is odd; hence the r.h.s. of (2) is even and thus divisible by 2. Now, taking the r.h.s. modulo 3, we get

(6*m + 2)/2^n + 3 - 2*(-1)^n == 2/(-1)^n + 0 - 2*(-1)^n == 0 (mod 3);

so the r.h.s. of (2) is also divisible by 3. Therefore k is uniquely defined by

k = ((6*m + 2)/2^n + 3 - 2*(-1)^n)/6.

Finally, it is easy to see that (6*m + 2)/2^n >= 1, so k >= 1.

QED

Let v(y) denote the 2-adic valuation of y (see A007814). For x an odd natural number, define the function F(x) = (3*x+1)/2^v(3*x+1) (see A075677). Let F^(j)(x) denote k-fold iteration of F and defined by the recurrence F^(j)(x) = F(F^(j-1)(x)), j>0, with initial condition F^(0)(x) = x.

Lemma 2: The following statements are equivalent. (i) Row n of A is the set of all odd m such that F^(n)(4*m-3) == 1 (mod 4); (ii) Row n of A is the set of all odd m such that v(1+F(4m-3)) = n.

See A075677 for the function R applied to the odd numbers once. See A075680 for the number of iterations required to yield 1. Sequence A006884, with the number 2 removed, gives the odd numbers that produce new record maxima. The maxima of the current sequence are related to A006885: if m is a maximum of the usual Collatz iteration, then (m-1)/3 is the maximum for the reduced Collatz iteration.

Normally the '3x+1 problem' or 'Collatz problem' asks for the number of steps to go from n to 1 (A006577). Here we ask for the number of iterations of the mapping, msa, to go from n to less than n; the mapping of x is either -> (3x+1)/2 if x is odd or -> x/2 if x is even.

Since the number of iterations of msa for an even number is always 1, we will only investigate the odd numbers greater than one.

a(n) = 1 for no values of n;

a(n) = 2 for n = 2 + 2k (k=0,1,2,3,...);

a(n) = 3 for no values of n;

a(n) = 4 for n = 1 + 8k (k=0,1,2,3,...);

a(n) = 5 for n = 5 + 16k and 11 + 16k (k=0,1,2,3,...);

a(n) = 6 for no values of n;

a(n) = 7 for n = 3 + 64k, 7 + 64k, 29 + 64k, etc. (k=0,1,2,3,...).

Possible values for a(n) are: 2, 4, 5, 7, 8, 10, 12, 13, 15, 16, 18, 20, 21, 23, 24, 26, 27, 29, ... (A260593, sorted). Density is ~ 5/8.

Record values: 4, 7, 59, 81, 105, 135, 164, 165, 173, 176, 183, 224, 246, 287, 292, 298, 308, 376, 395, 398, 433, 447, 547, ....

And the records occur for n: 1, 3, 13, 351, 5043, 17827, 135135, 181171, 190863, 313165, 513715, 563007, 4044031, 6710835, 10319167, 13358335, 28462477, 31864063, 108870007, 600495895, 913698783, 1394004493, ....

Remember these n-values are the indices of odd numbers (A005408).

These are the bitmasks (or symmetric differences) obtained when the n-th iterate of 27 with Reduced Collatz-function R [= A372443(n), where R(n) = A000265(3*n+1)] is xored with that term of A086893 that has the same binary length. The binary expansions of the terms of A086893 are always of the form 10101...0101 (i.e., alternating 1's and 0's starting and ending with 1) when the binary length is odd, and of the form 110101...0101 (i.e., 1 followed by alternating 1's and 0's, and ending with 1) when n is even. Note that for all n >= 1, R(A086893(2n-1)) = 1, and R(A086893(2n)) = 5 (with R(5) = 1), so the first zero here, a(39) = 0 indicates that the iteration will soon have reached the terminal 1, and indeed, A372443(41) = 1.

Let N_1 be the set of odd natural numbers and v(y) the 2-adic valuation of y. Define the map F : N_1 -> N_1 by F(x) = (3*x+1)/2^v(3*x+1) (see A075677). Let F^(k)(x) denote k-fold iteration of F, with recurrence F^(k)(x) = F(F^(k-1)(x)), k > 0, and initial condition F^(0)(x) = x. Then, for n>0, a(n) is the least m such that F^(n)(4*m-3) == 1 (mod 4). Cf. A257499.

Let k == 1 mod 4, and k(r) be the r-th iteration at which k appears in a Collatz sequence. When n >= 2 and k(r) == [2^(n+1) - a(n)] mod 2^(n+1), then n is the number of halving steps following k(r+1). For instance, since a(5) = 11, there are 5 halving steps following k(r+1) when k(r) == 53 mod 64, because 2^(5+1) = 64 and 64-11 = 53; e.g., k(r) = 117: 117 -> 352 -> 176 -> 88 -> 44 -> 22 -> 11. - Bob Selcoe, Feb 09 2017

This is a modification of the reduced Collatz map given in A075677.

The Collatz conjecture is that iteration of the map fs leads to 1 for all positive odd integers.

In the Vaillant-Delarue (V-D) reference the present map fs: Odd -> Odd, 2*n+1 -> a(n) = fs(2*n+1), for n >= 0, is called f_{s}. The differences from b(n) = A075677(n+1) = fCr(2*n+1) (called f_{cr} in V-D) occur for the positions n = 2 + 4*k, for k >= 1: b(2 + 4*k) = b(k) = A075677(k+1) but a(2 + 4*k) = 1 + 2*k, which differs.

The advantage of the map fs (or a) over fCr (or b) is an explicit formula over a recurrence.

Additional steps are introduced in the iteration of fs versus fCr. This leads to an incomplete binary tree, called CfsTree, given in A324038. No such tree is available for fCr.

Such additional steps in fs can only occur after odd numbers congruent to 5 modulo 8: fs(5 + 8*k) = a(2 + 4*k) = 1 + 2*k and fs(1 + 2*k) = a(k). On the other hand, fCr(5 + 8*k) = b(2 + 4*k) = b(k).

The appearance of exactly N consecutive steps in fs versus fCr, for N >= 2, can be shown recursively to start with the odd numbers O(N;k) = 1 + 4*O(N-1;k), for N >= 3, with input O(2;k) = 53 + (4^3)*k. These are the numbers O(N;k) = A072197(N) + A000302(N+1)*k, for N >= 2. Therefore only one additional step follows directly after an odd number 5 (mod 8) if it is not of the O(N;k) type for N >= 2.

The minimal number of iterations of function fs acting on 2*n + 1 (or a acting on n), for n >= 0, to reach 1 is given in A324037 (if for very large n the number 1 should not be reached A324037(n) is set to -1).

When a(x) is iterated, what are the limit cycles? Are there any besides (1) and (17 -> 19 -> 43 -> 97 -> 109 -> 61)?

Up to 1000000000 every number eventually reaches one of those two cycles. In this range, the longest trajectory starts with n=458788881 and takes 193 steps to reach 1. - Christian Boyer (cboyer(AT)club-internet.fr), Sep 16 2006

This map is obtained from the array A(k, m) given in A347834. There all positive numbers congruent to 5 modulo 8 (A004770) appear uniquely in the columns for m >= 1, and the m = 0 column gives all numbers congruent to {1, 3, 7} (mod 8) (A047529). The surjective map is f: A004770 -> A047529, with b(n) = A004770(n) -> f(b(n)) = a(n).

See also the array A178415 which has permuted rows.

This maps all entries of each row k of the array A(k, m), given in A347834, with columns m >= 1 to the entry A(k, 0) = A047529(k), for k >= 1. The numbers b(n) appear once in the array A for columns m >= 1. Column A(k, 1) = A347836(k) gives the numbers congruent to {5, 32, 29} (mod 32), and each entry for columns m >= 2 is congruent to 21 (mod 32).

The surjective map of the numbers b(n) = 5 + 8*(n-1) = A004770(n), for n >= 1, to A047529 with element a(n), is computed by switching to the companion array A347839 of A347834, with the simple recurrence, removing all factors of 4, and then going back to array A347834. See the formula below. Thanks to Antti Karttunen for motivating me to simplify the prescription, and to add in A347834 the hint for the induction proof that all 5 (mod 8) numbers appear once in the columns n >= 1.

This map f is of interest in the context of the Collatz 3*n+1 conjecture. The (modified) rooted tree with only odd labeled nodes has for each row k of the array A(k, m) (A347834) the same precursor (or (modified) Collatz map given in A075677(n+1), for 2*n+1). Therefore, all nodes with labels b(n) == 5 (mod 8) can be represented by a(n). This leads to a further restricted Collatz tree with only node labels congruent to {1, 3, 7} (mod 8) (A047529).

An even further restricted Collatz tree has only node labels congruent to 1 (mod 8) (A017077), as any positive integer can be written as m*2^(v+1)+2^v-1 or (m,v) where v is the number of trailing 1-bits in binary, and for v > 1 the next odd Collatz successor of (m,v) is (3*m+1,v-1). - Ruud H.G. van Tol, Sep 13 2023