Small, Smaller, Smallest

Note that we want $\dfrac{13}{15}<\dfrac{a}{b}$ , or $15a-13b>0$ ; we want to minimize $15a-13b$ . Since $a,b$ are integers, the smallest difference possible between $15a-13b$ is $1$ ; therefore we let $15a-13b=1$ . Parameterizing for $a$ and $b$ , we get that $a=13n+7$ and $b=15n+8$ . Now note that the higher $n$ gets, the closer $\dfrac{a}{b}$ gets to $\dfrac{13}{15}$ . Therefore, we want the highest $n$ possible. Obviously, $13n+7<15n+8$ . We let $15n+8<500$ , and solving for the maximum $n$ gets gives us $n=32$ . Plugging this back into $a$ and $b$ , we get that $a=423$ and $b=488$ . Our answer is therefore $423+488=\boxed{911}$ .

Let $A=\{ \frac{a}{b} | a,b<500 \mbox{ and } \frac{13}{15}<\frac{a}{b}\}$ , we then have to find $min(A)$ . Suppose $\frac{a}{b}$ is an arbitrary fraction in $A$ , then : $\frac{13}{15}<\frac{a}{b} \Rightarrow \frac{13b}{15}<a$ . Obviously for a fixed $b$ , $a$ must be as small as possible (a fraction gets smaller as the numerator decreases) and the last inequality must hold at the same time. This is possible if we take $a$ to be the smallest integer bigger than $\frac{13b}{15}$ or in other words : $a={\lfloor{\frac{13b}{15}}\rfloor}+1$ , where $\lfloor x \rfloor$ is the floor of x .

*Assertion 1 : * $\mbox{If 'b' is a positive integer then } {\frac{13}{15}<\frac{{\lfloor{\frac{13b}{15}}\rfloor}+1}{b}\le\frac{a}{b}} \mbox{ for any 'a' for which } \frac{13}{15}<\frac{a}{b}$

We'll prove this by contradiction : Suppose there is $a$ and $b$ such that : $\frac{13}{15}<\frac{a}{b}$ , but $\frac{{\lfloor{\frac{13b}{15}}\rfloor}+1}{b}>\frac{a}{b}$ .Then : $\frac{13b}{15}<a < \lfloor{\frac{13b}{15}}\rfloor+1$ , $\lfloor \frac{13b}{15} \rfloor \le \frac{13b}{15} \Rightarrow \lfloor \frac{13b}{15} \rfloor<a < \lfloor{\frac{13b}{15}}\rfloor+1 \Rightarrow$ contradiction , there can't be an integer between two consecutive integers .

Now the problem is finding the minimum of : ${ \frac{{\lfloor{\frac{13b}{15}}\rfloor}+1}{b} }$ where $b \in \{1,2,...,499\}$ .This sequence behaves rather strangely , locally it's neither increasing nor decreasing but globally it decreases to $\frac{13}{15}$ .

Let's turn our attention to the Divison Theorem for now , which says that for all integers $n ,m$ we can find only one pair of numbers $q\in\mathbb{Z},r\in\{0,1,...,m-1\}$ such that : $n=q*m+r$ .Intuitively $q$ is the amount of times $m$ goes into $n$ , or better said $q$ is the biggest number for which $mq\le n \Rightarrow q\le\frac{n}{m} \Rightarrow q=\lfloor \frac{n}{m} \rfloor$ .And we'll denote the remainder when $n$ is divided by $m$ by $r(n,m)$ $\Rightarrow n=m*\lfloor \frac{n}{m} \rfloor+r(n,m) \Rightarrow \lfloor \frac{n}{m} \rfloor = \frac{n-r(n,m)}{m}$ , for all integers $n,m$ .

Then $\lfloor{\frac{13b}{15}}\rfloor= \frac{13b-r(13b,15)}{15}$ , and the whole expression we have to minimize becomes : ${ \frac{{\lfloor{\frac{13b}{15}}\rfloor}+1}{b} } = \frac{\frac{13b-r(13b,15)}{15}+1}{b} = \frac{\frac{13b-r(13b,15)+15}{15}}{b} =\frac{13b+15-r(13b,15)}{15b}=\frac{13}{15}+\frac{1}{15}\frac{15-r(13b,15)}{b}$ . The only part we have to minimize is $\frac{15-r(13b,15)}{b}$ , the rest of it doesn't depend on $b$ .From the Division Theorem we have $b=15q+r \Rightarrow \frac{15-r(13b,15)}{b}=\frac{15-r(13*15q+13r,15)}{15q+r} =\frac{15-r(13r,15)}{15q+r}$ . Keeping $q$ fixed ,let's try to find for which remainder that fraction is the smallest , we have two cases :

1) $0\le r \le 7$

If $r=0$ then $\frac{15-r(13r,15)}{15q+r}=\frac{1}{q}$ , otherwise $r(13r,15)=r(15+13r,15)=r(15+13r+2r-2r,15)=r(15+15r-2r,15)=$ $r(15-2r,15)=15-2r \Rightarrow \frac{15-(15-2r)}{15q+r}=\frac{2r}{15q+r}$ .As $r$ grows so does $\frac{2r}{15q+r}$ , so its smallest value is when $r=1$ : $\frac{2}{15q+1}$ .This is less than $\frac{1}{q}$ .

2) $8\le r \le 14$

