Day 1: A Partridge in a Number Tree
A partridge sits in its tree. However, this is not a pear tree; it is a number tree! It rummages around until it finds a special type of number- let us call them partridge numbers.
Define a partridge number to be a number such that:
- It is a square number,
- It can be expressed in the form x 2 y 2 − x 2 − y 2 + 2 where the positive integers x and y are not consecutive,
- It cannot be expressed in the form x 2 y 2 − x 2 − y 2 + 2 for any consecutive positive integers x and y .
The first partridge number is between 1 and 2 0 1 4 . What number is it?
This problem is part of the set Advent Calendar 2014 .
The answer is 961.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
Put x=2 and y=11 then n=19. I think the first partridge should be 361. Please correct me if I am wrong.
Log in to reply
You were close; 361 does indeed satisfy condition 1 and 2, but doesn't satisfy condition 3 as x=4, y=5 works as well.
Log in to reply
condition 3 states that x,y are not consecutive. since x=3., and y = 11 ., satisfy the given conditions that 361 must be the answer. I think u r seeing consecutive numbers BETWEEN the x=3., Y =11.,
Log in to reply
@Anil Ram – While x=3, y=11 is one way to arrive at 361, the fact that x=4, y=5 also arrives at the same number means there is a way to express 361 using the equation with consecutive numbers, therefore it fails condition 3, which states that this should not be possible, not that there is a way to do it without consecutive numbers. Michael Ng is correct.
I used x 2 − 1 = ( x − 1 ) ( x + 1 ) for easy factorisation; looking at factors greatly helps estimate whether the equation for x , y , z is satisfied.
I arrived at ( x 2 − 1 ) ( y 2 − 1 ) = n 2 − 1 , but could not figure out the next steps. Thank you for this solution.
what i not understand is condition 2 that u frame ( Not the product of two consecutive elements, that is, not in the set {0*3 = 0,24,120,...}
please explain with some more details .
There is a family of solutions of the form ( x , y , n ) = ( a + 1 , 2 a 2 + 2 a − 1 , 2 a 3 + 4 a 2 − 1 ) . I generated these by setting n = x y − a and getting a Pell equation when I tried to solve the resulting quadratic in y . It's not hard to see that a = 1 in general implies that x and y are consecutive. Putting a = 2 yields ( 3 , 1 1 , 3 1 ) .
This is by no means a complete solution (and that family is by no means the only family of points); I just thought it was pretty.
Imo it's still better than the method of checking repeatedly for different values.
Yes it is very pretty. I'm at a loss to understand how a human could have thought of this
A little Visual Basic program helped finding possible candidates 361 and 961. Since 361 is cunstructible from x=4 / y=5 that follows from the solution of ( x 2 + x − 1 ) 2 = 1 9 2 it is to be excluded.
From condition 1 and 2, notice that x 2 y 2 − x 2 − y 2 + 2 = n 2 for some integer n which implies that: ( x 2 − 1 ) ( y 2 − 1 ) = n 2 − 1
Notice that the equation above seems very symmetric. In fact now we can restate the problem to make it simpler:
In the set { 0 , 3 , 8 , 1 5 , 2 4 , 3 5 , 4 8 , ⋯ } of all numbers less than 2 0 1 4 of the form a 2 − 1 for some integer a , find an element that is:
We can draw a small multiplication table with the products of elements. Then a bit of calculation (modular arithmetic can help to eliminate some cases) shows that 9 6 0 works and therefore the first partridge number is 9 6 1 .