|
%I M2353 #286 Mar 29 2024 18:45:52
%S 0,1,3,4,9,10,12,13,27,28,30,31,36,37,39,40,81,82,84,85,90,91,93,94,
%T 108,109,111,112,117,118,120,121,243,244,246,247,252,253,255,256,270,
%U 271,273,274,279,280,282,283,324,325,327,328,333,334,336,337,351,352
%N Numbers whose base-3 representation contains no 2.
%C 3 does not divide binomial(2s, s) if and only if s is a member of this sequence, where binomial(2s, s) = A000984(s) are the central binomial coefficients.
%C This is the lexicographically earliest increasing sequence of nonnegative numbers that contains no arithmetic progression of length 3. - Robert Craigen (craigenr(AT)cc.umanitoba.ca), Jan 29 2001
%C In the notation of A185256 this is the Stanley Sequence S(0,1). - _N. J. A. Sloane_, Mar 19 2010
%C Complement of A074940. - _Reinhard Zumkeller_, Mar 23 2003
%C Sums of distinct powers of 3. - _Ralf Stephan_, Apr 27 2003
%C Numbers n such that central trinomial coefficient A002426(n) == 1 (mod 3). - _Emeric Deutsch_ and _Bruce E. Sagan_, Dec 04 2003
%C A039966(a(n)+1) = 1; A104406(n) = number of terms <= n.
%C Subsequence of A125292; A125291(a(n)) = 1 for n>1. - _Reinhard Zumkeller_, Nov 26 2006
%C Also final value of n - 1 written in base 2 and then read in base 3 and with finally the result translated in base 10. - Philippe LALLOUET (philip.lallouet(AT)wanadoo.fr), Jun 23 2007
%C a(n) modulo 2 is the Thue-Morse sequence A010060. - _Dennis Tseng_, Jul 16 2009
%C Also numbers such that the balanced ternary representation is the same as the base 3 representation. - _Alonso del Arte_, Feb 25 2011
%C Fixed point of the morphism: 0 -> 01; 1 -> 34; 2 -> 67; ...; n -> (3n)(3n+1), starting from a(1) = 0. - _Philippe Deléham_, Oct 22 2011
%C It appears that this sequence lists the values of n which satisfy the condition sum(binomial(n, k)^(2*j), k = 0..n) mod 3 <> 0, for any j, with offset 0. See Maple code. - _Gary Detlefs_, Nov 28 2011
%C Also, it follows from the above comment by Philippe Lallouet that the sequence must be generated by the rules: a(1) = 0, and if m is in the sequence then so are 3*m and 3*m + 1. - _L. Edson Jeffery_, Nov 20 2015
%C Add 1 to each term and we get A003278. - _N. J. A. Sloane_, Dec 01 2019
%D Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section E10, pp. 317-323.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H David W. Wilson, <a href="/A005836/b005836.txt">Table of n, a(n) for n = 1..10000</a> (first 1024 terms from T. D. Noe)
%H J.-P. Allouche, G.-N. Han, and J. Shallit, <a href="https://arxiv.org/abs/2006.08909">On some conjectures of P. Barry</a>, arXiv:2006.08909 [math.NT], 2020.
%H J.-P. Allouche and J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/as0.ps">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.
%H J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1007/3-540-52282-4_28">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.
%H J.-P. Allouche, J. Shallit and G. Skordev, <a href="http://dx.doi.org/10.1016/j.disc.2004.12.004">Self-generating sets, integers with missing blocks and substitutions</a>, Discrete Math. 292 (2005) 1-15.
%H David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
%H Megumi Asada, Bruce Fang, Eva Fourakis, Sarah Manski, Nathan McNew, Steven J. Miller, Gwyneth Moreland, Ajmain Yamin, and Sindy Xin Zhang, <a href="https://web.williams.edu/Mathematics/sjmiller/public_html/math/papers/ramseynoncommutative10.pdf">Avoiding 3-Term Geometric Progressions in Hurwitz Quaternions</a>, Williams College (2023).
%H Robert Baillie and Thomas Schmelzer, <a href="https://library.wolfram.com/infocenter/MathSource/7166/">Summing Kempner's Curious (Slowly-Convergent) Series</a>, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008.
%H Noam Benson-Tilsen, Samuel Brock, Brandon Faunce, Monish Kumar, Noah Dokko Stein, and Joshua Zelinsky, <a href="https://arxiv.org/abs/2107.11706">Total Difference Labeling of Regular Infinite Graphs</a>, arXiv:2107.11706 [math.CO], 2021.
%H Raghavendra Bhat, Cristian Cobeli, and Alexandru Zaharescu, <a href="https://arxiv.org/abs/2309.03922">Filtered rays over iterated absolute differences on layers of integers</a>, arXiv:2309.03922 [math.NT], 2023. See page 16.
%H Matvey Borodin, Hannah Han, Kaylee Ji, Tanya Khovanova, Alexander Peng, David Sun, Isabel Tu, Jason Yang, William Yang, Kevin Zhang, and Kevin Zhao, <a href="https://arxiv.org/abs/1901.09818">Variants of Base 3 over 2</a>, arXiv:1901.09818 [math.NT], 2019.
%H Ben Chen, Richard Chen, Joshua Guo, Tanya Khovanova, Shane Lee, Neil Malur, Nastia Polina, Poonam Sahoo, Anuj Sakarda, Nathan Sheffield, and Armaan Tipirneni, <a href="https://arxiv.org/abs/1808.04199">On Base 3/2 and its Sequences</a>, arXiv:1808.04304 [math.NT], 2018.
%H Karl Dilcher and Larry Ericksen, <a href="https://doi.org/10.37236/4822">Hyperbinary expansions and Stern polynomials</a>, Elec. J. Combin, Vol. 22 (2015), Article P2.24.
%H P. Erdős, V. Lev, G. Rauzy, C. Sandor, and A. Sarkozy, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00385-9">Greedy algorithm, arithmetic progressions, subset sums and divisibility</a>, Discrete Math., Vol. 200, No. 1-3 (1999), pp. 119-135 (see Table 1). <a href="http://www.math.haifa.ac.il/~seva/Papers/greeda.dvi">alternate link</a>.
%H Joseph L. Gerver and L. Thomas Ramsey, <a href="http://dx.doi.org/10.1090/S0025-5718-1979-0537982-0">Sets of integers with no long arithmetic progressions generated by the greedy algorithm</a>, Math. Comp., Vol. 33, No. 148 (1979), pp. 1353-1359.
%H Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, p. 45.
%H Kathrin Kostorz, Robert W. Hölzel and Katharina Krischer, <a href="http://dx.doi.org/10.1088/1367-2630/15/8/083010">Distributed coupling complexity in a weakly coupled oscillatory network with associative properties</a>, New J. Phys., Vol. 15 (2013), #083010; doi:10.1088/1367-2630/15/8/083010.
%H Clark Kimberling, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00085-2">Affinely recursive sets and orderings of languages</a>, Discrete Math., Vol. 274, Vol. 1-3 (2004), pp. 147-160.
%H John W. Layman, <a href="https://cs.uwaterloo.ca/journals/JIS/LAYMAN/layman.html">Some Properties of a Certain Nonaveraging Sequence</a>, J. Integer Sequences, Vol. 2 (1999), Article 99.1.3.
%H Manfred. Madritsch and Stephan Wagner, <a href="https://doi.org/10.1007/s00605-009-0126-y">A central limit theorem for integer partitions</a>, Monatsh. Math., Vol. 161, No. 1 (2010), pp. 85-114.
%H Richard A. Moy and David Rolnick, <a href="https://doi.org/10.1016/j.disc.2015.10.017">Novel structures in Stanley sequences</a>, Discrete Math., Vol. 339, No. 2 (2016), pp. 689-698; <a href="http://arxiv.org/abs/1502.06013">arXiv preprint</a>, arXiv:1502.06013 [math.CO], 2015.
%H A. M. Odlyzko and R. P. Stanley, Some curious sequences constructed with the greedy algorithm, 1978, remark 1 (<a href="http://www.dtc.umn.edu/~odlyzko/unpublished/greedy.sequence.pdf">PDF</a>, <a href="http://www.dtc.umn.edu/~odlyzko/unpublished/greedy.sequence.ps">PS</a>, <a href="http://www.dtc.umn.edu/~odlyzko/unpublished/greedy.sequence.tex">TeX</a>).
%H Paul Pollack, <a href="http://www.math.dartmouth.edu/~ppollack/notes.pdf">Analytic and Combinatorial Number Theory</a> Course Notes, p. 228. [?Broken link]
%H Paul Pollack, <a href="http://alpha01.dm.unito.it/personalpages/cerruti/ac/notes.pdf">Analytic and Combinatorial Number Theory</a> Course Notes, p. 228.
%H David Rolnick and Praveen S. Venkataramana, <a href="https://doi.org/10.1016/j.disc.2015.04.006">On the growth of Stanley sequences</a>, Discrete Math., Vol. 338, No. 11 (2015), pp. 1928-1937, see p. 1930; <a href="http://arxiv.org/abs/1408.4710">arXiv preprint</a>, arXiv:1408.4710 [math.CO], 2014.
%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>.
%H Ralf Stephan, <a href="https://arxiv.org/abs/math/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.
%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences with (relatively) simple ordinary generating functions</a>, 2004.
%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>.
%H Zoran Sunic, <a href="https://arxiv.org/abs/math/0612080">Tree morphisms, transducers and integer sequences</a>, arXiv:math/0612080 [math.CO], 2006.
%H B. Vasic, K. Pedagani and M. Ivkovic, <a href="http://dx.doi.org/10.1109/TCOMM.2004.833037">High-rate girth-eight low-density parity-check codes on rectangular integer lattices</a>, IEEE Transactions on Communications, Vol. 52, Issue 8 (2004), pp. 1248-1252.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CentralBinomialCoefficient.html">Central Binomial Coefficient</a>.
%H <a href="/index/Ar#3-automatic">Index entries for 3-automatic sequences</a>.
%F a(n) = A005823(n)/2 = A003278(n)-1 = A033159(n)-2 = A033162(n)-3.
%F Numbers n such that the coefficient of x^n is > 0 in prod (k >= 0, 1 + x^(3^k)). - _Benoit Cloitre_, Jul 29 2003
%F a(n+1) = Sum_{k=0..m} b(k)* 3^k and n = Sum( b(k)* 2^k ).
%F a(2n+1) = 3a(n+1), a(2n+2) = a(2n+1) + 1, a(0) = 0.
%F a(n+1) = 3*a(floor(n/2)) + n - 2*floor(n/2). - _Ralf Stephan_, Apr 27 2003
%F G.f.: (x/(1-x)) * Sum_{k>=0} 3^k*x^2^k/(1+x^2^k). - _Ralf Stephan_, Apr 27 2003
%F a(n) = Sum_{k = 1..n-1} (1 + 3^A007814(k)) / 2. - _Philippe Deléham_, Jul 09 2005
%F From _Reinhard Zumkeller_, Mar 02 2008: (Start)
%F A081603(a(n)) = 0.
%F If the offset were changed to zero, then: a(0) = 0, a(n+1) = f(a(n) + 1, f(a(n)+1) where f(x, y) = if x < 3 and x <> 2 then y else if x mod 3 = 2 then f(y+1, y+1) else f(floor(x/3), y). (End)
%F With offset a(0) = 0: a(n) = Sum_{k>=0} A030308(n,k)*3^k. - _Philippe Deléham_, Oct 15 2011
%F a(2^n) = A003462(n). - _Philippe Deléham_, Jun 06 2015
%F We have liminf_{n->infinity} a(n)/n^(log(3)/log(2)) = 1/2 and limsup_{n->infinity} a(n)/n^(log(3)/log(2)) = 1. - _Gheorghe Coserea_, Sep 13 2015
%F a(2^k+m) = a(m) + 3^k with 1 <= m <= 2^k and 1 <= k, a(1)=0, a(2)=1. - _Paul Weisenhorn_, Mar 22 2020
%F Sum_{n>=2} 1/a(n) = 2.682853110966175430853916904584699374821677091415714815171756609672281184705... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - _Amiram Eldar_, Feb 12 2022
%F A065361(a(n)) = n-1. - _Rémy Sigrist_, Feb 06 2023
%F a(n) ≍ n^k, where k = log 3/log 2 = 1.5849625007. (I believe the constant varies from 1/2 to 1.) - _Charles R Greathouse IV_, Mar 29 2024
%e a(6) = 12 because 6 = 0*2^0 + 1*2^1 + 1*2^2 = 2+4 and 12 = 0*3^0 + 1*3^1 + 1*3^2 = 3 + 9.
%e This sequence regarded as a triangle with rows of lengths 1, 1, 2, 4, 8, 16, ...:
%e 0
%e 1
%e 3, 4
%e 9, 10, 12, 13
%e 27, 28, 30, 31, 36, 37, 39, 40
%e 81, 82, 84, 85, 90, 91, 93, 94, 108, 109, 111, 112, 117, 118, 120, 121
%e ... - _Philippe Deléham_, Jun 06 2015
%p t := (j, n) -> add(binomial(n,k)^j, k=0..n):
%p for i from 1 to 400 do
%p if(t(4,i) mod 3 <>0) then print(i) fi
%p od; # _Gary Detlefs_, Nov 28 2011
%p # alternative Maple program:
%p a:= proc(n) option remember: local k, m:
%p if n=1 then 0 elif n=2 then 1 elif n>2 then k:=floor(log[2](n-1)): m:=n-2^k: procname(m)+3^k: fi: end proc:
%p seq(a(n), n=1.. 20); # _Paul Weisenhorn_, Mar 22 2020
%p # third Maple program:
%p a:= n-> `if`(n=1, 0, irem(n-1, 2, 'q')+3*a(q+1)):
%p seq(a(n), n=1..100); # _Alois P. Heinz_, Jan 26 2022
%t Table[FromDigits[IntegerDigits[k, 2], 3], {k, 60}]
%t Select[Range[0, 400], DigitCount[#, 3, 2] == 0 &] (* _Harvey P. Dale_, Jan 04 2012 *)
%t Join[{0}, Accumulate[Table[(3^IntegerExponent[n, 2] + 1)/2, {n, 57}]]] (* _IWABUCHI Yu(u)ki_, Aug 01 2012 *)
%t FromDigits[#,3]&/@Tuples[{0,1},7] (* _Harvey P. Dale_, May 10 2019 *)
%o (PARI) A=vector(100);for(n=2,#A,A[n]=if(n%2,3*A[n\2+1],A[n-1]+1));A \\ _Charles R Greathouse IV_, Jul 24 2012
%o (PARI) is(n)=while(n,if(n%3>1,return(0));n\=3);1 \\ _Charles R Greathouse IV_, Mar 07 2013
%o (PARI) a(n) = fromdigits(binary(n-1),3); \\ _Gheorghe Coserea_, Jun 15 2018
%o (Haskell)
%o a005836 n = a005836_list !! (n-1)
%o a005836_list = filter ((== 1) . a039966) [0..]
%o -- _Reinhard Zumkeller_, Jun 09 2012, Sep 29 2011
%o (Python)
%o def A005836(n):
%o return int(format(n-1,'b'),3) # _Chai Wah Wu_, Jan 04 2015
%o (Julia)
%o function a(n)
%o m, r, b = n, 0, 1
%o while m > 0
%o m, q = divrem(m, 2)
%o r += b * q
%o b *= 3
%o end
%o r end; [a(n) for n in 0:57] |> println # _Peter Luschny_, Jan 03 2021
%Y Cf. A039966 (characteristic function).
%Y Cf. A002426, A004793, A005823, A007088, A007089, A032924, A033042-A033052, A054591, A055246, A062548, A065361, A074940, A081601, A081603, A081611, A083096, A089118, A121153, A170943, A185256.
%Y For generating functions Product_{k>=0} (1+a*x^(b^k)) for the following values of (a,b) see: (1,2) A000012 and A000027, (1,3) A039966 and A005836, (1,4) A151666 and A000695, (1,5) A151667 and A033042, (2,2) A001316, (2,3) A151668, (2,4) A151669, (2,5) A151670, (3,2) A048883, (3,3) A117940, (3,4) A151665, (3,5) A151671, (4,2) A102376, (4,3) A151672, (4,4) A151673, (4,5) A151674.
%Y Row 3 of array A104257.
%Y Summary of increasing sequences avoiding arithmetic progressions of specified lengths (the second of each pair is obtained by adding 1 to the first):
%Y 3-term AP: A005836 (>=0), A003278 (>0);
%Y 4-term AP: A005839 (>=0), A005837 (>0);
%Y 5-term AP: A020654 (>=0), A020655 (>0);
%Y 6-term AP: A020656 (>=0), A005838 (>0);
%Y 7-term AP: A020657 (>=0), A020658 (>0);
%Y 8-term AP: A020659 (>=0), A020660 (>0);
%Y 9-term AP: A020661 (>=0), A020662 (>0);
%Y 10-term AP: A020663 (>=0), A020664 (>0).
%Y See also A000452.
%K nonn,nice,easy,base,tabf
%O 1,3
%A _N. J. A. Sloane_, _Jeffrey Shallit_
%E Offset corrected by _N. J. A. Sloane_, Mar 02 2008
%E Edited by the Associate Editors of the OEIS, Apr 07 2009
|
