PELLFOUR - Pell Fourth

no tags 

The double palindrome, or Quarter Pell Art

Leo was quietly fighting with XerK along the East-coast with 300 friends, when XerK proposed Leo a beer, it was a Pell-Fourth.
Then XerK told Leo he had a good problem found in an ancient book :

D is a given positive integer, consider the equation :
X² = D×Y² + 1, with X and Y positive integers.
Find the minimum number X within all solutions.
Sometimes it's possible, sometimes not!

Examples :
If D=2, 3² = 2×2² + 1, so X=3.
If D=3, 2² = 3×1² + 1, so X=2.
If D=4, it's impossible!

Leo said that he very well knows this problem and claimed that there is yet on SPOJ a classic edition and surely others related ones. But XerK told him he had an army of byteland's computer that gave him the list of the worst test cases for D. This list begins with 2, 5, 10, ...

First examples are:

 D   X
 2   3
 5   9
10  19

where each new line is the minimal D to break a new record for X.
E.g : for any D in [5, 10[, X(D) will be not greater than 9; and X(10) is greater than 9.

The search and print of those 'pell-fect' (D, X) is the goal of this challenge.


There's no input for this challenge.


Start with D=2 and X=3, and print consecutive 'pell-fect' "D X" of this sequence.
As the answer X could be a huge number, print instead CHK(X, 2^16384), this only affect X numbers on line 127 and after.


2 3
5 9
10 19


This is madness, but XerK can judge 1000 lines. (Edit 12/II/2017 : the MasterJudge take time into account if all 1000 lines are given.)


If you can output n lines, XerK decided that the fairest score was exp(sqrt(n)), but he didn't want to tell why, so it was decided to set the score at 'just' n. You need to output more than 44 lines to get accepted.

Added by:Francky
Time limit:44s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Extension of Project Euler n°###