I was recently using this program that I made for a question I was asked.
It goes as follows,
"Kevin and Devin each make one hat per day for charity, but they started on different days. Today, Kevin made his 520th hat, and Devin made his 50th. A celebration is planned for the next day that Kevin’s hat count is evenly divisible by Devin’s hat count. In how many days from today will they celebrate?"
I made it so that my code could work for any number of hats Kevin and Devin start with. My code only checks for the first 1000 days, so the program does not go on forever.
I was wondering, is there a way to check if Kevin and Devin will ever celebrate, given to numbers to start with?
At the very least you can reduce the problem to testing a finite set of values.
Let $k$ and $d$ be the initial hat counts for Kevin and Devin, respectively. After $n$ days their hat counts are $k+n$ and $d+n$. Suppose that $k+n$ is a multiple of $d+n$, say $k+n=m(d+n)$; then
$$k-md=(m-1)n\;.$$
If $m=1$, $k=d$, and we can simply take $n=0$. Otherwise,
$$n=\frac{k-md}{m-1}\;,$$
and it’s clear that at worst we need only try values of $m$ satisfying $1<m\le\left\lfloor\frac{k}d\right\rfloor$, since $n$ cannot be negative.
A different bound can be obtained by noticing that no $n$ satisfying $\frac{k+n}{d+n}<2$ can be a solution, so we need only consider $n\le k-2d$. Thus, at worst we need test only
$$\min\left\{k-2d,\left\lfloor\frac{k}d\right\rfloor\right\}$$
possibilities.