Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Stanley sequence
open-in-new
<h2 id="binaryternary-sequence">Binary–ternary sequence</h2> <p>The Stanley sequence starting from the empty set consists of those numbers whose <a href="/facts/Ternary_number/bMUfR74P">ternary representations</a> have only the digits 0 and 1.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> That is, when written in ternary, they look like <a href="/facts/Binary_number/a6JDSRPs">binary numbers</a>. These numbers are </p> 0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... (sequence A005836 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>) <p>By their construction as a Stanley sequence, this sequence is the <a href="/facts/Lexicographical_order/xQANy8Br">lexicographically</a> first <a href="/facts/Salem%E2%80%93Spencer_set/aWogz0JA">arithmetic-progression-free sequence</a>. Its elements are the sums of distinct <a href="/facts/Power_of_three/D8PSevmm">powers of three</a>, the numbers n {\displaystyle n} such that the n {\displaystyle n} th central binomial coefficient is 1 mod 3, and the numbers whose <a href="/facts/Balanced_ternary/5GsqVUCk">balanced ternary</a> representation is the same as their ternary representation.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p><p>The construction of this sequence from the ternary numbers is analogous to the construction of the <a href="/facts/Moser%E2%80%93de_Bruijn_sequence/LGlv7DkT">Moser–de Bruijn sequence</a>, the sequence of numbers whose base-4 representations have only the digits 0 and 1, and the construction of the <a href="/facts/Cantor_set/6NUcMJvN">Cantor set</a> as the subset of real numbers in the interval [ 0 , 1 ] {\displaystyle [0,1]} whose ternary representations use only the digits 0 and 2. More generally, they are a <a href="/facts/K-regular_sequence/n0ae3bc9">2-regular sequence</a>, one of a class of integer sequences defined by a linear <a href="/facts/Recurrence_relation/JolXC71M">recurrence relation</a> with multiplier 2.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p><p>This sequence includes three <a href="/facts/Power_of_two/MA6WEpTt">powers of two</a>: 1, 4, and 256 = 35 + 32 + 3 + 1. <a href="/facts/Paul_Erd%C5%91s/63LoUTe1">Paul Erdős</a> conjectured that these are the only powers of two that it contains.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p> <h2 id="growth-rate">Growth rate</h2> <p><a href="/facts/Andrew_Odlyzko/rBsYtPz5">Andrew Odlyzko</a> and <a href="/facts/Richard_P._Stanley/8bQ4QrLM">Richard P. Stanley</a> observed that the number of elements up to some threshold n {\displaystyle n} in the binary–ternary sequence, and in other Stanley sequences starting from { 0 , 3 k } {\displaystyle \{0,3^{k}\}} or { 0 , 2 ⋅ 3 k } {\displaystyle \{0,2\cdot 3^{k}\}} , grows proportionally to n log 2 3 ≈ n 0.631 {\displaystyle n^{\log _{2}3}\approx n^{0.631}} . For other starting sets { 0 , s } {\displaystyle \{0,s\}} the Stanley sequences that they considered appeared to grow more erratically but even more sparsely.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> For instance, the first irregular case is s = 4 {\displaystyle s=4} , which generates the sequence </p> 0, 4, 5, 7, 11, 12, 16, 23, 26, 31, 33, 37, 38, 44, 49, 56, 73, 78, 80, 85, 95, 99, ... (sequence A005487 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>) <p>Odlyzko and Stanley conjectured that in such cases the number of elements up to any threshold n {\displaystyle n} is O ( n log n ) {\displaystyle O{\bigl (}{\sqrt {n\log n}}{\bigr )}} . That is, there is a dichotomy in the growth rate of Stanley sequences between the ones with similar growth to the binary–ternary sequence and others with a much smaller growth rate; according to this conjecture, there should be no Stanley sequences with intermediate growth.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a><a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p><p>Moy proved that Stanley sequences cannot grow significantly more slowly than the conjectured bound for the sequences of slow growth. Every Stanley sequence has Ω ( n ) {\displaystyle \Omega {\bigl (}{\sqrt {n}}{\bigr )}} elements up to n {\displaystyle n} . More precisely Moy showed that, for every such sequence, every ε > 0 {\displaystyle \varepsilon >0} , and all sufficiently large n {\displaystyle n} , the number of elements is at least ( 2 − ε ) n {\displaystyle ({\sqrt {2}}-\varepsilon ){\sqrt {n}}} .<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> Later authors improved the constant factor in this bound,<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> and proved that for Stanley sequences that grow as n log 2 3 {\displaystyle n^{\log _{2}3}} the constant factor in their growth rates can be any rational number whose denominator is a power of three.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p> <h2 id="history">History</h2> <p>A variation of the binary–ternary sequence (with one added to each element) was considered in 1936 by <a href="/facts/Paul_Erd%C5%91s/63LoUTe1">Paul Erdős</a> and <a href="/facts/P%C3%A1l_Tur%C3%A1n/nkWkQB6M">Pál Turán</a>, who observed that it has no three-term arithmetic progression and conjectured (incorrectly) that it was the densest possible sequence with no arithmetic progression.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> </p><p>In unpublished work with <a href="/facts/Andrew_Odlyzko/rBsYtPz5">Andrew Odlyzko</a> in 1978, <a href="/facts/Richard_P._Stanley/8bQ4QrLM">Richard P. Stanley</a> experimented with the greedy algorithm to generate progression-free sequences. The sequences they studied were exactly the Stanley sequences for the initial sets { 0 , s } {\displaystyle \{0,s\}} .<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> </p><p>Stanley sequences were named, and generalized to other starting sets than { 0 , s } {\displaystyle \{0,s\}} , in a paper published in 1999 by Erdős (posthumously) with four other authors.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> </p> <h2 id="further-reading">Further reading</h2> <ul><li>Moy, Richard A. (2017), <i>Stanley sequences with odd character</i>, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1707.02037">1707.02037</a></li> <li>Moy, Richard A.; Rolnick, David (2016), "Novel structures in Stanley sequences", <i><a href="/facts/Discrete_Mathematics_(journal)/K4e6z8wQ">Discrete Mathematics</a></i>, 339 (2): 689–698, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1502.06013">1502.06013</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.disc.2015.10.017">10.1016/j.disc.2015.10.017</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=3431382">3431382</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:6660477">6660477</a></li> <li>Rolnick, David (2017), "On the classification of Stanley sequences", <i><a href="/facts/European_Journal_of_Combinatorics/a6jNXFuH">European Journal of Combinatorics</a></i>, 59: 51–70, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1408.1940">1408.1940</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.ejc.2016.06.004">10.1016/j.ejc.2016.06.004</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=3546902">3546902</a></li> <li>Sawhney, Mehtaab (2017), <i>Character Values of Stanley Sequences</i>, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1706.05444">1706.05444</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Odlyzko, A. M.; Stanley, R. P. (January 1978), OdlSta-78 (PDF) <a href="/wiki/Andrew_Odlyzko" target="_blank">/wiki/Andrew_Odlyzko</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Sloane, N. J. A. (ed.). "Sequence A005836". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. <a href="/wiki/Neil_Sloane" target="_blank">/wiki/Neil_Sloane</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Allouche, Jean-Paul; Shallit, Jeffrey (1992), "The ring of k {\displaystyle k} -regular sequences", Theoretical Computer Science, 98 (2): 163–197, CiteSeerX 10.1.1.8.6912, doi:10.1016/0304-3975(92)90001-V, MR 1166363. See Example 26, p. 192. <a href="/wiki/Jeffrey_Shallit" target="_blank">/wiki/Jeffrey_Shallit</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Gupta, Hansraj (1978), "Powers of 2 and sums of distinct powers of 3", Univerzitet u Beogradu Publikacije Elektrotehničkog Fakulteta, Serija Matematika i Fizika (602–633): 151–158 (1979), MR 0580438 <a href="/wiki/MR_(identifier)" target="_blank">/wiki/MR_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Odlyzko, A. M.; Stanley, R. P. (January 1978), OdlSta-78 (PDF) <a href="/wiki/Andrew_Odlyzko" target="_blank">/wiki/Andrew_Odlyzko</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Odlyzko, A. M.; Stanley, R. P. (January 1978), OdlSta-78 (PDF) <a href="/wiki/Andrew_Odlyzko" target="_blank">/wiki/Andrew_Odlyzko</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Erdős, P.; Lev, V.; Rauzy, G.; Sándor, C.; Sárközy, A. (1999), "Greedy algorithm, arithmetic progressions, subset sums and divisibility", Discrete Mathematics, 200 (1–3): 119–135, doi:10.1016/S0012-365X(98)00385-9, MR 1692285 <a href="/wiki/Paul_Erd%C5%91s" target="_blank">/wiki/Paul_Erd%C5%91s</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Moy, Richard A. (2011), "On the growth of the counting function of Stanley sequences", Discrete Mathematics, 311 (7): 560–562, arXiv:1101.0022, doi:10.1016/j.disc.2010.12.019, MR 2765623, S2CID 11040813 <a href="/wiki/Discrete_Mathematics_(journal)" target="_blank">/wiki/Discrete_Mathematics_(journal)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Dai, Li-Xia; Chen, Yong-Gao (2013), "On the counting function of Stanley sequences", Publicationes Mathematicae Debrecen, 82 (1): 91–95, doi:10.5486/PMD.2013.5286, MR 3034370 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Rolnick, David; Venkataramana, Praveen S. (2015), "On the growth of Stanley sequences", Discrete Mathematics, 338 (11): 1928–1937, arXiv:1408.4710, doi:10.1016/j.disc.2015.04.006, MR 3357778, S2CID 2568329 <a href="/wiki/Discrete_Mathematics_(journal)" target="_blank">/wiki/Discrete_Mathematics_(journal)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Erdős, Paul; Turán, Paul (1936), "On some sequences of integers" (PDF), Journal of the London Mathematical Society, 11 (4): 261–264, doi:10.1112/jlms/s1-11.4.261, MR 1574918 <a href="/wiki/Paul_Erd%C5%91s" target="_blank">/wiki/Paul_Erd%C5%91s</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Odlyzko, A. M.; Stanley, R. P. (January 1978), OdlSta-78 (PDF) <a href="/wiki/Andrew_Odlyzko" target="_blank">/wiki/Andrew_Odlyzko</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Erdős, P.; Lev, V.; Rauzy, G.; Sándor, C.; Sárközy, A. (1999), "Greedy algorithm, arithmetic progressions, subset sums and divisibility", Discrete Mathematics, 200 (1–3): 119–135, doi:10.1016/S0012-365X(98)00385-9, MR 1692285 <a href="/wiki/Paul_Erd%C5%91s" target="_blank">/wiki/Paul_Erd%C5%91s</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> </ol>