|
%I #117 Oct 20 2022 16:06:11
%S 0,2,5,8,11,13,16,19,22,25,28,31,33,36,39,42,45,48,50,53,56,59,62,65,
%T 68,70,73,76,79,81,84,87,90,93,96,99,101,104,107,110,113,116,118,121,
%U 124,127,130,133,136,138,141,144,147,150,153,156,158,161,164,167,170,173
%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 Y(n) (for X(n) see A140100).
%C Sequence A140100 = {X(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 A140099(n) = [n*(1+t)], a Beatty sequence involving the tribonacci constant t = t^3 - t^2 - 1 = 1.83928675521416113255...
%C Theorem: A140099(n) - A140101(n) is always in {-1,0,1} (see A275926). (See also A276385.)
%C Comments from _N. J. A. Sloane_, Aug 30 2016: (Start) This is the same problem as the "Greedy Queens in a spiral" problem described in A273059. In A273059 the queens come in sets of 4, each set of 4 being on the same shell around the central square.
%C a(n) specifies the shell number for the successive sets of 4 (taking the central square to be shell 0, the 8 squares around the center to be shell 1, etc.).
%C For example, the queens at squares 9, 13, 17, 21 in the spiral (terms A273059(2)-A273059(5)) are all on shell a(1) = 2. The next four queens, at squares 82, 92, 102, 112, are on shell a(2) = 5.
%C The four "spokes" in A273059 are given in A275916-A275919. The precise connection with the current sequence is that a(n) = nearest integer to (1 + sqrt(A275917(n-1)+1))/2.
%C This sequence links together the spokes A275916-A275919 in the sense that A275918(n) = A275917(n)+2*a(n+1), A275919(n) = A275917(n)+4*a(n+1), and A275916(n+1) = A275917(n)+6*a(n+1).
%C (End)
%C Conjecture: a(n) = A003144(n) + n. (This is from my notebook Lattices 115 page 20 from Oct 25 2016. It is now a theorem - see the Dekking et al. paper.) - _N. J. A. Sloane_, Jul 22 2019
%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 23 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) = A140100(n). - _Jeffrey Shallit_, Oct 04 2022
%D Robbert Fokkink, Gerard Francis Ortega, Dan Rust, Corner the Empress, arXiv:2204.11805. See Table 3.
%H N. J. A. Sloane, <a href="/A140101/b140101.txt">Table of n, a(n) for n = 0..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="https://cs.uwaterloo.ca/~shallit/walnut.html">Using Walnut to Prove Results About Sequences in the OEIS</a>, Seminar, Oct 18 2
%H 022
%H Jeffrey Shallit, <a href="/A140101/a140101.txt">Automaton to be called yaut.txt in Walnut format, recognizing (n, Y(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 a(n)/n = 1+t and limit of X(n)/n = 1+1/t so that limit of a(n)/X(n) = t = tribonacci constant (A058265), and thus the limit of [a(n) + X(n)]/[a(n) - X(n)] = t^2 and the limit of [a(n)^2 + X(n)^2]/[a(n)^2 - X(n)^2] = t.
%F Conjectured recursion: Take first differences: 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 2, ... (appears to consist of only 3's and 2's); list the run lengths: 3, 1, 6, 1, 5, 1, 6, 1, 3, 1, 6, 1, 5, 1, 6, 1, ... {it appears that every second term is 1 and the other terms are 3, 5, and 6); and bisect, getting 3, 6, 5, 6, 3, 6, 5, 6, 6, 5, 6, 3, 6, ... This is (although I do not have a proof) the recursively defined A275925. Thanks to _Alois P. Heinz_ for providing enough terms of A273059 to enable a (morally) convincing check of this conjecture. - _N. J. A. Sloane_, Aug 30 2016
%F From _Michel Dekking_, Mar 17 2019: (Start)
%F This conjecture can be reformulated as follows (cf. A140100).
%F The first differences of (a(n)) = (Y(n)) as a word are given by
%F 3 delta(x),
%F where x is the tribonacci word x = A092782, and delta is the morphism
%F 1 -> 3333332,
%F 2 -> 333332,
%F 3 -> 3332.
%F This conjecture implies the frequency conjecture above: let N(i,n) be the number of letters i in a(1)a(2)...a(n). Then simple counting gives
%F a(7*N(1,n)+6*N(2,n)+4*N(3,n)) = 20*N(1,n)+17*N(2,n)+11*N(3,n), where we neglected the first symbol of a = Y.
%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/t + 17/t^2 + 11/t^3 = (1+t)*(7/t + 6/t^2 + 4/t^3).
%F This is a simple verification, using t^3 = t^2 + t + 1.
%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
%e such that Y-X and Y+X do not appear earlier as a difference or sum.
%e This sequence gives the y-coordinates of the positive quadrant in the construction given in the examples for A140100.
%p See link.
%t y[0] = 0; x[1] = 1; y[1] = 2;
%t y[n_] := y[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], x[n] = xn; Return[yn]]]];
%t Table[y[n], {n, 0, 100}] (* _Jean-François Alcover_, Jun 17 2018 *)
%o (PARI) /* Print (x,y) coordinates of the positive quadrant */ {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. A140100 (complement); A140102, A140103, A275926 (deviation from A140099).
%Y Cf. related Beatty sequences: A140098, A140099; A000201.
%Y Cf. A058265 (tribonacci constant).
%Y Cf. Greedy Queens in a spiral, A273059, A275916, A275917, A275918, A275919, A275925.
%Y See also A276385.
%Y For first differences of A140100, A140101, A140102, A140103 see A305392, A305374, A305393, A305394.
%Y The indicator function of this sequence is A305386.
%K nonn
%O 0,2
%A _Paul D. Hanna_, Jun 04 2008
%E Terms computed independently by _Reinhard Zumkeller_ and _Joshua Zucker_
%E Edited and a(0)=0 added by _N. J. A. Sloane_, Aug 30 2016
|
