# Chaitanya's Random Pages

## September 30, 2012

### When is a perfect square the difference of two consecutive cubes?

Filed under: mathematics — ckrao @ 12:13 pm

This post is inspired by an attempt at the final question of the 2008 AIME II.

We consider the question of when a perfect square is equal to the difference of two consecutive cubes. If we let the cubes be $a^3$ and $(a+1)^3$, we see that we require $\displaystyle (a+1)^3 - a^3 = 3a^2 + 3a + 1$ to be a perfect square, say ${n^2}$.

If you list the first cubes they are $0,1,8,27,64,125,216,343,512,729,1000$ and their differences are $1,7,19,37,61,91,127,169,217,271$. Of these the squares are $1 = 1^3 - 0^3$ and $169 = 13^2 = 8^3 - 7^3$. By continuing to list cubes it would take a while to find the next instance of a square as a difference – the next solution is $32761 = 181^2 = 105^3 - 104^3$. 🙂

Initially I tried solving this problem by rearranging $n^2 = 3a^2 + 3a + 1$ as $(n-1)(n+1) = 3a(a+1)$ but that did not take me far. Another approach was via congruences, noting that the right side is $1 \mod 6$ so that $n$ had to be of the form $n = 6m \pm 1$. The third and most fruitful approach for me was to view the equation as a quadratic in $a$.

$\displaystyle 3a^2 + 3a + 1 - n^2 = 0 \quad \quad (1)$

Since this has integer roots, its discriminant must be a perfect square. In other words, $9 - 4.3(1-n^2) = 3(4n^2 - 1) = t^2$ for some integer $t$. This equation implies $t$ must be a multiple of 3, so letting $t = 3m$ we obtain $3(4n^2 - 1) = 9m^2$, or

$\displaystyle (2n)^2 - 3m^2= 1.$

In other words, we need to find (positive) integer solutions to $x^2 - 3y^2 = 1$ where $x$ is even. An equation of this form is known as Pell’s equation. We claim that solutions to this equation are of the form $\pm (x_0 + y_0 \sqrt{3})^n$, where $x_0 + y_0 \sqrt{3}$  is the smallest positive solution to $x^2 - 3y^2 = 1$ while $x_0 > 1$.

To see why this is so, firstly note that if $(x_1, y_1)$ is another positive solution with $x_1 > x_0$, then the equation $x_0^2 - 3y_0^2 = x_1^2 - 3y_1^2 = 1$ leads to $0 < x_1^2 - x_0^2 = 3(y_1^2 - y_0^2)$, so $y_1 > y_0$ and $x_0 + y_0\sqrt{3} < x_1 + y_1\sqrt{3}$. Hence it makes sense to define the “smallest solution”.

Next, we know there exists some $k$ for which

$\displaystyle (x_0 + y_0\sqrt{3})^k \leq x_1 + y_1\sqrt{3} < (x_0 + y_0\sqrt{3})^{k+1}$.

Multiplying all sides by $(x_0 - y_0\sqrt{3})^k$ and using the fact that $x_0^2 - 3y_0^2 = 1$ gives us

$\displaystyle 1 \leq (x_1 + y_1 \sqrt{3})(x_0 - y_0\sqrt{3})^k < x_0 + y_0\sqrt{3}.\quad \quad (2)$

Define $u + v\sqrt{3} := (x_1 + y_1 \sqrt{3})(x_0 - y_0\sqrt{3})^k$. We can use norms in $\mathbb{Z}[\sqrt{3}]$ or explicit computation to show that $u^2 - 3v^2 = 1$. Equation (2) then contradicts the minimality assumption on $x_0 + y_0\sqrt{3}$ unless we have $u =1, v= 0$. We conclude that $(x_1 + y_1 \sqrt{3}) = (x_0 + y_0 \sqrt{3})^k$, so all solutions are of this form proving the claim.

In our case, the minimal solution is $x_0 = 2, y_0 = 1$, so we have the general solution

$x_k + y_k \sqrt{3} = \pm (2 + \sqrt{3})^k, \quad k = 0, 1, 2, \ldots$

We can use the recurrence $x_{k+1} + y_{k+1}\sqrt{3} = (x_k + \sqrt{3}y_k)(2 + \sqrt{3}) = (2x_k + 3y_k) + (x_k + 2y_k)\sqrt{3}$ to see that $x_{k+1}$ and $y_k$ have the same parity (odd or even), as do $y_{k+1}$ and $x_k$. Since initially $x_0 = 2, y_0 = 1$, we see that the solutions alternate in parity. Since we are looking for $x$ being even, we are looking for odd $k$.

