A005836 Numbers whose base-3 representation contains no 2. (Formerly M2353)

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, 81, 82, 84, 85, 90, 91, 93, 94, 108, 109, 111, 112, 117, 118, 120, 121, 243, 244, 246, 247, 252, 253, 255, 256, 270, 271, 273, 274, 279, 280, 282, 283, 324, 325, 327, 328, 333, 334, 336, 337, 351, 352

Offset

1,3

Comments

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.

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

In the notation of A185256 this is the Stanley Sequence S(0,1). - N. J. A. Sloane, Mar 19 2010

Complement of A074940. - Reinhard Zumkeller, Mar 23 2003

Sums of distinct powers of 3. - Ralf Stephan, Apr 27 2003

Numbers n such that central trinomial coefficient A002426(n) == 1 (mod 3). - Emeric Deutsch and Bruce E. Sagan, Dec 04 2003

A039966(a(n)+1) = 1; A104406(n) = number of terms <= n.

Subsequence of A125292; A125291(a(n)) = 1 for n>1. - Reinhard Zumkeller, Nov 26 2006

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

a(n) modulo 2 is the Thue-Morse sequence A010060. - Dennis Tseng, Jul 16 2009

Also numbers such that the balanced ternary representation is the same as the base 3 representation. - Alonso del Arte, Feb 25 2011

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

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

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

Add 1 to each term and we get A003278. - N. J. A. Sloane, Dec 01 2019

References

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section E10, pp. 317-323.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

David W. Wilson, Table of n, a(n) for n = 1..10000 (first 1024 terms from T. D. Noe)

J.-P. Allouche, G.-N. Han, and J. Shallit, On some conjectures of P. Barry, arXiv:2006.08909 [math.NT], 2020.

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.

J.-P. Allouche, J. Shallit and G. Skordev, Self-generating sets, integers with missing blocks and substitutions, Discrete Math. 292 (2005) 1-15.

David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, 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.]

Megumi Asada, Bruce Fang, Eva Fourakis, Sarah Manski, Nathan McNew, Steven J. Miller, Gwyneth Moreland, Ajmain Yamin, and Sindy Xin Zhang, Avoiding 3-Term Geometric Progressions in Hurwitz Quaternions, Williams College (2023).

Robert Baillie and Thomas Schmelzer, Summing Kempner's Curious (Slowly-Convergent) Series, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008.

Noam Benson-Tilsen, Samuel Brock, Brandon Faunce, Monish Kumar, Noah Dokko Stein, and Joshua Zelinsky, Total Difference Labeling of Regular Infinite Graphs, arXiv:2107.11706 [math.CO], 2021.

Raghavendra Bhat, Cristian Cobeli, and Alexandru Zaharescu, Filtered rays over iterated absolute differences on layers of integers, arXiv:2309.03922 [math.NT], 2023. See page 16.

Matvey Borodin, Hannah Han, Kaylee Ji, Tanya Khovanova, Alexander Peng, David Sun, Isabel Tu, Jason Yang, William Yang, Kevin Zhang, and Kevin Zhao, Variants of Base 3 over 2, arXiv:1901.09818 [math.NT], 2019.

Ben Chen, Richard Chen, Joshua Guo, Tanya Khovanova, Shane Lee, Neil Malur, Nastia Polina, Poonam Sahoo, Anuj Sakarda, Nathan Sheffield, and Armaan Tipirneni, On Base 3/2 and its Sequences, arXiv:1808.04304 [math.NT], 2018.

Karl Dilcher and Larry Ericksen, Hyperbinary expansions and Stern polynomials, Elec. J. Combin, Vol. 22 (2015), Article P2.24.

P. Erdős, V. Lev, G. Rauzy, C. Sandor, and A. Sarkozy, Greedy algorithm, arithmetic progressions, subset sums and divisibility, Discrete Math., Vol. 200, No. 1-3 (1999), pp. 119-135 (see Table 1). alternate link.

Joseph L. Gerver and L. Thomas Ramsey, Sets of integers with no long arithmetic progressions generated by the greedy algorithm, Math. Comp., Vol. 33, No. 148 (1979), pp. 1353-1359.

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 45.

Kathrin Kostorz, Robert W. Hölzel and Katharina Krischer, Distributed coupling complexity in a weakly coupled oscillatory network with associative properties, New J. Phys., Vol. 15 (2013), #083010; doi:10.1088/1367-2630/15/8/083010.

Clark Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., Vol. 274, Vol. 1-3 (2004), pp. 147-160.

John W. Layman, Some Properties of a Certain Nonaveraging Sequence, J. Integer Sequences, Vol. 2 (1999), Article 99.1.3.

Manfred. Madritsch and Stephan Wagner, A central limit theorem for integer partitions, Monatsh. Math., Vol. 161, No. 1 (2010), pp. 85-114.

Richard A. Moy and David Rolnick, Novel structures in Stanley sequences, Discrete Math., Vol. 339, No. 2 (2016), pp. 689-698; arXiv preprint, arXiv:1502.06013 [math.CO], 2015.

A. M. Odlyzko and R. P. Stanley, Some curious sequences constructed with the greedy algorithm, 1978, remark 1 (PDF, PS, TeX).

Paul Pollack, Analytic and Combinatorial Number Theory Course Notes, p. 228. [?Broken link]

Paul Pollack, Analytic and Combinatorial Number Theory Course Notes, p. 228.

David Rolnick and Praveen S. Venkataramana, On the growth of Stanley sequences, Discrete Math., Vol. 338, No. 11 (2015), pp. 1928-1937, see p. 1930; arXiv preprint, arXiv:1408.4710 [math.CO], 2014.

N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS.

Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.

Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.

