cp's OEIS Frontend

A065825 Smallest k such that n numbers may be picked in {1,...,k} with no three terms in arithmetic progression.

%I A065825 #93 Feb 17 2025 12:20:18
%S A065825 1,2,4,5,9,11,13,14,20,24,26,30,32,36,40,41,51,54,58,63,71,74,82,84,
%T A065825 92,95,100,104,111,114,121,122,137,145,150,157,163,165,169,174,194,
%U A065825 204,209
%N A065825 Smallest k such that n numbers may be picked in {1,...,k} with no three terms in arithmetic progression.
%C A065825 "Sequences containing no 3-term arithmetic progressions" is another phrase people may be searching for. See also A003002.
%C A065825 _Don Reble_ notes large gaps between a(4k) and a(4k+1).
%C A065825 _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.
%C A065825 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.
%C A065825 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
%D A065825 Donald E. Knuth, Satisfiability, Fascicle 6, volume 4 of The Art of Computer Programming. Addison-Wesley, 2015, pages 135 and 190, Problem 31.
%D A065825 C. R. J. Singleton, "No Progress": Solution to Problem 2472, Journal of Recreational Mathematics, 30(4) 305 1999-2000.
%H A065825 Tanbir Ahmed, Janusz Dybizbanski and Hunter Snevily, <a href="https://doi.org/10.37236/3007">Unique Sequences Containing No k-Term Arithmetic Progressions</a>, Electronic Journal of Combinatorics, 20(4), 2013, #P29.
%H A065825 Cyriac Antony, Jacob Antony, D. Laavanya, and S. Devi Yamini, <a href="https://doi.org/10.1007/978-3-031-83438-7_2">Graceful Coloring is Computationally Hard</a>, Algorithms and Discrete Applied Mathematics, Eds. Daya Gaur, Rogers Mathew, Proc. 11th Int'l Conf. (CALDAM 2025)  Lect. Notes Comp. Sci. (LNCS) Vol. 15536, Springer, 13-24. See also <a href="https://arxiv.org/abs/2407.02179">arXiv:2407.02179</a>, [math.CO], 2024. See pp. 1-2.
%H A065825 F. Behrend, <a href="https://doi.org/10.1073/pnas.32.12.331">On sets of integers which contain no three terms in an arithmetic progression</a>, Proc. Nat. Acad. Sci. USA, v. 32, 1946, pp. 331-332.
%H A065825 Thomas F. Bloom and Olof Sisask, <a href="https://arxiv.org/abs/2007.03528">Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions</a>, arXiv:2007.03528 [math.NT], 2020.
%H A065825 Janusz Dybizbanski, <a href="https://doi.org/10.37236/2061">Sequences containing no 3-term arithmetic progressions</a>, The Electronic Journal of Combinatorics, 19, no. 2 (2012), #P15.
%H A065825 Erica Klarreich, <a href="https://www.quantamagazine.org/landmark-math-proof-clears-hurdle-in-top-erdos-conjecture-20200803/">Landmark Math Proof Clears Hurdle in Top Erdős Conjecture</a>, Quanta Magazine, Aug 03 2020.
%H A065825 Tom Sanders, <a href="http://dx.doi.org/10.4007/annals.2011.174.1.20">On Roth's theorem on progressions</a>, Annals of Mathematics 174:1 (2011), pp. 619-636; <a href="http://arxiv.org/abs/1011.0104">arXiv version</a>, arXiv:1011.0104 [math.CA], 2010-2011.
%H A065825 Samuel S. Wagstaff, Jr., <a href="http://dx.doi.org/10.1090/S0025-5718-1972-0325500-5">On k-free sequences of integers</a>, Math. Comp., 26 (1972), 767-771.
%H A065825 Wikipedia, <a href="https://en.wikipedia.org/wiki/Salem-Spencer_set">Salem-Spencer set</a>
%H A065825 J. Wroblewski, <a href="http://dx.doi.org/10.1090/S0025-5718-1984-0744935-8">A Nonaveraging Set of Integers with a Large Sum of Reciprocals</a>, Math. Comput. 43, 261-262, 1984.
%H A065825 J. Wroblewski, <a href="http://www.math.uni.wroc.pl/~jwr/non-ave.htm">Nonaveraging Sets</a>
%H A065825 <a href="/index/No#non_averaging">Index entries related to non-averaging sequences</a>
%F A065825 a(n) = A005047(n) + 1. - _Rob Pratt_, Jul 09 2015
%e A065825 a(9) = 20 = 1 2 6 7 9 14 15 18 20
%e A065825 a(10) = 24 = 1 2 5 7 11 16 18 19 23 24
%e A065825 a(11) = 26 = 1 2 5 7 11 16 18 19 23 24 26
%e A065825 a(12) = 30 = 1 3 4 8 9 11 20 22 23 27 28 30 (unique)
%e A065825 a(13) = 32 = 1 2 4 8 9 11 19 22 23 26 28 31 32
%e A065825 a(14) = 36 = 1 2 4 8 9 13 21 23 26 27 30 32 35 36
%e A065825 a(15) = 40 = 1 2 4 5 10 11 13 14 28 29 31 32 37 38 40
%e A065825 a(16) = 41 = 1 2 4 5 10 11 13 14 28 29 31 32 37 38 40 41
%e A065825 a(17) = 51 = 1 2 4 5 10 13 14 17 31 35 37 38 40 46 47 50 51
%e A065825 a(18) = 54 = 1 2 5 6 12 14 15 17 21 31 38 39 42 43 49 51 52 54
%e A065825 a(19) = 58 = 1 2 5 6 12 14 15 17 21 31 38 39 42 43 49 51 52 54 58
%e A065825 a(20) = 63 = 1 2 5 7 11 16 18 19 24 26 38 39 42 44 48 53 55 56 61 63
%e A065825 a(21) = 71 = 1 2 5 7 10 17 20 22 26 31 41 46 48 49 53 54 63 64 68 69 71
%e A065825 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
%e A065825 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
%e A065825 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
%e A065825 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
%e A065825 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
%e A065825 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
%t A065825 ThreeAPFree[n_, k_, a_] := Module[{d, j},
%t A065825    For[d = 1, d < k/2, d ++,
%t A065825     For[j = 1, j <= n - 2, j++,
%t A065825      If[MemberQ[a, a[[j]] + d] && MemberQ[a, a[[j]] + 2 d],
%t A065825       Return[False]]]];
%t A065825    Return[True]];
%t A065825 A065825[n_] := Module[{k, x, a},
%t A065825   k = n;
%t A065825   While[True,
%t A065825    x = Subsets[Range[k], {n}];
%t A065825    For[i = 1, i <= Length[x], i++,
%t A065825     a = x[[i]];
%t A065825     If[a[[1]] != 1 || a[[n]] != k, Continue[]];
%t A065825     If[ThreeAPFree[n, k, a], Return[k]]];
%t A065825    k++]]
%t A065825 Table[A065825[n], {n, 1, 10}]  (* _Robert Price_, Mar 11 2019 *)
%o A065825 (PARI) \\ brute force
%o A065825 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
%o A065825 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
%Y A065825 Cf. A003002 (three-free sequences), A003003, A003004, A003005, A003278, A005047, A225745.
%K A065825 nonn,hard,nice,more
%O A065825 1,2
%A A065825 _Ed Pegg Jr_, Nov 23 2001
%E A065825 a(19) found by Guenter Stertenbrink in response to an A003278-based puzzle on www.mathpuzzle.com
%E A065825 More terms from _Don Reble_, Nov 25 2001
%E A065825 a(28)-a(32) from _William Rex Marshall_, Mar 24 2002
%E A065825 a(33) from _William Rex Marshall_, Nov 15 2003
%E A065825 a(34) from _William Rex Marshall_, Jan 24 2004
%E A065825 a(35)-a(36) (found by Gavin Theobold in 2004) communicated by _William Rex Marshall_, Mar 10 2007
%E A065825 a(37)-a(41) (from Wroblewski's web page) added by _Joerg Arndt_, Apr 25 2012
%E A065825 a(42)-a(43) from _Fausto A. C. Cariboni_, Sep 02 2018