Exploring Information Flow

In my last post I discussed a method of programming that I called "Information Flow Programming". In it I introduced my style of information flow diagram. Go check it out if you want to get the primer on today's topic. In this post I want to show this method in action in more detail.

Summing Proper Divisors

Last year I did some streams practicing my x64 assembly programming on the Project Euler problems. For one of these problems, the way I found my solution makes an interesting example of information flow programming. I won't go over the whole problem, but I will spoil the key ideas to my solution. If you're a problem solving enthusiast and you want to take a look at it before it gets spoiled, this is your stop.

The part of the problem I will focus on is finding the sum of the proper divisors of a number n. This post is going to have a lot of math starting... now!

A proper divisor of a number n is a number in the range from 1 to n - 1 that divides n.

Example: For the number 10 the proper divisors are 1, 2, and 5.

With the initial diagram written down, the next step of my "method" is to break this down into smaller more manageable arrows. Any decomposition will do. I don't know an easy way to compute this off the top of my head, but I do know an easy way to compute a sum off the top of my head, so let's start there!

Now if I had a way to get the correct "array of numbers", I could compose these two pieces to solve the problem. But actually, that array is not that hard to build either. It's just a matter of testing each number in the finite range 1 to n - 1. If I pick a number k from that range, it is a proper divisor of n if k "divides" n, which is to say that k divided by n must have a remainder of zero. That's good because that's easy to compute with the tools I already have. C's modulo operator gives me exactly that.

There's nothing wrong with this solution as a first pass, but now I want to use a deeper understanding of the problem to do something better. Doing this first pass wasn't a waste of time, it gives me a tool to go get a deeper understanding. If this was a larger problem I might have converted this first pass solution into code just to give me something that could help me check future ideas. For most of this post, it will be reasonable to just apply this logic by hand.

Finding an Exploitable Pattern

When I want to get deeper insight into a general problem, one useful technique I use is to look at specific cases first. Since I can compute the function by hand, I can generate a table like this and start searching for patterns:

Since this problem deals with divisibility, my first thought is to check what's going on with the primes:

And look at that, all the primes have a sum of 1. Sadly it's also not that useful. If a prime p is only divisible by 1 and itself, then 1 is the only number in the range 1 to p - 1 that divides p. But that's okay, because that naturally takes me to my next best guess, what's going on with powers of primes?

Of course, again it's obvious once you've looked at it. The proper divisors of a power of a prime will just be the smaller powers of the same prime! If you're not sure how this is progress: any new pattern is progress. Difficult problems often require building several insights on top of eachother. This might be a dead end, but the fact that we don't see a way to use it right away doesn't mean we should abandon it.

In this case I would want to know if there's some way I can get sums for these powers without actually doing the whole sum, and it turns out there is. It's known as a geometric series and it satisfies this equation:

To translate this into programmer speak: on the left side of the equation we have an expression that would be computed by a for loop with n iterations, on the right hand side we have an expression that is close to some fixed arithmetic (that a to the power n is still a wrinkle). Since they are equal, I can replace the more expensive computation on the left with the cheaper computation on the right.

Now I have a new arrow to add to my information flow diagram!

This is where it gets important that I use more than just types as I annotate the arrows. The formula for the geometric series is really a function of two arguments, a and n, and in general it's output isn't a sum of proper divisors. But within the context of my original problem the point is that this is a way to find the sum of proper divisors for a power of a prime. The function geometric_series is just the tool that makes the arrow possible.

I am still far from a solution to the original problem. The next step here is to figure out what other arrows I need on the board so that they can all compose into a solution to the original problem.

Filling in the Gaps

The diagram I have so far shows the shape of the missing piece. I am supposed to have an arrow that starts with any number, and goes to the sum of proper divisors. The arrow I actually have ends in the right place, but it starts with something more restricted. The gap in my diagram is an arrow that takes any number to a power of a prime.

I can't just plug in any arrow that maps a number to a power of a prime. For instance, I might try to fill the gap with an arrow that throws away the input and outputs a 2. That does technically qualify as an arrow with a number input, and a power of prime output. But that's obviously not a solution to the overarching problem. If I did that the arrows would be composable, but when I compose them they would not be equivalent to the arrow that represents my original problem. I need an arrow that fits the gap, but that's not the only constraint.

In this case I also need an arrow that preserve enough information about the original number to actually let me solve the problem. So what takes in any number, outputs a power of a prime, and does not lose any information about the original number? There's only one candidate in my number theory tool box that meets those requirements: factorization.

We can view a number a mixture of primes. From this view factorization is the operation that takes in a mixed number, and splits it out into it's pieces as a list of powers of primes. It has the property that when you multiply the powers of primes together, you recover the original input number. Drawn as an arrow in my diagram it therefore looks like this:

