From: "John Conway" Date: Mon, 31 Oct 94 Testing for linear recurrence relations: There is a very nice method that I heard (only once in my life) under the name of "the QD algorithm", or "quotient-difference" algorithm. I don't think this is a very good name, and Richard Guy and I call the resulting patterns "number-walls" in our "book of numbers" that might one day get published. You do this: Take your starting sequence a b c d ... and put a row of 1s above it, and compute further sequences A B C D ... and so on to fill out a "number-wall": 1 1 1 1 1 1 1 1 1 1 a b c d e f g h i j B C D E F G H I X Y Z ... by the rule that for any entry and its 4 neighbors: N W C E S we have NS + EW = C^2. I'll do this for the example 0 2 1 2 2 3 4 6 9 14 22 35 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 2 1 2 2 3 4 6 9 14 22 35 56 90 145 got it yet? 4 -3 2 -2 1 -2 0 -3 -2 -6 ... can't be bothered 1 -1 1 -1 1 -1 1 -1 0 0 0 0 ? 0 and if it's given by a linear recurrence, it will vanish beyond some row. There are problems like that ? mark, whenever you get a 0. I worked out a fairly neat way to work around 0s. It's a fantastic theorem that they always come in square arrays, which Guy and I called "windows". I think more people should know about this. I tried to persuade Sloane to put it in the introduction to the new version of his book, but don't think I succeeded. Superseeker doesn't use it. He does have what Guy and I called "difference fans", under the name of "difference tables of depth d". (I tried to persuade him to use my term "pth differences q times removed", but again without success.) These work as follows: construct the difference table a b c d e f g h A B C D E F G X Y Z ... U V ... Now take the leading differences a A X U .... as the first row of a new difference table which is the next leaf of the fan, and which I'd like to call the first removed difference table. From its initial differences, start yet another table, the differences at second remove, and so on. These difference fans, or removed difference tables, can be used to detect linear recurrence relations in a manner I don't quite recall, and I think superseeker does that. Quite a nice exercise is to draw the difference fan for (say) 1,5,25,125,625,.... John Conway ----------------------------------------------------------------- From: "John Conway" Date: Tue, 1 Nov 94 On number walls: If the original sequence is a b c d ... then the next row is |b c| |a b| etc and the next one |c d e| |b c d| |a b c| and so on. If you're equipped with a computer, that's all you'll need (at least, unless you also want to understand things). It explains why the fractions don't happen. What happens around a window is this The numbers immediately bordering the window form 4 geometric progressions: A --- ratio N ---> B | /|\ | 0s in here | ratio W ratio E | | \|/ | C <--- ratio S ---- D this not very symmetric labelling turns out to be best. now consider 4 numbers all the same distance along their geometric progressions: x Sorry - I should have said first that NS = +-EW, with the sign being - whenever it can be, + when it must be. Now consider the four numbers I was about to, just outside four corresponding terms of these progressions: n --------> | w| | | | | |e | | --------- s Then there's some simple relation R(N,S,E,W,n,s,e,w) = 0, that I can't quite remember, but I can look it up if you have much trouble reconstructing it. It's vaguely like n/N + s/S = w/W + e/E but I bet that isn't exactly right. Maybe n,s,e,w should really be the ratios of those numbers on the second border to the terms of the first border just inside them? I found the properties of number-walls absolutely fascinating, and recommend them to everyone else. Do you know about frieze patterns? Also the Moessner magic? It's similar vaguely mystical stuff. John Conway