$r(15-2r,15)=r(30-2r,15)=30-2r \Rightarrow \frac{15-r(13r,15)}{15q+r}=\frac{2r-15}{15q+r}$ , again this grows with $r$ .The smallest possible value is when $r=8$ : $\frac{1}{15q+8}$ .Between $\frac{2}{15q+1}$ and $\frac{1}{15q+8}$ , the later is the smallest $\Rightarrow$ For a fixed $q$ , $\frac{15-r(13r,15)}{15q+r}$ is the smallest when $r=8$ .And obviously for a fixed $r$ , $\frac{15-r(13r,15)}{15q+r}$ gets smaller as $q$ grows . Let's denote $\frac{15-r(13r,15)}{15q+r}$ by $E(b)$ , $q$ and $r$ are simply the quotient and the remainder when $b$ is divided by 15.The last number between 1 and 499 to have a remainder of 8 is 488 , so $E(488) \le E(n) , 0< n<494$ .Now $E(496) < E(497) <... < E(499)$ and $E(496) > E(495)$ since 496 has a remainder of 1 .We only need to know whether $E(488) < E(496)$ or not .

Looking at the more general statement : $E(15q+8)<E(15(q+1)+1) \Leftrightarrow$ $\frac{1}{15q+8}<\frac{2}{15q+1}$ , so $E(15q+8)<E(15(q+1)+1)$

The fractions is the smallest when $b=488$ , and $a= \lfloor{\frac{13b}{15}\rfloor}+1 = 423$ .

$a+b= \boxed{911}$

JAVA CODE ::

import java.io.*;

import java.math.*;

public class SmallSmallerSmallest

{

public static void main(String args[])throws IOException

{

    double i=0.0,j=0.0,k=13.0/15.0,l=0,m=10000.0,x=0.0,y=0.0;

    for(i=1.0;i<500.0;i+=1.0)

    {

        for(j=1.0;j<500.0;j+=1.0)

        {

            l=i/j;

            if(l>k)

            {

                if(m>l)

                {

                    m=l;

                    x=i;

                    y=j;

                }

            }

        }

    }

    System.out.println((x+y));

}

}

OUTPUT :: 911.0

It follows from the property of Farey sequence that if a real number $x$ is between $\frac{a}{b}$ and $\frac{c}{d}$ then the farey median $\frac{a+b}{c+d}$ is a new estimate to $x$ and we iterate to get the best two fractional estimate and the answer is of course the larger ones.

Simple question with clear algorithmic solution. We start from $\frac{0}{1}$ and $\frac{1}{1}$ , the next one is $\frac{1}{2}$ ... and we get our answers eventually.

A solution with Diophantine equations

For simplicity, let $N:=500$ ..

• Let us analyse the condition for $0<a,\:b<N$ : $\begin{aligned} \frac{a}{b}&\overset{!}{>}\frac{13}{15}&&\Leftrightarrow&15a-13b&\overset{!}{>}0&\underset{\text{LHS is integer}}{\Leftrightarrow}&&15a-13b&=l>0,&l\in\mathbb{N} \end{aligned}$

The integers $a,\:b$ are a solution to a Diophantine Equation ! We can be sure a solution exists, because $13,\:15$ are coprime. Use Euclid's Algorithm to find the general solution: \[\begin{align} \begin{array}{r|r|r|r} n&p_n&a_n&x_n\\ \hline -2&15&\%&\red{8}\\ -1&-13&\%&\green{7}\\ 0&2&-1&1\\ 1&1&-7&0\\ 2&0&2&1 \end{array}&&\Rightarrow&&

\begin{pmatrix} a\\b \end{pmatrix}&=\begin{pmatrix} \green{7}&13\\ \red{8}&15 \end{pmatrix}\begin{pmatrix} l\\\Psi \end{pmatrix},&&&l&\in\mathbb{N},&\Psi\in\mathbb{Z} \end{align}\]

• The restriction $0<a,\:b < N$ together with $l>0$ leads to a restriction for $t:=\Psi/l$ : $\begin{aligned} 0&<a,\:b<N&\Rightarrow&&\frac{\Psi}{l}=t\in\left(-\frac{8}{15};\:\min\left\{\frac{N}{15l}-\frac{8}{15},\:\frac{N}{13l}-\frac{7}{13}\right\}\right)=:I(l)&&(*) \end{aligned}$

• Insert the solution of the Diophantine Equation into $a,\:b$ : $\frac{a}{b}=\frac{7l+13\Psi}{8l+15\Psi}=\frac{7+13t}{8+15t}=\frac{13}{15}+\frac{1}{15}\cdot\frac{1}{15t+8}=:f(t),\qquad t=\frac{\Psi}{l}$

• Notice that $f$ is strictly decreasing for $t\in I(l)$ - if we want to minimize $\frac{a}{b}=f(t)$ , we need to maximize the upper bound of $I(l)$ in $(*)$ ! As that decreases with $l>0$ , we need to use $l=1$ :

$\begin{aligned} \Psi&=\frac{\Psi}{1}<\min\left\{\frac{N-8}{15},\:\frac{N-7}{13}\right\}\underset{N=500}{=}32\:\frac{3}{5}&&\Rightarrow&\Psi=32,&& \begin{pmatrix} a\\b \end{pmatrix}&=\begin{pmatrix} 7&13\\ 8&15 \end{pmatrix}\begin{pmatrix} 1\\32 \end{pmatrix}=\begin{pmatrix} 423\\ 488 \end{pmatrix} \end{aligned}$

• $a,\:b$ are coprime; the answer is $a+b=\boxed{911}$

You might want to specify that a and b are positive integers. Otherwise you could get arbitrarily close to 13/15th, by choosing, for example, a = -13,000,000,001 and b = -15,000,000,000 (both less than 500, but a/b just barely > 13/15)