A075677 -id:A075677 - cp's OEIS frontend

A363270 The result, starting from n, of Collatz steps x -> (3x+1)/2 while odd, followed by x -> x/2 while even.

1, 1, 1, 1, 1, 3, 13, 1, 7, 5, 13, 3, 5, 7, 5, 1, 13, 9, 11, 5, 1, 11, 5, 3, 19, 13, 31, 7, 11, 15, 121, 1, 25, 17, 5, 9, 7, 19, 67, 5, 31, 21, 49, 11, 17, 23, 121, 3, 37, 25, 29, 13, 5, 27, 47, 7, 43, 29, 67, 15, 23, 31, 91, 1, 49, 33, 19, 17, 13, 35, 121, 9, 55

Offset: 1

Dustin Theriault, May 23 2023

Each x -> (3x+1)/2 step decreases the number of trailing 1-bits by 1 so A007814(n+1) of them, and the result of those steps is 2*A085062(n).

Dustin Theriault, Table of n, a(n) for n = 1..10000

Cf. A000265, A085062.
Cf. A160541 (number of iterations).
Cf. A075677.

int a(int n) {
  while (n & 1) n += (n >> 1) + 1;
  while (!(n & 1)) n >>= 1;
  return n;
}

OddPart[x_] := x / 2^IntegerExponent[x, 2]
Table[OddPart[(3/2)^IntegerExponent[i + 1, 2] * (i + 1) - 1], {i, 100}]

oddpart(n) = n >> valuation(n, 2); \\ A000265
a(n) = oddpart((3/2)^valuation(n+1, 2)*(n+1) - 1); \\ Michel Marcus, May 24 2023

a(n) = OddPart((3/2)^A007814(n+1)*(n+1) - 1), where OddPart(t) = A000265(t).

a(n) = OddPart(A085062(n)).

A254068 Irregular triangle T read by rows in which the entry in row n and column k is given by T(n,k) = 4*A253676(n,k) - 3, k = 1..A253720(n), assuming the 3x+1 (or Collatz) conjecture.

Original entry on oeis.org

1, 5, 1, 9, 17, 13, 5, 1, 13, 5, 1, 17, 13, 5, 1, 21, 1, 25, 29, 17, 13, 5, 1, 29, 17, 13, 5, 1, 33, 25, 29, 17, 13, 5, 1, 37, 17, 13, 5, 1, 41, 161, 121, 137, 233, 593, 445, 377, 425, 2429, 3077, 577, 433, 325, 61, 53, 5, 1, 45, 17, 13, 5, 1

Offset: 1

L. Edson Jeffery, May 03 2015

Definitions: Let v(y) denote the 2-adic valuation of y. Let N_1 denote the set of odd natural numbers. Let F : N_1 -> N_1 be the map defined by F(x) = (3*x + 1)/2^v(3*x + 1) (cf. A075677). 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.
This triangle can be constructed by restricting the initial values to the numbers 4*n - 3, iterating F until 1 is reached (assuming the 3x+1 conjecture) and removing all iterates not congruent to 1 modulo 4. Equivalently, for each n, this is accomplished by iterating (until 1 is reached, assuming the 3x+1 conjecture) the function S defined in A257480 to get the triangle A253676, and finally taking T(n,k) = 4*A253676(n,k) - 3.
Conjecture: For each natural number n, there exists a k >= 0, such that F^k(4*n - 3) = 1.
Theorem 1: Conjecture 1 is equivalent to the 3x+1 (or Collatz) conjecture.
Proof: See A257480.

			T begins:
   1
   5   1
   9  17  13   5   1
  13   5   1
  17  13   5   1
  21   1
  25  29  17  13   5   1
  29  17  13   5   1
  33  25  29  17  13   5   1
  37  17  13   5   1
  41 161 121 137 233 593 445 377 425 2429 3077 577 433 325 61 53 5 1
  45  17  13   5   1
  49  37  17  13   5   1
  53   5   1
  57  65  49  37  17  13   5   1

