|Re: Mini Challenge|
Message #11 Posted by Egan Ford on 25 Jan 2009, 1:58 p.m.,
in response to message #1 by Egan Ford
I found this problem in Recreations in the Theory of Numbers by Beiler. This very inexpensive Dover reprint is very well written and a lot of fun. Chapter 22 (The Pellian) is entirely devoted to Pell Equations.
The number 48 is special in that if you add one to it, or add one to half of it, the sum is a perfect square, i.e.:
48 + 1 = 49 = 7 * 7
48/2 + 1 = 25 = 5 * 5
Using your favorite calculator how many more can you find?
NOTE: All code will be end of this post.
MC1: Brute Force
As Thomas pointed out:
This program takes a single argument (number of solutions to find), then sequentially tests each odd square. The output below took over an hour (I stopped watching) with an input of 7.
n + 1 = x2
n/2 + 1 = y2
x2 - 2y2 = -1
As Thomas pointed out x2 - 2y2 = -1 is a Pell Equation. Clearly x = 1 and y = 1. To find any x the following can be use:
x = [(1 + sqrt(2))r + (1 - sqrt(2))r]/2.
However, r must be odd. See Beiler for details.
This program counts odds from 1 to 13 to find the first seven solutions in seconds. NOTE: the 7th solution is a bit off (rounding error), however the following 50g version does not have this problem:
<< 1 13 FOR r 1 2 v/ + r ^ 1 2 v/ - r ^ + 2 / 2 ^ 1 - EVAL 2 STEP >>
MC3: Recurrence Relation
As Peter pointed out this can be found here: http://en.wikipedia.org/wiki/Pell%27s_equation.
However, like MC2, for this type of Pell Equation (-1) only every other recurrence will have a valid solution. Solving for xn+2 a new recurrence relation can be obtained:
xn+1 = 3xn + sqrt(8(xn2 + 1)).
This program will compute the first 7 solutions in seconds. This was my final solution.
MC4: Recurrence Relation
This identical to Pauli's 50g version (thanks for the incredible find (A078522)).
This program will find the first 7 solutions in seconds.
The On-Line Encyclopedia of Integer Sequences is treasure trove of integer sequences. You can find many interesting solutions there, e.g. when I searched for 1, 49, 1681 I found A008843 and created the following 15C version:
001 LBL A 010 x
002 SF 8 011 COSH
003 2 012 x^2
004 x 013 CHS
005 1 014 1
006 - 015 -
007 2 016 INT
008 SQRT 017 RTN
Note the requirement for complex numbers and hyperbolic functions. To use, just enter the term you want (1 through 7). NOTE: the 7th solution is a bit off.
41CX Code and Results
I liked this problem because there were so many ways to write programs for it. Thanks all for participating.
Edited: 25 Jan 2009, 2:19 p.m.