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











up vote
13
down vote

favorite
3












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)









share|improve this question




















  • 1




    lookup knapsack algorithm. Basically the hard part is to avoid to test x+y+z if you're sure they won't match n because too big.
    – Jean-François Fabre
    Dec 1 at 9:40










  • dynamic programming algorithm, involves computing partial sums, sorting results, and bisection algortithm to find the answer. The cosines are there to introduce some "randomness" in the results. Interesting "project euler" like problem
    – Jean-François Fabre
    Dec 1 at 9:50












  • I think you don't mean "simplify" but "make it run faster".
    – gnasher729
    Dec 1 at 15:24










  • What's the correct result for x, y and z?
    – iGian
    Dec 1 at 19:13










  • Presumably you mean three unique integers?
    – MSalters
    Dec 1 at 23:03















up vote
13
down vote

favorite
3












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)









share|improve this question




















  • 1




    lookup knapsack algorithm. Basically the hard part is to avoid to test x+y+z if you're sure they won't match n because too big.
    – Jean-François Fabre
    Dec 1 at 9:40










  • dynamic programming algorithm, involves computing partial sums, sorting results, and bisection algortithm to find the answer. The cosines are there to introduce some "randomness" in the results. Interesting "project euler" like problem
    – Jean-François Fabre
    Dec 1 at 9:50












  • I think you don't mean "simplify" but "make it run faster".
    – gnasher729
    Dec 1 at 15:24










  • What's the correct result for x, y and z?
    – iGian
    Dec 1 at 19:13










  • Presumably you mean three unique integers?
    – MSalters
    Dec 1 at 23:03













up vote
13
down vote

favorite
3









up vote
13
down vote

favorite
3






3





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)









share|improve this question















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)






python optimization numbers combinations






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Dec 1 at 11:28

























asked Dec 1 at 9:36









barbossa

1128




1128








  • 1




    lookup knapsack algorithm. Basically the hard part is to avoid to test x+y+z if you're sure they won't match n because too big.
    – Jean-François Fabre
    Dec 1 at 9:40










  • dynamic programming algorithm, involves computing partial sums, sorting results, and bisection algortithm to find the answer. The cosines are there to introduce some "randomness" in the results. Interesting "project euler" like problem
    – Jean-François Fabre
    Dec 1 at 9:50












  • I think you don't mean "simplify" but "make it run faster".
    – gnasher729
    Dec 1 at 15:24










  • What's the correct result for x, y and z?
    – iGian
    Dec 1 at 19:13










  • Presumably you mean three unique integers?
    – MSalters
    Dec 1 at 23:03














  • 1




    lookup knapsack algorithm. Basically the hard part is to avoid to test x+y+z if you're sure they won't match n because too big.
    – Jean-François Fabre
    Dec 1 at 9:40










  • dynamic programming algorithm, involves computing partial sums, sorting results, and bisection algortithm to find the answer. The cosines are there to introduce some "randomness" in the results. Interesting "project euler" like problem
    – Jean-François Fabre
    Dec 1 at 9:50












  • I think you don't mean "simplify" but "make it run faster".
    – gnasher729
    Dec 1 at 15:24










  • What's the correct result for x, y and z?
    – iGian
    Dec 1 at 19:13










  • Presumably you mean three unique integers?
    – MSalters
    Dec 1 at 23:03








1




1




lookup knapsack algorithm. Basically the hard part is to avoid to test x+y+z if you're sure they won't match n because too big.
– Jean-François Fabre
Dec 1 at 9:40




lookup knapsack algorithm. Basically the hard part is to avoid to test x+y+z if you're sure they won't match n because too big.
– Jean-François Fabre
Dec 1 at 9:40












dynamic programming algorithm, involves computing partial sums, sorting results, and bisection algortithm to find the answer. The cosines are there to introduce some "randomness" in the results. Interesting "project euler" like problem
– Jean-François Fabre
Dec 1 at 9:50






dynamic programming algorithm, involves computing partial sums, sorting results, and bisection algortithm to find the answer. The cosines are there to introduce some "randomness" in the results. Interesting "project euler" like problem
– Jean-François Fabre
Dec 1 at 9:50














I think you don't mean "simplify" but "make it run faster".
– gnasher729
Dec 1 at 15:24




I think you don't mean "simplify" but "make it run faster".
– gnasher729
Dec 1 at 15:24












What's the correct result for x, y and z?
– iGian
Dec 1 at 19:13




What's the correct result for x, y and z?
– iGian
Dec 1 at 19:13












Presumably you mean three unique integers?
– MSalters
Dec 1 at 23:03




Presumably you mean three unique integers?
– MSalters
Dec 1 at 23:03












5 Answers
5






active

oldest

votes

















up vote
5
down vote



accepted










Ideally, you want to calculate each possible combination only once. Ignoring the geometric properties of cos, and treating it as simply some mapping from number to number (e.g. using it as a random property, as @Jean mentioned in his second comment).

First, you must realize that after picking 2 numbers, the third is given. and you can pick 'smart' to avoid redundant picks:



from math import cos
import time
import numpy as np
from numba import jit



def calc(n):
x = 1
y = 1
z = 1
total = cos(x) + cos(y) + cos(z)
for x in range(n, int((n/3 - 1)),-1): #I only want to pick X from n-2 to n/3 -1 , after that we will repeat.
cosx = cos(x)
for y in range(max(int(((n-x)/2))-1,1),min(int(n-x),int(n/3))): #I would only pick number that will not be choosen for the z
z = n-x-y #Infer the z, taking the rest in account
temp = cosx + cos(y) + cos(z)
if temp > total: total = temp
return total

tic = time.clock()
total = calc(10000)
print(time.clock()-tic)

print (total)


Will take 1.3467099999999999 (on my machine).

And as @fuglede mentioned, it is worth using numba for further optimizing.



Edit:
Saving all the previously calculated cos values is actuallty more expensive then recalculating them, when you access np array you are not simply accessing a point in memory,but using an ndarray function. Using python built-in cos is actually faster:



import numpy as np

from math import cos
import time
import timeit

cos_arr = np.cos(np.arange(10000000))
tic = time.time()

def calc1():
total = 0
for j in range(100):
for i in range(10000000):
total += cos_arr[i]

def calc2():
total = 0
for j in range(100):
for i in range(10000000):
total += cos(i)

time1 = timeit.Timer(calc1).timeit(number=1)

time2 = timeit.Timer(calc2).timeit(number=1)
print(time1)
print(time2)


With output:



127.9849290860002
108.21062094399986


If i move the array creation inside the timer, its even slower.






