$f(n)=0$ for numbers of the form $7k, 7k+2$ and $f(n)=1$ for numbers of the form $7k+1, 7k+3, 7k+4, 7k+5, 7k+6$ . We can show this by induction. The base case of $k=0$ can be verified by calculating the first 7 terms of $f(n)$ . For the inductive step, we need to verify these 7 equations: $f(7(k+1))=0, f(7(k+1)+1)=1, f(7(k+1)+2)=0, f(7(k+1)+3)=1, f(7(k+1)+4)=1, f(7(k+1)+5)=1, f(7(k+1)+6)=1$ All of these are true by the definition of $f(n)$ so we are done. Starting with $n=1$ (because $f(0)=0$ ), for every group of 7 $n$ , we have 5 1's and 2 0's and 2016 is a multiple of 7, so the sum we are looking for is $(2016 \div 7) \times 5 +f(2017)+f(2018)=\boxed{1441}$

Bonus: $f(n)$ models one version of the game of NIM. In this version, players take turns subtracting 1,3, or 4 from the running total until one person wins by reaching 0. $f(n)$ tells us whether the first player has a winning strategy (indicated by $f(n)=1$ , otherwise $f(n)=0$ ) when the game starts at $n$ . To solve NIM, we can start at $n=0$ and determine whether each $n$ is a winning or a losing level. $n$ will be a winning level iff at least one of $(n-1,n-3,n-4)$ is a losing level (i.e. if you can force your opponent onto a losing $n$ ). This can be modeled by $f(n-1)f(n-3)f(n-4)$ because the product will be 0 iff one of the factors is 0 (otherwise the product will be 1). Of course our winning/losing label numbers are switched from the product so we need to run the product through a function that maps 0 to 1 and 1 to 0. $1-x$ works, so we have an iterative function $f(n)=1-f(n-1)f(n-3)f(n-4)$ which models the winning and losing $n$ of NIM. Edit: Because this problem is on Problems of the Week, you don't see the title, but the title ("Numbers Iterated Manually") gave a clue to the bonus question.

To build up the $f(n)$ iteratively, you only need to know the previous 4 terms. If you find 4 consecutive terms that match 4 earlier consecutive terms, then $f(n)$ will be periodic.

It's not hard to see that $f(n)$ is always either 0 or 1 and so there are only $2^4=16$ different sequences of length 4. By the time we get $f(16)$ , we must have started some periodicity. Hence, we can be confident that manually finding the repeating sequence is possible and then finding the sum should be easy.

$f(-4)=f(-3)=f(-2)=f(-1)=1$

$f(0)=1-1\cdot 1\cdot 1=0$

$f(1)=1-0\cdot 1\cdot 1=1$

$f(2)=1-1\cdot 1\cdot 1=0$

$f(3)=1-0\cdot 0\cdot 1=1$

$f(4)=1-1\cdot 1\cdot 0=1$

$f(5)=1-1\cdot 0\cdot 1=1$

$f(6)=1-1\cdot 1\cdot 0=1$

The repetition of the sequence of four 1's in a row mean that $f(7+k)=f(0+k)$ for all non-negative integers $k$ . The period is 7 and the number of terms in the sum is $2019=7*288+3$ . The sum of any consecutive seven terms is 5 and the first three terms in the period sum to 1.

So $\sum_{n=0}^{2018} f(n)=7\cdot 288 \cdot \frac{5}{7}+1=1441$ .

We can directly verify by induction on $n\geq -3$ that $f(n) = \begin{cases}0, & \text{ if } n \equiv 0,2 \pmod{7} \\ 1, & \text{ otherwise}\end{cases}$ (The base case is $-3 \leq n \leq 3$ , and the inductive step would require seven separate cases, for each of the seven remainders modulo $7$ )

Then, since $2018 = 7\times 288 + 2$ $\begin{aligned} \sum_{n=0}^{2018} f(n) &= \left(\sum_{q=0}^{287} \sum_{r=0}^6 f(7q+r)\right) + \sum_{r=0}^2 f(7\times 288 + r) \\ &= \left(\sum_{q=0}^{287} 5 \right) + (0 + 1 + 0) \\ &= 288\times 5 + 1 \\ &= \boxed{1441} \end{aligned}$

