A241957 -id:A241957 - 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

A075300 Array A read by antidiagonals upwards: A(n, k) = array A054582(n,k) - 1 = 2^n(2k+1) - 1 with n,k >= 0.

Original entry on oeis.org

0, 1, 2, 3, 5, 4, 7, 11, 9, 6, 15, 23, 19, 13, 8, 31, 47, 39, 27, 17, 10, 63, 95, 79, 55, 35, 21, 12, 127, 191, 159, 111, 71, 43, 25, 14, 255, 383, 319, 223, 143, 87, 51, 29, 16, 511, 767, 639, 447, 287, 175, 103, 59, 33, 18, 1023, 1535, 1279, 895, 575, 351, 207, 119

Offset: 0

Antti Karttunen, Sep 12 2002

From Philippe Deléham, Feb 19 2014: (Start)
A(0,k)  = 2*k = A005843(k),
A(1,k)  = 4*k + 1 = A016813(k),
A(2,k)  = 8*k + 3 = A017101(k),
A(n,0)  = A000225(n),
A(n,1)  = A153893(n),
A(n,2)  = A153894(n),
A(n,3)  = A086224(n),
A(n,4)  = A052996(n+2),
A(n,5)  = A086225(n),
A(n,6)  = A198274(n),
A(n,7)  = A238087(n),
A(n,8)  = A198275(n),
A(n,9)  = A198276(n),
A(n,10) = A171389(n). (End)
A permutation of the nonnegative integers. - Alzhekeyev Ascar M, Jun 05 2016
The values in array row n, when expressed in binary, have n trailing 1-bits. - Ruud H.G. van Tol, Mar 18 2025

			The array A begins:
   0    2    4    6    8   10   12   14   16   18 ...
   1    5    9   13   17   21   25   29   33   37 ...
   3   11   19   27   35   43   51   59   67   75 ...
   7   23   39   55   71   87  103  119  135  151 ...
  15   47   79  111  143  175  207  239  271  303 ...
  31   95  159  223  287  351  415  479  543  607 ...
  ... - _Philippe Deléham_, Feb 19 2014
From _Wolfdieter Lang_, Jan 31 2019: (Start)
The triangle T begins:
   n\k   0    1    2   3   4   5   6   7  8  9 10 ...
   0:    0
   1:    1    2
   2:    3    5    4
   3:    7   11    9   6
   4:   15   23   19  13   8
   5    31   47   39  27  17  10
   6:   63   95   79  55  35  21  12
   7:  127  191  159 111  71  43  25  14
   8:  255  383  319 223 143  87  51  29 16
   9:  511  767  639 447 287 175 103  59 33 18
  10: 1023 1535 1279 895 575 351 207 119 67 37 20
  ...
T(3, 1) = 2^2*(2*1+1) - 1 = 12 - 1 = 11.  (End)

Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A075301. Transpose: A075302. The X-projection is given by A007814(n+1) and the Y-projection A025480.

Cf. A002262, A025581, A054582, A241957.

A075300bi := (x,y) -> (2^x * (2*y + 1))-1;
A075300 := n -> A075300bi(A025581(n), A002262(n));
A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);
A025581 := n -> binomial(1+floor((1/2)+sqrt(2*(1+n))),2) - (n+1);

