A109732 -id:A109732 - cp's OEIS frontend

A109734 In A109732, the number 2n+1 appears in position a(n).

1, 2, 5, 3, 30, 6, 28, 4, 38, 26, 11, 7, 36, 29, 14, 8, 201, 39, 34, 27, 180, 12, 175, 9, 199, 37, 46, 31, 25, 15, 178, 10, 242, 202, 49, 40, 197, 35, 54, 32, 192, 158, 23, 13, 208, 176, 57, 16, 240, 200, 61, 41, 83, 47, 195, 33, 121, 42, 67, 17, 190, 179, 70, 18, 689, 243

Offset: 0

N. J. A. Sloane, Aug 10 2005

nonn

			9 appears in position 30 in A109732, so a(4) = 30.

N. J. A. Sloane and Alois P. Heinz, Table of n, a(n) for n = 0..20000 (first 1024 terms from N. J. A. Sloane)

Cf. A109732. For records see A109739 and A109740.

with(LinearAlgebra);
hit:=Array(1..200000); a:=[1,3,7];
hit[1]:=1; hit[3]:=2; hit[7]:=3; S:={15}; L:=7;
for n from 4 to 20000 do
if (L mod 3 = 0) and hit[L/3]=0 then
L:=L/3; a:=[op(a),L]; hit[L]:=n; S:= S minus {L};
   if hit[2*L+1]=0 then S:=S union {2*L+1}; fi;
else L:=min(S); a:=[op(a),L]; hit[L]:=n; S:=S minus {L};
   if hit[2*L+1]=0 then S:=S union {2*L+1}; fi;
fi;
od:
#a;
w:=[];
for i from 0 to 50000 do
if hit[2*i+1]=0 then break; fi;
w:=[op(w),hit[2*i+1]]; od:
w; # N. J. A. Sloane, Aug 25 2015

(* using the M generated in A109732 *) ms=Sort[M]; k=1; While[ms[[k]]==2k-1, k++ ]; k=k-1; Take[Ordering[M], k] (* T. D. Noe, Aug 10 2005 *)

More terms from T. D. Noe and Ray Chandler, Aug 10 2005

A261412 Positions of records in A109732.

Original entry on oeis.org

1, 2, 3, 4, 7, 8, 9, 10, 13, 16, 17, 18, 19, 20, 21, 22, 56, 59, 60, 63, 64, 65, 66, 69, 72, 73, 74, 75, 76, 79, 80, 88, 89, 90, 91, 92, 95, 96, 97, 98, 99, 100, 103, 114, 115, 116, 125, 126, 127, 128, 134, 135, 138, 139, 140, 141, 142, 145, 146, 147, 148, 149, 152, 153, 154, 166, 167, 170, 171, 172

Offset: 1

N. J. A. Sloane, Aug 25 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Cf. A109732, A261413.

A261413 Records in A109732.

Original entry on oeis.org

1, 3, 7, 15, 23, 31, 47, 63, 87, 95, 119, 127, 175, 191, 239, 255, 279, 287, 303, 311, 319, 343, 351, 375, 383, 407, 415, 431, 447, 463, 471, 479, 503, 511, 559, 567, 575, 599, 607, 623, 631, 639, 687, 703, 751, 759, 767, 815, 823, 831, 847, 855, 863, 895, 911, 919, 927, 943, 959, 1007, 1015, 1023

Offset: 1

N. J. A. Sloane, Aug 25 2015

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Cf. A109732, A261412.

A261414 2^n+1 appears in A109732 at position a(n).

Original entry on oeis.org

2, 5, 30, 38, 201, 242, 689, 1806, 7175, 10839, 21474, 64607, 290563, 290579, 581260, 872576, 2617577, 5238258, 7858320, 19886365, 47140605, 70713773, 212133736

Offset: 1

N. J. A. Sloane, Aug 25 2015

This assumes van der Poorten's conjecture that every odd number does appear in A109732.

			A109732(38) = 17 = 2^4+1, so a(4)=38.

Cf. A109732, A109734, A109739, A109740, A261412, A261413.

m:= 22000: # m is the search limit
b:= proc() true end:
s:= heap[new]((x, y)-> is(x>y), 1):
for n to m do t:= heap[extract](s); b(t):= false;
  if t>1 and t-1=2^ilog2(t-1) then print(ilog2(t-1), t, n) fi;
  k:= 2*t+1; if b(k) then heap[insert](k, s) fi;
  if irem(t, 3, 'k')=0 and b(k) then heap[insert](k, s) fi
