# Finding three integers such that their sum of cosine values become max

• A+
Category：Languages

There are three integers `x`, `y` and `z` (each of them >= 1) and a given upper bound integer `n` < 10^6. Also, `n = x + y + z` and `output = cos(x) + cos(y) + cos(z)`.

The exercise is to maximize `output`.

I wrote a simple script for this, but the time complexity is O(n^3). Is there any way to simplify this?

``from math import cos  n = 50 x = 1 y = 1 z = 1  total = cos(x) + cos(y) + cos(z)  for x in xrange(n):     for y in xrange(n):         for z in xrange(n):             if x + y + z == n:                 temp = cos(x) + cos(y) + cos(z)                 if temp > total: total = temp  print round(total, 9)  ``

As pointed out by Jean-François Fabre in the comments, there are plenty of tricks you could apply to improve performance, but by first of all

• noting that the values of `a` and `b` determine the value of `c`,
• noting that at least one of the three variables, WLOG `a`, is less than or equal to `N/3`,
• using the remaining symmetry in `b` and `c` to bound `b` between 1 and `(N - a)//2 + 1`
• precomputing all relevant values of cos,
• using Numba to JIT-compile the code and get some performance for free (about a factor of 400 for `N = 500`),

then the otherwise bruteforcy solution terminates relatively quickly for `N = 1000000` (thus also for any given `N < 1000000`):

``import numpy as np from numba import jit  @jit def maximize(N):     cos = np.cos(np.arange(N))     m = -3     for a in range(1, N//3 + 1):         for b in range(1, (N - a)//2 + 1):             c = N - a - b             res = cos[a] + cos[b] + cos[c]             if res > m:                 m = res                 bestabc = (a, b, c)     return m, bestabc  maximize(1000000)  # (2.9787165245899025, (159775, 263768, 576457)) ``