f(n) follows a sequence of 0, 1, 0, 1, 1, 1, 1 with a period of 7 which sums up to 5. Hence f(n+7)= f(n). Now, 2018÷7=288 with a remainder of 2. The sum of 1st two numbers in the srquence is 1. So, the total sum will be 288×5+1=1441.

c++ solution using dynamic programming and recursivity :

include <iostream>

int t[2019]; using namespace std; int f(int n) { if (n<0) return 1; if (t[n]==-1) { t[n]=(1-f(n-1) f(n-3) f(n-4)); return t[n]; } return t[n]; } int main() { for ( int i=0; i<=2018; i++) { t[i]=-1; } int sum=0; for( int i=0; i<=2018; i++) sum+=f(i); cout<<sum; }

Derive and enumerate the sequence {f(n), n=0,1,2.....} to get a pattern of {0,1,0,1,1,1,1} which repeats. Therefore, series sum=2019-289-289=1441.

Answer=1441

I chose to use Python to calculate the answer, tacking a memoization decorator onto the function to eliminate repeated calls for the same values.

def memoize(f):
    memo = {}
    def fn(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return fn


@memoize
def f(n):
    if n < 0:
        return 1
    else:
        return 1 - f(n-1)*f(n-3)*f(n-4)


def F(min, max):
    s = 0
    for i in range(min, max+1):
        s += f(i)
    return(s)


print(F(0,2018))

If you're a programmer, please let me know what you think of my code, especially if you have any tips for how I could better write the code to make it more versatile.

My solution will likely leave out some detail, but I'm going to try and make it intuitive. By calculating explicitly f(0), f(1), etc. you can come to the conclusion that this produces a repeating pattern of 0, 1, 0, 1, 1, 1, 1. If there were no zeros, the sum would be 2018. The number of this pattern repeated fully is $\left\lfloor{2018}/7\right\rfloor$ and in each repetition you lose 2 of the total 7. The last repetition only includes the first 2018 mod 7 = 2 terms of the pattern, which loses you another one of the total 2018. So, the sum ends up being 2018 - 2 $\left\lfloor 2018/7\right\rfloor$ - 1 = 1441. In retrospect this is kind of convoluted; you can think of this as each repetition adding 5 more ones and the final incomplete repetition adding 1 in which case you get 5 $\left\lfloor{2018}/7\right\rfloor$ +1 = 1441. The logic works both ways though.

It can be easily solve with Python

1
2
3
4
5
6
7

array = []
def f(x):
    return 1 if x < 0 else array[x]
for i in range(0, 2018):
    array.append(1 - f(i - 1) * f(i - 3) * f(i - 4))
print sum(array)
 #output : 1441 

Using this code i get $\boxed{1441}$ as output which is the correct answer.

If we start calculating f(n), we realize it equals to 1 or 0, and that all the zeros have the form of 5+7k, or 7+7k, except f(n=2), so we only need to substract these zeros from 2018, because 2018 is the sum if all f(n) were equal to 1. So we have 1 zero from f(n=2), 288 zeros from 5+7k<=2018, and 288 zeros from 7+7k<=2018, for a total of 1+288+288=577 zeros. Final answer would be 2018-577=1441 As a non mathematician i dont like induction :P

I checked the values of f(n) until n =14, and it yielded a repetitive occurrence of values is found to start after a cycle of 7 elements. The values were: f(0) = 0 f(1) = 1 f(2) = 0 f(3) = 1 f(4) = 1 f(5) = 1 f(6) = 1

since 7 288 = 2016 (the closest one can get to 2018). The summation now gives 5 288 = 1440. 5 is received from summation of { SUMof [f(n) : 0,1,2,3,4,5,6,7] } then add 1 more to 1440 to get 1441 since we get values (0,1) when we increase n to 2018. So final answer is 1441.