od:  # Alois P. Heinz, Aug 27 2015

maxVal = 5*10^5; (* 5*10^5 gives 12 terms *)
f[n_] := Module[{lst = {}, x = n}, While[x = 2x+1; x < maxVal, AppendTo[lst, x]]; lst];
M = {1}; pending = f[1];
A261414 = Reap[Print[2]; Sow[2]; While[Length[pending] > 0, next = First[pending]; pending = Rest[pending]; If[!MemberQ[M, next], AppendTo[M, next]; While[Mod[next, 3]==0 && !MemberQ[M, next/3], next = next/3; If[IntegerQ[Log[2, next-1]], Print[an = Length[M]+1]; Sow[an]]; AppendTo[M, next]; pending = Union[pending, f[next]]]]]][[2, 1]] (* Jean-François Alcover, Nov 25 2020, after T. D. Noe in A109732 *)

a(10)-a(17) from Alois P. Heinz, Aug 27 2015

a(18)-a(23) from Alois P. Heinz, Aug 28 2015

A261690 a(1) = 1; for n>1, a(n) is the smallest number not already present which is entailed by the rules (i) k present => 3k+1 present; (ii) 2k present => k present.

Original entry on oeis.org

1, 4, 2, 7, 13, 22, 11, 34, 17, 40, 20, 10, 5, 16, 8, 25, 31, 49, 52, 26, 61, 67, 76, 38, 19, 58, 29, 79, 88, 44, 94, 47, 103, 115, 121, 133, 142, 71, 148, 74, 37, 112, 56, 28, 14, 43, 85, 130, 65, 157, 169, 175, 184, 92, 46, 23, 70, 35, 106, 53, 139, 160, 80

Offset: 1

Vladimir Shevelev, Aug 28 2015

nonn

An analog of A109732 such that the statement 'the sequence is a permutation of the positive integers not divisible by 3' is equivalent to the (3*n+1)-conjecture for numbers not divisible by 3.
On Aug 29 2015, Max Alekseyev noted that, while the (3*n+1)-conjecture indeed implies that the sequence is a permutation of the positive integers not divisible by 3, the opposite statement is an open question. The author cannot yet prove this, so his previous comment is only a conjecture.
In connection with this, consider the following conjecture which could be called the (n-1)/3-conjecture. Let n be any number not divisible by 3. If n==1 (mod 3) and (n-1)/3 is not divisible by 3, then set n_1 = (n-1)/3. Otherwise set n_1 = 2*n. Conjecture. There exists an iteration n_m = 1. Does the (n-1)/3-conjecture imply the (3*n+1)-conjecture?
Example: 19->38->76->25->8->16->5->10->20->40->13->4->1.

Peter J. C. Moses, Table of n, a(n) for n = 1..10000

Cf. A006577, A006877, A006884, A109732.

A261671 If n even, a(n) = 6n+3, otherwise a(n) = n.

Original entry on oeis.org

3, 1, 15, 3, 27, 5, 39, 7, 51, 9, 63, 11, 75, 13, 87, 15, 99, 17, 111, 19, 123, 21, 135, 23, 147, 25, 159, 27, 171, 29, 183, 31, 195, 33, 207, 35, 219, 37, 231, 39, 243, 41, 255, 43, 267, 45, 279, 47, 291, 49, 303, 51, 315, 53, 327, 55, 339, 57, 351, 59, 363

Offset: 0

N. J. A. Sloane, Sep 02 2015

Although the OEIS indexes sequences by consecutive integers, it is better to think of this sequence as defined on the odd numbers 1,3,5,7,... and given by f(4m+1)=12m+3, f(4m+3)=2m+1, that is, subtract 1 and divide by 2 if the result is odd, otherwise multiply by 3. This arises in analyzing A109732.

It is conjectured that starting with any positive odd number d and iterating f, we always eventually reach either 1, 9, or 33 (see Comments in A135730).

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,2,0,-1).

Cf. A109732, A135730.

Table[If[EvenQ[n],6n+3,n],{n,0,60}] (* or *) LinearRecurrence[{0,2,0,-1},{3,1,15,3},70] (* Harvey P. Dale, Dec 30 2023 *)