Once again I have a gap. This time the gap is between the factorization and the geometric_series arrows. The factorization arrow outputs an array of powers of primes, and the geometric_series arrow takes only a single power of prime.

This sort of gap suggests a few different courses of action. One option is to mix the array down into a single value. In this case it's pretty clear that's not what we want. Prime factorizations are unique, so it seems likely that replacing one prime factorization with another will lose important information about the original number.

Another option in this scenario is to apply the geometric_series arrow across the entire array. In the language of functional programming this might be called "mapping" or closer to the category theory side of things "lifting". In very grounded terms, it means our arrow with a single input can be transformed into an arrow with an array input like so:

That move has closed the gap between factorization and geometric_series, but I've opened up a gap between the output of the geometric_series and desired output from the original problem. Again, we're looking at a gap between an array type and a single value of the same type. Unlike before there is no arrow to "map" or "lift". This time our only option is to find a way to mix the array down to a single value, we're crossing our fingers that that will be possible.

Concrete View

I've made a few moves here guided entirely by the abstract view given by these arrow diagrams. I have a "shape" for this final arrow, but I don't have the slightest hint at what it's internal guts need to be. To make progress, I need to switch to a concrete view and see exactly what the information looks like with the transformations on my board so far.

Here's what it looks like when I plug a 9 into this system.

This starts to help. We can see that the 4 we want to arrive at is showing up along the way, but 9 is a pretty simple case. It's a power of a prime, and we were already satisfied with how to handle those. So it doesn't really highlight what the mixing is going to be like. Let's try something that isn't a power of a prime, like 12:

Now this is a better picture of what's going on. The input gets broken down into a factorization. The factorization gets converted into sums of proper divisors. And then, somehow, we have to mix the 3 and the 1 into a 16. That last step is still a bit unclear. Let's search for a pattern in a bigger table:

My first observation here is that I should really just be ignoring the primes and powers of primes. The only interesting cases here are 6, 10, and 12. My second observation is that we have a serious problem!

We were hoping to find a way to take these arrays of sums of proper divisors and mix them down into the final answer. But in this table I can see that that's not going to be possible. The case 6 and 10 both arrive at the same intermediate values, but our desired output values are different in each case! The only way for a determinstic function to have two different outputs is to have two different inputs, so our plan is broken.

Back to the Beginning

At this point I would not be surprised if you're thinking all this diagramming and arrow decomposition stuff isn't doing us any good. And in a certain way that's true. Nothing about this thinking tool gaurantees that it leads straight to a correct solution, or even that it eventually leads to a correct solution.

Despite the fact that it did not magically solve the problem, I think it has been very useful. It kept us organized and on track. If you go back to our original pattern hunting, we noticed that powers of primes had a regular pattern and we decided to see if we could build up an entire solution from just that insight. The information flow diagrams helped us explore the space of solutions shaped around that idea. Each step of the way was more or less forced.

Abstract tools only become a problem when you forget what they're for. When they have served their purpose we put them down and return to the concrete side of the problem. Therefore let's return to this table:

Last time we looked at this table, we were hunting for a pattern to exploit. We looked at primes and powers of primes. No surprise then, that in the end our solution failed on the composites with multiple prime factors! This time let's look specifically at those:

Looking at this, it jumps out at me that 6, 10, 14, and 15 all follow a very regular pattern too. They are the composites with exactly two distinct primes in their factorization, and with all of the powers being 1. Thinking about this case it becomes obvious that if we have two primes p and q, and our n is p times q, then the proper divisors in that case will always be 1, p, and q.

But since focusing on special corner cases has already failed me once, I want to really understand the 12. That's the first case where we have both a mix of primes and and a power higher than 1 at the same time.

This is a lot messier than the nice powers of primes we noticed the first time around, but I still sort of see them lurking in there. The 12 has a "1, 2, 4" under it, and it also has a "1, 3" under it. This highlights why the last solution was losing information. When we converted a power of a prime like 4 into it's proper divisors we only had "1, 2", but in case like 12 where 4 is "in the mix", but is not n we need more than just the "1, 2". Even worse, when we got down to a prime like 3, the list under that prime is just "1", making all primes look the same, but 12 needs the "1, 3".

This is about half of a new idea. If 12 breaks down into the sequences "1, 2, 4" and "1, 3", can we then assemble the list "1, 2, 3, 4, 6" from that? It already looks close, but it's not as simple as concatenating these lists. That would lead to an extra "1" and a missing "6". The 6 is particularly intersting, because it's the only divisor that isn't just a power of a prime. We would only discover it by mixing together primes from two different lists. Of course by "mixing" here I just mean multiplying, since that's how one "mixes" primes.

There's another piece of an idea: what happens if we multiply these two lists? We could imagine such a multiplication happening in a table like this:

Now that is encouraging! We have all the numbers from the list coming out, plus an extra 12, which happens to be the input number. Just to make sure this isn't another special case, what happens if we pick something with even more primes?

Here we're looking at the divisors of 180. 180 factorizes into the powers of primes 4, 9, and 5. For the 4 we use the list "1, 2, 4", for the 9 we use the list "1, 3, 9" for the 5 we use the list "1, 5". We then multiply the elements of these lists in every combination.

I haven't said anything here that is sufficient to prove that this is the right list for 180, but it is. We could go write that very simple solution from the beginning of the post to check. Or we could try to write a proof that this technique works in the general case. Confirming that this idea works is a good idea, but not really the point of this post. Let's call it an "exercise for the reader" and move on!

Shifting the Problem

The problem originally set us up to think about the proper divisors of n, but we've actually switched to thinking about divisors of n. Let me explain the difference.

A proper divisor of a number n is a number in the range from 1 to n - 1 that divides n.

A divisor of a number n is a number in the range from 1 to n that divides n.

Example: For the number 10 the proper divisors are 1, 2, and 5, while the divisors are 1, 2, 5, and 10.

The list of divisors of n is almost the same thing as the list of proper divisors but with n included at the end. It's a trivial change that makes all the difference.

Remember our original overarching problem?

What if we try to decompose it like this?

In other words, what if we just compute a sum of divisors and substract the extra n off the end?

Earlier it seemed we were really close to a solution, but it turned out to be impossible to take an array of sums of proper divisors and mix it down in the final stage. After exploring a bit more, we found it was much easier to work with divisors than proper divisors, so maybe by shifting the problem in this way, the mixing problem will become solvable. Let's bring back the old plan:

All I've done is taken the old plan, the one that looked like a dead end, and shifted it. It used to be a decomposition of the arrow sum_proper_divisors but now it is a decomposition of the arrow sum_divisors.

We need to revisit the old arrows to work in this new context. The factorization arrow remains the same, but we need to tweak the parameters on the geometric series equation so that it counts one more power than it did before:

Next we can take the concrete view of how this system transforms inputs to see if we might be able to solving the new "mixing problem":

Again 6, 10, and 12 make up the interesting cases. Here those cases are pointing us to a relatively simple solution. It appears we can just multiply the sums of divisors together to get the combined sum of divisors.

That's a pattern, but does it work in general? It turns out it does. Take a look at the case of 12 in particular:

Earlier we saw tables where multiplying lists of prime powers generated lists of divisors. Here we're seeing the same pattern. This is working because of the way "foil" works, or in more general language, because of the way multiplication distributes over addition. When we have two numbers that are the results of sums of lists, multiplying the numbers together gives the same result as if we first multiplied the two lists to make a combined list and then added up the combined list.

How Did That Happen?

With that last piece of the puzzle we can complete our information flow diagram:

This is where this post ends. From here there are still steps of building a factorization table, figuring out how to actually compute that geometric series expression, and fusing all of the paths together so that instead of generating and consuming actual arrays, it all gets handled in one pass with accumulators gathering the values in the array as quickly as they are generated. This has been about making a plan, the rest is about executing a plan.

All of this has been a retelling of how I solved this problem, but I think if you go back and watch the stream where I first did this, the series of steps I went through is pretty much the same. I wasn't drawing arrows at the time, but I was holding them in my head in a very similar same way.

As I said last time, I believe this is a more "convergent" methodology of programming than the more commonly used narrative-driven methodologies. For reasons I can't fully explain, this way of writing down ideas and plans for software manages to isolate the effects of small tweaks. Small changes to the starting premise don't lead to full rearangements of code. In this example we can clearly see this as large parts of our fist dead end plan ended up coming back to life in the final solution.

Takeaways

The primary aim of this post is to give an example of using this information flow method, so here are some key takeaways:

First, find an easy decomposition of your problem that works no matter how slow. We're not going to ship crappy software, but having one dumb solution up your sleave is always helpful.

Second, once you have an idea for a clever solution, make sure you understand your idea as an arrow and put it on the board. Annotate everything that matters about the input and output ends of your idea, not just low level types.

Third, fill the gaps. The arrows will show you where your solution is incomplete. If there is a way to make a full solution around your idea, then there will be a way to capture the shape of that solution with the arrows. Remember there are several techniques for filling gaps. You can introduce new arrows, so long as they preserve the necessary information. You can modify existing arrows by "lifting" them, for example array-ifying an arrow. And there are more things you can do that we didn't cover here - use your creativity!

Conclusion

For now I think we've covered plenty, perhaps a bit too much. If you have any thoughts or questions about this, you can reach out to me at allenw@mr4th.com. We still have other ways to explore this style, in future posts I'd like to look at how this works in much larger architecture problems. You can be notified of when these come out by subscribing to my Newsletter. Thanks for reading!