login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005836 Numbers n whose base 3 representation contains no 2.
(Formerly M2353)
166

%I M2353

%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 n 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 Equivalently, lexicographically earliest increasing sequence of nonnegative numbers that does contains the arithmetic mean of any pair of terms. - _Keith F. Lynch_, Jan 28 2018

%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 A081603(a(n)) = 0. - _Reinhard Zumkeller_, Mar 02 2008

%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

%D R. K. Guy, Unsolved Problems in Number Theory, E10.

%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 David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="http://neilsloane.com/doc/tooth.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>

%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 K. Dilcher and L. Ericksen, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p24">Hyperbinary expansions and Stern polynomials</a>, Elec. J. Combin, 22, 2015, #P2.24.

%H P. Erdos, V. Lev, G. Rauzy, C. Sandor, 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., 200 (1999), 119-135 (see Table 1). <a href="http://www.math.haifa.ac.il/~seva/Papers/greeda.dvi">alternate link</a>

%H J. L. Gerver and L. T. 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., 33 (1979), 1353-1359.

%H Kathrin Kostorz et al., <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. 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., 274 (2004), 147-160.

%H J. 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, #4.

%H M. Madritsch, S. Wagner, <a href="https://doi.org/10.1007/s00605-009-0126-y">A central limit theorem for integer partitions</a>, Monatsh. Math. 161 (1) (2010) 85-114.

%H R. A. Moy and D. Rolnick, Novel structures in Stanley sequences, Discrete Math., 339 (2016), 689-698. Also <a href="http://arxiv.org/abs/1502.06013">arXiv:1502.06013v1</a>, 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 P. Pollack, <a href="http://www.math.dartmouth.edu/~ppollack/notes.pdf">Analytic and Combinatorial Number Theory</a> Course Notes, p. 228. [?Broken link]

%H P. Pollack, <a href="http://alpha01.dm.unito.it/personalpages/cerruti/ac/notes.pdf">Analytic and Combinatorial Number Theory</a> Course Notes, p. 228.

%H Rolnick, David, and Praveen S. Venkataramana, <a href="http://arxiv.org/abs/1408.4710">On the growth of Stanley sequences</a>, arXiv preprint arXiv:1408.4710 [math.CO], 2014. Also Discrete Math., 338 (2015), 1928-1937. See page 1930 of the Disc. Math. version.

%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 R. Stephan, <a href="http://arXiv.org/abs/math.CO/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.

%H R. Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H R. Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H Z. Sunic, <a href="http://arXiv.org/abs/math.CO/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), 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( b(k)* 3^k ) for k = 0..m 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 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). - _Reinhard Zumkeller_, Mar 02 2008

%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

%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)-> sum(binomial(n,k)^j,k=0..n):for i from 1 to 400 do if(t(4,i) mod 3 <>0) then print(i) fi od; # _Gary Detlefs_, Nov 28 2011

%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 *)

%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

%Y Cf. A005823, A032924, A054591, A007089, A081603, A081611, A007088, A033042-A033052, A074940, A083096. A002426, A004793, A055246, A062548, A081601, 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,changed

%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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 22:38 EDT 2018. Contains 316404 sequences. (Running on oeis4.)