IMO Question Six with a difference

In 1988, the International Mathematical Olympiad (IMO) featured this as its final question, Question Six:

Let $$\a\$$ and $$\b\$$ be positive integers such that $$\ab + 1\$$ divides $$\a^2 + b^2\$$. Show that $$\\frac{a^2 + b^2}{ab + 1}\$$ is the square of an integer.

This can be proven using a technique called Vieta jumping. The proof is by contradiction - if a pair did exist with an integer, non-square $$\N=\frac{a^2 + b^2}{ab + 1}\$$ then there would always be a pair with a smaller $$\a+b\$$ with both $$\a\$$ and $$\b\$$ positive integers, but such an infinite descent is not possible using only positive integers.

The "jumping" in this proof is between the two branches of the hyperbola $$\x^2+y^2-Sxy-S=0\$$ defined by $$\S\$$ (our square). These are symmetrical around $$\x=y\$$ and the implication is that if $$\(A,B)\$$ is a solution where $$\A\ge B\$$ then $$\(B,SB-A)\$$ is either $$\(\sqrt S,0)\$$ or it is another solution (with a smaller $$\A+B\$$). Similarly if $$\B\ge A\$$ then the jump is "down" to $$\(SA-B,A)\$$.

Challenge

Given a non-negative integer, $$\n\$$, determine whether a pair of positive integers $$\(a,b)\$$ with $$\n=|a-b|\$$ exists such that $$\ab+1\$$ divides $$\a^2+b^2\$$.

This is , so try to write the shortest code in bytes that your chosen language allows.

Your output just needs to differentiate between "valid" $$\n\$$ and "invalid" $$\n\$$, some possible ways include the below, feel free to ask if unsure:

• Two distinct, consistent values
• Truthy vs Falsey using your language's definition (either way around)
• A solution if valid vs something consistent and distinguishable if not
• Return code (if using this be sure that errors are not due to resource limits being hit - your program would still need to produce the expected error given infinite time/memory/precision/etc)

Valid inputs

Here are the $$\n\lt 10000\$$ which should be identified as being possible differences $$\|a-b|\$$:

0 6 22 24 60 82 120 210 213 306 336 504 720 956 990 1142 1320 1716 1893 2184 2730 2995 3360 4080 4262 4896 5814 6840 7554 7980 9240


For example $$\22\$$ is valid because $$\30\times 8+1\$$ divides $$\30^2+8^2\$$ and $$\|30-8| = 22\$$
...that is $$\(30, 8)\$$ and $$\(8, 30)\$$ are solutions to Question Six. The first jumps "down" to $$\(8, 2)\$$ then $$\(2, 0)\$$ while the second jumps "down" to $$\(2, 8)\$$ then $$\(0, 2)\$$.

Note: One implementation approach would be to ascend (jump the other way) from each of $$\(x, 0) | x \exists [1,n]\$$ until the difference is greater than $$\n\$$ (move to next $$\x\$$) or equal (found that $$\n\$$ is valid). Maybe there are other, superior methods though?

• Sep 14 at 18:07

Python, 49 bytes

f=lambda n,a=1:a>n+1or(n*n-2)%~(a*(a+n))*f(n,a+1)


Try it online!

Outputs Truthy/Falsey reversed.

Checks whether $$\frac{n^2-2}{a(a+n)+1}$$ is ever an integer for any $$\a\$$ with $$\1 \leq a \leq n+1\$$. This upper bound suffices because for $$\ a \geq n > 1 \$$, the denominator is larger than the numerator, and for $$\n=0\$$ we just need to get a positive on $$\a=1\$$.

JavaScript (ES6), 43 bytes

-4 bytes with the formula used in @xnor's answer

Returns either 0 (falsy) or a positive integer (truthy).

f=(n,a=n)=>(n*n-2)%~(a*(a+n))?f(n,a-1):a|!n


Try it online!

C (gcc), 50 bytes

a;f(n){for(a=0;a++<=n&&(n*n-2)%~(a*(a+n)););a-=n;}


Try it online!

Returns $$\2\$$ for invalid and an integer less than $$\2\$$ for valid.

Pyth, 18 bytes

lfsIc-*QQ2h*T+QTSh


Test suite

A naïve implementation of the algorithm layed out in @xnor's answer. I'll see if I can get a better score later.

R, 35 bytes

\(n,a=1:n)all(n^2%%(a*(a+n)+1)-2)&n


Attempt This Online!

Outputs reversed TRUE/FALSE.

Slight modification of @xnor's algorithm: checks whether $$n^2 = 2 \mod a(a+n)+1.$$ This needs handling $$\0\$$ as a special case (&n), so we may check $$\a\$$ only up to $$\n\$$.

