# Give two points with the most similar distances to the origin

Consider an $$\(n+1) \times (n+1) \$$ grid of points places at non-negative integer coordinates. Given two points in the grid at $$\(a, b)\$$ and $$\(c, d)\$$, we know that the distance of the first point to the origin at $$\(0, 0)\$$ is $$\x = \sqrt{a^2 + b^2}\$$ and the distance of the second point to the origin is $$\y = \sqrt{c^2 + d^2}\$$.

Given a positive integer $$\n\$$, the task is to find non-negative integers $$\0 \leq a, b, c, d \leq n \$$ so that $$\|x - y|\$$ is as small as possible but not equal to zero.

# Input

Positive integer $$\n\$$

# Output

Two points $$\(a, b)\$$ and $$\(c, d)\$$ that minimize $$\ |\sqrt{a^2 + b^2} - \sqrt{c^2 + d^2}|\$$ under the constraint that $$\ |\sqrt{a^2 + b^2} - \sqrt{c^2 + d^2}| \ne 0\$$.

# Example

If $$\n=7\$$ then $$\(7, 2)\$$, $$\(4, 6)\$$ is a valid output.

• What is the range of coordinates for the points in terms of n? If it's 0 to n then it's an n+1 grid.
– Tbw
Mar 9 at 21:23
• Can output be in complex numbers?
– Tbw
Mar 9 at 21:37
• @Tbw No, sorry,
– Simd
Mar 9 at 21:37
• @KaiBurghardt yes that's ok
– Simd
Mar 9 at 22:53
• @Simd what is the rationale for not allowing complex representation? Mar 9 at 23:54

# Python, 114 bytes

-1 byte thanks to @Stefan Pochmann

lambda s:[r:=range(s+1)]*0+max([(e:=a*a+b*b)-c*c-d*d==1,e,a,b,c,d]for a in r for b in r for c in r for d in r)[2:]


Attempt This Online!

Finds $$\a, b, c, d\$$ where $$\(a^2+b^2)-(c^2+d^2)=1\$$ and $$\a^2+b^2\$$ is maximal.

## Proof

The lower bound on difference between distances when $$\(a^2+b^2)-(c^2+d^2)>1\$$ is $$\sqrt{n^2+n^2}-\sqrt{n^2+n^2-2}$$ $$\sqrt{2n^2}-\sqrt{2n^2-2}$$ We can show points $$\(n, 1)\$$ and $$\(n, 0)\$$ always have distances closer than this lower bound with some simplification $$\sqrt{n^2+1^2}-\sqrt{n^2-0^2}<\sqrt{2n^2}-\sqrt{2n^2-2}$$ $$\sqrt{n^2+1}-\sqrt{n^2}<\sqrt{2}\cdot(\sqrt{n^2}-\sqrt{n^2-1})$$ $$\sqrt{n^2+1}-\sqrt{n^2}<\sqrt{n^2}-\sqrt{n^2-1}$$ The last statement is easy to see as $$\\sqrt{x}\$$ increases more slowly the further right in the $$\x\$$-axis we go, more formally the second derivative (change in slope) of $$\\sqrt{x}\$$ is always negative.

This means in the solution $$\(a^2+b^2)-(c^2+d^2)=1\$$ will always hold. Maximizing $$\a^2+b^2\$$ is also easy to see and also arises due the second derivatives of $$\\sqrt{x}\$$ being always negative.

• Proof Request..
– l4m2
Mar 10 at 2:59
• Checking with my code, it seems to be true for n up to 500. I'll probably work out a proof if I make a new answer with this idea.
– Tbw
Mar 10 at 3:16
• Ok I don't feel like typing it all out formally so I'll put the gist in this comment. a^2 + b^2 and c^2 + d^2 are both at most 2n^2. If they differ by at least 2, then their roots differ by at least 1/(n*sqrt(2)) (by looking at the derivative of sqrt). The points (0,n) and (1,n) have distances that differ by sqrt(n^2+1)-n. Multiplying both expressions by n, we find that n*(sqrt(n^2+1)-n) is increasing and has limit 1/2 as n goes to infinity, never exceeding 1/sqrt(2). Therefore, a^2+b^2-c^2-d^2 must be 1. From there, it is obvious why a^2+b^2 is maximized.
– Tbw
Mar 10 at 3:39
• 114: lambda s:[r:=range(s+1)]*0+max([(e:=a*a+b*b)-c*c-d*d==1,e,a,b,c,d]for a in r for b in r for c in r for d in r)[2:] Mar 10 at 17:36