Vec((x^3+9*x^2+x+3)/((x-1)^2*(x+1)^2) + O(x^100)) \\ Colin Barker, Sep 13 2015

From Colin Barker, Sep 13 2015: (Start)
a(n) = (3+3*(-1)^n+7*n+5*(-1)^n*n)/2.
a(n) = 2*a(n-2) - a(n-4) for n>3.
G.f.: (x^3+9*x^2+x+3) / ((x-1)^2*(x+1)^2).
(End)

A261870 a(n) = minimal number of steps to get from n to 1, where a step is x -> 3x-1 if x is odd, or x -> either x/2 or 3x-1 if x is even.

Original entry on oeis.org

0, 1, 4, 2, 15, 5, 13, 3, 16, 11, 6, 6, 19, 14, 9, 4, 35, 17, 17, 12, 25, 7, 20, 7, 33, 15, 15, 15, 10, 10, 23, 5, 36, 36, 18, 18, 31, 18, 13, 13, 26, 26, 8, 8, 26, 21, 21, 8, 34, 34, 21, 16, 16, 16, 29, 16, 29, 11, 11, 11, 24, 24, 24, 6, 37, 37, 24, 19, 19, 19, 19, 19, 32, 32, 19, 19, 14, 14, 14, 14, 27, 27, 27, 27, 27, 9, 40, 9, 27, 27, 22, 22, 22, 22, 22, 9, 35, 35, 35, 22

Offset: 1

Max Alekseyev, Sep 03 2015

nonn

The 3x-1 variation of Collatz conjecture would imply that this sequence is well defined. In turn, if this sequence is well-defined, then A109732 represents a permutation of the odd positive integers.

Kevin Ryde, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Max Alekseyev)
Kevin Ryde, C Code

Cf. A127885, A006577, A109732.

C
```
/* See links. */
```

{ A261870(n) = my(S, k); S=[n]; k=0; while( S[1]!=1, k++; S=vecsort( concat(apply(x->3*x-1, S), apply(x->x\2, select(x->x%2==0, S) )), , 8);  ); k } /* Max Alekseyev, Sep 03 2015 */

A261728 a(1)=1; a(2n) = 3n; for odd n>1, a(n) is the smallest number not already present which is entailed by the rules (i) k present => 3k+1 present; (ii) 2k present => k present.

Original entry on oeis.org

1, 3, 4, 6, 2, 9, 7, 12, 10, 15, 5, 18, 13, 21, 16, 24, 8, 27, 19, 30, 22, 33, 11, 36, 25, 39, 28, 42, 14, 45, 31, 48, 34, 51, 17, 54, 37, 57, 40, 60, 20, 63, 43, 66, 46, 69, 23, 72, 49, 75, 52, 78, 26, 81, 55, 84, 58, 87, 29, 90, 61, 93, 64, 96, 32, 99, 67, 102, 70, 105, 35, 108, 73, 111, 76, 114, 38, 117, 79

Offset: 1

Vladimir Shevelev, Aug 30 2015

Theorem. The only fixed points are 6*k+1, k>=0; if n==3 (mod 6), then a(n) = n+1; if n==5 (mod 6), then a(n) = (n-1)/2.
Proof. By definition, we every time consider the smallest c which has not already given the term 3*c+1.
Lemma. If c=2*k is even, then 3*c+1 appears in the position 6*k+1 and in this case 3*c+1=6*k+1, while if c=2*k+1 is odd, then 3*c+1 appears in the position 6*k+3 and in this case 3*c+1=6*k+4=(6*k+3)+1; finally, in the position 6*k+5 we have 3*k+2=((6*k+5)-1)/2.
Proof. We use induction. The induction hypothesis (IH) is that the lemma is true for every even c<=2*k and odd c<=2*k+1.
Using (IH), note that, by the condition, in the position 6*k+5 we have (6*k+4)/2=3*k+2, and even it is even, then 3*(k/2)+1 cannot occupy the position 6*k+7, since, by IH, 3*(k/2)+1 has already appeared. So the position 6*k+7=6*(k+1)+1 is occupied by 3*c+1, where c is the not yet used, i.e., c=2*k+2=2*(k+1). So the position 6*k+7 is occupied by 6*(k+1)+1=6*k+7. Further, the position 6*k+9=6*(k+1)+3 is occupied by 3*c+1, where c is the not yet used, i.e., c=2*k+3=2*(k+1)+1. Thus we have that the position 6*(k+1)+3 is occupied by the term 6*(k+1)+4=(6*(k+1)+3)+1. Finally, since in the position 6*k+9 we have an even term, then, by the condition, in the position 6*k+11=6*(k+1)+5 we have (6*(k+1)+4)/2=3*(k+1)+2=((6*(k+1)+5)-1)/2. This completes the induction.
Thus, by Lemma, we have a(6*k+1) = 6*k+1, a(6*k+3) = 6*k+4, a(6*k+5) = 3*k+2 and so, if n==3 (mod 6), then a(n) = n+1; if n==5 (mod 6), then a(n) = (n-1)/2. OED
Corollary. The sequence is a permutation of the positive integers.
On the other hand, the statement 'the sequence is a permutation of the positive integers' conjecturally is equivalent to the (3*n+1)-conjecture.

