The OEIS is supported by the many generous donors to the OEIS Foundation.

A065825
Smallest k such that n numbers may be picked in {1,...,k} with no three terms in arithmetic progression.
17
1, 2, 4, 5, 9, 11, 13, 14, 20, 24, 26, 30, 32, 36, 40, 41, 51, 54, 58, 63, 71, 74, 82, 84, 92, 95, 100, 104, 111, 114, 121, 122, 137, 145, 150, 157, 163, 165, 169, 174, 194, 204, 209
OFFSET
1,2
"Sequences containing no 3-term arithmetic progressions" is another phrase people may be searching for. See also A003002.
Don Reble notes large gaps between a(4k) and a(4k+1).
Ed Pegg Jr conjectures the 2^k term always equals (3^k+1)/2 and calls these "unprogressive" sets. Jaroslaw Wroblewski (jwr(AT)math.uni.wroc.pl), Nov 04 2003, remarks that this conjecture is known to be false.
Further comments from Jaroslaw Wroblewski (jwr(AT)math.uni.wroc.pl), Nov 05 2003: log a(n) / log n tends to 1 was established in 1946 by Behrend. This was extended by me in the Math. Comp. paper. Using appropriately chosen intervals from B(4,9,4) and B(6,9,11) I have determined that log (2a(n)-1) / log n < log 3 / log 2 holds for n=60974 and for n=2^19 since a(60974) <= 19197041, a(524288) <= 515749566. See my web page for further bounds.
Bloom & Sisask prove that a(n) >> n (log n)^(1+c) for an absolute (small) constant c > 0. This improves the o(1) in Behrend's result that log a(n)/log n = 1 + o(1) to log log n/log n. - Charles R Greathouse IV, Aug 04 2020
REFERENCES
Donald E. Knuth, Satisfiability, Fascicle 6, volume 4 of The Art of Computer Programming. Addison-Wesley, 2015, pages 135 and 190, Problem 31.
C. R. J. Singleton, "No Progress": Solution to Problem 2472, Journal of Recreational Mathematics, 30(4) 305 1999-2000.
Tanbir Ahmed, Janusz Dybizbanski and Hunter Snevily, Unique Sequences Containing No k-Term Arithmetic Progressions, Electronic Journal of Combinatorics, 20(4), 2013, #P29.
Cyriac Antony, Laavanya D., and Devi Yamini S, Graceful coloring is computationally hard, arXiv:2407.02179 [math.CO], 2024. See pp. 1, 2.
F. Behrend, On sets of integers which contain no three terms in an arithmetic progression, Proc. Nat. Acad. Sci. USA, v. 32, 1946, pp. 331-332.
Thomas F. Bloom and Olof Sisask, Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions, arXiv:2007.03528 [math.NT], 2020.
Janusz Dybizbanski, Sequences containing no 3-term arithmetic progressions, The Electronic Journal of Combinatorics, 19, no. 2 (2012), #P15.
Erica Klarreich, Landmark Math Proof Clears Hurdle in Top ErdÅ‘s Conjecture, Quanta Magazine, Aug 03 2020.
Tom Sanders, On Roth's theorem on progressions, Annals of Mathematics 174:1 (2011), pp. 619-636; arXiv version, arXiv:1011.0104 [math.CA], 2010-2011.
Samuel S. Wagstaff, Jr., On k-free sequences of integers, Math. Comp., 26 (1972), 767-771.
J. Wroblewski, A Nonaveraging Set of Integers with a Large Sum of Reciprocals, Math. Comput. 43, 261-262, 1984.
J. Wroblewski, Nonaveraging Sets
FORMULA
a(n) = A005047(n) + 1. - Rob Pratt, Jul 09 2015
EXAMPLE
a(9) = 20 = 1 2 6 7 9 14 15 18 20
a(10) = 24 = 1 2 5 7 11 16 18 19 23 24
a(11) = 26 = 1 2 5 7 11 16 18 19 23 24 26
a(12) = 30 = 1 3 4 8 9 11 20 22 23 27 28 30 (unique)
a(13) = 32 = 1 2 4 8 9 11 19 22 23 26 28 31 32
a(14) = 36 = 1 2 4 8 9 13 21 23 26 27 30 32 35 36
a(15) = 40 = 1 2 4 5 10 11 13 14 28 29 31 32 37 38 40
a(16) = 41 = 1 2 4 5 10 11 13 14 28 29 31 32 37 38 40 41
a(17) = 51 = 1 2 4 5 10 13 14 17 31 35 37 38 40 46 47 50 51
a(18) = 54 = 1 2 5 6 12 14 15 17 21 31 38 39 42 43 49 51 52 54
a(19) = 58 = 1 2 5 6 12 14 15 17 21 31 38 39 42 43 49 51 52 54 58
a(20) = 63 = 1 2 5 7 11 16 18 19 24 26 38 39 42 44 48 53 55 56 61 63
a(21) = 71 = 1 2 5 7 10 17 20 22 26 31 41 46 48 49 53 54 63 64 68 69 71
a(22) = 74 = 1 2 7 9 10 14 20 22 23 25 29 46 50 52 53 55 61 65 66 68 73 74
a(23) = 82 = 1 2 4 8 9 11 19 22 23 26 28 31 49 57 59 62 63 66 68 71 78 81 82
a(24) = 84 = 1 3 4 8 9 16 18 21 22 25 30 37 48 55 60 63 64 67 69 76 77 81 82 84
a(25) = 92 = 1 2 6 8 9 13 19 21 22 27 28 39 58 62 64 67 68 71 73 81 83 86 87 90 92
a(26) = 95 = 1 2 4 5 10 11 22 23 25 26 31 32 55 56 64 65 67 68 76 77 82 83 91 92 94 95
a(27) = 100 = 1 3 6 7 10 12 20 22 25 26 29 31 35 62 66 68 71 72 75 77 85 87 90 91 94 96 100
MATHEMATICA
ThreeAPFree[n_, k_, a_] := Module[{d, j},
For[d = 1, d < k/2, d ++,
For[j = 1, j <= n - 2, j++,
If[MemberQ[a, a[[j]] + d] && MemberQ[a, a[[j]] + 2 d],
Return[False]]]];
Return[True]];
A065825[n_] := Module[{k, x, a},
k = n;
While[True,
x = Subsets[Range[k], {n}];
For[i = 1, i <= Length[x], i++,
a = x[[i]];
If[a[[1]] != 1 || a[[n]] != k, Continue[]];
If[ThreeAPFree[n, k, a], Return[k]]];
k++]]
Table[A065825[n], {n, 1, 10}] (* Robert Price, Mar 11 2019 *)
PROG
(PARI) \\ brute force
has3AP(v)=for(i=1, #v-2, for(j=i+2, #v, my(t=(v[i]+v[j])/2); if(denominator(t)==1 && setsearch(v, t), return([v[i], t, v[j]])))); 0
a(n)=for(k=n, oo, forvec(u=vector(n, i, if(i==1, [1, 1], i==k, [k, k], [2, k-1])), if(has3AP(u)==0, /* print(u); */ return(u[n])), 2)) \\ Charles R Greathouse IV, Aug 04 2020
CROSSREFS
Cf. A003002 (three-free sequences), A003003, A003004, A003005, A003278, A005047, A225745.
Sequence in context: A364732 A047378 A101155 * A113755 A124254 A192615
KEYWORD
nonn,hard,nice,more
AUTHOR
Ed Pegg Jr, Nov 23 2001
EXTENSIONS
a(19) found by Guenter Stertenbrink in response to an A003278-based puzzle on www.mathpuzzle.com
More terms from Don Reble, Nov 25 2001
a(28)-a(32) from William Rex Marshall, Mar 24 2002
a(33) from William Rex Marshall, Nov 15 2003
a(34) from William Rex Marshall, Jan 24 2004
a(35)-a(36) (found by Gavin Theobold in 2004) communicated by William Rex Marshall, Mar 10 2007
a(37)-a(41) (from Wroblewski's web page) added by Joerg Arndt, Apr 25 2012
a(42)-a(43) from Fausto A. C. Cariboni, Sep 02 2018
STATUS
approved

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

Last modified September 20 23:55 EDT 2024. Contains 376078 sequences. (Running on oeis4.)