cp's OEIS Frontend

In the following, let F^(k)(x) denote k-fold iteration of F and defined by the recurrence F^(k)(x) = F(F^(k-1)(x)), k > 0, with initial condition F^(0)(x) = x, and let S^(k)(n) denote k-fold iteration of S and defined by the recurrence S^(k)(n) = S(S^(k-1)(n)), k > 0, with initial condition S^(0)(n) = n, where F and S are as defined above.

Theorem 1: For each x, there exists a j>0 such that F^(j)(x) == 1 (mod 4).

Theorem 2: S(n) = m if and only if S(4*n-2) = m.

Conjecture 1: For each n, there exists a k such that S^(k)(n) = 1.

Theorem 3: Conjecture 1 is equivalent to the 3x+1 conjecture.

Theorem 4: The sequence {log(S(n))/log(n)}_{n>1} is bounded with least upper bound equal to log(3)/log(2).

[I have proved Theorems 1--4 (along with several lemmas) and am trying to finish typesetting the draft containing the proofs but had been too ill to finish that work until now. The draft also contains the derivation of the function S from properties of the known function F (A075677). When that paper is completed (hopefully within two weeks) I will then upload it to the links section and delete this comment.]

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.