At the begginning I'd like to sorry for the long intro, but I think it helps in fully understanding the problem. Of course the math problem is much shorter, so if you are not interested in the full story, just skip to Math problem header.
Story
I recently got my AtMega32. I started creating some example circuits and I think I found a cool math problem.
So, lets start with how does button input work. Button is a very simple part, it just physicaly connects its pins if its pressed. From the software side, I can check if a given pin of microprocessor is currently powered. So basicaly, if I want to test if the given button is pressed, I just connect vcc (power) to one button pin, and the other button pin to one of the processor pins.
Now when I want to test if btn1 is presed I just check if pin1 is powered. Simple enough?
Okay, lets move further. If I have let's say 3 buttons, I have to connect each one to another pin, just like I did with first one:
Now it seems that if I want to connect N buttons, I need N pins on microprocessor, right?
Actually not. Another cool feature of microprocessors is that they can set power to some of the pins which are defined as outputs. So, let's say I need 6 buttons. It seems that I need 6 free pins, but I'm able to connect it using only 5. How? This circuit demonstrates:
Okay, I have to grant it, I'm a bad drawer. But, I hope I can explain it somehow. Firstly, Red pins are outputs, Green pins are inputs. Darker and Lighter cables don't cross. At first, I power up pin6, and check all inputs 1-3. Then I switch the power to pin7 and again I check all inputs 1-3. Now, programmers would know how it works, this is pseudo-code:
output: boolean buttons[6];
o = 0;
while (o < outputNumber)
{
setPowered(o);
i = 0;
while (i < inputNumber)
{
if (isPowered(i))
buttons[outputNumber * o + i] = true;
else
buttons[outputNumber * o + i] = false;
}
setUnpowered(o);
}
Now in the array buttons I have states for each of 6 buttons, using only 5 pins (3 in, 2 out)! Of course, I could use 3 outputs and 2 inputs, same technique. For this math problem lets assume the processor has infinte speed, so the number of iterations is not important.
Let's also say that I can't connect any button to VCC directly, so to have 3 buttons I need 4 pins (3 in, 1 out, instead of 3 in all connected to vcc).
Now my problem is: How many pins do I need to connect N buttons?
I came up with:
Math Problem
We have given sequence defined as:
$$a_n = minimal\;(a+b)\;where\;a*b\ge n$$
where $a,b,n \in \mathbb{N}; a,b,n \gt 0$
How to easily calculate N-th element of that sequence? For example, what is $a_{1000}$?
First elements are (assuming $a \ge b$):
- $a_1 = 2$, a = 1, b = 1
- $a_2 = 2$, a = 1, b = 1
- $a_3 = 3$, a = 2, b = 1
- $a_4 = 4$, a = 2, b = 2
- $a_5 = 5$, a = 3, b = 2
- $a_6 = 5$, a = 3, b = 2
- $a_7 = 6$, a = 3, b = 3
- $a_8 = 6$, a = 3, b = 3
- $a_9 = 6$, a = 3, b = 3
- $a_{10} = 7$, a = 4, b = 3
Suppose we have $k$ pins and want as many buttons as we can get with that many pins. As a function of $a$ that is $ab=a(n-a)$ buttons, and the graph of this is parabola with maximum at $a=k/2$.
So if you have an even number of pins, the optimal number of buttons is reached by selecting $a$ and $b$ to be equal (half of the pins). If there's an odd number of pins, you get the same maximum result for $a=\frac{k-1}{2}, b=\frac{k+1}{2}$ or vice versa.
Therefore, if you desire $n$ buttons, then $2\lceil \sqrt{n}\rceil$ pins will certainly do, where $\lceil\sqrt n\rceil$ is the square root of $n$ rounded up to the nearest integer. $2\lceil \sqrt{n}\rceil-2$ will be too few, but $2\lceil\sqrt n\rceil-1$ might work.
It's not too difficult to derive a formula that tells you exactly when to subtract 1 and when not to, but it's simpler and less error-prone simply test whether it works.