login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A140101 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). 32
0, 2, 5, 8, 11, 13, 16, 19, 22, 25, 28, 31, 33, 36, 39, 42, 45, 48, 50, 53, 56, 59, 62, 65, 68, 70, 73, 76, 79, 81, 84, 87, 90, 93, 96, 99, 101, 104, 107, 110, 113, 116, 118, 121, 124, 127, 130, 133, 136, 138, 141, 144, 147, 150, 153, 156, 158, 161, 164, 167, 170, 173 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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}.

Compare with A140099(n) = [n*(1+t)], a Beatty sequence involving the tribonacci constant t = t^3 - t^2 - 1 = 1.83928675521416113255...

Theorem: A140099(n) - A140101(n) is always in {-1,0,1} (see A275926). (See also A276385.)

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.

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.).

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.

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.

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).

(End)

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

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..50000, Sep 13 2016 (First 1001 terms from Reinhard Zumkeller)

F. Michel Dekking, Jeffrey Shallit, and N. J. A. Sloane, Queens in exile: non-attacking queens on infinite chess boards, Electronic J. Combin., 27:1 (2020), #P1.52.

Eric Duchêne and Michel Rigo, A morphic approach to combinatorial games: the Tribonacci case. RAIRO - Theoretical Informatics and Applications, 42, 2008, pp 375-393. doi:10.1051/ita:2007039. [Also available here]

Robbert Fokkink, Dan Rust, A modification of Wythoff's Nim, arXiv:1904.08339 [math.CO], 2019.

N. J. A. Sloane, Maple program for A140100, A140101, A140102, A140103

FORMULA

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.

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

From Michel Dekking, Mar 17 2019: (Start)

This conjecture can be reformulated as follows (cf. A140100).

The first differences of (a(n)) = (Y(n)) as a word are given by

      3 delta(x),

where x is the tribonacci word x = A092782, and delta is the morphism

      1 -> 3333332,

      2 -> 333332,

      3 -> 3332.

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

       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.

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

     20/t + 17/t^2 + 11/t^3 = (1+t)*(7/t + 6/t^2 + 4/t^3).

This is a simple verification, using t^3 = t^2 + t + 1.

End)

EXAMPLE

Start with Y(0)=0, X(1)=1, Y(1)=2 ; Y(1)-X(1)=1, Y(1)+X(1)=3.

Next choose X(2)=3 and Y(2)=5; Y(2)-X(2)=2, Y(2)+X(2)=8.

Next choose X(3)=4 and Y(3)=8; Y(3)-X(3)=4, Y(3)+X(3)=12.

Next choose X(4)=6 and Y(4)=11; Y(4)-X(4)=5, Y(4)+X(4)=17.

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.

This sequence gives the y-coordinates of the positive quadrant in the construction given in the examples for A140100.

MAPLE

See link.

MATHEMATICA

y[0] = 0; x[1] = 1; y[1] = 2;

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]]]];

Table[y[n], {n, 0, 100}] (* Jean-François Alcover, Jun 17 2018 *)

PROG

(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))))))}

CROSSREFS

Cf. A140100 (complement); A140102, A140103, A275926 (deviation from A140099).

Cf. related Beatty sequences: A140098, A140099; A000201.

Cf. A058265 (tribonacci constant).

Cf. Greedy Queens in a spiral, A273059, A275916, A275917, A275918, A275919, A275925.

See also A276385.

For first differences of A140100, A140101, A140102, A140103 see A305392, A305374, A305393, A305394.

Sequence in context: A093609 A249118 A292643 * A141207 A190057 A190305

Adjacent sequences:  A140098 A140099 A140100 * A140102 A140103 A140104

KEYWORD

nonn

AUTHOR

Paul D. Hanna, Jun 04 2008

EXTENSIONS

Terms computed independently by Reinhard Zumkeller and Joshua Zucker

Edited and a(0)=0 added by N. J. A. Sloane, Aug 30 2016

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 20 16:31 EDT 2020. Contains 337265 sequences. (Running on oeis4.)