Table[(2^# (2 k + 1)) - 1 &[m - k], {m, 0, 10}, {k, 0, m}] (* Michael De Vlieger, Jun 05 2016 *)

From Wolfdieter Lang, Jan 31 2019: (Start)
Array A(n, k) = 2^n*(2*k+1) - 1, for n >= 0 and m >= 0.
The triangle is T(n, k) = A(n-k, k) = 2^(n-k)*(2*k+1) - 1, n >= 0, k=0..n.
See also A054582 after subtracting 1. (End)
From Ruud H.G. van Tol, Mar 17 2025: (Start)
A(0, k) is even. For n > 0, A(n, k) is odd and (3 * A(n, k) + 1) / 2 = A(n-1, 3*k+1).
A(n, k) = 2^n - 1 (mod 2^(n+1)) (equivalent to the comment about trailing 1-bits). (End)

A191664 Dispersion of A014601 (numbers >2, congruent to 0 or 3 mod 4), by antidiagonals.

Original entry on oeis.org

1, 3, 2, 7, 4, 5, 15, 8, 11, 6, 31, 16, 23, 12, 9, 63, 32, 47, 24, 19, 10, 127, 64, 95, 48, 39, 20, 13, 255, 128, 191, 96, 79, 40, 27, 14, 511, 256, 383, 192, 159, 80, 55, 28, 17, 1023, 512, 767, 384, 319, 160, 111, 56, 35, 18, 2047, 1024, 1535, 768, 639

Offset: 1

Clark Kimberling, Jun 11 2011

Row 1:  A000225 (-1+2^n)
Row 2:  A000079 (2^n)
Row 3:  A055010
Row 4:  3*A000079
Row 5:  A153894
Row 6:  5*A000079
Row 7:  A086224
Row 8:  A005009
Row 9:  A052996
For a background discussion of dispersions, see A191426.
...
Each of the sequences (4n, n>2), (4n+1, n>0), (3n+2, n>=0), generates a dispersion.  Each complement (beginning with its first term >1) also generates a dispersion.  The six sequences and dispersions are listed here:
...
A191663=dispersion of A042948 (0 or 1 mod 4 and >1)
A054582=dispersion of A005843 (0 or 2 mod 4 and >1; evens)
A191664=dispersion of A014601 (0 or 3 mod 4 and >1)
A191665=dispersion of A042963 (1 or 2 mod 4 and >1)
A191448=dispersion of A005408 (1 or 3 mod 4 and >1, odds)
A191666=dispersion of A042964 (2 or 3 mod 4)
...
EXCEPT for at most 2 initial terms (so that column 1 always starts with 1):
A191663 has 1st col A042964, all else A042948
A054582 has 1st col A005408, all else A005843
A191664 has 1st col A042963, all else A014601
A191665 has 1st col A014601, all else A042963
A191448 has 1st col A005843, all else A005408
A191666 has 1st col A042948, all else A042964
...
There is a formula for sequences of the type "(a or b mod m)", (as in the Mathematica program below):
   If f(n)=(n mod 2), then (a,b,a,b,a,b,...) is given by
   a*f(n+1)+b*f(n), so that "(a or b mod m)" is given by
   a*f(n+1)+b*f(n)+m*floor((n-1)/2)), for n>=1.
This sequence is a permutation of the natural numbers.  - L. Edson Jeffery, Aug 13 2014

			Northwest corner:
1...3...7....15...31
2...4...8....16...32
5...11..23...47...95
6...12..24...48...96
9...19..39...79...159

Ivan Neretin, Table of n, a(n) for n = 1..5050 (first 100 antidiagonals, flattened)

Cf. A042963, A014601, A191665, A191426.

Cf. A241957.

(* Program generates the dispersion array T of the increasing sequence f[n] *)
r = 40; r1 = 12;  c = 40; c1 = 12;
a = 3; b = 4; m[n_] := If[Mod[n, 2] == 0, 1, 0];
f[n_] := a*m[n + 1] + b*m[n] + 4*Floor[(n - 1)/2]
Table[f[n], {n, 1, 30}]  (* A014601(n+2): (4+4k,5+4k) *)
mex[list_] := NestWhile[#1 + 1 &, 1, Union[list][[#1]] <= #1 &, 1, Length[Union[list]]]
rows = {NestList[f, 1, c]};
Do[rows = Append[rows, NestList[f, mex[Flatten[rows]], r]], {r}];
t[i_, j_] := rows[[i, j]];
TableForm[Table[t[i, j], {i, 1, 10}, {j, 1, 10}]] (* A191664 *)
Flatten[Table[t[k, n - k + 1], {n, 1, c1}, {k, 1, n}]] (* A191664  *)
(* Clark Kimberling, Jun 11 2011 *)
Grid[Table[2^k*(2*Floor[(n + 1)/2] - 1) - Mod[n, 2], {n, 12}, {k, 12}]] (* L. Edson Jeffery, Aug 13 2014 *)

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

A075300 Array A read by antidiagonals upwards: A(n, k) = array A054582(n,k) - 1 = 2^n(2k+1) - 1 with n,k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A191664 Dispersion of A014601 (numbers >2, congruent to 0 or 3 mod 4), by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A075300 Array A read by antidiagonals upwards: A(n, k) = array A054582(n,k) - 1 = 2^n*(2*k+1) - 1 with n,k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A191664 Dispersion of A014601 (numbers >2, congruent to 0 or 3 mod 4), by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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.

A075300 Array A read by antidiagonals upwards: A(n, k) = array A054582(n,k) - 1 = 2^n(2k+1) - 1 with n,k >= 0.