$x_{2k+1} + y_{2k+1}\sqrt{3} = \pm (2 + \sqrt{3})^{2k+1} = \pm (2 + \sqrt{3})(7 + 4\sqrt{3})^k$.

Using the same method as before this leads to the recurrences

\begin{aligned} x_{2k+3} &= 7x_{2k+1} + 12y_{2k+1}\\ y_{2k+3} &= 4x_{2k+1} + 7y_{2k+1}\end{aligned}

We can decouple these by taking 7 times the first equation minus 12 times the second to obtain $7x_{2k+3} - 12 y_{2k+3} = x_{2k+1}$. Then $x_{2k+3} = 7x_{2k+1} + 12y_{2k+1} = 7x_{2k+1} +(7x_{2k+1} - x_{2k-1}) = 14x_{2k+1} - x_{2k-1}$. Similarly we find $y_{2k+3} = 14y_{2k+1} - y_{2k-1}$.

Initial solutions are $(2,1), (26, 15), (362, 209), ...$. From (1) we have $a = (-1 \pm t)/2 = (-1 \pm 3m)/2$, so we require $m = y$ to be odd. This will indeed be the case by our parity arguments from before (that $x_k$ and $y_k$ have different parity). We conclude that this recurrence gives us the entire solution set for $(2n, m)$. The non-negative $(a_k,n_k)$ solutions are $(0, 1), (7,13), (104, 181), (1455, 2521), ...$. In other words,

\begin{aligned} 8^3 - 7^3 &= 13^2\\105^3 - 104^3 &= 181^2\\ 1456^3 - 1455^3 &= 2521^2, \ldots \end{aligned}

The recurrence linking these can be found to be $a_{k+1} = 14a_k - a_{k-1} + 6$ and $n_{k+1} = 14 n_k - n_{k-1}$ and it can be verified that $(a_k+1)^3 -a_k^3 = n_k^2$. The factor of 14 in the recurrence indicates that the solution set is relatively sparse (though still infinite).

A similar approach is shown in [3], where the Pell’s equation is obtained by completing the square to obtain $(2n)^2 - 3(2a+1)^2 = 1$ rather than using the discrminant.

#### References

[1] Dušan Đukić, “Pell’s equation”, The IMO Compendium Group

[2] Matthew Wright, “Solving Pell’s equation”, available here.

## September 27, 2012

### High averages in both test and ODI series against a nation

Filed under: cricket,sport — ckrao @ 12:12 pm

Recently Hashim Amla from South Africa performed a rare feat in averaging over 100 in both test and ODI cricket series against England. It led me to look up others who have performed similarly. The following lists in chronological order those who have averaged over 100 in both test and ODI series against a single team with the restriction that at least 180 ODI runs were scored. I collected the data manually starting with this list of high ODI series averages. Corrections/additions are welcome.

 Tests ODIs Name (nation) Opposition, venue Season Tests Inn Runs Ave 50/100 HS Inn Runs Ave 50/100 HS Sir Viv Richards (WI) vs England in England 1976 4 7 829 118.42 2/3 291 3 216 108 1,1 119* Javed Miandad (Pak) vs India in Pakistan 1982/83 6 6 594 118.8 1/2 280* 4 234 – 0,2 119* Jacques Kallis (SA) vs West Indies in South Africa 2003/04 4 6 712 178 1/4 177 3 361 180.5 2,1 139 Shivnarine Chanderpaul (WI) vs England in England 2007 3 5 446 148.67 3/2 136* 3 202 202 1,1 116* Graeme Smith (SA) vs Bangladesh in Bangladesh 2007/08 2 3 304 101.33 1/1 232 3 199 199 1,1 103* Jonathan Trott (Eng) vs Bangladesh in England 2010 2 3 265 132.5 0/1 226 2 204 102 1,1 110 Hashim Amla (SA) vs England in England 2012 3 5 482 120.5 0/2 311* 4 335 111.67 1,1 150

We see that Richards and Kallis were the only two to aggregate over 1000 runs, with Amla getting both a triple hundred in the tests and a 150 in ODIs.

Honourable mentions/close calls:

• In 2001 Steve Waugh averaged 100 in the NatWest series against England and Pakistan (200 runs in 4 innings), then 107 in the subsequent Ashes series.
• In 1983/84 Desmond Haynes averaged 340 in the ODI series (4 innings) and 93.6 (468 runs in 8 innings) in the test series against Australia.

## September 23, 2012

### 7^7 – 6^6

Filed under: mathematics — ckrao @ 11:07 am

I didn’t expect this number to be so memorable.

### $\displaystyle 7^7 - 6^6 = 776,887$

• It starts and ends with the digit 7.
• It has only 3 different digits (consecutive ones at that and including 6 and 7).
• The first three digits of the number are the same as the first three digits of the original expression $7^7 - 6^6$. They are also easy to recall if you link it to when the ancient Olympics were first held or when the US Declaration of Independence was signed. (I often link numbers to years of events as a memory aid.)
• The two three-digit numbers 776 and 887 making up the six-digit number differ by 111. 🙂

For what it’s worth the result also happens to be prime.

## September 13, 2012

### Tournament wins before a first grand slam

Filed under: sport — ckrao @ 11:30 am

This week Andy Murray broke through with his first grand slam singles title in the 2012 US Open. This led me to compile the following list of the grand slam singles champions (winning for the first time in the Open era from 1968) along with the number of tournaments they won before winning that first grand slam. As can be seen, only a handful won more than a dozen tournaments before their first major, with Ivan Lendl leading the way with 40 tournament wins spanning four years before his first major! Aside from Murray and his coach Lendl, Chris Evert, Martina Navratilova, Jana Novotna, Kim Clijsters, Guillermo Vilas, Thomas Muster and Goran Ivanišević won more than 20 tournaments before finally achieving that first grand slam win.

A few players won a grand slam as their first tournament victory, Gustavo Kuerten the most recent to do so. As far as I can tell only Chris O’Neil won her one and only singles tournament at a grand slam.

As an aside, I noticed that Thomas Muster had an amazing run in 1995, winning 11 tournaments in just over six months, all on clay!

 Men # tournament wins before first slam Women # tournament wins before first slam Andy Murray 23 Victoria Azarenka 9 Juan Martín del Potro 6 Samantha Stosur 2 Novak Djokovic 7 Petra Kvitová 4 Rafael Nadal 6 Li Na 4 Gastón Gaudio 2 Francesca Schiavone 3 Andy Roddick 10 Ana Ivanović 6 Roger Federer 8 Amélie Mauresmo 19 Juan Carlos Ferrero 9 Kim Clijsters 27 Albert Costa 11 Svetlana Kuznetsova 3 Thomas Johansson 6 Maria Sharapova 3 Lleyton Hewitt 9 Anastasia Myskina 7 Goran Ivanišević 21 Justine Henin 9 Marat Safin 4 Jennifer Capriati 12 Carlos Moyá 4 Venus Williams 9 Petr Korda 9 Serena Williams 3 Patrick Rafter 1 Lindsay Davenport 17 Gustavo Kuerten 0 Jana Novotná 21 Richard Krajicek 9 Iva Majoli 8 Yevgeny Kafelnikov 9 Martina Hingis 3 Thomas Muster 28 Mary Pierce 5 Sergi Bruguera 7 Conchita Martínez 18 Andre Agassi 15 Gabriela Sabatini 14 Michael Stich 1 Monica Seles 6 Jim Courier 3 Arantxa Sánchez Vicario 2 Pete Sampras 2 Steffi Graf 14 Andrés Gómez 19 Hana Mandlíková 11 Michael Chang 1 Tracy Austin 7 Pat Cash 3 Barbara Jordan 1? Boris Becker 1 Martina Navratilova 22 Stefan Edberg 5 Virginia Ruzici 2 Ivan Lendl 40 Chris O’Neil 0 Yannick Noah 13 Mima Jaušovec 2 Mats Wilander 0 Kerry Melville Reid ? Johan Kriek 3 Sue Barker 5 Brian Teacher 3 Chris Evert [3] 30 John McEnroe 11 Evonne Goolagong Cawley 6 Vitas Gerulaitis 7 Virginia Wade 0 Guillermo Vilas 22 Roscoe Tanner 8 Adriano Panatta 5 Mark Edmondson 0 Manuel Orantes 18 Björn Borg 4 Jimmy Connors 17 Ilie Năstase 17 Andrés Gimeno 3 Stan Smith 7 Jan Kodeš 0 Arthur Ashe 1

#### References

Blog at WordPress.com.