Peter J. C. Moses, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,2,0,0,0,0,0,-1).

Cf. A109732, A261690.

I:=[1,3,4,6,2,9,7,12,10,15,5,18]; [n le 12 select I[n] else 2*Self(n-6)-Self(n-12): n in [1..100]]; // Vincenzo Librandi, Sep 02 2015

a[1] = 1; a[n_?EvenQ] := 3n/2; a[n_] := a[n] = Switch[Mod[n, 6], 1|5, (3/2)*(n-1), 3, 2n-1] - a[n-2]; Array[a, 100] (* Jean-François Alcover, Aug 31 2015, after Vladimir Shevelev *)
LinearRecurrence[{0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, -1}, {1, 3, 4, 6, 2, 9, 7, 12, 10, 15, 5, 18}, 100] (* Vincenzo Librandi, Sep 02 2015 *)

From Peter Bala, Aug 31 2015: (Start)
O.g.f.: ( 1 + 3*x + 4*x^2 + 6*x^3 + 2*x^4 + 9*x^5 + 5*x^6 + 6*x^7 + 2*x^8 + 3*x^9 + x^10 )/(1 - 2*x^6 + x^12).
Recurrence equations: a(n) = 2*a(n-6) - a(n-12); a(2*n+1) = 3*n + (n+1)*floor(mod(n+1,3)/2) - a(2*n-1).
The latter recurrence leads to the formula a(2*n+1) = 1/4*(6*n + 3 + (-1)^n) + (-1)^floor( mod(n,3)/2 ) * floor( (3*ceiling(n/3) + 1)/2 ). (End)
a(2*n) = 3*n and, for k>=0, a(6k+1)=6k+1; a(6k+3)=6k+4; a(6k+5)=3k+2. - Vladimir Shevelev, Aug 31 2015

A261702 a(1) = 1; for n>1, a(n) is the smallest positive integer not already present which is entailed by the rules (i) k present => 2k present; (ii) 3k+1 present and k odd => k present.

Original entry on oeis.org

1, 2, 4, 8, 16, 5, 10, 3, 6, 12, 20, 24, 32, 40, 13, 26, 48, 52, 17, 34, 11, 22, 7, 14, 28, 9, 18, 36, 44, 56, 64, 21, 42, 68, 72, 80, 84, 88, 29, 58, 19, 38, 76, 25, 50, 96, 100, 33, 66, 104, 112, 37, 74, 116, 128, 132, 136, 45, 90, 144, 148, 49, 98, 152

Offset: 1

Paul Tek, Aug 28 2015

If the Collatz 3n+1 conjecture is true, then this is a permutation of all positive integers. See A261715 for putative inverse.

Paul Tek, Table of n, a(n) for n = 1..10000
Paul Tek, PERL program for this sequence
Paul Tek, C++ program for this sequence
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A088975, A033491, A109732, A261690, A261715 (putative inverse).

a:= proc() local a, b, s; b, s:= proc() true end,
      heap[new]((x, y)-> is(x>y), 1); a:=
      proc(n) option remember; local k, t;
        if n>1 then a(n-1) fi;
        t:= heap[extract](s); b(t):= false;
        k:= 2*t; if b(k) then heap[insert](k, s) fi;
        if irem(t-1, 3, 'k')=0 and (k::odd) and
          b(k) then heap[insert](k, s) fi; t
      end
    end():
