A255138 -id:A255138 - cp's OEIS frontend

A257480 S(n) = (3 + (3/2)^v(1 + F(4n - 3))(1 + F(4n - 3)))/6, n >= 1, where F(x) = (3x + 1)/2^v(3*x + 1) for x odd, and v(y) denotes the 2-adic valuation of y.

1, 1, 5, 2, 4, 1, 8, 5, 7, 5, 41, 5, 10, 2, 17, 14, 13, 4, 32, 8, 16, 1, 26, 14, 19, 8, 68, 11, 22, 5, 35, 41, 25, 7, 59, 14, 28, 5, 44, 23, 31, 41, 365, 17, 34, 5, 53, 41, 37, 10, 86, 20, 40, 2, 62, 32, 43, 17, 149

Offset: 1

L. Edson Jeffery, Apr 26 2015

nonn

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

K. H. Metzger, Untersuchungen zum (3n+1)-Algorithmus, Teil II: Die Konstruktion des Zahlenbaums, PM (Praxis der Mathematik in der Schule) 42, 2000, 27-32.

I. Korec and Štefan Znám, A Note on the 3x+1 Problem, Amer. Math. Monthly 94, 1987, pp. 771-772.
J. C. Lagarias, The 3x + 1 Problem and Its Generalizations, Amer. Math. Monthly 92, 1985, pp. 3-23.
J. C. Lagarias, The 3x+1 Problem: An Annotated Bibliography (1963-2000), arXiv:math/0309224 [math.NT], 2003-2011.
J. C. Lagarias, The 3x+1 Problem: an annotated bibliography, II (2000-2009), arXiv:math/0608208 [math.NT], 2006-2012.

Cf. A006370, A070165, A075677, A256598.
Cf. A241957, A254067, A254311, A257499, A257791 (all used in the proof of Thm 4).
Cf. A253676 (iteration of S terminating at the first occurrence of 1, assuming the 3x+1 conjecture).
Cf. A253720, A254068, A254070, A254131, A254312, A255138, A255168, A258415.

v[x_] := IntegerExponent[x, 2]; f[x_] := (3*x + 1)/2^v[3*x + 1]; s[n_] := (3 + (3/2)^v[1 + f[4*n - 3]]*(1 + f[4*n - 3]))/6; Table[s[n], {n, 59}]

a(n) = my(x=3*n-2, v=valuation(x, 2)); x>>=v; v=valuation(x+1, 2); (((x>>v)+1)*3^(v-1)+1)/2; \\ Ruud H.G. van Tol, Jul 30 2023

A257499 Array A read by upward antidiagonals in which the entry in row n and column k is defined by A(n,k) = (1 + 2^n(6k-3+2*(-1)^n))/3, n,k >= 1.

Original entry on oeis.org

1, 7, 5, 3, 15, 9, 27, 19, 23, 13, 11, 59, 35, 31, 17, 107, 75, 91, 51, 39, 21, 43, 235, 139, 123, 67, 47, 25, 427, 299, 363, 203, 155, 83, 55, 29, 171, 939, 555, 491, 267, 187, 99, 63, 33, 1707, 1195, 1451, 811, 619, 331, 219, 115, 71, 37

Offset: 1

L. Edson Jeffery, Apr 27 2015

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.

			Array A begins:
.       1     5     9    13    17     21     25     29     33     37
.       7    15    23    31    39     47     55     63     71     79
.       3    19    35    51    67     83     99    115    131    147
.      27    59    91   123   155    187    219    251    283    315
.      11    75   139   203   267    331    395    459    523    587
.     107   235   363   491   619    747    875   1003   1131   1259
.      43   299   555   811  1067   1323   1579   1835   2091   2347
.     427   939  1451  1963  2475   2987   3499   4011   4523   5035
.     171  1195  2219  3243  4267   5291   6315   7339   8363   9387
.    1707  3755  5803  7851  9899  11947  13995  16043  18091  20139

Max Alekseyev, Proof of conjecture in A257499, Sequence fanatics mailing list, April 29 and May 01, 2015

Cf. A007814, A075677, A254067, A257480.

Cf. A255138 (column 1).

(* Array: *)
Grid[Table[(1 + 2^n*(6*k - 3 + 2*(-1)^n))/3, {n, 10}, {k, 10}]]
(* Array antidiagonals flattened: *)
Flatten[Table[(1 + 2^(n - k + 1)*(6*k - 3 + 2*(-1)^(n - k + 1)))/3, {n, 10}, {k, n}]]

A364602 Triangle T(n,k) with rows of length 2n-1, generated by T(1,1)=0, T(n,1)=T(n-1,1)+2, T(n,2)=4(n-1)-1, and for k>=3, T(n,k)=4*T(n-1,k-2)+1.

Original entry on oeis.org

0, 2, 3, 1, 4, 7, 9, 13, 5, 6, 11, 17, 29, 37, 53, 21, 8, 15, 25, 45, 69, 117, 149, 213, 85, 10, 19, 33, 61, 101, 181, 277, 469, 597, 853, 341, 12, 23, 41, 77, 133, 245, 405, 725, 1109, 1877, 2389, 3413, 1365, 14, 27, 49, 93, 165, 309, 533, 981, 1621, 2901

