# Solution to "Beans, Beans, Beans"

The sons inherited and planted $19{,}897$ beans in a rectangle of dimensions $197 \times 101$ beans.

Here is one way to arrive at this answer:

Let $n$ represent our elusive number of beans. We will go clue by clue imposing new conditions until we have met all of them.

We have three primary clues: There are (1) $3$ left when counting by $7$, (2) $7$ left when counting by $9$, and (3) $196$ left when counting by $1+2+3+\cdots$. There are some secondary clues, such as $n < 30{,}000$, which we will remember for later. For now, let's go to the first primary clue: if you count them by $7$'s you end up with a remainder of $3$. Then we can say for some $i\ge 0$, $n=7i+3$. The next clue is that $n$ leaves a remainder of $7$ when divided by $9$, so then using the Chinese Remainder Theorem we will set up our second congruence using the results of the first:

Since $\gcd{(7,9)}=1$, we expect one incongruent solution $\pmod{9}$ for $i$. And by eying it, that would be

for some $j\ge 0$.

$n=7i+3$ and $i=9j+7$, then

Now the last primary clue is that when the sons take one more than the other in sequence until impossible to continue the pattern, there are $196$ left, which gives us the equation

where $m$ represents the number of turns they go back and forth until they can no longer continue the pattern. This also implies that $m\ge 196$ since if they took fewer turns than that and still had $196$ beans left, there would be enough beans to continue the pattern.

Previously we showed that $n\equiv 52\pmod{63}$, therefore

Here we can rewrite $m$ as $64m$ since $1\equiv 64\pmod{63}$, and we then complete the square. So

Now we need to know what numbers when squared leave a remainder of $43$ when divided by $63$. The quickest way to do this is with a chart. Since $43$ is not a perfect square, then we can eliminate every number whose square is less than $63$, therefore let's start with $8$. The calculations are expedited by use of a table of squares as well as a modulo calculator (there are some free apps for this).

 $x$ $8$ $9$ $10$ $11$ $12$ $13$ $14$ $15$ $16$ $17$ $18$ $19$ $x^2\pmod{63}$ $1$ $18$ $37$ $58$ $18$ $43$ $7$ $36$ $4$ $37$ $9$ $46$
 $x$ $20$ $21$ $22$ $23$ $24$ $25$ $26$ $27$ $28$ $29$ $30$ $31$ $32$ $x^2\pmod{63}$ $22$ $0$ $43$ $25$ $9$ $58$ $46$ $36$ $28$ $22$ $18$ $16$ $16$

We only have to go half-way to $63$ as the remaining will be a mirror reflection of the first half. In other words, if we extended our table further with $x=33,34,35,36,\dots$, then we would expect $x^2\pmod{63}=18,22,28,36,\dots$. So it appears that we have two values less than $63/2$, and by using the fact just mentioned, we can get the other two values greater than $63/2$. So $x=13,22,41,50$ all give us $x^2\equiv 43\pmod{63}$. Thus

Now remember that $m\ge 196$. If we model the above congruences for $m$ as such:

for some $a\ge0$, then we could apply the restriction $m\ge 196$ to each case to get

for some $b\ge 0$.

We have a formula for $n$ (number of beans the boys inherited) in terms of $m$ ($n=\frac{1}{2}m^2+\frac{1}{2}m+196$) and we have all the values for $m$, then we can calculate all possible values less than $30{,}000$ (the clue I said we would come back to!). The first four values of $m$ provide us all $n<30{,}000$:

 $m$ $n=\frac{1}{2}m^2+\frac{1}{2}m+196$ $198$ $19{,}897$ $207$ $21{,}724$ $233$ $27{,}457$ $242$ $29{,}599$

The last clue which will narrow the answer down to one is that there is only one way to form a rectangle out of the beans, which means that (1) $n$ is not prime (otherwise it couldn't be formed into a rectangle of more than one row), and (2) there is only one unique factorization for $n$ other than $1\cdot n$. Using an app for prime factorization, the following can be deduced very quickly:

So our only non-prime $n$ with one unique factorization is $n=19{,}897=101\cdot 197$ and we have our solution!