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.

%I A109732 #45 Jan 10 2025 04:30:21
%S A109732 1,3,7,15,5,11,23,31,47,63,21,43,87,29,59,95,119,127,175,191,239,255,
%T A109732 85,171,57,19,39,13,27,9,55,79,111,37,75,25,51,17,35,71,103,115,143,
%U A109732 151,159,53,107,207,69,139,215,223,231,77,155,279,93,187,287,303,101,203
%N 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.
%C A109732 Van der Poorten asks if every odd number is in the sequence. This seems very likely.
%C A109732 From _Max Alekseyev_, Aug 28 2015: (Start)
%C A109732 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.
%C A109732 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?
%C A109732 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.
%C A109732 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).
%C A109732 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)
%C A109732 In short, the question of showing that every odd number occurs is likely to be very difficult. - _N. J. A. Sloane_, Aug 29 2015
%C A109732 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]
%H A109732 N. J. A. Sloane, <a href="/A109732/b109732.txt">Table of n, a(n) for n = 1..20000</a> (first 1000 terms from T. D. Noe)
%H A109732 T. D. Noe, <a href="/A109732/a109732.gif">Graph of first 1000 terms</a>.
%p A109732 with(LinearAlgebra);
%p A109732 hit:=Array(1..200000); a:=[1,3,7]; hit[1]:=1; hit[3]:=1; hit[7]:=1; S:={15}; L:=7;
%p A109732 for n from 4 to 20000 do
%p A109732 if (L mod 3 = 0) and hit[L/3]=0 then
%p A109732 L:=L/3; a:=[op(a),L]; hit[L]:=1; S:= S minus {L};
%p A109732    if hit[2*L+1]=0 then S:=S union {2*L+1}; fi;
%p A109732 else L:=min(S); a:=[op(a),L]; hit[L]:=1; S:=S minus {L};
%p A109732    if hit[2*L+1]=0 then S:=S union {2*L+1}; fi;
%p A109732 fi; od: a; # _N. J. A. Sloane_, Aug 25 2015
%t A109732 maxVal=1000; f[n_]:=Module[{lst={}, x=n}, While[x=2x+1; x<maxVal, AppendTo[lst, x]]; lst]; M={1}; pending=f[1]; 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; AppendTo[M, next]; pending=Union[pending, f[next]]]]]; M (Noe)
%Y A109732 Cf. A109734 (inverse), A261412 and A261413 (records), A261414 (where 2^k+1 appears),
%Y A109732 A261690 (an analog connected with (3n+1)-problem).
%Y A109732 See also A003124, A003079.
%K A109732 nonn,easy,look
%O A109732 1,2
%A A109732 _N. J. A. Sloane_, prompted by a posting by Alf van der Poorten to the Number Theory List, Aug 10 2005
%E A109732 More terms from _T. D. Noe_, Aug 10 2005