Offset: 1

Ruud H.G. van Tol, Jul 29 2023

The sequence is a permutation of all integers >= 0.
Each row of T contains n*2-1 terms; the terms in column k increase by 2^k.
T(1,1) = 0; T(2,2) = 3.
T(2,1) = T(1,1)+2 = 2; T(2,3) = 4*T(1,1)+1 = 1 ("knight jump").
In the context of the 3x+1 problem, when a term x is used to represent the odd 4*x+1, its successor is 3*x+1, and k-1 is the 2-adic valuation of 3*x+1.
Right diagonal is A002450.
The terms at the top of the columns are A096773(k), or (2^(k-1)*(3 + 2*(-1)^k) - 1)/3.
When the table is analytically continued upwards by subtracting 2^k, the first layer of values are -A255138(k), or -(2^k*(3 + 2*(-1)^k) + 1)/3.

			Triangle T(n,k) begins:
n/k 1| 2| 3| 4|  5|  6|  7|  8|  9| 10| 11|
1|  0
2|  2  3  1
3|  4  7  9 13   5
4|  6 11 17 29  37  53  21
5|  8 15 25 45  69 117 149 213  85
6| 10 19 33 61 101 181 277 469 597 853 341
7| 12 ...

Cf. A002450, A007310, A071797, A087445, A096773, A255138, A257480.

my(N=8, v=Vec([0, 2, 3, 1], N^2), p=4); for(n=3, N, my(K=2*n-1); for(k=1, K, v[p+k]=if(k<=2, v[p-K+k+2]+2^k, 4*v[p-K+k]+1)); p+=K); v

T(n, k) = 2^k*(n-(6*k+3-(-1)^k)/12)-1/3;

n_of_x(x) = my(n=0); while(1==x%4, x>>=2; n++); n + if(x%2,(x+1)/4,  x/2) + 1;

PARI
```
k_of_x(x) = valuation(3*x+1,2) + 1;
```

For n>1, T(n,k) = T(n-1,k) + 2^k, so T(n,1) = 2*(n-1).
T(n,2) = 4*(n-1)-1 = 2*T(n,1)-1, so T(2,2) = 3.
For n>1 and k>2, T(n,k) = 4*T(n-1,k-2)+1, so T(2,3) = 1.
For i>=0, a(i^2+1) = T(i+1,1).
T(n, k) = 2^k * (n - (6*k + 3 - (-1)^k)/12) - 1/3.
T(n,1) == 0 (mod 2); T(n,2) == 3 (mod 4); T(n,k>=3) == 1 (mod 4).
k = v2(3*T(n,k)+1) + 1, where v2(x) = A007814(x) is the 2-adic valuation of x.

cp's OEIS Frontend

A257480 S(n) = (3 + (3/2)^v(1 + F(4n - 3))(1 + F(4n - 3)))/6, n >= 1, where F(x) = (3x + 1)/2^v(3*x + 1) for x odd, and v(y) denotes the 2-adic valuation of y.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

A257499 Array A read by upward antidiagonals in which the entry in row n and column k is defined by A(n,k) = (1 + 2^n(6k-3+2*(-1)^n))/3, n,k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A364602 Triangle T(n,k) with rows of length 2n-1, generated by T(1,1)=0, T(n,1)=T(n-1,1)+2, T(n,2)=4(n-1)-1, and for k>=3, T(n,k)=4*T(n-1,k-2)+1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

PARI

PARI

PARI

Formula

cp's OEIS Frontend

A257480 S(n) = (3 + (3/2)^v(1 + F(4*n - 3))*(1 + F(4*n - 3)))/6, n >= 1, where F(x) = (3*x + 1)/2^v(3*x + 1) for x odd, and v(y) denotes the 2-adic valuation of y.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

A257499 Array A read by upward antidiagonals in which the entry in row n and column k is defined by A(n,k) = (1 + 2^n*(6*k-3+2*(-1)^n))/3, n,k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A364602 Triangle T(n,k) with rows of length 2*n-1, generated by T(1,1)=0, T(n,1)=T(n-1,1)+2, T(n,2)=4*(n-1)-1, and for k>=3, T(n,k)=4*T(n-1,k-2)+1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

PARI

PARI

PARI

Formula

A257480 S(n) = (3 + (3/2)^v(1 + F(4n - 3))(1 + F(4n - 3)))/6, n >= 1, where F(x) = (3x + 1)/2^v(3*x + 1) for x odd, and v(y) denotes the 2-adic valuation of y.

A257499 Array A read by upward antidiagonals in which the entry in row n and column k is defined by A(n,k) = (1 + 2^n(6k-3+2*(-1)^n))/3, n,k >= 1.

A364602 Triangle T(n,k) with rows of length 2n-1, generated by T(1,1)=0, T(n,1)=T(n-1,1)+2, T(n,2)=4(n-1)-1, and for k>=3, T(n,k)=4*T(n-1,k-2)+1.