Cf. A014682, A070165, A075677, A256598, A257480, A253676, A254070.

v[x_] := IntegerExponent[x, 2]; f[x_] := (3*x + 1)/2^v[3*x + 1]; s[n_] := NestWhileList[(3 + (3/2)^v[1 + f[4*# - 3]]*(1 + f[4*# - 3]))/6 &, n, # > 1 &]; t = Table[4*s[n] - 3, {n, 1, 15}]; Flatten[t] (* Replace Flatten with Grid to display the triangle *)

A160322 a(n) = min(A160198(n), A160267(n)).

Original entry on oeis.org

2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2

Offset: 1

Vladimir Shevelev, May 08 2009, May 11 2009

nonn

Let f be defined as in A159885. Then a(n) is the least k such that either f^k(2n+1))<2n+1 or A000120(f^k(2n+1)) < A000120(2n+1) or A006694((f^k(2n+1)-1)/2) < A006694(n).

In connection with A160198, A160267, A160322 we pose a new (3x+1)-problem: does there exist a finite number of sequences A_i(n), i=1,...,T, such that: 1) A_i(0)=0 and A_i(n)>0 for n>=1; 2) if B_i(n) denotes the least k for which A_i(n)>A_i((f^k(2n+1)-1)/2), then B(n)=min_{i=1,...,T}B_i(n)=1 for every n>=1? Note that this problem is weaker than (3x+1)-Collatz problem. Indeed, if the Collatz conjecture is true, then there exist nonnegative sequences A(n) for which A(0)=0 and A(n)>A((f(2n+1)-1)/2) for every n>=1 (see A160348). - Vladimir Shevelev, May 15 2009

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A000120, A006694, A122458, A159885, A159945, A160198, A160266, A160267.

f(n) = ((3*((n-1)/2))+2)/A006519((3*((n-1)/2))+2); \\ Defined for odd n only. Cf. A075677.
A006519(n) = (1<A006694(n) = (sumdiv(2*n+1, d, eulerphi(d)/znorder(Mod(2, d))) - 1); \\ From A006694
A160322(n) = { my(v=A006694(n), u = (n+n+1), w = hammingweight(u), k=0); while((u >= (n+n+1))&&(hammingweight(u) >= w)&&(A006694((u-1)/2) >= v), k++; u = f(u)); (k); }; \\ Antti Karttunen, Sep 25 2018

a(n) = min(A122458(n), A159885(n), A160266(n)). - Antti Karttunen, Sep 25 2018

a(1) corrected and sequence extended by Antti Karttunen, Sep 25 2018

A246425 In the Collatz 3x+1 problem: start at an odd number 2n+1 and find the next odd number 2m+1 in the trajectory; then a(n) = m-n.

Original entry on oeis.org

0, 1, -2, 2, -1, 3, -4, 4, -2, 5, -10, 6, -3, 7, -9, 8, -4, 9, -15, 10, -5, 11, -14, 12, -6, 13, -24, 14, -7, 15, -19, 16, -8, 17, -28, 18, -9, 19, -24, 20, -10, 21, -42, 22, -11, 23, -29, 24, -12, 25, -41, 26, -13, 27, -34, 28, -14, 29, -53, 30, -15, 31, -39, 32, -16, 33, -54, 34, -17, 35, -44, 36, -18, 37, -71, 38, -19, 39, -49, 40, -20, 41, -67, 42, -21, 43, -54, 44, -22, 45, -82, 46, -23, 47, -59, 48, -24, 49, -80, 50

Offset: 0

K. G. Stier, Aug 26 2014

Positive terms indicate the next odd number 2m+1 in the trajectory is greater than 2n+1 which is the case every second time giving a(n) = m-n = (n+1)/2.

Negative terms indicate the next odd number 2m+1 in the trajectory is smaller than 2n+1. For behavior of this part refer to A087230.

			a(14)=-9 because 2*14 + 1 = 29 and the Collatz trajectory to reach the next odd number goes: 29, 88, 44, 22, 11. Thus, m=5 and 5 - 14 = -9.

Ruud H.G. van Tol, Table of n, a(n) for n = 0..20000
Ruud H.G. van Tol, Perl program
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A005408, A075677, A087230, A349414.

f:= proc(n) local m;
   m:= 6*n+4;
   m/2^(1+padic:-ordp(m,2))-n-1/2
end proc:
map(f, [$0..100]); # Robert Israel, Mar 22 2020

a[n_] := ((6n+4)/2^IntegerExponent[6n+4, 2] - (2n+1))/2;
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, May 15 2023 *)

forstep(n=0, 1000, 1, m=6*n+4; print1(((m/2^valuation(m, 2)-(2*n+1))/2),", "))

a(n) = ((6*n+4)/2^A087230(n) - (2*n+1))/2.

A324037 The minimal number of iterations to reach 1 of the modified reduced Collatz function, defined for odd numbers 1 + 2*n in A324036 (assuming the Collatz conjecture).

Original entry on oeis.org

0, 2, 1, 6, 7, 5, 3, 7, 4, 8, 2, 6, 9, 48, 7, 46, 10, 5, 8, 14, 47, 11, 6, 45, 9, 10, 4, 49, 12, 13, 8, 47, 10, 11, 5, 44, 50, 5, 9, 15, 9, 48, 3, 12, 12, 40, 7, 46, 51, 10, 10, 38, 16, 43, 49, 30, 4, 13, 8, 14, 41, 19, 47, 20, 52, 11, 11, 16, 39, 17, 6

Offset: 0

Nicolas Vaillant, Philippe Delarue, Wolfdieter Lang, May 09 2019

nonn

The Collatz conjecture is that a(n) is finite. If 1 should never be reached then a(n) = -1.
Compare this sequence with the analogous one A075680(n+1) for the reduced Collatz map of A075677.
a(n) gives also the minimal number of iterations of the Vaillant-Delarue map f, defined in A324245, acting on n to reach 0 (assuming the Collatz conjecture).
For the link to the Vaillant-Delarue paper (where fs is called f_s) see A324036.

			a(4) = 7 because 1 + 2*4 = 9 and the 7 fs iterations acting on 9 are 7, 11, 17, 13, 3, 5, 1.
Compare this to the reduced Collatz map given in A075677 which needs only 6 = A075680(5) iterations 7, 11, 17, 13, 5, 1. The additional step in the fs case follows 13 == 5 mod(8).

Cf. A075677, A075680(n+1), A324036, A324245.

fs^[a(n)](1 + 2*n) = 1 but fs^[a(n)-1](1 + 2*n) is not 1 (for all n with finite a(n)), where fs is the modified reduced Collatz map defined for 1 + 2*n in A324036(n), for n >= 1, and a(0) = 0.

A373730 Reduced Collatz function R applied to the numbers 6n+1: a(n) = R(6n+1), where R(k) = (3k+1)/2^r, with r as large as possible.

Original entry on oeis.org

1, 11, 5, 29, 19, 47, 7, 65, 37, 83, 23, 101, 55, 119, 1, 137, 73, 155, 41, 173, 91, 191, 25, 209, 109, 227, 59, 245, 127, 263, 17, 281, 145, 299, 77, 317, 163, 335, 43, 353, 181, 371, 95, 389, 199, 407, 13, 425, 217, 443, 113, 461, 235, 479, 61, 497, 253, 515

Offset: 0

Jonas Kaiser, Jun 17 2024

Paolo Xausa, Table of n, a(n) for n = 0..10000

Cf. A000265, A017185, A075677, A260658.

A373730[n_] := #/2^IntegerExponent[#, 2] & [9*n + 2];
Array[A373730, 100, 0] (* Paolo Xausa, Aug 19 2024 *)

PARI
```
a(n) = n=9*n+2; n>>valuation(n,2);
```

a(n) = A000265(A017185(n)).

A166466 Trisection a(n) = A000265(3n).

Original entry on oeis.org

3, 3, 9, 3, 15, 9, 21, 3, 27, 15, 33, 9, 39, 21, 45, 3, 51, 27, 57, 15, 63, 33, 69, 9, 75, 39, 81, 21, 87, 45, 93, 3, 99, 51, 105, 27, 111, 57, 117, 15, 123, 63, 129, 33, 135, 69, 141, 9, 147, 75, 153, 39, 159, 81, 165, 21, 171, 87, 177, 45, 183, 93, 189, 3, 195, 99, 201, 51

Offset: 1

Paul Curtz, Oct 14 2009

The other trisections are A067745 and A075677.

G. C. Greubel, Table of n, a(n) for n = 1..10000

Cf. A000265, A007283, A067745, A075677.

A166466:= func< n | 3*n/2^Valuation(n,2) >;
[A166466(n): n in [1..120]]; // G. C. Greubel, Jul 31 2024

A166468 := proc(n) A000265(3*n) ; end: seq(A166468(n),n=1..80) ; # R. J. Mathar, Oct 21 2009

A166466[n_]:= If[n==0, 0, 3*n/2^IntegerExponent[n, 2]];
Table[A166466[n], {n,100}] (* based on Michael Somos's code of A000265 *) (* G. C. Greubel, Jul 31 2024 *)

a(n)=3*n>>valuation(n,2);
vector(100,n,a(n))  \\ Joerg Arndt, Aug 01 2024

def A166466(n): return 3*n//2^valuation(n,2)
[A166466(n) for n in (1..121)] # G. C. Greubel, Jul 31 2024

A000265(A007283(n)) = 3. a(A007283(n)) = 9.
a(n) = 3*A000265(n).
Sum_{k=1..n} a(k) ~ n^2. - Amiram Eldar, Aug 30 2024

Comments turned into formulas by R. J. Mathar, Oct 21 2009

A182078 Odd numbers n such that the reduced Collatz map n -> (3n+1)/2^k gives a trajectory of decreasing odd numbers.

Original entry on oeis.org

5, 13, 17, 21, 45, 53, 69, 85, 113, 141, 181, 213, 241, 277, 301, 321, 341, 369, 401, 453, 565, 725, 753, 853, 909, 965, 1069, 1109, 1137, 1205, 1285, 1365, 1425, 1477, 1605, 1713, 1813, 1933, 1969, 2261, 2417, 2573, 2577, 2625, 2901, 2957, 3013, 3213, 3413

Offset: 1

Michel Lagneau, Apr 10 2012

nonn

			45 is in the sequence because 45 generates the trajectory of odd numbers : 45 -> 17 -> -> 13 -> 5 -> 1.

Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006666, A075677 (reduced Collatz map), A256598 (trajectory).

for n from 3 by 2 to 5000 do:i:=0:x:=n:n0:=n: u0:=0:for it from 1 to 1000 while(n0<>1 and u0=0) do: for a from 1 to 100 while(x mod 2 = 0 ) do: i:=i+1:x:=x/2: od:if x > n0 then u0:=1:else i:=i+1:n0:=x :x:=3*n0+1: fi:od: if u0=0 then printf(`%d, `,n):else fi:od:

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.

A273692 a(n) is the denominator of 2*O(n+1) - O(n+2) where O(n) = n/2^n, the n-th Oresme number.

Original entry on oeis.org

2, 8, 2, 32, 32, 128, 64, 512, 512, 2048, 128, 8192, 8192, 32768, 16384, 131072, 131072, 524288, 131072, 2097152, 2097152, 8388608, 4194304, 33554432, 33554432, 134217728, 16777216, 536870912, 536870912, 2147483648, 1073741824, 8589934592, 8589934592, 34359738368

Offset: 0

Paul Curtz, May 28 2016

O(n) is the Horadam notation.
O(n) or Oresme(n) = n/2^n = 0, 1/2, 1/2, 3/8, 1/4, ... . The positive Oresme numbers are O(n+1) = A000265(n+1)/A075101(n+1). See A209308. Consider Oco(n) = 2*O(n+1) - O(n+2) = 1/2, 5/8, 1/2, 11/32, 7/32, ... = A075677(n+1)/a(n). (See Coll(n) in A209308.)
Oco(n) = 1/2, 5/8, 1/2, 11/32, 7/32, 17/128, 5/64, 23/512, 13/512, 29/2048, 1/128, 35/8192, 19/8192, ... . Compare to (2+3*n)/2^(n+2).
Differences table of Oco(n):
   1/2,    5/8,    1/2,   11/32,    7/32,  17/128, 5/64, ...
   1/8,   -1/8,   -5/32,  -1/8,   -11/128, -7/128, ...
  -1/4,   -1/32,   1/32,   5/128,   1/32, ...
   7/32,   1/16,   1/128, -1/128, ...
  -5/32,  -7/128, -1/64, ...
  13/128,  5/128, ...
  -1/16, ... .
First column: Io(n) = 1/2 followed by (-1)^n* A067745(n)/(8, 4, 32, 32, ...).
1) Alternated Oco(2n) + Io(2n) and Oco(2n+1) - Io(2n+1) gives 2^n.
2) Alternated Oco(2n) - Io(2n) and Oco(2n+1) + Io(2n+1) gives 3*O(n)/2.
   (1/2 - 1/2 = 0, 5/8 + 1/8 = 3/4, 1/2 + 1/4 = 3/4, 11/32 + 7/32 = 9/16, ...)

