cp's OEIS Frontend

A229037 The "forest fire": sequence of positive integers where each is chosen to be as small as possible subject to the condition that no three terms a(j), a(j+k), a(j+2k) (for any j and k) form an arithmetic progression.

%I A229037 #124 Oct 16 2024 14:53:07
%S A229037 1,1,2,1,1,2,2,4,4,1,1,2,1,1,2,2,4,4,2,4,4,5,5,8,5,5,9,1,1,2,1,1,2,2,
%T A229037 4,4,1,1,2,1,1,2,2,4,4,2,4,4,5,5,8,5,5,9,9,4,4,5,5,10,5,5,10,2,10,13,
%U A229037 11,10,8,11,13,10,12,10,10,12,10,11,14,20,13
%N A229037 The "forest fire": sequence of positive integers where each is chosen to be as small as possible subject to the condition that no three terms a(j), a(j+k), a(j+2k) (for any j and k) form an arithmetic progression.
%C A229037 Added name "forest fire" to make it easier to locate this sequence. - _N. J. A. Sloane_, Sep 03 2019
%C A229037 This sequence and A235383 and A235265 were winners in the best new sequence contest held at the OEIS Foundation booth at the 2014 AMS/MAA Joint Mathematics Meetings. - _T. D. Noe_, Jan 20 2014
%C A229037 See A236246 for indices n such that a(n)=1. - _M. F. Hasler_, Jan 20 2014
%C A229037 See A241673 for indices n such that a(n)=2^k. - _Reinhard Zumkeller_, Apr 26 2014
%C A229037 The graph (for up to n = 10000) has an eerie similarity (why?) to the distribution of rising smoke particles subjected to a lateral wind, and where the particles emanate from randomly distributed burning areas in a fire in a forest or field. - _Daniel Forgues_, Jan 21 2014
%C A229037 The graph (up to n = 100000) appears to have a fractal structure. The dense areas are not random but seem to repeat, approximately doubling in width and height each time. - _Daniel Forgues_, Jan 21 2014
%C A229037 a(A241752(n)) = n and a(m) != n for m < A241752(n). - _Reinhard Zumkeller_, Apr 28 2014
%C A229037 The indices n such that a(n) = 1 are given by A236313 (relative spacing) up to 19 terms, and A003278 (directly) up to 20 terms. If just placing ones, the 21st 1 would be n=91. The sequence A003278 fails at n=91 because the numbers filling the gaps create an arithmetic progression with a(27)=9, a(59)=5 and a(91)=1. Additionally, if you look at indices n starting at the first instance of 4 or 5, A003278/A236313 provide possible indices for a(n)=4 or a(n)=5, with some indexes instead filled by numbers < (4,5). A003278/A236313 also fail to predict indices for a(n)=4 or a(n)=5 by the ~20th term. - _Daniel Putt_, Sep 29 2022
%H A229037 Giovanni Resta, Alois P. Heinz, and Charles R Greathouse IV, <a href="/A229037/b229037.txt">Table of n, a(n) for n = 1..100000</a> (1..1000 from Resta, 1001..10000 from Heinz, and 10001..100000 from Greathouse)
%H A229037 Jean Bickerton, <a href="/A229037/a229037_4.png">Colored plot of 200000 terms; color is difference from previous term in sequence</a>
%H A229037 Xan Gregg, <a href="/A229037/a229037_1.png">Enhanced scatterplot of 10000 terms</a> [In this plot, the points have been made translucent to reduce the information lost to overstriking, and the point size varies with n in an attempt to keep the density comparable.]
%H A229037 OEIS, <a href="/A229037/a229037.png">Pin plot of 200 terms and scatterplot of 10000 terms</a>
%H A229037 Sébastien Palcoux, <a href="https://mathoverflow.net/q/338415/34538">On the first sequence without triple in arithmetic progression</a> (version: 2019-08-21), MathOverflow
%H A229037 Sébastien Palcoux, <a href="/A229037/a229037.txt">Table of n, a(n) for n = 1..1000000</a>
%H A229037 Sébastien Palcoux, <a href="/A229037/a229037_3.png">Density plot of the first 1000000 terms</a>
%H A229037 Reddit User "garnet420", <a href="/A229037/a229037.jpg">Colored plot of 16 million terms; horizontal divisions are 1000000; vertical divisions are 25000</a>
%H A229037 Reddit User "garnet420", <a href="/A229037/a229037_5.png">B/W plot of 16 million terms; horizontal divisions are 1000000; vertical divisions are 25000</a>
%H A229037 N. J. A. Sloane, New Gilbreath Conjectures, Sum and Erase, Dissecting Polygons, and Other New Sequences, Doron Zeilberger's Exper. Math. Seminar, Rutgers, Sep 14 2023: <a href="https://vimeo.com/866583736?share=copy">Video</a>, <a href="http://neilsloane.com/doc/EMSep2023.pdf">Slides</a>, <a href="http://neilsloane.com/doc/EMSep2023.Updates.txt">Updates</a>. (Mentions this sequence.)
%H A229037 N. J. A. Sloane and Brady Haran, <a href="https://www.youtube.com/watch?v=o8c4uYnnNnc">Amazing Graphs II (including Star Wars)</a>, Numberphile video (2019)
%H A229037 <a href="http://oeis.org/wiki/Index_to_OEIS:_Section_Gra#graphs_plots">Index entries for sequences with interesting graphs or plots</a>
%H A229037 <a href="http://oeis.org/wiki/Index_to_OEIS:_Section_No#non_averaging">Index entries for non-averaging sequences</a>
%F A229037 a(n) <= (n+1)/2. - _Charles R Greathouse IV_, Jan 21 2014
%t A229037 a[1] = 1; a[n_] := a[n] = Block[{z = 1}, While[Catch[ Do[If[z == 2*a[n-k] - a[n-2*k], Throw@True], {k, Floor[(n-1)/2]}]; False], z++]; z]; a /@ Range[100] (* _Giovanni Resta_, Jan 01 2014 *)
%o A229037 (PARI) step(v)=my(bad=List(),n=#v+1,t); for(d=1,#v\2,t=2*v[n-d]-v[n-2*d]; if(t>0, listput(bad,t))); bad=Set(bad); for(i=1,#bad, if(bad[i]!=i, return(i))); #bad+1
%o A229037 first(n)=my(v=List([1])); while(n--, listput(v, step(v))); Vec(v) \\ _Charles R Greathouse IV_, Jan 21 2014
%o A229037 (Haskell)
%o A229037 import Data.IntMap (empty, (!), insert)
%o A229037 a229037 n = a229037_list !! (n-1)
%o A229037 a229037_list = f 0 empty  where
%o A229037    f i m = y : f (i + 1) (insert (i + 1) y m) where
%o A229037      y = head [z | z <- [1..],
%o A229037                    all (\k -> z + m ! (i - k) /= 2 * m ! (i - k `div` 2))
%o A229037                        [1, 3 .. i - 1]]
%o A229037 -- _Reinhard Zumkeller_, Apr 26 2014
%o A229037 (Python)
%o A229037 A229037_list = []
%o A229037 for n in range(10**6):
%o A229037     i, j, b = 1, 1, set()
%o A229037     while n-2*i >= 0:
%o A229037         b.add(2*A229037_list[n-i]-A229037_list[n-2*i])
%o A229037         i += 1
%o A229037         while j in b:
%o A229037             b.remove(j)
%o A229037             j += 1
%o A229037     A229037_list.append(j) # _Chai Wah Wu_, Dec 21 2014
%Y A229037 Cf. A094870, A362942 (partial sums).
%Y A229037 For a variant see A309890.
%Y A229037 A selection of sequences related to "no three-term arithmetic progression": A003002, A003003, A003278, A004793, A005047, A005487, A033157, A065825, A092482, A093678, A093679, A093680, A093681, A093682, A094870, A101884, A101886, A101888, A140577, A185256, A208746, A229037.
%K A229037 nonn,easy,nice,look
%O A229037 1,3
%A A229037 _Jack W Grahl_, Sep 11 2013