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.

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

Author

N. J. A. Sloane and Richard Stanley

Keywords

• nonn
• nice
• easy

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

Examples

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

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

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.

Programs

Julia

function a(n)
    return 1 + parse(Int, bitstring(n-1), base=3)
end # Gabriel F. Lipnik, Apr 16 2021

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

PARI

a(n)=1+sum(i=1,n-1,(1+3^valuation(i,2))/2) \\ Ralf Stephan, Jan 21 2014

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

Python

def A003278(n):
    return int(format(n-1,'b'),3)+1 # Chai Wah Wu, Jan 04 2015

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