mersenneforum.org April 2022
 Register FAQ Search Today's Posts Mark Forums Read

 2022-04-02, 12:24 #1 Xyzzy     Aug 2002 32×23×41 Posts April 2022
 2022-04-04, 01:44 #2 Kebbaj     "Kebbaj Reda" May 2018 Casablanca, Morocco 6316 Posts For trying n=4 I get this optimal solution: x = [0.825694, -0.0756939 , -0.5 , -0.25] y = [-0.0756939, -0.25, -0.5 , 0.825694] f(x,y)= 6.74306 Can anyone confirm if there is other optimal results for n=4 ? Last fiddled with by Kebbaj on 2022-04-04 at 02:09
2022-04-04, 02:20   #3
uau

Jan 2017

2258 Posts

Quote:
 Originally Posted by Kebbaj I get this optimal solution:
Why do you call that "optimal"? It does not meet the criterion.

2022-04-04, 02:38   #4
Kebbaj

"Kebbaj Reda"
May 2018
Casablanca, Morocco

32×11 Posts

Quote:
 Originally Posted by uau Why do you call that "optimal"? It does not meet the criterion.
Whos criterion you want to say? f(x,y)=4.?
Precisely for n=4, it seems to me that f has the optimum at 6.74. Am I wrong or I don't understand well the question?

Last fiddled with by Kebbaj on 2022-04-04 at 03:01

2022-04-04, 03:27   #5
uau

Jan 2017

14910 Posts

Quote:
 Originally Posted by Kebbaj Whos criterion you want to say? f(x,y)=4.? Precisely for n=4, it seems to me that f has the optimum at 6.74. Am I wrong or I don't understand well the question?
You're wrong.

2022-04-04, 07:55   #6
tgan

Jul 2015

1000012 Posts

Quote:
 Originally Posted by Kebbaj Whos criterion you want to say? f(x,y)=4.? Precisely for n=4, it seems to me that f has the optimum at 6.74. Am I wrong or I don't understand well the question?
Reda i checked your Solution for n = 4 and getting the same results as you.
i did not search for optimal just checked that per my understanding it meets the constraints and calculate f(x,y)

Last fiddled with by tgan on 2022-04-04 at 07:58 Reason: fix the logic

 2022-05-29, 12:16 #7 Dieter   Oct 2017 2×32×7 Posts April 2022 Did anyone else find the excellent solution of Anders Kaseorg? How do you find something like that?
 2022-06-04, 19:54 #8 uau   Jan 2017 149 Posts Note that you can permute the order of x_i arbitrarily if you also permute y_i the same way. Take the example solution given in the problem statement and order the x_i in ascending order: x = [-0.3688259, -0.36163773, -0.3562014, 0.45420977, 0.63245526] y = [-0.05259805, -0.04540969, -0.03997346, 0.77043701, -0.6324558] Note that the last element in each is about the negative of the other. Also, y-x = [ 0.31622785, 0.31622804, 0.31622794, 0.31622724, -1.26491106] except for the last element, y is about x plus a constant. Now if we assume these features (except for last, y_i = x_i + c; y_last = -x_last) hold for solutions, what do they imply together with the general problem requirements? The general problem requirements say x.x=1, y.y=1, sum(x)=0, sum(y)=0, x.y=0. Since sum(x)=sum(y)=0, the changes to last and other elements from x to y must also sum to 0. c*(n-1) - 2*x_last = 0. So c = x_last * 2/(n-1). (In the example case, 0.316 = 0.632 * 2/4). sum(x)=0 implies x.[c,c,c,c,c]=0. Thus x.(x+c)=x.x=1. y=x+c except for last element, and x.y must be 0. Thus changing the last element from x_last+c=x_last*(n+1)/(n-1) to -x_last must change the dot product from 1 to 0. Thus x_last*x_last*(n+1)/(n-1) = x_last*(-x_last)+1, and x_last = sqrt((n-1)/(2n)). (In the example, 0.632 = sqrt(4/10)). So this limits the values of n for which such rational solutions can exist to those for which (n-1)/(2n) is a square. Up to a million such values are 1, 2, 9, 50, 289, 1682, 9801, 57122, 332929. It turns out that these are actually sufficient requirements to make a solution optimal. ANY x which fulfills sum(x)=0, x.x=1, x_last=sqrt(n-1)/(2n)) gives a solution by setting y=x+c except y_last. To find an optimal solution of say length 50, it's now enough to find a vector of length 50 which fulfills these conditions: sum(x)=0 x_last = sqrt(49/100) = 7/10 x.x = 1 (7/10)^2 = 49/100, so we need to fill the remaining elements of x with values that have these properties: they sum to -7/10, and their squares sum to 51/100. We'll just take -7/10, which leaves sum 0 and square-sum 2/100, and then add -1/10 and 1/10 which doesn't alter sum and fills square sum. (The published solution from Anders Kaseorg is one special case of constructing some values that have the required sum and sum of squares, but there are lots of other possibilities.) So now we have x=[-7/10, -1/10, 1/10, 0, 0, ..., 7/10] and y=x+c, where c=x_last * 2/(n-1)=7/245, except last element. y = [-7/10+7/245, -1/10+7/245, 1/10+7/245, 7/245, 7/245, ..., -7/10] You can verify that these give a rational solution of length 50, which is valid (x.x=y.y=1, sum(x)=sum(y)=0, x.y=0), and fulfills the optimality condition f(x,y)=4.

 Similar Threads Thread Thread Starter Forum Replies Last Post gd_barnes Conjectures 'R Us 5 2022-07-18 04:01 tgan Puzzles 21 2022-03-23 21:59 Xyzzy Puzzles 7 2022-03-21 10:45 Xyzzy Puzzles 25 2022-02-14 01:08

All times are UTC. The time now is 02:40.

Thu Aug 18 02:40:15 UTC 2022 up 8 mins, 0 users, load averages: 0.98, 0.92, 0.51