Crazy Function

For fixed integers $a, b, c$, define the crazy function $F(n)$ as follows:
$F(n) = n – c$ for all $n \gt b$
$F(n) = F(a + F(a + F(a + F(a + n))))$ for all $n \le b$.

Also, define $S(a, b, c) = \sum \limits_{n = 0}^b F(n)$.

For example, if $a = 50$, $b = 2000$ and $c = 40$, then $F(0) = 3240$ and $F(2000) = 2040$.
Also, $S(50, 2000, 40) = 5204240$.

Find the last $9$ digits of $S(21^7, 7^{21}, 12^7)$.

This question appears to be coming from the Project Euler Plus problem number 340 on HackerRank.

The solution for this problem requires using an iterative process to solve for F(n). We know that F(n) = n – c when n > b.

When n ≤ b, F(n) is a complex function. For this case, you must break the function down. This can begin with manipulating this function so that it can be rewritten as:
F(n) = F(a + (a + c) + F(a + (n – a -c))).

Now, evaluate the recursive relation stuff inside:

1. Just denote m = (n – a – c), so that we can express the equation as F(n) = F(a + (a + c) + F(a + m))

2. If m ≤ b, then F(a + m) = a + m – c

If m > b, then F(a + m) = a + m

Therefore:

1. If m ≤ (b + c – a) = k, then F(n) = a + a + c – c + a + m – c = 3a + m

2. If m > k, then F(n) = a + a + c + a + m = 3a + c + m

We want to find (for 0 ≤ n ≤ b),

S = ΣF(n) = Σ (3a + min(n, k)) = 3ab + Σ min(n, k)

But this sum Σ min(n, k) is simply the sum of all the integers from 0 to k (for each n from 0 to k, min(n, k) = n), plus k for each n from k+1 to b (for each n in this range, min(n, k) = k). So this sum is (k/2) * (k+1) if k is even, or ((k+1)/2) * k if k is odd, plus k * (b – k) if b > k (or zero otherwise).

Let’s denote these equations as follows:
h(k) = (k/2) * (k+1) if k is even
h(k) = ((k+1)/2) * k if k is odd
h(k) = b * k – k * (k + 1) / 2 for k >= b

so,

S = 3ab + h(min(b, k))

As for the specific numbers given in the problem, they are far too big to calculate this directly, but we only need the solution modulo 1e9, so it will simplify things greatly if we reduce each addend mod 1e9 before adding them together.

So, we just need to do these calculations while taking everything modulo 1e9, take a + b + h(min(b, k)) where a = 21^7, b = 7^21, c = 12^7 and k = b + c – a.

Finally, using Python programming language we can get the answer:

“`python
a = pow(21, 7, 10**9)
b = pow(7, 21, 10**9)
c = pow(12, 7, 10**9)
k = (b+c-a) % (10**9)
h = (min(b,k)*(min(b,k)+1)//2)
S = (3*a*b+h) % (10**9)
print(S)
“`

This will print out the last 9 digits of S(21^7, 7^21, 12^7). Remember, the “//” operator in Python performs an integer (floor) division, discarding any fractional part, and “%” performs modulus operation.

Please run this code in a Python environment, as I currently cannot execute it in this text-based platform.

More Answers: