|
%I #89 Oct 18 2022 16:36:09
%S 1,3,4,6,7,9,10,12,14,15,17,18,20,21,23,24,26,27,29,30,32,34,35,37,38,
%T 40,41,43,44,46,47,49,51,52,54,55,57,58,60,61,63,64,66,67,69,71,72,74,
%U 75,77,78,80,82,83,85,86,88,89,91,92,94,95,97,98,100,102,103,105,106
%N Start with Y(0)=0, X(1)=1, Y(1)=2. For n > 1, choose least positive integers Y(n) > X(n) such that neither Y(n) nor X(n) appear in {Y(k), 1 <= k < n} or {X(k), 1 <= k < n} and such that Y(n) - X(n) does not appear in {Y(k) - X(k), 1 <= k < n} or {Y(k) + X(k), 1 <= k < n}; sequence gives X(n) (for Y(n) see A140101).
%C Sequence A140101 = {Y(n), n >= 1} is the complement of the current sequence, while the sequence of differences, A140102 = {Y(n) - X(n), n >= 1}, forms the complement of the sequence of sums, A140103 = {Y(n) + X(n), n >= 1}.
%C Compare with A140098(n) = floor(n*(1+1/t)), a Beatty sequence involving the tribonacci constant t = t^3 - t^2 - 1 = 1.83928675521416113255...
%C Conjecture: A140100(n) - A140098(n) = A276404(n) is always 0 or 1; see A276406 for the positions where a difference of 1 occurs.
%C This is the same problem as the "Greedy Queens in a spiral" problem described in A273059. See the Dekking et al. paper and comments in A140101. - _N. J. A. Sloane_, Aug 30 2016
%C The sequence is "Tribonacci-synchronized"; this means there is a finite automaton recognizing the Tribonacci representation of (n,a(n)) input in parallel, where a shorter input is padded with leading zeros. This finite automaton has 22 states and was verified with Walnut. In particular this finite automaton and a similar one for A140101 was used to verify that (conjecture of J. Cassaigne) either a(b(n)) = a(n)+b(n) or b(a(n)) = a(n)+b(n) for all n>=1, where b(n) = A140101(n). - _Jeffrey Shallit_, Oct 04 2022
%H N. J. A. Sloane, <a href="/A140100/b140100.txt">Table of n, a(n) for n = 1..50000</a>, Sep 13 2016 (First 1001 terms from Reinhard Zumkeller)
%H F. Michel Dekking, Jeffrey Shallit, and N. J. A. Sloane, <a href="https://doi.org/10.37236/8905">Queens in exile: non-attacking queens on infinite chess boards</a>, Electronic J. Combin., 27:1 (2020), #P1.52.
%H Eric Duchêne and Michel Rigo, <a href="http://dx.doi.org/10.1051/ita:2007039">A morphic approach to combinatorial games: the Tribonacci case</a>. RAIRO - Theoretical Informatics and Applications, 42, 2008, pp 375-393. doi:10.1051/ita:2007039. [Also available <a href="http://archive.numdam.org/item/ITA_2008__42_2_375_0">here</a>]
%H Robbert Fokkink and Dan Rust, <a href="https://arxiv.org/abs/1904.08339">A modification of Wythoff's Nim</a>, arXiv:1904.08339 [math.CO], 2019.
%H Jeffrey Shallit, <a href="https://arxiv.org/abs/2210.03996">Some Tribonacci conjectures</a>, arXiv:2210.03996 [math.CO], 2022.
%H Jeffrey Shallit, <a href="/A140100/a140100_1.txt">Automaton to be called xaut.txt in Walnut format, recognizing (n, X(n)) in parallel, in Tribonacci representation</a>
%H N. J. A. Sloane, <a href="/A140100/a140100.txt">Maple program for A140100, A140101, A140102, A140103</a>
%F Conjecture: the limit of X(n)/n = 1+1/t and limit of Y(n)/n = 1+t where the limit of Y(n)/X(n) = t = tribonacci constant (A058265), and thus the limit of (Y(n) + X(n))/(Y(n) - X(n)) = t^2 and the limit of (Y(n)^2 + X(n)^2)/(Y(n)^2 - X(n)^2) = t.
%F From _Michel Dekking_, Mar 16 2019: (Start)
%F It is conjectured in A305392 that the first differences of (X(n)) as a word are given by 212121 delta(x), where x is the tribonacci word x = A092782, and delta is the morphism
%F 1 -> 2212121212121,
%F 2 -> 22121212121,
%F 3 -> 2212121.
%F This conjecture implies the frequency conjectures above: let N(i,n) be the number of letters i in x(1)x(2)...x(n). Then simple counting gives
%F X(13*N(1,n)+11*N(2,n)+7*N(3,n)) = 20*N(1,n)+17*N(2,n)+11*N(3,n), where we neglected the first 6 symbols of X.
%F It is well known (see, e.g., A092782) that the frequencies of 1, 2 and 3 in x are respectively 1/t, 1/t^2 and 1/t^3. Dividing all the N(i,n) by n, and letting n tend to infinity, we then have to see that
%F 20*1/t + 17*1/t^2 + 11*1/t^3 = (1+1/t)*(13*1/t + 11*1/t^2 + 7*1/t^3)
%F This is a simple verification.
%F End)
%e Start with Y(0)=0, X(1)=1, Y(1)=2; Y(1)-X(1)=1, Y(1)+X(1)=3.
%e Next choose X(2)=3 and Y(2)=5; Y(2)-X(2)=2, Y(2)+X(2)=8.
%e Next choose X(3)=4 and Y(3)=8; Y(3)-X(3)=4, Y(3)+X(3)=12.
%e Next choose X(4)=6 and Y(4)=11; Y(4)-X(4)=5, Y(4)+X(4)=17.
%e Continue to choose the least positive X and Y>X not appearing earlier such that Y-X and Y+X do not appear earlier as a difference or sum.
%e CONSTRUCTION: PLOT OF (A140100(n), A140101(n)).
%e This sequence gives the x-coordinates of the following construction.
%e Start with an x-y coordinate system and place an 'o' at the origin.
%e Define an open position as a point not lying in the same row, column, or diagonal (slope +1/-1) as any point previously given an 'o' marker.
%e From then on, place an 'o' marker at the first open position with integer coordinates that is nearest the origin and the y-axis in the positive quadrant, while simultaneously placing markers at rotationally symmetric positions in the remaining three quadrants.
%e Example: after the origin, begin placing markers at x-y coordinates:
%e n=1: (1,2), (2,-1), (-1,-2), (-2,1);
%e n=2: (3,5), (5,-3), (-3,-5), (-5,3);
%e n=3: (4,8), (8,-4), (-4,-8), (-8,4);
%e n=4: (6,11), (11,-6), (-6,-11), (-11,6);
%e n=5: (7,13), (13,-7), (-7,-13), (-13,7); ...
%e The result of this process is illustrated in the following diagram (see A273059 for an equivalent picture - _N. J. A. Sloane_, Aug 30 2016).
%e ----------------+---o------------
%e --o-------------+----------------
%e ----o-----------+----------------
%e ----------------+--o-------------
%e --------o-------+----------------
%e -----------o----+----------------
%e ----------------+o---------------
%e --------------o-+----------------
%e ++++++++++++++++o++++++++++++++++
%e ----------------+-o--------------
%e ---------------o+----------------
%e ----------------+----o-----------
%e ----------------+-------o--------
%e -------------o--+----------------
%e ----------------+------------o---
%e ----------------+--------------o-
%e ------------o---+----------------
%e Graph: no two points lie in the same row, column, diagonal, or antidiagonal.
%e Points in the positive quadrant are at (A140100(n), A140101(n)).
%e A140101 begins: [2,5,8,11,13,16,19,22,25,28,31,33,36,39,42,...].
%p See link.
%t y[0] = 0; x[1] = 1; y[1] = 2;
%t x[n_] := x[n] = For[yn = y[n - 1] + 1, True, yn++, For[xn = x[n - 1] + 1, xn < yn, xn++, xx = Array[x, n - 1]; yy = Array[y, n - 1]; If[FreeQ[xx, xn] && FreeQ[xx, yn] && FreeQ[yy, xn] && FreeQ[yy, yn] && FreeQ[yy - xx, yn - xn] && FreeQ[yy + xx, yn - xn], y[n] = yn; Return[xn]]]];
%t Table[x[n], {n, 1, 100}] (* _Jean-François Alcover_, Jun 17 2018 *)
%o (PARI) /* Print (x,y) coordinates of the positive quadrant */
%o {X=[1]; Y=[2]; D=[1]; S=[3]; print1("["X[1]", "Y[1]"], "); for(n=1, 100, for(j=2, 2*n, if(setsearch(Set(concat(X, Y)), j)==0, Xt=concat(X, j); for(k=j+1, 3*n, if(setsearch(Set(concat(Xt, Y)), k)==0, if(setsearch(Set(concat(D, S)), k-j)==0, if(setsearch(Set(concat(D, S)), k+j)==0, X=Xt; Y=concat(Y, k); D=concat(D, k-j); S=concat(S, k+j); print1("["X[ #X]", "Y[ #Y]"], "); break); break))))))}
%Y Cf. A140101 (complement); A140102, A140103, A276404, A276405, A276406, A275926.
%Y Cf. related Beatty sequences: A140098, A140099; A000201.
%Y Cf. A058265 (tribonacci constant).
%Y Cf. Greedy Queens in a spiral, A273059.
%Y For first difference of A140100, A140101, A140102, A140103 see A305392, A305374, A305393, A305394.
%K nonn
%O 1,2
%A _Paul D. Hanna_, Jun 04 2008
%E Terms computed independently by _Reinhard Zumkeller_ and _Joshua Zucker_
%E Edited by _N. J. A. Sloane_, Aug 30 2016
|
