[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Search: a276404 -id:a276404
     Sort: relevance | references | number | modified | created      Format: long | short | data
Lengths of runs in A276404.
+20
4
8, 1, 1, 1, 10, 1, 10, 1, 19, 1, 1, 1, 1, 1, 8, 1, 1, 1, 8, 1, 1, 1, 10, 1, 12, 1, 10, 1, 19, 1, 1, 1, 10, 1, 10, 1, 1, 1, 10, 1, 10, 1, 19, 1, 1, 1, 1, 1, 8, 1, 1, 1, 8, 1, 1, 1, 10, 1, 23, 1, 19, 1, 1, 1, 10, 1, 10, 1, 1, 1, 10, 1, 6, 1, 1, 1, 1, 1, 8, 1, 1, 1, 8, 1, 1, 1, 10, 1, 1, 1, 10, 1, 10
OFFSET
1,1
LINKS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Sep 14 2016
STATUS
approved
Positions of 1's in A276404.
+20
4
9, 11, 22, 33, 53, 55, 57, 66, 68, 77, 79, 90, 103, 114, 134, 136, 147, 158, 160, 171, 182, 202, 204, 206, 215, 217, 226, 228, 239, 263, 283, 285, 296, 307, 309, 320, 327, 329, 331, 340, 342, 351, 353, 364, 366, 377, 388, 408, 410, 412, 421, 423, 432, 434, 445, 456, 469, 476, 478, 480, 489, 491, 500
OFFSET
1,1
LINKS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Sep 14 2016
STATUS
approved
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).
+10
25
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, 40, 41, 43, 44, 46, 47, 49, 51, 52, 54, 55, 57, 58, 60, 61, 63, 64, 66, 67, 69, 71, 72, 74, 75, 77, 78, 80, 82, 83, 85, 86, 88, 89, 91, 92, 94, 95, 97, 98, 100, 102, 103, 105, 106
OFFSET
1,2
COMMENTS
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}.
Compare with A140098(n) = floor(n*(1+1/t)), a Beatty sequence involving the tribonacci constant t = t^3 - t^2 - 1 = 1.83928675521416113255...
Conjecture: A140100(n) - A140098(n) = A276404(n) is always 0 or 1; see A276406 for the positions where a difference of 1 occurs.
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
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
LINKS
N. J. A. Sloane, Table of n, a(n) for n = 1..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 and Dan Rust, A modification of Wythoff's Nim, arXiv:1904.08339 [math.CO], 2019.
Jeffrey Shallit, Some Tribonacci conjectures, arXiv:2210.03996 [math.CO], 2022.
FORMULA
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.
From Michel Dekking, Mar 16 2019: (Start)
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
1 -> 2212121212121,
2 -> 22121212121,
3 -> 2212121.
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
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.
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*1/t + 17*1/t^2 + 11*1/t^3 = (1+1/t)*(13*1/t + 11*1/t^2 + 7*1/t^3).
This is a simple verification. (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.
CONSTRUCTION: PLOT OF (A140100(n), A140101(n)).
This sequence gives the x-coordinates of the following construction.
Start with an x-y coordinate system and place an 'o' at the origin.
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.
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.
Example: after the origin, begin placing markers at x-y coordinates:
n=1: (1,2), (2,-1), (-1,-2), (-2,1);
n=2: (3,5), (5,-3), (-3,-5), (-5,3);
n=3: (4,8), (8,-4), (-4,-8), (-8,4);
n=4: (6,11), (11,-6), (-6,-11), (-11,6);
n=5: (7,13), (13,-7), (-7,-13), (-13,7); ...
The result of this process is illustrated in the following diagram (see A273059 for an equivalent picture - N. J. A. Sloane, Aug 30 2016).
----------------+---o------------
--o-------------+----------------
----o-----------+----------------
----------------+--o-------------
--------o-------+----------------
-----------o----+----------------
----------------+o---------------
--------------o-+----------------
++++++++++++++++o++++++++++++++++
----------------+-o--------------
---------------o+----------------
----------------+----o-----------
----------------+-------o--------
-------------o--+----------------
----------------+------------o---
----------------+--------------o-
------------o---+----------------
Graph: no two points lie in the same row, column, diagonal, or antidiagonal.
Points in the positive quadrant are at (A140100(n), A140101(n)).
A140101 begins: [2,5,8,11,13,16,19,22,25,28,31,33,36,39,42,...].
MAPLE
See link.
MATHEMATICA
y[0] = 0; x[1] = 1; y[1] = 2;
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]]]];
Table[x[n], {n, 1, 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. related Beatty sequences: A140098, A140099; A000201.
Cf. A058265 (tribonacci constant).
Cf. Greedy Queens in a spiral, A273059.
For first difference of A140100, A140101, A140102, A140103 see A305392, A305374, A305393, A305394.
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Jun 04 2008
EXTENSIONS
Terms computed independently by Reinhard Zumkeller and Joshua Zucker
Edited by N. J. A. Sloane, Aug 30 2016
STATUS
approved

Search completed in 0.005 seconds