login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 7
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Van der Poorten asks if every odd number is in the sequence. This seems very likely.

Comment 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 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 non-trivial 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

LINKS

T. D. Noe and 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

MAPLE

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; # From N. J. A. Sloane, Aug 25 2015

MATHEMATICA

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)

CROSSREFS

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.

Sequence in context: A234042 A001203 A154883 * A114396 A102032 A086517

Adjacent sequences:  A109729 A109730 A109731 * A109733 A109734 A109735

KEYWORD

nonn,easy,look,changed

AUTHOR

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

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified September 5 03:49 EDT 2015. Contains 261339 sequences.