Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.