A003278 Szekeres's sequence: a(n)-1 in ternary = n-1 in binary; also: a(1) = 1, a(2) = 2, and thereafter a(n) is smallest number k which avoids any 3-term arithmetic progression in a(1), a(2), ..., a(n-1), k. (Formerly M0975)

1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41, 82, 83, 85, 86, 91, 92, 94, 95, 109, 110, 112, 113, 118, 119, 121, 122, 244, 245, 247, 248, 253, 254, 256, 257, 271, 272, 274, 275, 280, 281, 283, 284, 325, 326, 328, 329, 334, 335, 337, 338, 352, 353

Offset

1,2

Comments

That is, there are no three elements A, B and C such that B - A = C - B.

Positions of 1's in Richard Stanley's Forest Fire sequence A309890. - N. J. A. Sloane, Dec 01 2019

Subtracting 1 from each term gives A005836 (ternary representation contains no 2's). - N. J. A. Sloane, Dec 01 2019

Difference sequence related to Gray code bit sequence (A001511). The difference patterns follows a similar repeating pattern (ABACABADABACABAE...), but each new value is the sum of the previous values, rather than simply 1 more than the maximum of the previous values. - Hal Burch (hburch(AT)cs.cmu.edu), Jan 12 2004

Sums of distinct powers of 3, translated by 1.

Positions of 0 in A189820; complement of A189822. - Clark Kimberling, May 26 2011

Also, Stanley sequence S(1): see OEIS Index under Stanley sequences (link below). - M. F. Hasler, Jan 18 2016

Named after the Hungarian-Australian mathematician George Szekeres (1911-2005). - Amiram Eldar, May 07 2021

If A_n=(a(1),a(2),...,a(2^n)), then A_(n+1)=(A_n,A_n+3^n). - Arie Bos, Jul 24 2022

References

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 164.

Richard K. Guy, Unsolved Problems in Number Theory, E10.

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 [a(1..1024) from T. D. Noe]

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

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

Paul Erdős and Paul Turan, On some sequences of integers, J. London Math. Soc., 11 (1936), 261-264.

Joseph Gerver, James Propp and Jamie Simpson, Greedily partitioning the natural numbers into sets free of arithmetic progressions Proc. Amer. Math. Soc. 102 (1988), no. 3, 765-772.

Fanel Iacobescu, Smarandache Partition Type and Other Sequences, Bull. Pure Appl. Sci. 16E, 237-240, 1997.

Henry Ibstedt, A Few Smarandache Sequences, Smarandache Notions Journal, Vol. 8, No. 1-2-3, 1997, 170-183.

Gabor Korvin, Short note: Every large set of integers contains a three term arithmetic progression arXiv 1404.1557 [math.NT], Apr 6 2014.

Leo Moser, An Introduction to the Theory of Numbers, The Trillia Group, 2011 (written in 1957). See pp. 61-62.

James Propp and N. J. A. Sloane, Email, March 1994

Florentin Smarandache, Sequences of Numbers Involved in Unsolved Problems.

R. P. Stanley, Letter to N. J. A. Sloane, c. 1991

Eric Weisstein's World of Mathematics, Smarandache Sequences.

Index entries for sequences related to binary expansion of n

Index entries related to non-averaging sequences

Index entries related to Stanley sequences

Formula

a(2*k + 2) = a(2*k + 1) + 1, a(2^k + 1) = 2*a(2^k).

a(n) = b(n+1) with b(0) = 1, b(2*n) = 3*b(n)-2, b(2*n+1) = 3*b(n)-1. - Ralf Stephan, Aug 23 2003

G.f.: x/(1-x)^2 + x * Sum_{k>=1} 3^(k-1)*x^(2^k)/((1-x^(2^k))*(1-x)). - Ralf Stephan, Sep 10 2003, corrected by Robert Israel, May 25 2011

Conjecture: a(n) = (A191107(n) + 2)/3 = (A055246(n) + 5)/6. - L. Edson Jeffery, Nov 26 2015

a(n) mod 2 = A010059(n). - Arie Bos, Aug 13 2022

Example

G.f. = x + 2*x^2 + 4*x^3 + 5*x^4 + 10*x^5 + 11*x^6 + 13*x^7 + 14*x^8 + 28*x^9 + ...

Maple

a:= proc(n) local m, r, b; m, r, b:= n-1, 1, 1;
      while m>0 do r:= r+b*irem(m, 2, 'm'); b:= b*3 od; r
    end:
seq(a(n), n=1..100); # Alois P. Heinz, Aug 17 2013

Mathematica

Take[ Sort[ Plus @@@ Subsets[ Table[3^n, {n, 0, 6}]]] + 1, 58] (* Robert G. Wilson v, Oct 23 2004 *)
a[1] = 0; h = 180;
Table[a[3 k - 2] = a[k], {k, 1, h}];
Table[a[3 k - 1] = a[k], {k, 1, h}];
Table[a[3 k] = 1, {k, 1, h}];
Table[a[n], {n, 1, h}]   (* A189820 *)
Flatten[Position[%, 0]]  (* A003278 *)
Flatten[Position[%%, 1]] (* A189822 *)
(* A003278 from A189820, from Clark Kimberling, May 26 2011 *)
Table[FromDigits[IntegerDigits[n, 2], 3] + 1, {n, 0, 57}] (* Amit Munje, Jun 03 2018 *)

Prog

(Perl) $nxt = 1; @list = (); for ($cnt = 0; $cnt < 1500; $cnt++) { while (exists $legal{$nxt}) { $nxt++; } print "$nxt "; last if ($nxt >= 1000000); for ($i = 0; $i <= $#list; $i++) { $t = 2*$nxt - $list[$i]; $legal{$t} = -1; } $cnt++; push @list, $nxt; $nxt++; } # Hal Burch
(PARI) a(n)=1+sum(i=1, n-1, (1+3^valuation(i, 2))/2) \\ Ralf Stephan, Jan 21 2014
(Python)
def A003278(n):
    return int(format(n-1, 'b'), 3)+1 # Chai Wah Wu, Jan 04 2015
(Julia)
function a(n)
    return 1 + parse(Int, bitstring(n-1), base=3)
end # Gabriel F. Lipnik, Apr 16 2021

Crossrefs

Equals 1 + A005836. Cf. A001511, A098871.

Row 0 of array in A093682.

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).

Cf. A003002, A229037 (the Forest Fire sequence), A309890 (Stanley's version).

Similar formula:

If A_n=(a(1),a(2),...,a(2^n)), then A_(n+1)=(A_n,A_n+4^n) produces A098871;

If A_n=(a(1),a(2),...,a(2^n)), then A_(n+1)=(A_n,A_n+2*3^n) produces A191106.

Sequence in context: A220696 A275482 A156799 * A236246 A004792 A167795

Adjacent sequences: A003275 A003276 A003277 * A003279 A003280 A003281

Keyword

nonn,nice,easy

Author

N. J. A. Sloane and Richard Stanley

Status

approved