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)) 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: