1
$\begingroup$

I'm trying to speed up the following code:

 sum = 0 for (k = 1 ... N) {   f = Fibonacci(k);   for (a = 1 ... 24)     for (b = 1 ... 24)       for (c = 1 ... 24) {         sum = sum + m(a, b, c) // m(a, b, c) <= 24 for all input           * ((f - c) / 24) * ((f - b) / 24) * ((f - a) / 24);       } } 

So I have $\sum_k\sum_a\sum_b\sum_cM_{a, b, c}\Bigg\lfloor\frac{F_k - a}{24}\Bigg\rfloor\Bigg\lfloor\frac{F_k - b}{24}\Bigg\rfloor\Bigg\lfloor\frac{F_k - c}{24}\Bigg\rfloor$

So then I push the summation over $k$ in and apply $\lfloor x / y\rfloor = \frac{x - (x \text{ mod } y)}{y}$ to get

$\sum_a\sum_b\sum_cM_{a, b, c}\left(\sum_k\Bigg\lfloor\frac{F_k - a}{24}\Bigg\rfloor\Bigg\lfloor\frac{F_k - b}{24}\Bigg\rfloor\Bigg\lfloor\frac{F_k - c}{24}\Bigg\rfloor\right)$

$\frac{1}{24^3}\sum_a\sum_b\sum_cM_{a, b, c}\sum_k(F_k - c - (F_k - c \text{ mod } 24))\times(F_k - b - (F_k - b \text{ mod } 24)) \times (F_k - a - (F_k - a \text{ mod } 24)) $

Actually that's about as far as I get. Typing this up helped me find a mistake in a simplification I thought I could make earlier. Can't seem to simplify this further. If it helps at all everything is also mod 1e9.

0 Answers 0