A257499 -id:A257499 - cp's OEIS frontend

A254067 Rectangular array A read by upward antidiagonals in which the entry in row n and column k is defined by A(n,k) = S(4*A257499(n,k) - 3), n,k >= 1, where the function S is as defined in A257480.

1, 8, 4, 5, 17, 7, 68, 32, 26, 10, 41, 149, 59, 35, 13, 608, 284, 230, 86, 44, 16, 365, 1337, 527, 311, 113, 53, 19, 5468, 2552, 2066, 770, 392, 140, 62, 22, 3281, 12029, 4739, 2795, 1013, 473, 167, 71, 25, 49208, 22964, 18590, 6926, 3524, 1256, 554, 194, 80, 28

Offset: 1

L. Edson Jeffery, May 02 2015

Theorem: For all indices n and k such that n + k > 2, log(A(n,k))/log(A257499(n,k)) < log_2(3).

Conjecture: Arranging the sequence in ascending order gives A189707 (positions of 0 in A189706).

			.       1      4      7     10     13     16     19     22     25     28
.       8     17     26     35     44     53     62     71     80     89
.       5     32     59     86    113    140    167    194    221    248
.      68    149    230    311    392    473    554    635    716    797
.      41    284    527    770   1013   1256   1499   1742   1985   2228
.     608   1337   2066   2795   3524   4253   4982   5711   6440   7169
.     365   2552   4739   6926   9113  11300  13487  15674  17861  20048
.    5468  12029  18590  25151  31712  38273  44834  51395  57956  64517
.    3281  22964  42647  62330  82013 101696 121379 141062 160745 180428
.   49208 108257 167306 226355 285404 344453 403502 462551 521600 580649

(* Array antidiagonals flattened: *)
v[x_] := IntegerExponent[x, 2]; f[x_] := (3*x + 1)/2^v[3*x + 1]; s[x_] := (3 + (3/2)^v[1 + f[x]] (1 + f[x]))/6; A257499[n_, k_] := (1 + 2^n*(6*k - 3 + 2*(-1)^n))/3; A254067[n_, k_] := s[4*A257499[n, k] - 3]; Flatten[Table[A254067[n - k + 1, k], {n, 10}, {k, n}]]

A(n,k) = S(4*A257499(n,k) - 3) = (3 + 3^n*(6*k - 3 + 2*(-1)^n))/6, where the function S is as defined in A257480.

For all k, A(1,k) <= A257499(1,k), and A(n,k) > A257499(n,k), for all n > 1.

A254131 Rectangular array A read by upward antidiagonals in which the entry in row n and column k is defined by A(n,k) = A254067(n,k) - A257499(n,k), n,k >= 1.

Original entry on oeis.org

0, 1, -1, 2, 2, -2, 41, 13, 3, -3, 30, 90, 24, 4, -4, 501, 209, 139, 35, 5, -5, 322, 1102, 388, 188, 46, 6, -6, 5041, 2253, 1703, 567, 237, 57, 7, -7, 3110, 11090, 4184, 2304, 746, 286, 68, 8, -8, 47501, 21769, 17139, 6115, 2905, 925, 335, 79, 9, -9

Offset: 1

L. Edson Jeffery, May 03 2015

			A begins:
.       0     -1     -2     -3     -4     -5     -6     -7     -8     -9
.       1      2      3      4      5      6      7      8      9     10
.       2     13     24     35     46     57     68     79     90    101
.      41     90    139    188    237    286    335    384    433    482
.      30    209    388    567    746    925   1104   1283   1462   1641
.     501   1102   1703   2304   2905   3506   4107   4708   5309   5910
.     322   2253   4184   6115   8046   9977  11908  13839  15770  17701
.    5041  11090  17139  23188  29237  35286  41335  47384  53433  59482
.    3110  21769  40428  59087  77746  96405 115064 133723 152382 171041
.   47501 104502 161503 218504 275505 332506 389507 446508 503509 560510

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

A(n,k) = (1 + (3^n - 2^(n + 1))*(6*k - 3 + 2*(-1)^n))/6, n,k >= 1.

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.

Original entry on oeis.org

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

A255138 a(n) = (1 + 2^n(3 + 2(-1)^n))/3.

Original entry on oeis.org

2, 1, 7, 3, 27, 11, 107, 43, 427, 171, 1707, 683, 6827, 2731, 27307, 10923, 109227, 43691, 436907, 174763, 1747627, 699051, 6990507, 2796203, 27962027, 11184811, 111848107, 44739243, 447392427, 178956971

Offset: 0

L. Edson Jeffery, May 04 2015

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

Index entries for linear recurrences with constant coefficients, signature (1,4,-4).

Cf. A007583, A075677, A096773, A136412, A257499.

[(1 + 2^n*(3 + 2*(-1)^n))/3: n in [0..50]]; // Wesley Ivan Hurt, Nov 05 2015

A255138:=n->(1 + 2^n*(3 + 2*(-1)^n))/3: seq(A255138(n), n=0..50); # Wesley Ivan Hurt, Nov 05 2015

a[n_] := (1 + 2^n*(3 + 2*(-1)^n))/3; Table[a[n], {n, 0, 29}]
LinearRecurrence[{1,4,-4},{2,1,7},30] (* Harvey P. Dale, Aug 03 2024 *)

vector(30, n, n--; (1 + 2^n*(3 + 2*(-1)^n))/3) \\ Altug Alkan, Nov 05 2015

