brhfl.com

Well, I was right about one thing – there was a straightforward solution to this whole Aztec diamond problem. To be fair to myself, my original solution holds up – I neglected to add one somewhere in my equation (we’ll get to that later), an error that was insignificant at the start, and less significant as the Aztec numbers increased. To get to the reveal, it’s worth backing up to our series, OEIS: A046092 again. Somehow, in my haste, I kind of glossed over the fact that these are ‘4 times triangular numbers,’ a fact that became readily apparent to me when I was coming up with the diagrams for the last post. You see…

…our Aztec diamond is made up of four triangles; and it is in fact true that each of our Aztec numbers is 4× the corresponding triangle number. A funny thing about triangle numbers is that if you multiply them by eight and add one, they become perfect squares. This can be demonstrated visually:

This visual only proves that it’s true for the triangle number, 6, but it is universally true and readily proven – this ‘Cool Math Stuff’ post shows it succinctly, and John Conway and Richard Guy discuss it in The Book of Numbers. Rehashing the proof here seems rather pointless. Fascinatingly, I did almost figure this out last time, with the extra unit hypotenuse theory.

So, we know that for our Aztec number, x, x/4 is a triangle number, and for this triangle number, y, 8y+1 is a perfect square. We know that any given side of this square is made up of 2× the length of a side of triangle y plus one, which is ultimately the value that we need to recreate our square from our grid. We can see this rather clearly in the first diagram with the triangle highlighted – the three dots forming the outer side correspond directly to segments of our grid.

Thus, given a triangle number, y, the length of any of its sides is (sqrt(8y+1)-1)/2. Which then leads us to the same thing for our Aztec number, x, (sqrt(2x+1)-1)/2. Now, to solve my problem, I actually need to add one to this. Given that we’re dealing with integers, this can be simplified to ceil(sqrt(2x+1)/2) – precisely what I originally came up with, aside from the +1.

So, my equation was wrong, but it provably works – the off-by-one error is clearly insignificant for a 3×3 square, and, given x, sqrt(x²)-sqrt(x²-1) converges toward zero:

My initial test of x=ceil(sqrt(2y)/2) to determine the size of a square given a value in A046092 corresponding to how many line segments would remain if the grid formed internally at every unit of height and width of the square was broken at every intersection was tested and shown to be valid for the first 1000 numbers in the sequence. I did this haphazardly in Excel, just to make sure it wasn’t going to fail quickly.

I have since scripted a test in python, which has thus far shown my method viable up to a 50907428697×50907428697 square. The script is called by passing it an argument containing the initial integer for the square’s size (default 2), and it loops infinitely until it either fails or is halted with SIGINT. Upon halting, it returns something like Last success: Square 39033633; azNum 3047249088424644; urNum 39033633.0, where Square is the height/width of the square being tested, azNum is the number of line segments (or squares in the equivalent Aztec diamond), and urNum is the calculation which (hopefully) is equal to Square. Revealing the last success in this way tells me where to start next time. The code:

import signal
import sys
from math import ceil,sqrt
def sigintHdl(signal,f):
    print "Last success: Square %s; azNum %s; urNum %s" % (tNum-1,azNum,urNum)
    sys.exit(0)
signal.signal(signal.SIGINT,sigintHdl)
tNum = 2 if len(sys.argv)<2 or int(sys.argv[1])<2 else int(sys.argv[1])
result=0
while result==0:
    azNum=tNum**2+tNum*(tNum-2)
    urNum=ceil(((2*azNum)**.5)/2)
    result=urNum-tNum
    tNum+=1
print "FAILURE: Square %s; azNum %s; urNum %s" % (tNum-1,azNum,urNum)

There’s another way of looking at this whole thing. If we consider an isosceles right triangle with hypotenuse h, we know the length of either of the legs is equal to sqrt(h^2/2). Interestingly enough, if we work with a hypotenuse of one unit larger (which should never exist as a halved Aztec diamond), h^2/2 is equal to our A046092 value +0.5.