# Jelly, 15 bytes

ŻŒċ⁺µ²§½ạ/ȯ1µÞḢ


A monadic Link that accepts $$\N\$$ and yields a pair of pairs of integers.

Try it online!

### How?

Brute force, although I can't help but think some divisor-based logic could work.

ŻŒċ⁺µ²§½ạ/ȯ1µÞḢ - Link: positive integer, N
Ż               - zero-range {N} -> [0..N]
Œċ             - unordered pairs, with replacement -> points above or on y=x
⁺            - repeat -> all pairs of those points (up to reordering)
µ       µÞ  - sort these pairs of points by:
²          -   square all the values
§         -   sum each pair of squares
½        -   square-root these two values
ạ/      -   reduce by absolute difference
ȯ1    -   logical OR with 1 (replace zeros with ones)

• A non brute force solution would be awesome. It seems that one of the four variables is always n as well although that might need a proof.
– Simd
Mar 9 at 22:39
• @Simd 22 seems to be the first counterexample.
– Neil
Mar 10 at 0:34
• Oh well, that's a shame.
– Simd
Mar 10 at 7:50

# Vyxal 3, 14 bytes

z:Ẋ:Ẋⁿλ²Ṡ√/ȧ1∨


Try it Online!

Pretty much just the trivial solution. Uses Jonathan Allan's trick for avoiding returning zero values (well, this is just a port of Jonathan Allan's solution, but it's pretty much straightforward).

### Explanation

z:Ẋ:Ẋⁿλ²Ṡ√/ȧ1∨    Full Program
z                 0..x
:Ẋ               Cartesian Product with itself (gives a list of points)
:Ẋ             Cartesian Product with itself (gives a list of pairs)
ⁿλ           Minimum by lambda:
²          - Square (vectorized)
Ṡ         - Sum Each
√        - Square Root (vectorized)
/ȧ      - Reduce over Absolute Difference
1∨    - || 1 (if 0, replace with 1)


# Uiua 0.10.0, 30 bytes SBCS (updated)

⍉⊟°ℂ⊏⊢⍏∩▽,⟜±⌵≡/-⌵.☇1⊞⊂.♭⊞ℂ.⇡+1


## Old solution, 32 bytes, faster

⍉⊟°ℂ⊏+⇡2⊢⍏≡/-◫2⌵.⊏⍏⌵.▽◰⌵.♭⊞ℂ.⇡+1


⇡+1      # range 0...n
♭⊞ℂ.    # grid of complex values
▽◰⌵.   # remove duplicate lengths
⊏⍏⌵.    # sort by lengths
≡/-◫2⌵. # get differences between adjacent lengths
+⇡2⊢⍏    # get indices for smallest difference
⍉⊟°ℂ⊏   # pick and translate complex to points


The new solution is slower because it makes a list of every possible pair of points, but otherwise it does much of the same.

f n=tail$minimum[e:l|l@[a,b,c,d]<-mapM id$[0..n]<$"four",e<-[abs$sqrt(a^2+b^2)-sqrt(c^2+d^2)],e>0]


Try it online!

# Charcoal, 54 43 bytes

≔⊕ＮθＩΦ⌈ＥΦＥ…Ｘθ³Ｘθ⁴↨ιθ⁼¹↨Ｅ⪪Ｘι²¦²Σλ±¹⮌⊞ＯιΣＸι²κ


Try it online! Link is to verbose version of code. Explanation: Even more brute force than before, but still a port of @Mukandan314's Python answer.

≔⊕Ｎθ


Input n and increment it.

Ｅ…Ｘθ³Ｘθ⁴↨ιθ


Convert the range from (n+1)³ to (n+1)⁴ into base n+1 so the results all have four base-n+1 digits d, c, b and a.

Φ...⁼¹↨Ｅ⪪Ｘι²¦²Σλ±¹


Filter on those where a²+b²=c²+d²+1.

Ｅ...⮌⊞ＯιΣＸι²


For each of those, prefix a²+b²+c²+d² to a,b,c,d.

ＩΦ⌈...κ


Output the a,b,c,d with the maximum sum of squares.

# JavaScript (ES7), 108 bytes

Returns [a,b,c,d].

This is based on Mukundan314's method.

n=>eval(m="for(i=++n**4;i--;a*a+b*b+~(x=c*c+d*d)|x<m||(m=x,o=A))A=[a,b,c,d]=[1,0,3,2].map(j=>i/n**j%n|0);o")


Try it online!

• Assuming your code is correct, 1, 12, 8, 9 seems to be the answer for n between 12 and 50 at least! Can that be right?
– Simd
Mar 9 at 22:14
• Ah no that's a bug. That gives a difference of 0 which is not allowed
– Simd
Mar 9 at 22:16
• Not really a bug, but rather a floating point rounding error. Mar 9 at 22:19
• So Math.hypot is less accurate than manual square roots? That seems suboptimal.
– Neil
Mar 10 at 7:40
• @Neil It depends on the implementation. Both functions give the same results on Firefox. Mar 10 at 8:06

# Wolfram Language (Mathematica), 8260 bytes

-22 bytes thanks to @att!

MinimalBy[Range@#~Tuples~{2,2},N[r={1,-1}.Norm/@#]/Sign@r&]&


Significantly different approach from this answer, so separate post.
As is customary in Codegolf we don’t have to be efficient in performance or running time.
So here just brute-force selection from all possible tuples. So answer is also all possible combinations, eg for input 7 output is {{{2, 7}, {4, 6}}, {{2, 7}, {6, 4}}, {{4, 6}, {2, 7}}, {{4, 6}, {7, 2}}, {{6, 4}, {2, 7}}, {{6, 4}, {7, 2}}, {{7, 2}, {4, 6}}, {{7, 2}, {6, 4}}}

Try it online!

• 60 bytes (:
– att
Mar 11 at 9:33

# Wolfram Language (Mathematica), 13296 68 bytes

Saved 36 bytes thanks to @lesobrod, Saved 28 bytes thanks to @att

68 bytes version. Try it online!

ArgMin[{g=Abs[Norm@{x,y}-Norm@{z,}],g>0<=a<=#},a={x,y,z,},Integers]&


96 bytes version. Try it online!

ArgMin[{g=Abs[Norm@{x,y}-Norm@{z,}],g>0<=a<=#},a={x,y,z,},Integers]&


132 bytes version. Try it online!

f[n_]:=Module[{r=Minimize[{Sqrt[a*a+b*b]-Sqrt[c*c+d*d],0<=a<=n,0<=b<=n,0<=c<=n,0<=d<=n,a*a+b*b>c*c+d*d},{a,b,c,d},Integers]},r[[2]]]

• The outputs are not correct. Check you get the same answer for n=7 as in the question.
– Simd
Mar 10 at 13:59
• @Simd Thanks, I have corrected the code. Mar 10 at 14:06
• I am afraid it is still largely wrong. Look at the answer you should get from tio.run/##ASoA1f9qZWxsef//… .
– Simd
Mar 10 at 14:09
• @Simd Sorry, now the correction is done. Mar 10 at 14:18
• Same idea, but 96 bytes Mar 11 at 7:21

# JavaScript (Node.js), 100 bytes Mukundan314's method

n=>(m=g=(a,b,c,d)=>(a?g(a-1,b,c,d):1)/d?a*a+b*b+~(x=c*c+d*d)|x<m||(o=[a,b,c,d],m=x):g(n,a,b,c))()&&o


Try it online!

# JavaScript (Node.js), 113 bytes

n=>(m=g=(a,b,c,d)=>(a?g(a-1,b,c,d):1)/d?(v=(h=Math.hypot)(a,b)-h(c,d))>m|v<=0||(o=[a,b,c,d],m=v):g(n,a,b,c))()&&o


Try it online!

+1 byte like Arnauld's if some issue

n=>(
m=                     // Last Length
g=(a,b,c,d)=>
(a?g(a-1,b,c,d):1)   // g(a-1,b,c,d) would return a positive number
/d?                  // if d is number
(v=(h=Math.hypot)(a,b)-h(c,d))
// Compare length
>m|v<=0||          // Require it positive. Negative mean (c,d,a,b) is positive
(o=[a,b,c,d],m=v)  // Update
:g(n,a,b,c)          // Nest layer
)()&&o                   // Output