a(2*n) = A136412(n); a(2*n+1) = A007583(n).
G.f.: (2-x-2*x^2)/((x-1)*(2*x-1)*(2*x+1)). - R. J. Mathar, Jul 25 2015
a(n) = a(n-1) + 4*a(n-2) - 4*a(n-3) for n > 2. - Wesley Ivan Hurt, Nov 05 2015
a(n) = 4*a(n-2) - 1. - Bob Selcoe, Feb 09 2017
a(n) = 2^(n+1) - A096773(n+1). - Ruud H.G. van Tol, Sep 04 2023

A257791 Rectangular array A read by upward antidiagonals in which the entry in row n and column k is defined by A(n,k) = 2^(n+1)(2k - 1), n,k >= 1.

Original entry on oeis.org

4, 8, 12, 16, 24, 20, 32, 48, 40, 28, 64, 96, 80, 56, 36, 128, 192, 160, 112, 72, 44, 256, 384, 320, 224, 144, 88, 52, 512, 768, 640, 448, 288, 176, 104, 60, 1024, 1536, 1280, 896, 576, 352, 208, 120, 68, 2048, 3072, 2560, 1792, 1152, 704, 416, 240, 136, 76

Offset: 1

L. Edson Jeffery, May 08 2015

Lemma: The sequence is a permutation of A008586\{0} = {4*m : m = 1,2,...}.

Proof: Write A(n,k)/4 = A054582(n-1,k-1). The sequence A054582 is known to be a permutation of the natural numbers, and the result follows. QED

			Array A begins:
.       4    12     20     28     36     44     52     60     68     76
.       8    24     40     56     72     88    104    120    136    152
.      16    48     80    112    144    176    208    240    272    304
.      32    96    160    224    288    352    416    480    544    608
.      64   192    320    448    576    704    832    960   1088   1216
.     128   384    640    896   1152   1408   1664   1920   2176   2432
.     256   768   1280   1792   2304   2816   3328   3840   4352   4864
.     512  1536   2560   3584   4608   5632   6656   7680   8704   9728
.    1024  3072   5120   7168   9216  11264  13312  15360  17408  19456
.    2048  6144  10240  14336  18432  22528  26624  30720  34816  38912

Cf. A000079 (powers of 2), A005408 (odd numbers), A008586 (multiples of 4), A014480, A054582.

Cf. A257499.

(* Array: *)
A257791[n_, k_] := 2^(n + 1)*(2*k - 1); Grid[Table[A257791[n, k], {n, 10}, {k, 10}]]
(* Array antidiagonals flattened: *)
Flatten[Table[2^(n - k + 2)*(2*k - 1), {n, 10}, {k, n}]]

A(n,n) = 4*A014480(n-1).

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

Original entry on oeis.org

1, 4, 3, 2, 8, 5, 14, 10, 12, 7, 6, 30, 18, 16, 9, 54, 38, 46, 26, 20, 11, 22, 118, 70, 62, 34, 24, 13, 214, 150, 182, 102, 78, 42, 28, 15, 86, 470, 278, 246, 134, 94, 50, 32, 17, 854, 598, 726, 406, 310, 166, 110, 58, 36, 19

Offset: 1

L. Edson Jeffery, May 29 2015

The sequence is a permutation of the natural numbers.

Theorem: Let v(y) denote the 2-adic valuation of y. For x an odd natural number, let F(x) = (3*x+1)/2^v(3*x+1) (see A075677). Row n of A is the set of all natural numbers m such that v(1+F(4*(2*m-1)-3)) = n.

			Array begins:
.      1     3     5     7     9    11    13    15    17     19
.      4     8    12    16    20    24    28    32    36     40
.      2    10    18    26    34    42    50    58    66     74
.     14    30    46    62    78    94   110   126   142    158
.      6    38    70   102   134   166   198   230   262    294
.     54   118   182   246   310   374   438   502   566    630
.     22   150   278   406   534   662   790   918  1046   1174
.    214   470   726   982  1238  1494  1750  2006  2262   2518
.     86   598  1110  1622  2134  2646  3158  3670  4182   4694
.    854  1878  2902  3926  4950  5974  6998  8022  9046  10070

Cf. A005408, A008586, A017089 (rows 1-3).

Cf. A075677, A257480, A257499.

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

A(n,k) = (1 + A257499(n,k))/2.

cp's OEIS Frontend

A254067 Rectangular array A read by upward antidiagonals in which the entry in row n and column k is defined by A(n,k) = S(4*A257499(n,k) - 3), n,k >= 1, where the function S is as defined in A257480.

Views

Author

Keywords

Comments

Examples

Programs

Mathematica

Formula

A254131 Rectangular array A read by upward antidiagonals in which the entry in row n and column k is defined by A(n,k) = A254067(n,k) - A257499(n,k), n,k >= 1.

Views

Author

Keywords

Examples

Programs

Mathematica

Formula

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

A255138 a(n) = (1 + 2^n*(3 + 2*(-1)^n))/3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A257791 Rectangular array A read by upward antidiagonals in which the entry in row n and column k is defined by A(n,k) = 2^(n+1)*(2*k - 1), n,k >= 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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.

A255138 a(n) = (1 + 2^n(3 + 2(-1)^n))/3.

A257791 Rectangular array A read by upward antidiagonals in which the entry in row n and column k is defined by A(n,k) = 2^(n+1)(2k - 1), n,k >= 1.

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