# It's been a long day

Computer Science Level 5

There were $$x$$ friends who went on a sea voyage. Due to unforeseen circumstances, their ship wrecked and they reached a mysterious island. On that island, there were many monkeys.

On their first day they gathered as many coconuts as they could find into one big pile. They decided that, since it was getting dark, they would wait until the next day to divide the coconuts.

That night each man took a turn watching for rescue searchers while the others slept. The first watcher got bored so he decided to divide the coconuts into $$x$$ equal piles. When he did this, he found he had one remaining coconut. He gave this coconut to a monkey, took one of the piles, and hid it for himself. Then he jumbled up the remaining $$(x-1)$$ piles into one big pile again.

To cut a long story short, each of the $$x$$ men ended up doing exactly the same thing. They each divided the coconuts into $$x$$ equal piles and had one extra coconut left over, which they gave to the monkey. They each took one of the $$x$$ piles and hid those coconuts. They each came back and jumbled up the remaining $$(x-1)$$ piles into one big pile.

Let $$\Phi (x)$$ denote the smallest number of coconuts there could have been in the original pile, where $$x$$ is number of friends. And let $$\displaystyle S = \sum_{i=5}^{1000} \Phi(i)$$. Find the sum of digits of $$S$$.

As an explicit example: if $$x = 3$$, $$\Phi(3) = 25$$.

×