Adding Ones And Twos

Relevant wiki: Computational problems solved through Mathematical theory

We can construct a recursive statement for the number of ordered sums that can be constructed. Let this sequence be $f_n$ . We have $f_1=1$ and $f_2=2$ . Note how $f_n=f_{n-1}+f_{n-2}$ because all sums adding to $n$ are either all sums adding to $n-2$ , with an additional '2' added at the end of each sum, or are either all sums adding to $n-1$ , with an additional '1' added at the end of each sum. This makes all the sums of different order. Thus, we have constructed a recursive function as follows:

$f_n=f_{n-1}+f_{n-2},\ \quad f_1=1,\ \quad f_2=2$

From this, we can create a python script to determine $f_{666} \pmod{1000}$ :

1
2
3
4
5
6

def f(n, computed={1: 1, 2: 2}):
    if n not in computed:
        computed[n] = (f(n-1, computed) + f(n-2, computed))%1000
    return computed[n]

print(f(666))

This outputs 253, which is the answer we desire.

BTW, the above script works really well with large inputs, hence why I used it.

I didn't realise the beauty of Fibonacci related recursion this problem had! I did it this way: For any arrangement of 2's and 1's, there can be a max of $666$ 1's and $333$ 2's. Hence, every possible combination is the involvement of these 1's and 2's. For every 2 we write, we remove 2 1's from the sequence In a sequence with $k$ 2's we see that there are $666-2k$ 1's and in total $666-k$ terms Using the stars and bars technique, we see that possible arrangements for a particular number of 2's is: $\frac{(666-k)!}{k!(666-2k)!}$ Hence total arrangements are: $\displaystyle \sum_{k=0}^{333}\frac{(666-k)!}{k!(666-2k)!}$ Summing it is clearly out of range using common procedure in most architectures. Hence, by using the method of storing the values in an array, it can be easily computed with the answer being: $11098672708526908600764889580794591185766740194460441455645037457990760955740573933325912682002282764906185274340684734874403234129028461253$ The last 3 digits are: $253$