M. R. Bacon and C. K. Cook, Some properties of Oresme numbers and convolutions ..., Fib. Q., 62:3 (2024), 233-240.

Seiichi Manyama, Table of n, a(n) for n = 0..3320
A. F. Horadam, Oresme numbers, Fib. Quart., 12 (1974), 267-271.

Cf. A000079, A000265, A000302, A004171 (main diagonal), A006519, A016789, A067745, A075101, A075677, A209308.

Or(n) = n/2^n;
a(n) = denominator(2*Or(n+1) - Or(n+2)); \\ Michel Marcus, May 28 2016

a(n) = denominator of (2+3*n)/2^(n+2).
a(2n+1) = 8*4^n.
a(2n+2) = a(2n+1)/(4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, ..., shifted A006519?).

More terms from Michel Marcus, May 28 2016

cp's OEIS Frontend

A363270 The result, starting from n, of Collatz steps x -> (3x+1)/2 while odd, followed by x -> x/2 while even.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

C

Mathematica

PARI

Formula

A254068 Irregular triangle T read by rows in which the entry in row n and column k is given by T(n,k) = 4*A253676(n,k) - 3, k = 1..A253720(n), assuming the 3x+1 (or Collatz) conjecture.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A160322 a(n) = min(A160198(n), A160267(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A246425 In the Collatz 3x+1 problem: start at an odd number 2n+1 and find the next odd number 2m+1 in the trajectory; then a(n) = m-n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A324037 The minimal number of iterations to reach 1 of the modified reduced Collatz function, defined for odd numbers 1 + 2*n in A324036 (assuming the Collatz conjecture).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A373730 Reduced Collatz function R applied to the numbers 6n+1: a(n) = R(6n+1), where R(k) = (3k+1)/2^r, with r as large as possible.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A166466 Trisection a(n) = A000265(3n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A182078 Odd numbers n such that the reduced Collatz map n -> (3n+1)/2^k gives a trajectory of decreasing odd numbers.

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.