A257470 - OEIS

%I #20 Sep 26 2016 21:06:20

%S 0,1,2,4,8,3,6,12,5,10,20,7,14,28,9,18,36,11,22,44,13,26,52,15,30,60,

%T 16,32,64,17,34,68,19,38,76,21,42,84,23,46,92,24,48,96,25,50,100,27,

%U 54,108,29,58,116,31,62,124,33,66,132,35,70,140,37,74,148,39,78,156,40,80,160,41,82,164,43,86,172,45,90,180,47,94,188,49,98,196,51

%N a(n+1) = least number not occurring earlier such that max{a(n), a(n+1)} >= 2 min{a(n), a(n+1)}; a(0) = 0.

%C Otherwise said, a(n+1) is either the smallest number not occurring earlier if this number is smaller than a(n)/2, or else a(n+1) is the least unused number >= 2 a(n).

%C This is a simpler variant of A139080. Here the well-definedness of the infinite sequence is guaranteed.

%C This is a permutation of the nonnegative integers. Indeed, any number m appears either "early" as successor of m/2, or "late" as successor a(n+1) of some a(n) >= 2m (in which case n+1 = 3k-1, see below).

%C After the two initial terms, the following 3-periodic pattern repeats: a(3k-1) = the smallest term not occurring earlier, a(3k) = 2 a(3k-1), and a(3k+1) = 2 a(3k), since at this point the smallest unused number is necessarily > a(3k)/2 = a(3k-1), and therefore, using that number, the maximum would be smaller than twice the minimum.

%C In spite of the simplicity of the pattern, it seems not easy to give an explicit formula of a(n), i.e., for a(3k-1), cf. formulas. I conjecture the following properties:

%C (i) For all k>0, a(3k+2) = a(3k-1)+2 except for k in S = {1, 8, 9, 13, 14, 22, 23, 31, 32, 40, 41, 49, 50,...} where a(3k+2) = a(3k-1)+1.

%C (ii) Let D = (7, 1, 4, 1, 8, 1, 8, 1, 8, 1, 8, 1, 8, ...) be the first differences of the sequence S. Then D(2k) = 1 for all k>0.

%C (iii) D(2k+1) = 4 or 8 for all k>0; except for the first one, the 4's always come twice in a row (e.g., for k in {8, 9}, {13, 14}, {22, 23}, ...).

%C (iv) The length of runs of 8's in the subsequence D(2k+1) are: 6 (k=2..7), 3 (k=10..12), 7 (k=15..21), 7 (k=24..30), 7 (k=33..39), 7 (k=42..48), 7 (k=51..57), 7 (k=60..66), 3 (k=69..71), 3 (k=74..76), 7,... It seems that except for the first two terms, this consists of runs of 7 of various length, but always interrupted by two 3's.

%H <a href="/index/Per#IntegerPermutation">OEIS Index entries of sequences related to permutations of the nonnegative integers.</a>

%F For all k>0, a(3k-1) = least number not occurring earlier; a(3k) = 2 a(3k-1); a(3k+1) = 2 a(3k).

%e After a(0)=0, a(1)=1 is the least unused number such that max{1,0} >= 2 min{1,0} = 0.

%e After a(2)=2, a(3)=4 is the least unused number such that max{2,4} >= 2 min{2,4} = 4.

%e After a(3)=4, a(4)=8 is the least unused number such that max{8,4} >= 2 min{8,4} = 8, because the only smaller unused number, 3, would not satisfy the requirement.

%e After a(4)=8, a(5)=3 is the least unused number such that max{8,3} >= 2 min{8,3} = 6.

%t f[n_] := Block[{s = {1}}, For[i = 2, i <= n, i++, k = 1; While[Nand[! MemberQ[s, k], Max[k, s[[i - 1]]] >= 2 Min[k, s[[i - 1]]]], k++]; AppendTo[s, k]]; s]; f@ 86 (* _Michael De Vlieger_, Apr 25 2015 *)

%o (PARI) {a=vector(2000);u=[];a[1]=1;for(n=2,#a,u=setunion(u,[a[n-1]]); while(#u>1&&u[2]==u[1]+1, u=u[2..-1]); if( u[1]*2+1 < a[n-1], a[n]=u[1]+1, a[n]=a[n-1]*2; while(setsearch(u,a[n]),a[n]++)))}

%K nonn

%O 0,3

%A _M. F. Hasler_, Apr 25 2015