8
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ 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. \$\endgroup\$
    – Tbw
    Mar 9 at 21:23
  • \$\begingroup\$ Can output be in complex numbers? \$\endgroup\$
    – Tbw
    Mar 9 at 21:37
  • \$\begingroup\$ @Tbw No, sorry, \$\endgroup\$
    – Simd
    Mar 9 at 21:37
  • 1
    \$\begingroup\$ @KaiBurghardt yes that's ok \$\endgroup\$
    – Simd
    Mar 9 at 22:53
  • 4
    \$\begingroup\$ @Simd what is the rationale for not allowing complex representation? \$\endgroup\$
    – Jonah
    Mar 9 at 23:54

10 Answers 10

9
\$\begingroup\$

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.

\$\endgroup\$
4
  • 3
    \$\begingroup\$ Proof Request.. \$\endgroup\$
    – l4m2
    Mar 10 at 2:59
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Tbw
    Mar 10 at 3:16
  • 5
    \$\begingroup\$ 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. \$\endgroup\$
    – Tbw
    Mar 10 at 3:39
  • \$\begingroup\$ 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:] \$\endgroup\$ Mar 10 at 17:36
5
\$\begingroup\$

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)
              Ḣ - head
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Simd
    Mar 9 at 22:39
  • 1
    \$\begingroup\$ @Simd 22 seems to be the first counterexample. \$\endgroup\$
    – Neil
    Mar 10 at 0:34
  • \$\begingroup\$ Oh well, that's a shame. \$\endgroup\$
    – Simd
    Mar 10 at 7:50
5
\$\begingroup\$

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)
\$\endgroup\$
5
\$\begingroup\$

Uiua 0.10.0, 30 bytes SBCS (updated)

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

Old solution, 32 bytes, faster

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

Try on Uiua Pad!

⇡+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.

\$\endgroup\$
2
\$\begingroup\$

Haskell, 98 bytes

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!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 54 43 bytes

≔⊕NθIΦ⌈EΦE…Xθ³Xθ⁴↨ιθ⁼¹↨E⪪X鲦²Σλ±¹⮌⊞OιΣXι²κ

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.

≔⊕Nθ

Input n and increment it.

E…Xθ³Xθ⁴↨ιθ

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.

Φ...⁼¹↨E⪪X鲦²Σλ±¹

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

E...⮌⊞OιΣXι²

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

IΦ⌈...κ

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

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
5
  • \$\begingroup\$ 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? \$\endgroup\$
    – Simd
    Mar 9 at 22:14
  • \$\begingroup\$ Ah no that's a bug. That gives a difference of 0 which is not allowed \$\endgroup\$
    – Simd
    Mar 9 at 22:16
  • \$\begingroup\$ Not really a bug, but rather a floating point rounding error. \$\endgroup\$
    – Arnauld
    Mar 9 at 22:19
  • \$\begingroup\$ So Math.hypot is less accurate than manual square roots? That seems suboptimal. \$\endgroup\$
    – Neil
    Mar 10 at 7:40
  • 1
    \$\begingroup\$ @Neil It depends on the implementation. Both functions give the same results on Firefox. \$\endgroup\$
    – Arnauld
    Mar 10 at 8:06
2
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ 60 bytes (: \$\endgroup\$
    – att
    Mar 11 at 9:33
2
\$\begingroup\$

Wolfram Language (Mathematica), 132 96 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]]]
\$\endgroup\$
6
  • \$\begingroup\$ The outputs are not correct. Check you get the same answer for n=7 as in the question. \$\endgroup\$
    – Simd
    Mar 10 at 13:59
  • \$\begingroup\$ @Simd Thanks, I have corrected the code. \$\endgroup\$
    – 138 Aspen
    Mar 10 at 14:06
  • \$\begingroup\$ I am afraid it is still largely wrong. Look at the answer you should get from tio.run/##ASoA1f9qZWxsef//… . \$\endgroup\$
    – Simd
    Mar 10 at 14:09
  • \$\begingroup\$ @Simd Sorry, now the correction is done. \$\endgroup\$
    – 138 Aspen
    Mar 10 at 14:18
  • \$\begingroup\$ Same idea, but 96 bytes \$\endgroup\$
    – lesobrod
    Mar 11 at 7:21
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.