share|improve this answer























  • Any answer that calls cos(x) more than once for each x deserves a downvote.
    – TonyK
    Dec 1 at 20:43












  • Python built-in cos is faster then np array access, so you are actually wrong. Added code to demonstrate it.
    – Dinari
    Dec 1 at 22:25










  • You don't need an array access. You just set cosx = cos(x)` after the first for-statement, and use that instead of cos(x). Try it and see.
    – TonyK
    Dec 1 at 22:59












  • Yes you are right, had some bias regarding what you meant, so gave the wrong meaning to your comment. I was aiming just to reduce the O, and both (re-evaluating and saving it) are both O(1), but you are correct, and its redundant, fixed it.
    – Dinari
    Dec 2 at 5:26












  • I am unable to reproduce the improvements you mention: Testing with N = 10^5 and using the IPython %timeit magic, looking up cos[a] in the inner loop rather than once outside is slightly faster. At the same time, not precomputing the values of cos makes the thing drastically slower: On my machine, with N = 10^4, the precomputed version takes 1.55s to execute whereas calculating them each time takes 16.4 ms, while calculating cos in the inner loop takes 388 ms. The ratio between the two grows with N. Your test case is probably two small to capture the benefits of lookups properly.
    – fuglede
    Dec 2 at 5:53




















up vote
12
down vote













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, and trying to avoid looking up the same values in rapid succession,

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





share|improve this answer






























    up vote
    3
    down vote













    There is absolutely no need to calculate 3 x n^3 cosine values.



    We can assume that x ≤ y ≤ z. Therefore x can be any integer in the range from 1 to n/3. y can be any integer in the range from x to (n - x) / 2. And z must be equal to n - x - y. This alone reduces the number of triples (x, y, z) that you try out from n^3 to about n^2 / 6.



    Next assume that you found three numbers with a total of 2.749. And you try an x with cosine (x) = 0.748. Any total involving this x cannot be more than 2.748, so you can reject x outright. Once you found one good sum, you can reject many values of x.



    To make this more effective, you sort the values x from highest to lowest value of cosine(x), because that makes it more likely you find a high total which allows you to remove more values.



    And calculating cos(x) is slow, so you store the values into a table.



    So:



    Set c[i] = cos (i) for 1 ≤ i ≤ n. 
    Set x[i] = integers 1 to n/3, sorted in descending order by value of c[i].
    Set (bestx, besty, bestz) = (1, 1, n-2) and total = c[bestx] + c [besty] + c [bestz].

    for x = elements of array x where c[x] + 2 ≥ bestTotal
    for y = x to (n-x)/2
    z = n - x - y
    total = c[x] + cy] + c[z]
    if total > bestTotal
    (bestx, besty, bestz) = (x, y, z)
    bestTotal = total


    You can improve on this with a bit of maths. If the sum of y + z is constant, like here where y + z = n - x, the sum of cos(y) + cos (z) is limited. Let P be the integer closest to (n - x) / 2pi, and let d = (n - x) - P * 2pi, then the largest possible sum of cos (y) + cos (z) is 2 * cos (d/2).



    So for every x, 1 ≤ x ≤ n/3, we calculate this value d and cos (x) + 2 * cos (d/2), store these values as the maximum total that can be achieved with some x, sort x so that these values will be in descending order, and ignore those x where the achievable total is less than the best total so far.



    If n is really large (say a billion), then you can use Euclid's algorithm to find all integers y that are close to 2k*pi + d quickly, but that will be a bit complicated.



    for x in 1 to n/3
    let s = n - x
    let P = s / 2pi, rounded to the nearest integer
    let d = (s - P * 2pi) / 2
    let maxSum [x] = cos(x) + 2*cos(d)

    Set x[i] = integers 1 to n/3, sorted in descending order by value of maxSum[i].
    Set (bestx, besty, bestz) = (1, 1, n-2)
    Set bestTotal = c[bestx] + c [besty] + c [bestz].

    for x = elements of array x where maxSum[x] ≥ bestTotal
    for y = x to (n-x)/2
    z = n - x - y
    total = c[x] + cy] + c[z]
    if total > bestTotal
    (bestx, besty, bestz) = (x, y, z)
    bestTotal = total


    PS. I actually tried this for some values of N around 100 million. It turns out, I can either sort the array to try the most promising values for x first, which takes a long time, but often the first value for x is the only one that gets tried. Or I can use x = 1, 2, 3 etc. which means a few dozens values for x will be tried, which is faster than sorting.






    share|improve this answer























    • " z must be equal to n - x - y.". True, but n is mostly unknown (it's only restricted to <1.000.000).
      – MSalters
      Dec 1 at 23:00


















    up vote
    1
    down vote













    No need to ever compute a cosine to answer this question. Just keep track of the three (two if n=0 is allowed) smallest values of function
    f(n) = abs(2pi*n-round(2pi*n))
    as n goes from 1 to N, where N is your upper limit of search.



    Cosine is 1 at multiples of 2*pi so we search for the two or three multiples closest to an integer within the search limit.



    Haven't run a program to do this yet, but it should be easy in any programming langauage. I will use Mathematica.






    share|improve this answer










    New contributor




    William Vaughn is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.

























      up vote
      -1
      down vote













      This is purely a basic trigonometry problem. The max value for your equation will be when all the cosine's each have a value of 1. In cos(n), where n is any number, for all the values formed by the set of n = 2 * pi * k, where k >= 0 and k is an integer; your cosine will have a value of 1. Your x, y, z values belong in this set and the permutation of these values will get you your desired value.
      Also, don't forget to check whether n in the set is an integer to reduce the sample space.






      share|improve this answer



















      • 2




        Such numbers would be irrational while all @barbossa's inputs are rational.
        – fuglede
        Dec 1 at 9:49










      • 0 is a rational number as far as I know, so the complexity of the problem is now reduced to O(1). I edited my answer.
        – S. Patel
        Dec 1 at 10:07








      • 1




        The inputs are assumed to be positive.
        – fuglede
        Dec 1 at 10:08










      • @S.Patel since x, y, and z are positive integers, there are no solutions for finite n which give you cosines of 1.
        – Sneftel
        Dec 1 at 14:43










      • Please read the question carefully. Let n = 3, then your only choice is x = y = z = 1, and the total is 3 * cos(1) ≈ 1.62. Let n = 5 and the best solution is x = y = 1, z = 3 with a total about 0.09.
        – gnasher729
        Dec 1 at 18:54













      Your Answer






      StackExchange.ifUsing("editor", function () {
      StackExchange.using("externalEditor", function () {
      StackExchange.using("snippets", function () {
      StackExchange.snippets.init();
      });
      });
      }, "code-snippets");

      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "1"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });














      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53569487%2ffinding-three-integers-such-that-their-sum-of-cosine-values-become-max%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      5 Answers
      5






      active

      oldest

      votes








      5 Answers
      5






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes








      up vote
      5
      down vote



      accepted










      Ideally, you want to calculate each possible combination only once. Ignoring the geometric properties of cos, and treating it as simply some mapping from number to number (e.g. using it as a random property, as @Jean mentioned in his second comment).

      First, you must realize that after picking 2 numbers, the third is given. and you can pick 'smart' to avoid redundant picks:



      from math import cos
      import time
      import numpy as np
      from numba import jit



      def calc(n):
      x = 1
      y = 1
      z = 1
      total = cos(x) + cos(y) + cos(z)
      for x in range(n, int((n/3 - 1)),-1): #I only want to pick X from n-2 to n/3 -1 , after that we will repeat.
      cosx = cos(x)
      for y in range(max(int(((n-x)/2))-1,1),min(int(n-x),int(n/3))): #I would only pick number that will not be choosen for the z
      z = n-x-y #Infer the z, taking the rest in account
      temp = cosx + cos(y) + cos(z)
      if temp > total: total = temp
      return total

      tic = time.clock()
      total = calc(10000)
      print(time.clock()-tic)

      print (total)


      Will take 1.3467099999999999 (on my machine).

      And as @fuglede mentioned, it is worth using numba for further optimizing.



      Edit:
      Saving all the previously calculated cos values is actuallty more expensive then recalculating them, when you access np array you are not simply accessing a point in memory,but using an ndarray function. Using python built-in cos is actually faster:



      import numpy as np

      from math import cos
      import time
      import timeit

      cos_arr = np.cos(np.arange(10000000))
      tic = time.time()

      def calc1():
      total = 0
      for j in range(100):
      for i in range(10000000):
      total += cos_arr[i]

      def calc2():
      total = 0
      for j in range(100):
      for i in range(10000000):
      total += cos(i)

      time1 = timeit.Timer(calc1).timeit(number=1)

      time2 = timeit.Timer(calc2).timeit(number=1)
      print(time1)
      print(time2)


      With output:



      127.9849290860002
      108.21062094399986


      If i move the array creation inside the timer, its even slower.






      share|improve this answer























      • Any answer that calls cos(x) more than once for each x deserves a downvote.
        – TonyK
        Dec 1 at 20:43












      • Python built-in cos is faster then np array access, so you are actually wrong. Added code to demonstrate it.
        – Dinari
        Dec 1 at 22:25










      • You don't need an array access. You just set cosx = cos(x)` after the first for-statement, and use that instead of cos(x). Try it and see.
        – TonyK
        Dec 1 at 22:59












      • Yes you are right, had some bias regarding what you meant, so gave the wrong meaning to your comment. I was aiming just to reduce the O, and both (re-evaluating and saving it) are both O(1), but you are correct, and its redundant, fixed it.
        – Dinari
        Dec 2 at 5:26












      • I am unable to reproduce the improvements you mention: Testing with N = 10^5 and using the IPython %timeit magic, looking up cos[a] in the inner loop rather than once outside is slightly faster. At the same time, not precomputing the values of cos makes the thing drastically slower: On my machine, with N = 10^4, the precomputed version takes 1.55s to execute whereas calculating them each time takes 16.4 ms, while calculating cos in the inner loop takes 388 ms. The ratio between the two grows with N. Your test case is probably two small to capture the benefits of lookups properly.
        – fuglede
        Dec 2 at 5:53

















      up vote
      5
      down vote



      accepted










      Ideally, you want to calculate each possible combination only once. Ignoring the geometric properties of cos, and treating it as simply some mapping from number to number (e.g. using it as a random property, as @Jean mentioned in his second comment).

      First, you must realize that after picking 2 numbers, the third is given. and you can pick 'smart' to avoid redundant picks:



      from math import cos
      import time
      import numpy as np
      from numba import jit



      def calc(n):
      x = 1
      y = 1
      z = 1
      total = cos(x) + cos(y) + cos(z)
      for x in range(n, int((n/3 - 1)),-1): #I only want to pick X from n-2 to n/3 -1 , after that we will repeat.
      cosx = cos(x)
      for y in range(max(int(((n-x)/2))-1,1),min(int(n-x),int(n/3))): #I would only pick number that will not be choosen for the z
      z = n-x-y #Infer the z, taking the rest in account
      temp = cosx + cos(y) + cos(z)
      if temp > total: total = temp
      return total

      tic = time.clock()
      total = calc(10000)
      print(time.clock()-tic)

      print (total)


      Will take 1.3467099999999999 (on my machine).

      And as @fuglede mentioned, it is worth using numba for further optimizing.



      Edit:
      Saving all the previously calculated cos values is actuallty more expensive then recalculating them, when you access np array you are not simply accessing a point in memory,but using an ndarray function. Using python built-in cos is actually faster:



      import numpy as np

      from math import cos
      import time
      import timeit

      cos_arr = np.cos(np.arange(10000000))
      tic = time.time()

      def calc1():
      total = 0
      for j in range(100):
      for i in range(10000000):
      total += cos_arr[i]

      def calc2():
      total = 0
      for j in range(100):
      for i in range(10000000):
      total += cos(i)

      time1 = timeit.Timer(calc1).timeit(number=1)

      time2 = timeit.Timer(calc2).timeit(number=1)
      print(time1)
      print(time2)


      With output:



      127.9849290860002
      108.21062094399986


      If i move the array creation inside the timer, its even slower.






      share|improve this answer























      • Any answer that calls cos(x) more than once for each x deserves a downvote.
        – TonyK
        Dec 1 at 20:43












      • Python built-in cos is faster then np array access, so you are actually wrong. Added code to demonstrate it.
        – Dinari
        Dec 1 at 22:25










      • You don't need an array access. You just set cosx = cos(x)` after the first for-statement, and use that instead of cos(x). Try it and see.
        – TonyK
        Dec 1 at 22:59












      • Yes you are right, had some bias regarding what you meant, so gave the wrong meaning to your comment. I was aiming just to reduce the O, and both (re-evaluating and saving it) are both O(1), but you are correct, and its redundant, fixed it.
        – Dinari
        Dec 2 at 5:26












      • I am unable to reproduce the improvements you mention: Testing with N = 10^5 and using the IPython %timeit magic, looking up cos[a] in the inner loop rather than once outside is slightly faster. At the same time, not precomputing the values of cos makes the thing drastically slower: On my machine, with N = 10^4, the precomputed version takes 1.55s to execute whereas calculating them each time takes 16.4 ms, while calculating cos in the inner loop takes 388 ms. The ratio between the two grows with N. Your test case is probably two small to capture the benefits of lookups properly.
        – fuglede
        Dec 2 at 5:53















      up vote
      5
      down vote



      accepted







      up vote
      5
      down vote



      accepted






      Ideally, you want to calculate each possible combination only once. Ignoring the geometric properties of cos, and treating it as simply some mapping from number to number (e.g. using it as a random property, as @Jean mentioned in his second comment).

      First, you must realize that after picking 2 numbers, the third is given. and you can pick 'smart' to avoid redundant picks:



      from math import cos
      import time
      import numpy as np
      from numba import jit



      def calc(n):
      x = 1
      y = 1
      z = 1
      total = cos(x) + cos(y) + cos(z)
      for x in range(n, int((n/3 - 1)),-1): #I only want to pick X from n-2 to n/3 -1 , after that we will repeat.
      cosx = cos(x)
      for y in range(max(int(((n-x)/2))-1,1),min(int(n-x),int(n/3))): #I would only pick number that will not be choosen for the z
      z = n-x-y #Infer the z, taking the rest in account
      temp = cosx + cos(y) + cos(z)
      if temp > total: total = temp
      return total

      tic = time.clock()
      total = calc(10000)
      print(time.clock()-tic)

      print (total)


      Will take 1.3467099999999999 (on my machine).

      And as @fuglede mentioned, it is worth using numba for further optimizing.



      Edit:
      Saving all the previously calculated cos values is actuallty more expensive then recalculating them, when you access np array you are not simply accessing a point in memory,but using an ndarray function. Using python built-in cos is actually faster:



      import numpy as np

      from math import cos
      import time
      import timeit

      cos_arr = np.cos(np.arange(10000000))
      tic = time.time()

      def calc1():
      total = 0
      for j in range(100):
      for i in range(10000000):
      total += cos_arr[i]

      def calc2():
      total = 0
      for j in range(100):
      for i in range(10000000):
      total += cos(i)

      time1 = timeit.Timer(calc1).timeit(number=1)

      time2 = timeit.Timer(calc2).timeit(number=1)
      print(time1)
      print(time2)


      With output:



      127.9849290860002
      108.21062094399986


      If i move the array creation inside the timer, its even slower.






      share|improve this answer














      Ideally, you want to calculate each possible combination only once. Ignoring the geometric properties of cos, and treating it as simply some mapping from number to number (e.g. using it as a random property, as @Jean mentioned in his second comment).

      First, you must realize that after picking 2 numbers, the third is given. and you can pick 'smart' to avoid redundant picks:



      from math import cos
      import time
      import numpy as np
      from numba import jit



      def calc(n):
      x = 1
      y = 1
      z = 1
      total = cos(x) + cos(y) + cos(z)
      for x in range(n, int((n/3 - 1)),-1): #I only want to pick X from n-2 to n/3 -1 , after that we will repeat.
      cosx = cos(x)
      for y in range(max(int(((n-x)/2))-1,1),min(int(n-x),int(n/3))): #I would only pick number that will not be choosen for the z
      z = n-x-y #Infer the z, taking the rest in account
      temp = cosx + cos(y) + cos(z)
      if temp > total: total = temp
      return total

      tic = time.clock()
      total = calc(10000)
      print(time.clock()-tic)

      print (total)


      Will take 1.3467099999999999 (on my machine).

      And as @fuglede mentioned, it is worth using numba for further optimizing.



      Edit:
      Saving all the previously calculated cos values is actuallty more expensive then recalculating them, when you access np array you are not simply accessing a point in memory,but using an ndarray function. Using python built-in cos is actually faster:



      import numpy as np

      from math import cos
      import time
      import timeit

      cos_arr = np.cos(np.arange(10000000))
      tic = time.time()

      def calc1():
      total = 0
      for j in range(100):
      for i in range(10000000):
      total += cos_arr[i]

      def calc2():
      total = 0
      for j in range(100):
      for i in range(10000000):
      total += cos(i)

      time1 = timeit.Timer(calc1).timeit(number=1)

      time2 = timeit.Timer(calc2).timeit(number=1)
      print(time1)
      print(time2)


      With output:



      127.9849290860002
      108.21062094399986


      If i move the array creation inside the timer, its even slower.







      share|improve this answer














      share|improve this answer



      share|improve this answer








      edited Dec 2 at 6:07

























      answered Dec 1 at 10:19









      Dinari

      1,275422




      1,275422












      • Any answer that calls cos(x) more than once for each x deserves a downvote.
        – TonyK
        Dec 1 at 20:43












      • Python built-in cos is faster then np array access, so you are actually wrong. Added code to demonstrate it.
        – Dinari
        Dec 1 at 22:25










      • You don't need an array access. You just set cosx = cos(x)` after the first for-statement, and use that instead of cos(x). Try it and see.
        – TonyK
        Dec 1 at 22:59












      • Yes you are right, had some bias regarding what you meant, so gave the wrong meaning to your comment. I was aiming just to reduce the O, and both (re-evaluating and saving it) are both O(1), but you are correct, and its redundant, fixed it.
        – Dinari
        Dec 2 at 5:26












      • I am unable to reproduce the improvements you mention: Testing with N = 10^5 and using the IPython %timeit magic, looking up cos[a] in the inner loop rather than once outside is slightly faster. At the same time, not precomputing the values of cos makes the thing drastically slower: On my machine, with N = 10^4, the precomputed version takes 1.55s to execute whereas calculating them each time takes 16.4 ms, while calculating cos in the inner loop takes 388 ms. The ratio between the two grows with N. Your test case is probably two small to capture the benefits of lookups properly.
        – fuglede
        Dec 2 at 5:53




















      • Any answer that calls cos(x) more than once for each x deserves a downvote.
        – TonyK
        Dec 1 at 20:43












      • Python built-in cos is faster then np array access, so you are actually wrong. Added code to demonstrate it.
        – Dinari
        Dec 1 at 22:25










      • You don't need an array access. You just set cosx = cos(x)` after the first for-statement, and use that instead of cos(x). Try it and see.
        – TonyK
        Dec 1 at 22:59












      • Yes you are right, had some bias regarding what you meant, so gave the wrong meaning to your comment. I was aiming just to reduce the O, and both (re-evaluating and saving it) are both O(1), but you are correct, and its redundant, fixed it.
        – Dinari
        Dec 2 at 5:26












      • I am unable to reproduce the improvements you mention: Testing with N = 10^5 and using the IPython %timeit magic, looking up cos[a] in the inner loop rather than once outside is slightly faster. At the same time, not precomputing the values of cos makes the thing drastically slower: On my machine, with N = 10^4, the precomputed version takes 1.55s to execute whereas calculating them each time takes 16.4 ms, while calculating cos in the inner loop takes 388 ms. The ratio between the two grows with N. Your test case is probably two small to capture the benefits of lookups properly.
        – fuglede
        Dec 2 at 5:53


















      Any answer that calls cos(x) more than once for each x deserves a downvote.
      – TonyK
      Dec 1 at 20:43






      Any answer that calls cos(x) more than once for each x deserves a downvote.
      – TonyK
      Dec 1 at 20:43














      Python built-in cos is faster then np array access, so you are actually wrong. Added code to demonstrate it.
      – Dinari
      Dec 1 at 22:25




      Python built-in cos is faster then np array access, so you are actually wrong. Added code to demonstrate it.
      – Dinari
      Dec 1 at 22:25












      You don't need an array access. You just set cosx = cos(x)` after the first for-statement, and use that instead of cos(x). Try it and see.
      – TonyK
      Dec 1 at 22:59






      You don't need an array access. You just set cosx = cos(x)` after the first for-statement, and use that instead of cos(x). Try it and see.
      – TonyK
      Dec 1 at 22:59














      Yes you are right, had some bias regarding what you meant, so gave the wrong meaning to your comment. I was aiming just to reduce the O, and both (re-evaluating and saving it) are both O(1), but you are correct, and its redundant, fixed it.
      – Dinari
      Dec 2 at 5:26






      Yes you are right, had some bias regarding what you meant, so gave the wrong meaning to your comment. I was aiming just to reduce the O, and both (re-evaluating and saving it) are both O(1), but you are correct, and its redundant, fixed it.
      – Dinari
      Dec 2 at 5:26














      I am unable to reproduce the improvements you mention: Testing with N = 10^5 and using the IPython %timeit magic, looking up cos[a] in the inner loop rather than once outside is slightly faster. At the same time, not precomputing the values of cos makes the thing drastically slower: On my machine, with N = 10^4, the precomputed version takes 1.55s to execute whereas calculating them each time takes 16.4 ms, while calculating cos in the inner loop takes 388 ms. The ratio between the two grows with N. Your test case is probably two small to capture the benefits of lookups properly.
      – fuglede
      Dec 2 at 5:53






      I am unable to reproduce the improvements you mention: Testing with N = 10^5 and using the IPython %timeit magic, looking up cos[a] in the inner loop rather than once outside is slightly faster. At the same time, not precomputing the values of cos makes the thing drastically slower: On my machine, with N = 10^4, the precomputed version takes 1.55s to execute whereas calculating them each time takes 16.4 ms, while calculating cos in the inner loop takes 388 ms. The ratio between the two grows with N. Your test case is probably two small to capture the benefits of lookups properly.
      – fuglede
      Dec 2 at 5:53














      up vote
      12
      down vote













      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, and trying to avoid looking up the same values in rapid succession,

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





      share|improve this answer



























        up vote
        12
        down vote













        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, and trying to avoid looking up the same values in rapid succession,

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





        share|improve this answer

























          up vote
          12
          down vote










          up vote
          12
          down vote









          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, and trying to avoid looking up the same values in rapid succession,

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





          share|improve this answer














          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, and trying to avoid looking up the same values in rapid succession,

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






          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited Dec 2 at 5:46

























          answered Dec 1 at 10:13









          fuglede

          6,47911239




          6,47911239






















              up vote
              3
              down vote













              There is absolutely no need to calculate 3 x n^3 cosine values.



              We can assume that x ≤ y ≤ z. Therefore x can be any integer in the range from 1 to n/3. y can be any integer in the range from x to (n - x) / 2. And z must be equal to n - x - y. This alone reduces the number of triples (x, y, z) that you try out from n^3 to about n^2 / 6.



              Next assume that you found three numbers with a total of 2.749. And you try an x with cosine (x) = 0.748. Any total involving this x cannot be more than 2.748, so you can reject x outright. Once you found one good sum, you can reject many values of x.



              To make this more effective, you sort the values x from highest to lowest value of cosine(x), because that makes it more likely you find a high total which allows you to remove more values.



              And calculating cos(x) is slow, so you store the values into a table.



              So:



              Set c[i] = cos (i) for 1 ≤ i ≤ n. 
              Set x[i] = integers 1 to n/3, sorted in descending order by value of c[i].
              Set (bestx, besty, bestz) = (1, 1, n-2) and total = c[bestx] + c [besty] + c [bestz].

              for x = elements of array x where c[x] + 2 ≥ bestTotal
              for y = x to (n-x)/2
              z = n - x - y
              total = c[x] + cy] + c[z]
              if total > bestTotal
              (bestx, besty, bestz) = (x, y, z)
              bestTotal = total


              You can improve on this with a bit of maths. If the sum of y + z is constant, like here where y + z = n - x, the sum of cos(y) + cos (z) is limited. Let P be the integer closest to (n - x) / 2pi, and let d = (n - x) - P * 2pi, then the largest possible sum of cos (y) + cos (z) is 2 * cos (d/2).



              So for every x, 1 ≤ x ≤ n/3, we calculate this value d and cos (x) + 2 * cos (d/2), store these values as the maximum total that can be achieved with some x, sort x so that these values will be in descending order, and ignore those x where the achievable total is less than the best total so far.



              If n is really large (say a billion), then you can use Euclid's algorithm to find all integers y that are close to 2k*pi + d quickly, but that will be a bit complicated.



              for x in 1 to n/3
              let s = n - x
              let P = s / 2pi, rounded to the nearest integer
              let d = (s - P * 2pi) / 2
              let maxSum [x] = cos(x) + 2*cos(d)

              Set x[i] = integers 1 to n/3, sorted in descending order by value of maxSum[i].
              Set (bestx, besty, bestz) = (1, 1, n-2)
              Set bestTotal = c[bestx] + c [besty] + c [bestz].

              for x = elements of array x where maxSum[x] ≥ bestTotal
              for y = x to (n-x)/2
              z = n - x - y
              total = c[x] + cy] + c[z]
              if total > bestTotal
              (bestx, besty, bestz) = (x, y, z)
              bestTotal = total


              PS. I actually tried this for some values of N around 100 million. It turns out, I can either sort the array to try the most promising values for x first, which takes a long time, but often the first value for x is the only one that gets tried. Or I can use x = 1, 2, 3 etc. which means a few dozens values for x will be tried, which is faster than sorting.






              share|improve this answer























              • " z must be equal to n - x - y.". True, but n is mostly unknown (it's only restricted to <1.000.000).
                – MSalters
                Dec 1 at 23:00















              up vote
              3
              down vote













              There is absolutely no need to calculate 3 x n^3 cosine values.



              We can assume that x ≤ y ≤ z. Therefore x can be any integer in the range from 1 to n/3. y can be any integer in the range from x to (n - x) / 2. And z must be equal to n - x - y. This alone reduces the number of triples (x, y, z) that you try out from n^3 to about n^2 / 6.



              Next assume that you found three numbers with a total of 2.749. And you try an x with cosine (x) = 0.748. Any total involving this x cannot be more than 2.748, so you can reject x outright. Once you found one good sum, you can reject many values of x.



              To make this more effective, you sort the values x from highest to lowest value of cosine(x), because that makes it more likely you find a high total which allows you to remove more values.



              And calculating cos(x) is slow, so you store the values into a table.



              So:



              Set c[i] = cos (i) for 1 ≤ i ≤ n. 
              Set x[i] = integers 1 to n/3, sorted in descending order by value of c[i].
              Set (bestx, besty, bestz) = (1, 1, n-2) and total = c[bestx] + c [besty] + c [bestz].

              for x = elements of array x where c[x] + 2 ≥ bestTotal
              for y = x to (n-x)/2
              z = n - x - y
              total = c[x] + cy] + c[z]
              if total > bestTotal
              (bestx, besty, bestz) = (x, y, z)
              bestTotal = total


              You can improve on this with a bit of maths. If the sum of y + z is constant, like here where y + z = n - x, the sum of cos(y) + cos (z) is limited. Let P be the integer closest to (n - x) / 2pi, and let d = (n - x) - P * 2pi, then the largest possible sum of cos (y) + cos (z) is 2 * cos (d/2).



              So for every x, 1 ≤ x ≤ n/3, we calculate this value d and cos (x) + 2 * cos (d/2), store these values as the maximum total that can be achieved with some x, sort x so that these values will be in descending order, and ignore those x where the achievable total is less than the best total so far.



              If n is really large (say a billion), then you can use Euclid's algorithm to find all integers y that are close to 2k*pi + d quickly, but that will be a bit complicated.



              for x in 1 to n/3
              let s = n - x
              let P = s / 2pi, rounded to the nearest integer
              let d = (s - P * 2pi) / 2
              let maxSum [x] = cos(x) + 2*cos(d)

              Set x[i] = integers 1 to n/3, sorted in descending order by value of maxSum[i].
              Set (bestx, besty, bestz) = (1, 1, n-2)
              Set bestTotal = c[bestx] + c [besty] + c [bestz].

              for x = elements of array x where maxSum[x] ≥ bestTotal
              for y = x to (n-x)/2
              z = n - x - y
              total = c[x] + cy] + c[z]
              if total > bestTotal
              (bestx, besty, bestz) = (x, y, z)
              bestTotal = total


              PS. I actually tried this for some values of N around 100 million. It turns out, I can either sort the array to try the most promising values for x first, which takes a long time, but often the first value for x is the only one that gets tried. Or I can use x = 1, 2, 3 etc. which means a few dozens values for x will be tried, which is faster than sorting.






              share|improve this answer























              • " z must be equal to n - x - y.". True, but n is mostly unknown (it's only restricted to <1.000.000).
                – MSalters
                Dec 1 at 23:00













              up vote
              3
              down vote










              up vote
              3
              down vote









              There is absolutely no need to calculate 3 x n^3 cosine values.



              We can assume that x ≤ y ≤ z. Therefore x can be any integer in the range from 1 to n/3. y can be any integer in the range from x to (n - x) / 2. And z must be equal to n - x - y. This alone reduces the number of triples (x, y, z) that you try out from n^3 to about n^2 / 6.



              Next assume that you found three numbers with a total of 2.749. And you try an x with cosine (x) = 0.748. Any total involving this x cannot be more than 2.748, so you can reject x outright. Once you found one good sum, you can reject many values of x.



              To make this more effective, you sort the values x from highest to lowest value of cosine(x), because that makes it more likely you find a high total which allows you to remove more values.



              And calculating cos(x) is slow, so you store the values into a table.



              So:



              Set c[i] = cos (i) for 1 ≤ i ≤ n. 
              Set x[i] = integers 1 to n/3, sorted in descending order by value of c[i].
              Set (bestx, besty, bestz) = (1, 1, n-2) and total = c[bestx] + c [besty] + c [bestz].

              for x = elements of array x where c[x] + 2 ≥ bestTotal
              for y = x to (n-x)/2
              z = n - x - y
              total = c[x] + cy] + c[z]
              if total > bestTotal
              (bestx, besty, bestz) = (x, y, z)
              bestTotal = total


              You can improve on this with a bit of maths. If the sum of y + z is constant, like here where y + z = n - x, the sum of cos(y) + cos (z) is limited. Let P be the integer closest to (n - x) / 2pi, and let d = (n - x) - P * 2pi, then the largest possible sum of cos (y) + cos (z) is 2 * cos (d/2).



              So for every x, 1 ≤ x ≤ n/3, we calculate this value d and cos (x) + 2 * cos (d/2), store these values as the maximum total that can be achieved with some x, sort x so that these values will be in descending order, and ignore those x where the achievable total is less than the best total so far.



              If n is really large (say a billion), then you can use Euclid's algorithm to find all integers y that are close to 2k*pi + d quickly, but that will be a bit complicated.



              for x in 1 to n/3
              let s = n - x
              let P = s / 2pi, rounded to the nearest integer
              let d = (s - P * 2pi) / 2
              let maxSum [x] = cos(x) + 2*cos(d)

              Set x[i] = integers 1 to n/3, sorted in descending order by value of maxSum[i].
              Set (bestx, besty, bestz) = (1, 1, n-2)
              Set bestTotal = c[bestx] + c [besty] + c [bestz].

              for x = elements of array x where maxSum[x] ≥ bestTotal
              for y = x to (n-x)/2
              z = n - x - y
              total = c[x] + cy] + c[z]
              if total > bestTotal
              (bestx, besty, bestz) = (x, y, z)
              bestTotal = total


              PS. I actually tried this for some values of N around 100 million. It turns out, I can either sort the array to try the most promising values for x first, which takes a long time, but often the first value for x is the only one that gets tried. Or I can use x = 1, 2, 3 etc. which means a few dozens values for x will be tried, which is faster than sorting.






              share|improve this answer














              There is absolutely no need to calculate 3 x n^3 cosine values.



              We can assume that x ≤ y ≤ z. Therefore x can be any integer in the range from 1 to n/3. y can be any integer in the range from x to (n - x) / 2. And z must be equal to n - x - y. This alone reduces the number of triples (x, y, z) that you try out from n^3 to about n^2 / 6.



              Next assume that you found three numbers with a total of 2.749. And you try an x with cosine (x) = 0.748. Any total involving this x cannot be more than 2.748, so you can reject x outright. Once you found one good sum, you can reject many values of x.



              To make this more effective, you sort the values x from highest to lowest value of cosine(x), because that makes it more likely you find a high total which allows you to remove more values.



              And calculating cos(x) is slow, so you store the values into a table.



              So:



              Set c[i] = cos (i) for 1 ≤ i ≤ n. 
              Set x[i] = integers 1 to n/3, sorted in descending order by value of c[i].
              Set (bestx, besty, bestz) = (1, 1, n-2) and total = c[bestx] + c [besty] + c [bestz].

              for x = elements of array x where c[x] + 2 ≥ bestTotal
              for y = x to (n-x)/2
              z = n - x - y
              total = c[x] + cy] + c[z]
              if total > bestTotal
              (bestx, besty, bestz) = (x, y, z)
              bestTotal = total


              You can improve on this with a bit of maths. If the sum of y + z is constant, like here where y + z = n - x, the sum of cos(y) + cos (z) is limited. Let P be the integer closest to (n - x) / 2pi, and let d = (n - x) - P * 2pi, then the largest possible sum of cos (y) + cos (z) is 2 * cos (d/2).



              So for every x, 1 ≤ x ≤ n/3, we calculate this value d and cos (x) + 2 * cos (d/2), store these values as the maximum total that can be achieved with some x, sort x so that these values will be in descending order, and ignore those x where the achievable total is less than the best total so far.



              If n is really large (say a billion), then you can use Euclid's algorithm to find all integers y that are close to 2k*pi + d quickly, but that will be a bit complicated.



              for x in 1 to n/3
              let s = n - x
              let P = s / 2pi, rounded to the nearest integer
              let d = (s - P * 2pi) / 2
              let maxSum [x] = cos(x) + 2*cos(d)

              Set x[i] = integers 1 to n/3, sorted in descending order by value of maxSum[i].
              Set (bestx, besty, bestz) = (1, 1, n-2)
              Set bestTotal = c[bestx] + c [besty] + c [bestz].

              for x = elements of array x where maxSum[x] ≥ bestTotal
              for y = x to (n-x)/2
              z = n - x - y
              total = c[x] + cy] + c[z]
              if total > bestTotal
              (bestx, besty, bestz) = (x, y, z)
              bestTotal = total


              PS. I actually tried this for some values of N around 100 million. It turns out, I can either sort the array to try the most promising values for x first, which takes a long time, but often the first value for x is the only one that gets tried. Or I can use x = 1, 2, 3 etc. which means a few dozens values for x will be tried, which is faster than sorting.







              share|improve this answer














              share|improve this answer



              share|improve this answer








              edited Dec 1 at 18:46

























              answered Dec 1 at 15:21









              gnasher729

              41.2k44676




              41.2k44676












              • " z must be equal to n - x - y.". True, but n is mostly unknown (it's only restricted to <1.000.000).
                – MSalters
                Dec 1 at 23:00


















              • " z must be equal to n - x - y.". True, but n is mostly unknown (it's only restricted to <1.000.000).
                – MSalters
                Dec 1 at 23:00
















              " z must be equal to n - x - y.". True, but n is mostly unknown (it's only restricted to <1.000.000).
              – MSalters
              Dec 1 at 23:00




              " z must be equal to n - x - y.". True, but n is mostly unknown (it's only restricted to <1.000.000).
              – MSalters
              Dec 1 at 23:00










              up vote
              1
              down vote













              No need to ever compute a cosine to answer this question. Just keep track of the three (two if n=0 is allowed) smallest values of function
              f(n) = abs(2pi*n-round(2pi*n))
              as n goes from 1 to N, where N is your upper limit of search.



              Cosine is 1 at multiples of 2*pi so we search for the two or three multiples closest to an integer within the search limit.



              Haven't run a program to do this yet, but it should be easy in any programming langauage. I will use Mathematica.






              share|improve this answer










              New contributor




              William Vaughn is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.






















                up vote
                1
                down vote













                No need to ever compute a cosine to answer this question. Just keep track of the three (two if n=0 is allowed) smallest values of function
                f(n) = abs(2pi*n-round(2pi*n))
                as n goes from 1 to N, where N is your upper limit of search.



                Cosine is 1 at multiples of 2*pi so we search for the two or three multiples closest to an integer within the search limit.



                Haven't run a program to do this yet, but it should be easy in any programming langauage. I will use Mathematica.






                share|improve this answer










                New contributor




                William Vaughn is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.




















                  up vote
                  1
                  down vote










                  up vote
                  1
                  down vote









                  No need to ever compute a cosine to answer this question. Just keep track of the three (two if n=0 is allowed) smallest values of function
                  f(n) = abs(2pi*n-round(2pi*n))
                  as n goes from 1 to N, where N is your upper limit of search.



                  Cosine is 1 at multiples of 2*pi so we search for the two or three multiples closest to an integer within the search limit.



                  Haven't run a program to do this yet, but it should be easy in any programming langauage. I will use Mathematica.






                  share|improve this answer










                  New contributor




                  William Vaughn is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.









                  No need to ever compute a cosine to answer this question. Just keep track of the three (two if n=0 is allowed) smallest values of function
                  f(n) = abs(2pi*n-round(2pi*n))
                  as n goes from 1 to N, where N is your upper limit of search.



                  Cosine is 1 at multiples of 2*pi so we search for the two or three multiples closest to an integer within the search limit.



                  Haven't run a program to do this yet, but it should be easy in any programming langauage. I will use Mathematica.







                  share|improve this answer










                  New contributor




                  William Vaughn is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.









                  share|improve this answer



                  share|improve this answer








                  edited Dec 6 at 12:50









                  Cosmic Ossifrage

                  2,0151115




                  2,0151115






                  New contributor




                  William Vaughn is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.









                  answered Dec 6 at 11:54









                  William Vaughn

                  111




                  111




                  New contributor




                  William Vaughn is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.





                  New contributor





                  William Vaughn is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.






                  William Vaughn is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.






















                      up vote
                      -1
                      down vote













                      This is purely a basic trigonometry problem. The max value for your equation will be when all the cosine's each have a value of 1. In cos(n), where n is any number, for all the values formed by the set of n = 2 * pi * k, where k >= 0 and k is an integer; your cosine will have a value of 1. Your x, y, z values belong in this set and the permutation of these values will get you your desired value.
                      Also, don't forget to check whether n in the set is an integer to reduce the sample space.






                      share|improve this answer



















                      • 2




                        Such numbers would be irrational while all @barbossa's inputs are rational.
                        – fuglede
                        Dec 1 at 9:49










                      • 0 is a rational number as far as I know, so the complexity of the problem is now reduced to O(1). I edited my answer.
                        – S. Patel
                        Dec 1 at 10:07








                      • 1




                        The inputs are assumed to be positive.
                        – fuglede
                        Dec 1 at 10:08










                      • @S.Patel since x, y, and z are positive integers, there are no solutions for finite n which give you cosines of 1.
                        – Sneftel
                        Dec 1 at 14:43










                      • Please read the question carefully. Let n = 3, then your only choice is x = y = z = 1, and the total is 3 * cos(1) ≈ 1.62. Let n = 5 and the best solution is x = y = 1, z = 3 with a total about 0.09.
                        – gnasher729
                        Dec 1 at 18:54

















                      up vote
                      -1
                      down vote













                      This is purely a basic trigonometry problem. The max value for your equation will be when all the cosine's each have a value of 1. In cos(n), where n is any number, for all the values formed by the set of n = 2 * pi * k, where k >= 0 and k is an integer; your cosine will have a value of 1. Your x, y, z values belong in this set and the permutation of these values will get you your desired value.
                      Also, don't forget to check whether n in the set is an integer to reduce the sample space.






                      share|improve this answer



















                      • 2




                        Such numbers would be irrational while all @barbossa's inputs are rational.
                        – fuglede
                        Dec 1 at 9:49










                      • 0 is a rational number as far as I know, so the complexity of the problem is now reduced to O(1). I edited my answer.
                        – S. Patel
                        Dec 1 at 10:07








                      • 1




                        The inputs are assumed to be positive.
                        – fuglede
                        Dec 1 at 10:08










                      • @S.Patel since x, y, and z are positive integers, there are no solutions for finite n which give you cosines of 1.
                        – Sneftel
                        Dec 1 at 14:43










                      • Please read the question carefully. Let n = 3, then your only choice is x = y = z = 1, and the total is 3 * cos(1) ≈ 1.62. Let n = 5 and the best solution is x = y = 1, z = 3 with a total about 0.09.
                        – gnasher729
                        Dec 1 at 18:54















                      up vote
                      -1
                      down vote










                      up vote
                      -1
                      down vote









                      This is purely a basic trigonometry problem. The max value for your equation will be when all the cosine's each have a value of 1. In cos(n), where n is any number, for all the values formed by the set of n = 2 * pi * k, where k >= 0 and k is an integer; your cosine will have a value of 1. Your x, y, z values belong in this set and the permutation of these values will get you your desired value.
                      Also, don't forget to check whether n in the set is an integer to reduce the sample space.






                      share|improve this answer














                      This is purely a basic trigonometry problem. The max value for your equation will be when all the cosine's each have a value of 1. In cos(n), where n is any number, for all the values formed by the set of n = 2 * pi * k, where k >= 0 and k is an integer; your cosine will have a value of 1. Your x, y, z values belong in this set and the permutation of these values will get you your desired value.
                      Also, don't forget to check whether n in the set is an integer to reduce the sample space.







                      share|improve this answer














                      share|improve this answer



                      share|improve this answer








                      edited Dec 1 at 10:00

























                      answered Dec 1 at 9:46









                      S. Patel

                      1579




                      1579








                      • 2




                        Such numbers would be irrational while all @barbossa's inputs are rational.
                        – fuglede
                        Dec 1 at 9:49










                      • 0 is a rational number as far as I know, so the complexity of the problem is now reduced to O(1). I edited my answer.
                        – S. Patel
                        Dec 1 at 10:07








                      • 1




                        The inputs are assumed to be positive.
                        – fuglede
                        Dec 1 at 10:08










                      • @S.Patel since x, y, and z are positive integers, there are no solutions for finite n which give you cosines of 1.
                        – Sneftel
                        Dec 1 at 14:43










                      • Please read the question carefully. Let n = 3, then your only choice is x = y = z = 1, and the total is 3 * cos(1) ≈ 1.62. Let n = 5 and the best solution is x = y = 1, z = 3 with a total about 0.09.
                        – gnasher729
                        Dec 1 at 18:54
















                      • 2




                        Such numbers would be irrational while all @barbossa's inputs are rational.
                        – fuglede
                        Dec 1 at 9:49










                      • 0 is a rational number as far as I know, so the complexity of the problem is now reduced to O(1). I edited my answer.
                        – S. Patel
                        Dec 1 at 10:07








                      • 1




                        The inputs are assumed to be positive.
                        – fuglede
                        Dec 1 at 10:08










                      • @S.Patel since x, y, and z are positive integers, there are no solutions for finite n which give you cosines of 1.
                        – Sneftel
                        Dec 1 at 14:43










                      • Please read the question carefully. Let n = 3, then your only choice is x = y = z = 1, and the total is 3 * cos(1) ≈ 1.62. Let n = 5 and the best solution is x = y = 1, z = 3 with a total about 0.09.
                        – gnasher729
                        Dec 1 at 18:54










                      2




                      2




                      Such numbers would be irrational while all @barbossa's inputs are rational.
                      – fuglede
                      Dec 1 at 9:49




                      Such numbers would be irrational while all @barbossa's inputs are rational.
                      – fuglede
                      Dec 1 at 9:49












                      0 is a rational number as far as I know, so the complexity of the problem is now reduced to O(1). I edited my answer.
                      – S. Patel
                      Dec 1 at 10:07






                      0 is a rational number as far as I know, so the complexity of the problem is now reduced to O(1). I edited my answer.
                      – S. Patel
                      Dec 1 at 10:07






                      1




                      1




                      The inputs are assumed to be positive.
                      – fuglede
                      Dec 1 at 10:08




                      The inputs are assumed to be positive.
                      – fuglede
                      Dec 1 at 10:08












                      @S.Patel since x, y, and z are positive integers, there are no solutions for finite n which give you cosines of 1.
                      – Sneftel
                      Dec 1 at 14:43




                      @S.Patel since x, y, and z are positive integers, there are no solutions for finite n which give you cosines of 1.
                      – Sneftel
                      Dec 1 at 14:43












                      Please read the question carefully. Let n = 3, then your only choice is x = y = z = 1, and the total is 3 * cos(1) ≈ 1.62. Let n = 5 and the best solution is x = y = 1, z = 3 with a total about 0.09.
                      – gnasher729
                      Dec 1 at 18:54






                      Please read the question carefully. Let n = 3, then your only choice is x = y = z = 1, and the total is 3 * cos(1) ≈ 1.62. Let n = 5 and the best solution is x = y = 1, z = 3 with a total about 0.09.
                      – gnasher729
                      Dec 1 at 18:54




















                      draft saved

                      draft discarded




















































                      Thanks for contributing an answer to Stack Overflow!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      To learn more, see our tips on writing great answers.





                      Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                      Please pay close attention to the following guidance:


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53569487%2ffinding-three-integers-such-that-their-sum-of-cosine-values-become-max%23new-answer', 'question_page');
                      }
                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      Сан-Квентин

                      Алькесар

                      Josef Freinademetz