Displaying 1-3 of 3 results found.
page
1
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
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
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
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...
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
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.
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.
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.
A140101 begins: [2,5,8,11,13,16,19,22,25,28,31,33,36,39,42,...].
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]]]];
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. Greedy Queens in a spiral, A273059.
Search completed in 0.005 seconds
|