Actually a direct port works for the same byte-count:

R, 35 bytes

\(n,a=1:n)all((n^2-2)%%(a*(a+n)+1))


Attempt This Online!

It's because for $$\n=0\$$ a=1:n becomes [1 0], so we actually check $$\a\$$ up to $$\n+1\$$ for $$\n=0\$$, and up to $$\n\$$ for $$\n>0\$$, which is sufficient.

PARI/GP, 33 bytes

n->n*prod(a=1,n,n^2%(1+a*a+=n)-2)


Attempt This Online!

A port of @pajonk's R port of @xnor's Python answer. Returns falsy when there is a solution.

PARI/GP, 40 bytes

n->sumdiv(n^2-2,d,d--*issquare(n^2+4*d))


Attempt This Online!

Longer but faster. Checks if there is a divisor $$\d>1\$$ of $$\n^2-2\$$ such that $$\n^2+4d-4\$$ is a square.

Returns truthy when there is a solution.

05AB1E, 13 11 bytes

nÍILDI+*>Öà


-2 bytes porting @xnor's formula as well

Outputs 1/0 as truthy/falsey respectively.

Original 13 bytes approach:

L©+®ø.ΔnOyP>Ö


Outputs a valid pair as truthy or -1 as falsey.

If looping indefinitely would have been a valid falsey result, L©+® could have been ∞+∞ instead for -1 byte.

Explanation:

Uses formula $$\n^2-2 = 0 \mod a(a+n)+1\$$ on the range $$\[1,n]\$$.

n           # Square the (implicit) input-integer n
Í          # Decrease it by 2
IL        # Push a list in the range [1, input n]
# (note: n=0 will become list [1,0])
D       # Duplicate it
I+     # Add input n to each value in the copy
*    # Multiply the values at the same positions in the lists together
>   # Increase each by 1
Ö  # Check for each value in the list if it evenly divides the n²-2
à # Check if any is truthy
# (which is output implicitly as result)


Creates a list of pairs $$\[a,b]\$$ where $$\a\$$ is in the range $$\[n+1,2n]\$$ and $$\b\$$ in the range $$\[1,n]\$$, and does the check defined in the challenge description on each pair: $$\(a^2+b^2) = 0 \mod (ab+1)\$$.

L           # Push a list in the range [1, (implicit) input-integer n]
# (note: n=0 will become list [1,0])
©          # Store this list in variable ® (without popping)
+         # Add the (implicit) input to each value in the list
®ø       #  Pair it with list [1,n] of variable ®
# (we now have a list of pairs [a,b], where a is in the range [n+1,2n] and
# b in the range [1,n] and |a-b|==n)
.Δ          # Pop and find the first pair of this list which is truthy for,
# resulting in -1 if none are truthy:
n         #  Square the values in the pair
O        #   Sum them together
y       #   Push the pair again
P      #  Take the product
>     #  Increase it by 1
Ö    #  Check if (a²+b²) is divisible by (a*b+1)
# (after which the result is output implicitly)


Charcoal, 21 bytes

Ｎθ⊙…·¹⊕θ¬﹪⁻×θθ²⊕×ι⁺ιθ


Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for valid, nothing if invalid. Explanation: Uses @xnor's algorithm. I tried writing it using vectorisation but that weighed in at 27 bytes:

Ｎθ¬Π﹪⁻×θθ²⊕÷⁻Ｘ⁺θ⊗⊕…⁰⊕θ²×θθ⁴


Try it online! Link is to verbose version of code. Explanation:

Ｎθ                          Input n as a number
θ                    Input n
×                     Multiplied by
θ                   Input n
⁻                      Minus
²                  Literal integer 2
﹪                       Vectorised modulo by
θ            Input n
⁺             Vectorised plus
…         Range from
⁰        Literal integer 0 to
θ      Input n
⊕       Incremented
⊕          Vectorised incremented
⊗           Vectorised doubled
Ｘ              Vectorised raise to power
²     Literal integer 2
⁻               Vectorised subtract
θ   Input n
×    Multiplied by
θ  Input n
÷                Vectorised divided by
⁴ Literal integer 4
⊕                 Incremented
Π                        Take the product
¬                         Is zero (i.e. was any remainder zero)


J, 38 bytes

3 :'*/0<1|(_2+*:y)%1+(a+y)*a=.1+i.1+y'


Uses @xnor's formula, but implements it directly on an array containing a from 1 to n+1.

Try it here

Ruby, 43 bytes

->n{(0..n).any?{|a|(n*n-2)%~(~a*~a+=n)==0}}


Try it online!