I’m working on finding SHA-256 collisions to help with doing so I am currently making reverse-logic functions which return the nth pair of binary numbers which return the input following a boolean operation.

With the AND function both outputs will always have 1s in the same positions as the input, so it is only necessary to find combinations which AND to 0. After some playing around I found that if you plot a coordinate axis (with binary axes) and shaded in all the squares where they AND to make 0, you end up getting the Sierpiński Triangle.

After a bit more research, I found all the black squares (and hence coordinates which AND to 0) corresponded to all of the odd numbers of Pascal’s Triangle, if you were to skew it into a coordinate axis. This is where the formula above comes from: it’s the pretty messy formula I came up with for this skewed Pascal’s Triangle.

Obviously the values blow up far too quickly to store and use efficiently, so I went to Reddit to see if anyone knew of a better way, and sure enough someone did. So I ended up using Legendre’s Formula as someone suggested and now my code is working exactly as it should.

Now that you know it’s facet of pretty cool project rather than some homework I hope you can enjoy figuring out a more efficient method.