A261690 -id:A261690 - cp's OEIS frontend

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

1, 3, 7, 15, 5, 11, 23, 31, 47, 63, 21, 43, 87, 29, 59, 95, 119, 127, 175, 191, 239, 255, 85, 171, 57, 19, 39, 13, 27, 9, 55, 79, 111, 37, 75, 25, 51, 17, 35, 71, 103, 115, 143, 151, 159, 53, 107, 207, 69, 139, 215, 223, 231, 77, 155, 279, 93, 187, 287, 303, 101, 203

Offset: 1

N. J. A. Sloane, prompted by a posting by Alf van der Poorten to the Number Theory List, Aug 10 2005

Van der Poorten asks if every odd number is in the sequence. This seems very likely.
From Max Alekseyev, Aug 28 2015: (Start)
The question of whether every odd number is present in this sequence can be reformulated as follows. Can every odd number m be transformed into 1 using the maps: m -> (m-1)/2 (only if the result is an integer) and m -> 3m, applied in some order? It is clear that even numbers cannot appear in such a transformation, since they would remain even and thus not reach 1.
Replacing m by n = (m+1)/2, we get an equivalent question: Can any number n be transformed into 1 using the maps: n -> n/2 (only if n is even) and n -> 3n-1 applied in some order?
An affirmative answer to this question would follow from the 3x-1 variation of Collatz conjecture. This states that the maps x -> x/2 (for even x) and x -> 3x-1 (for odd x) eventually reach one of the three cycles: (1,2), (5, ...) of length 5 -- see A003079 -- or (17, ...) of length 17 -- see A003124.
However, in our problem, we have the freedom of choosing either of the two maps at each stage (the only restriction being that n -> n/2 can be used only if n is even). With this freedom, we can transform 5 and 17 from the nontrivial cycles of the 3x-1 problem to 1: (5, 14, 7, 20, 10, 29, 86, 43, 128, 64, 32, 16, 8, 4, 2, 1)  or (17, 50, 25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136, 68, 203, 608, 304, 152, 76, 38, 19, 56, 28, 14, ... as before).
That is, under the 3x-1 variation of Collatz conjecture, we can transform any number either to 1, 5, or 17, and in the latter two cases we can proceed further as explained above and still reach 1. (End)
In short, the question of showing that every odd number occurs is likely to be very difficult. - N. J. A. Sloane, Aug 29 2015
Odd numbers of the form 2^k+1 take a long time to appear; e.g., 2^12+1 appears at a(64607). - T. D. Noe, Aug 10 2005. [A109734, A261412, A261413, A261414 are related to this question. - N. J. A. Sloane, Aug 27 2015]

N. J. A. Sloane, Table of n, a(n) for n = 1..20000 (first 1000 terms from T. D. Noe)
T. D. Noe, Graph of first 1000 terms.

Cf. A109734 (inverse), A261412 and A261413 (records), A261414 (where 2^k+1 appears),
A261690 (an analog connected with (3n+1)-problem).
See also A003124, A003079.

with(LinearAlgebra);
hit:=Array(1..200000); a:=[1,3,7]; hit[1]:=1; hit[3]:=1; hit[7]:=1; 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]:=1; 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]:=1; S:=S minus {L};
   if hit[2*L+1]=0 then S:=S union {2*L+1}; fi;
fi; od: a; # N. J. A. Sloane, Aug 25 2015

maxVal=1000; f[n_]:=Module[{lst={}, x=n}, While[x=2x+1; x0, 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; AppendTo[M, next]; pending=Union[pending, f[next]]]]]; M (Noe)

More terms from T. D. Noe, Aug 10 2005

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.

A261931 a(0)=1, a(1)=2, for n>=1, a(2n) = 6n - 2; a(2n+1) = min(((a(2n)-1)/3)^, (2a(2n))^, (2a(2n-1))^), where, instead of t, we write t^, if t has not appeared earlier in the sequence and is neither of the form 3k nor of the form 6m-2.

Original entry on oeis.org

1, 2, 4, 8, 10, 20, 16, 5, 22, 7, 28, 14, 34, 11, 40, 13, 46, 26, 52, 17, 58, 19, 64, 38, 70, 23, 76, 25, 82, 50, 88, 29, 94, 31, 100, 62, 106, 35, 112, 37, 118, 74, 124, 41, 130, 43, 136, 86, 142, 47, 148, 49, 154, 98, 160, 53, 166, 55, 172, 110, 178, 59, 184

Offset: 0

Vladimir Shevelev, Sep 06 2015

nonn

Let n>=7. If n == 1 or 3 (mod 6), then a(n) = n-2; if n == 5 (mod 6), then a(n) = 2*(n-4). This could be proved by induction similar to the theorem in A261728.
The sequence is a permutation of the positive integers not divisible by 3 which are not of the form 12*s+8, s>=2.
This sequence is connected with Collatz's (3*n+1)-conjecture. For example, if n=29, then, by the formulas, 29 = a(31) => 88 = a(30) => 11 = a(13) => 34 = a(12) => 17 = a(19) => 52 = a(18) => 13 = a(15) => 40 = a(14) => 5 = a(7) => 16 = a(6) => 1 = a(0).

			At n=3, since a(1)=2 and a(2)=6*1-2=4, a(3) should be either (4-1)/3=1 or 2*a(2)=8 or 2*a(1)=4; 1 and 4 have already appeared, so a(3)=8.
At n=5, since a(3)=8 and a(4)=6*2-2=10, a(5) should be either (10-1)/3=3 or 2*a(4)=20 or 2*a(3)=16; 3 is divisible by 3, and 16 is of the form 6*t-2, so a(5)=20.

Peter J. C. Moses, Table of n, a(n) for n = 0..9999

Cf. A261690, A261728, A261831.

For n>=1, a(2*n) = 6*n - 2.
For t>=1, a(6*t+1) = 6*t - 1; a(6*t+3) = 6*t+1; a(6*t+5) = 12*t + 2.
And from the name, for n>=3, a(2*n+1) = min(((a(2*n)-1)/3)^, (2*a(2*n-1))^).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

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

Crossrefs

Programs

Maple

Perl

A261831 a(2*n-1) = 2*n-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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A261931 a(0)=1, a(1)=2, for n>=1, a(2*n) = 6*n - 2; a(2*n+1) = min(((a(2*n)-1)/3)^, (2*a(2*n))^, (2*a(2*n-1))^), where, instead of t, we write t^, if t has not appeared earlier in the sequence and is neither of the form 3*k nor of the form 6*m-2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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.

A261931 a(0)=1, a(1)=2, for n>=1, a(2n) = 6n - 2; a(2n+1) = min(((a(2n)-1)/3)^, (2a(2n))^, (2a(2n-1))^), where, instead of t, we write t^, if t has not appeared earlier in the sequence and is neither of the form 3k nor of the form 6m-2.