Addition: well, that escalated quickly!

Zara Siddique | Sunday 16:30 | Ferrier Hall

I'm interested in optimal addition chains. These first seemed to me like an adding game with only one rule: you can only use numbers you’ve used before, and you have to start at 1.

What if I were to ask you how many additions we needed to get to 4? Well 1 + 1 = 2 and 2 + 2 = 4, which is clearly 2 equations. Now try to get to 172, and do it with as few additions as possible. This is where the problem begins.

This talk will explore the various methods one can use to calculate optimal addition chains. We will look at why many intuitive solutions don’t work (no matter how hard I tried), and why there is not yet an efficient solution.

The final part looks at the Scholz Conjecture, the most famous unsolved problem related to addition chains, and one way you can use Python to show whether it is true for specific numbers.

Link to video