Ultimately, the problem seems to be one of dealing with a not-quite-proper triangle. It’s easy to imagine additional nodes that make the triangle more… triangular. Doing so leads to more funny math, but it all sort of, kind of makes sense. I guarantee there’s an off-the-shelf solution out there, and it’s likely quite straightforward and, in hindsight, obvious. But this sort of math isn’t necessarily my forté, so I’ll just fidget around until I come up with something conclusive. At this point, it’s all for fun – I have far more known-valid values than I could ever imagine needing. My little python test snippet will easily be reused for other things as well, so I’ll call that a win.

A little project I’m working on requires me to suss out the size of a square given the following: Imagine a square of width and height x units. The square is gridded by unit such that x^2 squares are visible inside it. How many of these squares’ perimeter lines exist inside the outer square? Or, put another way, if you then erase the border of the original square and break every line segment at the intersections, how many line segments do you have left?

It seems to work out to x^2+x*(x-2). For a 2×2 square, there are 4 segments left. 3×3 yields 12, 4×4 yields 24, 5×5 yields 40, 6×6 yields 60, and so on. I confirmed this far by manually counting the segments, and everything seemed good. This wasn’t what I needed, however, I needed to be able to do it in reverse – given 24 segments, I needed to come up with my outer square’s width and height of 4. This was not an obvious solution.

I tried searching for things like ‘size of square from inner grid segments’, but I couldn’t really articulate the thing in a way that got me anywhere. Or, perhaps, nobody has ever really needed this version of this problem solved before (though I find that doubtful). I needed a new angle. I searched OEIS for my sequence, 4, 12, 24, 40, 60, and came up with A046092, ‘4 times triangular numbers’. Now, OEIS is great, but it has a way of presenting a lot of information very tersely, which can be overwhelming. So I googled A046092, and nearly every hit came back to one thing – Aztec diamonds.

Further searching revealed that Aztec diamonds are popular because of the Aztec diamond theorem and the Arctic Circle theorem, both related to domino tilings. This is all very fascinating, but unfortunately presented me with a dead end. Fortunately, I did also discover that Aztec Diamond Equestrian is a company that makes leggings with very functional looking pockets, so that was a win. But on the math side of things, I wasn’t coming up with much. I did, at least, realize that if I rotated my grid and treated each of those segments as the diagonal of a square, I was in fact dealing with an Aztec diamond. If nothing else, this allowed me to confirm that A046092 was the sequence I was dealing with, it allowed me to confirm my original equation, and therefore meant I could test any arbitrary case without manually counting.

I started noticing other patterns, too. The problem is complicated because it’s like a square, but it’s missing the corners. This is where the narrative begins to fall apart. All these thoughts of squares and right triangles, hypotenuses… I established a formula that I have tested for the first 1000 integers in A046092, they all pass. But I cannot come up with a proof that explains it. Furthermore, I am not confident that it actually holds up despite the first 1000 integers validating. The next step is scripting the formulae out to test well beyond 1000.

Now, for my project, I don’t need anywhere near 1000, so the equation is Good Enough. Hell, I could probably hardcode the sequence as far as I need it, and a lookup table would likely be faster than a bunch of math. But now I’m really curious. So for a square x by x units, and y as the xth integer in A046092, I’d love to prove that x=ceil(sqrt(2y)/2). I don’t know that I can, but I would really like to. Ultimately I know I’m looking at a hypotenuse, or an approximation of a hypotenuse, with the Pythagorean theorem being beautifully simple given the area of a square.

I guess, in the end, I have an equation that more than meets my needs. I learned about Aztec diamonds, and I figured out why this problem is not as simple as it originally seems. I also learned about some pretty bangin’ equestrian leggings. I’m going to keep at this, though, because it fascinates me, and I haven’t found a solution in the wild. I’ll report back, but before I do, there will likely be a game-in-a-post to explain why I was trying to solve it in the first place.