f' [x,y,z,w] = [abs (x-y), abs (y-z), abs (z-w), abs (w-x)]\n\ng' xs = takeWhile (\/=[0,0,0,0]) (iterate f' xs)\n\nh' xs = length (g' xs) + 1\n\ni' n = maximum [(h' [a,b,c,d], [a,b,c,d]) | a <- [1], b <- [a..n], c <- [a..n], d <- [b..n]] <\/code><\/pre>\n\n\n\n(Not pictured: good choice of variable names.)<\/p>\n\n\n\n So an exhaust is down to using symmetry.<\/p>\n\n\n\n My next thought in these situations is that we’re doing an awful lot of recomputation. If I’ve already scored , why should I reevaluate it when scoring ? Why not store the score somewhere so we can look it up later?<\/p>\n\n\n\n
f n = maximum (elems table) where\n  table = array ((0,0,0),(n-1,n-1,n-1)) [((a,b,c), g a b c) | a <- [0..n-1], b <- [0..n-1], c <- [0..n-1]]\n  g 0 0 0 = 1 -- represents c c c c for c > 0 the first time you reach it\n  g a b c | a > c = g c b a\n          | otherwise = (table ! normalise a (abs (b-a)) (abs (c-b)) c) + 1\n\nnormalise a b c d = let m = minimum [a,b,c,d]\n                    in  normalise2 (a-m) (b-m) (c-m) (d-m)\n\nnormalise2 0 b c d = (b,c,d)\nnormalise2 a 0 c d = (c,d,a)\nnormalise2 a b 0 d = (d,a,b)\nnormalise2 a b c 0 = (a,b,c)<\/code><\/pre>\n\n\n\nThis is what I ended up with.  It isn’t pretty.  The thing that wasn’t, but should have been, immediately obvious is that the states I encounter along the way won’t be in the nicely normalised form we’ve just decided we want to work with, so the naive lookup table increases our time back up to .  On the other hand, normalising things like this is expensive compared to the computation we’re trying to save.  It’s a very bad deal, and even if it weren’t I can’t afford  memory for very large values of .<\/p>\n\n\n\n
So we’re back to computing  honestly for each  in time .  The next observation is that if we want  for lots of  we can do better: if  is to be larger than  then the pattern witnessing that had better use both  and , taking us to  for each new .  In fact, we can say a bit more.  The  and  would either have to be adjacent or opposite.<\/p>\n\n\n\n    1 -- b        1 -- n\n    |    |        |    |\n    d -- n        d -- c<\/pre>\n\n\n\nThen we still have some symmetries to play with with.   In the opposite case, all of the edges are related by symmetries so we can assume that  is the smallest difference.  In the adjacent case there is less symmetry, but we can still assume that .<\/p>\n\n\n\ndirect n = maximum ( [score 1 b n d | b <- [1..n`quot`2], d <- [b..n+1-b]]\n                  ++ [score 1 n c d | c <- [1..n], d <- [1..n+1-c]] )\n\nscore 0 0 0 0 = 0\nscore a b c d = 1 + (score (abs (a-b)) (abs  (b-c)) (abs (c-d)) (abs (d-a)))<\/code><\/pre>\n\n\n\nThat’s not bad and will get you well up into the thousands without difficulty.<\/p>\n\n\n\n
(Everything above is a mostly accurate representation of my progress through this problem, with light editing to fix errors and wholesale removal of dollar signs from my Haskell, since they confuse the LaTeX plugin.  What follows is ahistorical, presenting an endpoint without all the dead ends along the way.)<\/p>\n\n\n\n
So far we haven’t thought about the actual operation we’re iterating, so let’s do that now.  Suppose that we’re in the opposite case with  and  strictly between  and .  Then replacing  by  and  by  produces a pattern that goes to the same place as the original pattern under two rounds of iteration, so such patterns aren’t interesting in our search; they were considered in previous rounds.  Similarly, in the adjacent case where  we can decrease  and  to obtain an equivalent-after-two-iterations pattern with a smaller value of , so we don’t need to consider it.  Finally, if we’re in the opposite case but , say, then we could alternatively have viewed ourself as being in the adjacent case.  So we can reduce our search to<\/p>\n\n\n\ndirect n = maximum [score 1 a b n | a <- [1..n], b <- [a..n]]<\/code><\/pre>\n\n\n\nfor  or, after further assuming that ,<\/p>\n\n\n\ndirect n = maximum [score 1 a b n | a <- [1..(n+1)]`quot`2], b <- [a..n-a+1]]<\/code><\/pre>\n\n\n\nfor .  (Once these computations are taking hours or days the constant factor improvements shouldn’t be undervalued.)<\/p>\n\n\n\n
We’ve already seen that storing lots of information about previously computed results is not helpful, but we can store the known values of  and its “inverse” , the least  such that .  Then when testing whether  scores at least  it might be worth checking whether , which is the absolute minimum requirement to last at least  rounds.  But our scoring function is so cheap that you don’t have to do very much at all of this sort of thing before it becomes too expensive, and in practice the optimal amount of checking seems to be zero.<\/p>\n\n\n\n
Unless we can somehow do the checking without actually doing the checking?  If we’re currently trying to check whether  then we’d better have the smallest and largest differences differing by at least .  That  is the point at which I throw my hands up and switch to the interval  rather than , which means you have to keep an eye out for off by one errors when comparing earlier results with what comes next.  We already have 
   <\/span>   <\/span><\/p>  The largest difference at the beginning is , so we additionally require that either  or .  Rearranging, either  or .  This takes us to<\/p>\n\n\n\nnewRecord n = maximum [score 0 a b n | b <- [..n], a <- h b]\n  where\n    gk = firstTimeWeCanGet ! (recordUpTo ! (n-1)) -- see full listing\n    h b = let top = min b (n-b) in\n          if   n-gk < b-n+gk && n-gk < top\n          then [0..n-gk] ++ [b-n+gk..top]\n          else [0..top]\n<\/code><\/pre>\n\n\n\nwith a cheap improvement from doing the first round of the iteration by hand.<\/p>\n\n\n\nnewRecord n = maximum [score a (b-a) (n-b) n | b <- [0..n], a <- f b] + 1<\/code><\/pre>\n\n\n\nThere’s at least one more idea worth considering.  We haven’t used the fourth symmetry, of multiplying by non-zero constants.  The practical use would be to divide out any common factors of , but doing the gcd each time is too expensive.  I had greater hopes for checking that at least one of them is odd, which should save a quarter of the work half of the time, for a total saving of about 12%, but it doesn’t seem to help, even if you enforce it by never generating the bad pairs , the same way we are able to do for the size consideration in the current listing.<\/p>\n\n\n\n
diffy<\/a>Download<\/a><\/div>\n\n\n\nThis will produce the  pairs up to  in 100 minutes on my 3.6GHz machine.  It hasn’t found the next pair yet after a few days of searching.  It’s possible that some of the optimisation considerations (especially for what should be the cheap cases like eliminating ) change for large  as naive scoring becomes more expensive, but my haphazard trials have had inconsistent results, both algorithmically and in terms of apparently making the compiler stop favouring certain optimisations.<\/p>\n\n\n\n
(0,0)\n(1,1)\n(2,1)\n(3,1)\n(4,1)\n(5,3)\n(6,3)\n(7,4)\n(8,9)\n(9,11)\n(10,13)\n(11,31)\n(12,37)\n(13,44)\n(14,105)\n(15,125)\n(16,149)\n(17,355)\n(18,423)\n(19,504)\n(20,1201)\n(21,1431)\n(22,1705)\n(23,4063)\n(24,4841)\n(25,5768)\n(26,13745)\n(27,16377)\n(28,19513)<\/pre>\n","protected":false},"excerpt":{"rendered":"A week or so ago Rob Eastaway posted about the game Diffy on Twitter. Diffy begins with four numbers arranged around a cycle. Taking the (absolute values of) differences between adjacent pairs produces four more numbers around a cycle. If you start with positive integers then iterating this process eventually reaches . How many iterations … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[11,13,19],"_links":{"self":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/546"}],"collection":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/comments?post=546"}],"version-history":[{"count":0,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/546\/revisions"}],"wp:attachment":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/media?parent=546"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/categories?post=546"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/tags?post=546"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}