seq(a(n), n=1..80);  # Alois P. Heinz, Aug 29 2015

See Links section.
(C++) See Links section.

A261831 a(2n-1) = 2n-1; otherwise a(n) is the smallest even number not already present which is obtained from the existing terms by the rules of (3*n+1)-problem.

Original entry on oeis.org

1, 4, 3, 2, 5, 10, 7, 16, 9, 8, 11, 22, 13, 28, 15, 14, 17, 34, 19, 40, 21, 20, 23, 46, 25, 52, 27, 26, 29, 58, 31, 64, 33, 32, 35, 70, 37, 76, 39, 38, 41, 82, 43, 88, 45, 44, 47, 94, 49, 100, 51, 50, 53, 106, 55, 112, 57, 56, 59, 118, 61, 124, 63, 62, 65, 130, 67, 136, 69, 68, 71, 142, 73, 148, 75, 74, 77, 154, 79, 160, 81, 80

Offset: 1

Vladimir Shevelev, Sep 02 2015

nonn

By the rules of the (3*n+1)-problem, an even number can appear either by the operation 3*x+1 only when x is an odd number or by the division of a number of the form 4*k by 2.
Using induction as in the proof of the Theorem in A261728, one can prove that if n == 0(mod 6), then a(n) = 2*n-2; if n == 2(mod 6), then a(n) = 2*n; if n == 4(mod 6), then a(n) = n-2.
The sequence is a permutation of the positive integers not divisible by 6 (A047253).

			Let n=28. Since 28 is of the form 6*k+4 with k=4, then a(28) = 6*4+2 = 26.

Peter J. C. Moses, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,2,0,0,0,0,0,-1).

Cf. A109732, A261690, A261728.

a[n_] := If[OddQ[n], n, Switch[Mod[n, 6], 0, 2n-2, 2, 2n, 4, n-2]]; Array[a, 81] (* Jean-François Alcover, Sep 02 2015, from given formula *)
LinearRecurrence[{0,0,0,0,0,2,0,0,0,0,0,-1},{1,4,3,2,5,10,7,16,9,8,11,22},90] (* Harvey P. Dale, Feb 24 2025 *)

a(2*n-1) = 2*n-1, for n>=1.
a(6*k) = 12*k-2, a(6*k+2) = 12*k+4 and a(6*k+4) = 6*k+2, for k>=0.
O.g.f.:(1+x (4+x (3+x (2+x (5+x (10+x (5+x (8+x (3+x (4+x (1+2 x)))))))))))/(-1+x^6)^2.

cp's OEIS Frontend

A109734 In A109732, the number 2n+1 appears in position a(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A261412 Positions of records in A109732.

Views

Author

Keywords

Links

Crossrefs

A261413 Records in A109732.

Views

Author

Keywords

Links

Crossrefs

A261414 2^n+1 appears in A109732 at position a(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions

A261690 a(1) = 1; for n>1, a(n) is the smallest number not already present which is entailed by the rules (i) k present => 3*k+1 present; (ii) 2*k present => k present.

Views

Author

Keywords

Comments

Links

Crossrefs

A261671 If n even, a(n) = 6n+3, otherwise a(n) = n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A261870 a(n) = minimal number of steps to get from n to 1, where a step is x -> 3x-1 if x is odd, or x -> either x/2 or 3x-1 if x is even.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

C

PARI

A261728 a(1)=1; a(2*n) = 3*n; for odd n>1, a(n) is the smallest number not already present which is entailed by the rules (i) k present => 3*k+1 present; (ii) 2*k present => k present.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A261702 a(1) = 1; for n>1, a(n) is the smallest positive integer not already present which is entailed by the rules (i) k present => 2k present; (ii) 3k+1 present and k odd => k present.

Views

Author

Keywords

Comments

Links

A261690 a(1) = 1; for n>1, a(n) is the smallest number not already present which is entailed by the rules (i) k present => 3k+1 present; (ii) 2k present => k present.

A261728 a(1)=1; a(2n) = 3n; for odd n>1, a(n) is the smallest number not already present which is entailed by the rules (i) k present => 3k+1 present; (ii) 2k present => k present.

A261831 a(2n-1) = 2n-1; otherwise a(n) is the smallest even number not already present which is obtained from the existing terms by the rules of (3*n+1)-problem.