Ralf Stephan, Table of generating functions.

Zoran Sunic, Tree morphisms, transducers and integer sequences, arXiv:math/0612080 [math.CO], 2006.

B. Vasic, K. Pedagani and M. Ivkovic, High-rate girth-eight low-density parity-check codes on rectangular integer lattices, IEEE Transactions on Communications, Vol. 52, Issue 8 (2004), pp. 1248-1252.

Eric Weisstein's World of Mathematics, Central Binomial Coefficient.

Index entries for 3-automatic sequences.

Formula

a(n) = A005823(n)/2 = A003278(n)-1 = A033159(n)-2 = A033162(n)-3.

Numbers n such that the coefficient of x^n is > 0 in prod (k >= 0, 1 + x^(3^k)). - Benoit Cloitre, Jul 29 2003

a(n+1) = Sum_{k=0..m} b(k)* 3^k and n = Sum( b(k)* 2^k ).

a(2n+1) = 3a(n+1), a(2n+2) = a(2n+1) + 1, a(0) = 0.

a(n+1) = 3*a(floor(n/2)) + n - 2*floor(n/2). - Ralf Stephan, Apr 27 2003

G.f.: (x/(1-x)) * Sum_{k>=0} 3^k*x^2^k/(1+x^2^k). - Ralf Stephan, Apr 27 2003

a(n) = Sum_{k = 1..n-1} (1 + 3^A007814(k)) / 2. - Philippe Deléham, Jul 09 2005

From Reinhard Zumkeller, Mar 02 2008: (Start)

A081603(a(n)) = 0.

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)

With offset a(0) = 0: a(n) = Sum_{k>=0} A030308(n,k)*3^k. - Philippe Deléham, Oct 15 2011

a(2^n) = A003462(n). - Philippe Deléham, Jun 06 2015

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

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

Sum_{n>=2} 1/a(n) = 2.682853110966175430853916904584699374821677091415714815171756609672281184705... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - Amiram Eldar, Feb 12 2022

A065361(a(n)) = n-1. - Rémy Sigrist, Feb 06 2023

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

Example

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.
This sequence regarded as a triangle with rows of lengths 1, 1, 2, 4, 8, 16, ...:
   0
   1
   3,  4
   9, 10, 12, 13
  27, 28, 30, 31, 36, 37, 39, 40
  81, 82, 84, 85, 90, 91, 93, 94, 108, 109, 111, 112, 117, 118, 120, 121
... - Philippe Deléham, Jun 06 2015

Maple

t := (j, n) -> add(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
# alternative Maple program:
a:= proc(n) option remember: local k, m:
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:
seq(a(n), n=1.. 20); # Paul Weisenhorn, Mar 22 2020
# third Maple program:
a:= n-> `if`(n=1, 0, irem(n-1, 2, 'q')+3*a(q+1)):
seq(a(n), n=1..100);  # Alois P. Heinz, Jan 26 2022

Mathematica

Table[FromDigits[IntegerDigits[k, 2], 3], {k, 60}]
Select[Range[0, 400], DigitCount[#, 3, 2] == 0 &] (* Harvey P. Dale, Jan 04 2012 *)
Join[{0}, Accumulate[Table[(3^IntegerExponent[n, 2] + 1)/2, {n, 57}]]] (* IWABUCHI Yu(u)ki, Aug 01 2012 *)
FromDigits[#, 3]&/@Tuples[{0, 1}, 7] (* Harvey P. Dale, May 10 2019 *)

Prog

(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
(PARI) is(n)=while(n, if(n%3>1, return(0)); n\=3); 1 \\ Charles R Greathouse IV, Mar 07 2013
(PARI) a(n) = fromdigits(binary(n-1), 3);  \\ Gheorghe Coserea, Jun 15 2018
(Haskell)
a005836 n = a005836_list !! (n-1)
a005836_list = filter ((== 1) . a039966) [0..]
-- Reinhard Zumkeller, Jun 09 2012, Sep 29 2011
(Python)
def A005836(n):
    return int(format(n-1, 'b'), 3) # Chai Wah Wu, Jan 04 2015
(Julia)
function a(n)
    m, r, b = n, 0, 1
    while m > 0
        m, q = divrem(m, 2)
        r += b * q
        b *= 3
    end
r end; [a(n) for n in 0:57] |> println # Peter Luschny, Jan 03 2021

Crossrefs

Cf. A039966 (characteristic function).

Cf. A002426, A004793, A005823, A007088, A007089, A032924, A033042-A033052, A054591, A055246, A062548, A065361, A074940, A081601, A081603, A081611, A083096, A089118, A121153, A170943, A185256.

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.

Row 3 of array A104257.

Summary of increasing sequences avoiding arithmetic progressions of specified lengths (the second of each pair is obtained by adding 1 to the first):

3-term AP: A005836 (>=0), A003278 (>0);

4-term AP: A005839 (>=0), A005837 (>0);

5-term AP: A020654 (>=0), A020655 (>0);

6-term AP: A020656 (>=0), A005838 (>0);

7-term AP: A020657 (>=0), A020658 (>0);

8-term AP: A020659 (>=0), A020660 (>0);

9-term AP: A020661 (>=0), A020662 (>0);

10-term AP: A020663 (>=0), A020664 (>0).

See also A000452.

Sequence in context: A276672 A010400 A010439 * A054591 A121153 A276986

Adjacent sequences: A005833 A005834 A005835 * A005837 A005838 A005839

Keyword

nonn,nice,easy,base,tabf

Author

N. J. A. Sloane, Jeffrey Shallit

Extensions

Offset corrected by N. J. A. Sloane, Mar 02 2008

Edited by the Associate Editors of the OEIS, Apr 07 2009

Status

approved