14
\$\begingroup\$

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.

(IMO problems)

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?

\$\endgroup\$
1

10 Answers 10

7
\$\begingroup\$

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

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

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!

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

C (gcc), 50 bytes

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

Try it online!

Port of xnor's Python answer.

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

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

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.

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

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.

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

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.

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

05AB1E, 13 11 bytes

nÍILDI+*>Öà

-2 bytes porting @xnor's formula as well

Outputs 1/0 as truthy/falsey respectively.

Try it online or verify the range [0,100].

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.

Try it online or verify the range [0,100].

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

Ruby, 43 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 21 bytes

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

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:

Nθ¬Π﹪⁻×θθ²⊕÷⁻X⁺θ⊗⊕…⁰⊕θ²×θθ⁴

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

Nθ                          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
             X              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)
\$\endgroup\$
1
\$\begingroup\$

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

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