Minimum of $n$? $123456789x^2 - 987654321y^2 =n$ ($x$,$y$ and $n$ are positive integers)
What is the minimum of $n$?
$x$,$y$ and $n$ are positive integers, find the minimum of $n$, such that:
$123456789x^2 - 987654321y^2 =n$
Solution 1:
Here is some partial progress.
As has already been observed in comments, $GCD(123456789,9876545321)=9$. So $9$ divides the answer.
The prime fractorizations of the nine digit numbers are $$123456789 = 3^2 \times 3607 \times 3803 \quad 987654321 = 3^2 \times 17^2 \times 379721.$$ The quadratic residue symbols are $$\left( \frac{123456789}{17} \right)=1 \quad \left( \frac{123456789}{379721} \right)=1 \quad \left( \frac{-987654321}{3607} \right)=-1 \quad \left( \frac{-987654321}{3803} \right)=-1 $$ So we must have $$\left( \frac{n}{17} \right) = 1 \quad \left( \frac{n}{379721} \right)=1 \quad \left( \frac{n}{3607} \right)=-1 \quad \left( \frac{n}{3803} \right)=-1. $$
The first number divisible by $9$ and obeying these equations is $117$, the next few are $342$, $468$ and $495$. I'm going to guess the answer is one of these.
As people have already started trying in the comments, one way to make $123456789 x^2 - 987654321 y^2$ small is to take $x/y$ very close to $\sqrt{987654321/123456789}$, and a good way to find rational approximations to this number is to use convergents of its continued fraction.
This continued fraction starts off $2+\frac{1}{1+\frac{1}{2+\frac{1}{\cdots}}}$. After the initial $2$, the remaining terms are periodic with period $3861006$. (This periodic part is palindromic, so you only need to compute half of it.) The convergents look like they are growing exponentially, with rate about $3.6^n$. With intelligent use of a large number library, it should be possible to run through the whole list, as long as we clear memory as we go. (Storing a couple of 8 million bit numbers and computing with them is fine, storing 4 million of them is not.) I'm not going to do this, though, it sounds too much like work.
An interesting hint is that the largest integer in that list of length $3861006$ is $3103897$, occurring in position $472622$. Very good rational approximations often occur just before very large terms, so I might try scanning down to that position to see if it happens to give one of the very small numbers above.
The answer is very likely $495$, occuring after $18576$ terms of the continued fraction. Since $x$ and $y$ probably have $20,000$ digits or so, I'm not going to list them, but in principal they should be computable using this method. (As I was writing this answer, I see that Douglas Staple has computed them.)
What I actually did was to find the smallest positive value of $123456789 x^2 - 987654321 y^2$ occurring for $(x,y)$ a convergent of the continued fraction. It is not quite guaranteed that this is the minimum for any $(x,y)$, but I'm not going to work harder. The key was remembering enough about how continued fractions work to realize I could compute the answer without storing any of those thousand digit numbers.
Let $a_0+ 1/(a_1+1/(a_2+1/(\cdots)))$ be a continued fraction with convergents $p_0/q_0$, $p_1/q_1$, etcetera. It is helpful to formally define $p_{-1}/q_{-1} = 1/0$ and $p_{-2}/q_{-2} = 0/1$. Then we have the recursion $$\begin{pmatrix} p_{i-1} & p_{i} \\ q_{i-1} & q_i \end{pmatrix} = \begin{pmatrix} p_{i-2} & p_{i-1} \\ q_{i-2} & q_{i-1} \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & a_i \end{pmatrix} \quad (\ast)$$
We want to minimize $$\begin{pmatrix} p_i & q_i \end{pmatrix} \begin{pmatrix} 123456789 & 0 \\ 0 & -987654321 \end{pmatrix} \begin{pmatrix} p_i \\ q_i \end{pmatrix}$$ Note that this is the lower right entry of $$\begin{pmatrix} p_{i-1} & q_{i-1} \\ p_{i} & q_{i} \end{pmatrix} \begin{pmatrix} 123456789 & 0 \\ 0 & -987654321 \end{pmatrix} \begin{pmatrix} p_{i-1} & p_{i}\\ q_{i-1} & q_{i} \end{pmatrix} \quad (\dagger)$$
Using the recursion $(\ast)$ and its transpose, we have $$(\dagger) = \begin{pmatrix} 0 & 1 \\ 1 & a_i \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & a_0 \end{pmatrix} \begin{pmatrix} 123456789 & 0 \\ 0 & -987654321 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & a_0 \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & a_i \end{pmatrix} \quad (\S)$$
The matrix products in $(\S)$ are called reduced quadratic forms, and they tend to be much smaller than $(x,y)$; only ten digits or so. I decided to just compute these. Here is my Mathematica code.
foo = ContinuedFraction[Sqrt[987654321/123456789]];
The variable foo is of the form $\{3, L \}$ where $L$ is a list containing the entire periodic part. I make this into a single list:
blah = Prepend[Last[foo], First[foo]];
Length[blah]
(* Output is 3861007 *)
(min = 10^10; negmin = -10^10; qq = {{123456789, 0}, {0, -987654321}}; b = 1;
Do[
(qq = {{-a, 1}, {1, 0}}.qq.{{-a, 1}, {1, 0}};
If[qq[[1, 1]] > 0 && qq[[1, 1]] < min, (min = qq[[1, 1]]; Print[{min, b}])];
If[qq[[1, 1]] < 0 && qq[[1, 1]] > negmin,(negmin = qq[[1, 1]]; Print[{negmin, b}])];
b++;),
{a, blah}])
I tested this code by using it to solve the Pell's equation $x^2-13 y^2=1$ but was too lazy to write a general module, I just altered the constants by hand.
The first few lines of output are {-493827165,1}, {123456780,2}, {123456465,4}. This indicates that the best negative and positive values found so far are -493827165 and 123456465, using $1$ and $4$ convergents respectively.
Skipping a few, {68508,1636}, {-15228,3707}, ... then, finally, {495,18576}. After a number more lines, it finds the best negative value at {-225,472621}. I let it run to completion through the whole of blah, and it never did better than these.
Comparing my answer to Doug's, it looks like I might have a fence post error ($18576$ versus $18577$) but I am otherwise happy with it.
Solution 2:
I personally like to think in terms of Conway's topograph. One observation in the first chapter of Conway's The Sensual (Quadratic) Forms is the fact that the smallest values (both positive and negative) of an indefinite binary quadratic form can be found along the "river". So one way to answer this question is to move along the river and examine values we encounter.
Let $f(x,y) = 123456789x^2 - 987654321y^2$. We know one set of values along the river: $$\{ f(1,0), f(1,1), f(0,1) \} = \{ 123456789, -864197532,-987654321 \}$$ The set of values to the right of $\{ a, b, c \}$, where $a > 0$ and $b < 0$, is either $\{ c, b, 2(b+c) - a \}$ if $c > 0$ or $\{ a, c, 2(a+c) - b \}$ if $c < 0$. There are only finitely many triples we can get this way, i.e. the river is periodic.
How do we know it is time to stop? We can either iterate until the initial triple (or its permutation) shows up again or we can cheat by making use of the fact that the period is 3861006. In the language of Conway's topograph, there are 3861006 instances of $c$ becoming positive before the river repeats itself.
Here is a naive Mathematica implementation of the algorithm:
counter = 0;
conwayRiver[{a_?Positive, b_?Negative, c_}] := If[c > 0, counter++; {c, b, 2 (b + c) - a}, {a, c, 2 (a + c) - b}];
list = NestWhileList[conwayRiver, {a, b, c}, counter < 4000000 &];
positiveList = Select[Flatten[list], Positive];
Min[positiveList]
The whole thing takes about 3 minutes on my laptop, so it is definitely less efficient than the approach using continued fractions. However, Conway's topograph is very versatile. For example, it also provides a straightforward algorithm to solve the representation problem: given an integer $n$, to decide if it is a value of the quadratic form.
Solution 3:
Checking the first 50000 convergents, the minimal solution I've found corresponds to the 18577th convergent. This has $n=495$, consistent with @David's answer. I did the calculation in PARI/GP, double-checking the solution $(n,x,y)$ with python. The values for $x$ and $y$ are pretty scary looking:
x=4796374766605282503351751872331201400923514120426944040967627635895376189601418923539122980895157374664840701673814442926552540950110675302241932397036814865796905552070726240909298020358907240712876027631647322548624116166278598207211011547039911490388065046726364851240786240562467619706111839428229492887119534077543062504528844364634429084617112712589998613538372632646378604177109793182506195813043013688120071995599323193029081409670048794508288607174522431393551581158558427298005457565041698052146269574901121936462960380240600575759622236478905582105658997024956906688655138326553310731328347782142203140496025298736391110641341918163225508533166231994089466007836295263362737010739445853682313066216318858915104915054082818901309962893599148888908463393887875683817371433497875955581790796715649286641999079900837031462064566582174974031560254535548966225036875388858154888745956910395100248147770918072510598807399461114514401727433139642591126885962029568842037358345656940944393297517269542962094981260534550443901317030039502623582107694568383203769486945394903721597154012301854613011837845226306301324794958637108921073597009648097428310677706603949270173152625046664079731920432970257342582578959326926434443862393342786359445295797242165763797571438374279547953126950618739121129649014745039342479783642015047707732383633174360075154898478366066961890465534999423196794196390435368874070758131640004751257941381389752339450145469787164985568191325100341281692658878664153249898882691360291958275209811406444142072282005346386511860400218419420644334391530788357432259542173620708561887159405383197983661659836142502078580437827863965446035100818287640465637842612829485733666840425353102856036719869507009388178428651136411102969764640891892438976138713103700048126390276890532033399956490131903143025319328750012377694310924560860559997368111699463640197364829418189624766781718349859466954556900122179789891280991191950439543052613839091244645254552209407747021747392838011796247603110851718541166876919436242891309039501135586164266406814368865660447179235222014341033133477075882322372419355029959035062552201387385130615649432892230377378796661117665448920554938459188632960110096508361887429069685150970111247580638130231825953322118852961337450435705493485942954415176560172855883991828618553244017499025490630574390447778377797948031638415868175605911894990895505514669138287382592381002931895524455005501086070531121579702736810630486473539433383559812185698590289975115507650221238391948036688269113824823132757493777534152688726244793416319781405690423201448687281477142177996675141914555985724360936569454149914166182126856547916262829685792432037430347834367772925519944920031179592741414867646898328182168549393232028282899638088511076934204572717947817314405822567728979390080528976147889560900169462086769838975394565609204376076394224931675675478377253453904652258123449838462135733101031254142579028433828400248928854764368899784494853288531782749230757625069671863810249108734982704606768624912018410394798302564495797370400220686019475224885900683867148942517907559760432470720584079626650390406173572951485631992388031235915732491347981126946417497850466907767735568954133752100451069588569888840916423142370777302742719984664482176424185168009139946482644845818044035741006465529606278696834968060129881416869083817218270806086777689501146051602335724225849858931294629695819435224150158399036452058129571903139836740395602837366049422506043207780424579804464502359436314914935286140328283153643706158533273263315592983527505192619774421807765179786080420150513656002134659234087987608277609468226847743728323678428853844690139327042878318709516634359277016708089865749636396934480600765157725448780424355909447760397090437974233673821354407187804530115665594452164482972837236319797216326916201759521254823653593699289136902727192316095641194480546200804532908239790999683931963821259587921849015848858361006355298476913354445153959160724878185422816680344177937528749660715207862433472233906061338837453108489440005931655028328274057664920454644408681175818444081061963801092223913977172997175477111304604640829993734949924953616778790972901631671332446134685467868959160028423655663198135071300874796984286112394014664061979033035773701400883742702960712563001760024954375920239314497888550074306844737136247726137680752773705343148129194878559555822939924412055236438331095688396431923858326877004943669211479531214587557845042068454183903171621216209151204862899991298425278691772548801084527005446886367844704922168995016425364252883581201211153365162706829984950138124069228915417237420027921250846131922243446452492501966746856019703923374597494785770430815877387396643664232300734642972044754959073813941928310188575487523817143289793872137719772538422884034603969978449842704468224183792767966199974390391035165393774820657036555846608778429846434093892441739048623607399422631841216608608808409349385454628166458354389814444299927054562909822242797442873851361516178837976734450965299967151212100391630177011766453469564478407481425537089857007924508926144281248857578994211514312145466590800115002080485187561462190176420515254054272067780347662940961487185722652548969748772388624680754780353526315495864194367002648640427401488936847908919277973778767844906273309876081735620764174197666080038695010061021572331794286120497980420484099505701655221487739049496043747759609490003097948869902988348728187860978277551733148621492540696794141751547015214178432692304956581334490848073936030030246896653229993401807007384299915799824207616881896436015384141801220942336433592872333964924171296991475946299100472858821080723361507593534870528839747235388888493635435626508348141027766353857480492814188213831596400580722476499930810487614943707174611848737618939787655521514267287211443894721226045303368023774637842147447432203080791339450226500897356934057360454714093572780877945075002854569163779384425785320831109094504498698033746130421981890578940743777640729993475143347957825500045540271621808269867618238646430080394381387043154434352857732235732702325966893434500347446622465473310094503868473817341767295000091293167385027239060722714391010006183519380610247775299658583043105786808167052469075824960559791940261094728973961599324540009156496742230568384636424844964931005291116083508493667535897492777523126106778828299095625011625636461997959947801367875956607483017940366204829916481080558536502210714784926126173740481145529875906872169572648674397670757832637183706490085798855457740102735463303411286114924589826503579272190726413802930946083533948191499019996600320305947631398348260100744998614722687792878996456551680219696029103854413247593870662402512282980163980269368742516153331324853416947475804656804422123702426773749600673764115424856955764274062483879436777290251632335331379481277781400955538399221450188918837661950924569013340987944789335092797995624833455174736552691418840673204811014281452914705647075707048640213084577642498978975335467654156241859334626800527393608885050682953490367992772559541450116744258150252593974293348193534047726145586591615196400419604393600941386340141043983064782077456867773435179149625708133130641820872442868289708902716582360882845469306265524472166675386777163980821116334656100655869851044483388844756288414959681122854385543723285032608506675930977314937015198707263830222082573603037308029091202735370958823128581535738258079985128399363210647560006250365562284844681026869554329131885723063561991628999593536426513986669151129783302445015108642500344397592715099276730485558644663246274543883198107437351636314612670793447905885365960093524565305886041372017813204680441481063992760315366187511211972195302300798192860242965661807781703685307682549496356593159580413104657303048043924977895215761348350716920818176570626979687942863148877806099239386163015512638250533308236036374885850571914618453464837748833150458125720605955316605137204703941708539416725858775026659173727049362616006752314407796102062122077525197645006996792789303171973586506190624067152402696734006464256019809219658867064203359084335777667503580704036149203089873370911459299924544810397685397343919575182309824734231471444017025222036246221437903255613974861597878233676500762393256982868140313044480670759910811119097269944068691221223030788282987185943823178473021776661723341077753772947060775064837963776696038392161385318141338354043992970486141384974686731688467489329481466481027931325595259678395604067440768986723512110172107800714914273058287203552637579610501752875552165897534298114964885105548895001131148144819214199601188451816962922444332922838208727675714943425525529556185789057258335881405562983836947537516991304190958410514740211779923526456951189138335057350664024017683239657007717248499940478202030098526893590264904311263098771157226405790205911907754613407112544661482382957538570167564878504460566145683301254171114432549081798615208230773191666670057590546135705976794185908963055337853936791213729971276562167032461011602009778508771017447312054403791552466226423835202026542171441622270789155154545657328334465328172822495971062303567176883686245737448241851298479588733603547879635022009379716863981536594619991818980809052535107566049682407888357519018722241682078832599509474831224781513049014303441529935497976755844872476577901867241495292962856192083482688073810618302164018875100495570478156740924132693054332943967058589845523196657477173621762356898321295448764635215980677404625874505820791631409362669604298803606083022198957502428402102256950596847770305377630567477796264235411789354450439544518474493623124
y=1695774553562946861295259501185056916256944242172216626679092625881897531414164118050741057657721400429366054069593674925627385180460318164389471129155364372958213331714132453232324544818836245365128245079431272004151217935509723546830387185988582376662163002087012695954430617554877943127124146851455866770446121763445060762722398313238658201000195296955631807764310993221047022064098591376644904700284817649458764712735697622338588320080400985626390555222061429366131136345404059451677516539370271405033339519502123707254742643429654681607656337059170622288324702587077827918357339919282276548715981858991622489557370978659092013639664846187716062671764050045364779330341661240083844420203725226689155240966038920426750772295493447834448282984890024068837678660894515597545760212044500674993018015746901125065516600223891289427404366408478336391264592127121722245461776044147898393702269141964071154787829741225592498178844153210180795645192387535571499439643610073122941693334305848609508433531301834168666697608488718854026760170462502973309492095796848945247083671318632495065173899951112731078483956316002614381110712048853798006838144117357027293849652700869046425168142527200971932316921919608119588749140686228707754096500093558998664586326082009659440321537884868234486241593220528967592215083877323699194791392041715561061400076804647339209854727966423920207363638892602181762316261013785748159327978865609750934149204398370487639335012126314534470578018969776565935310459306314803756823838421881444414661356460902941048164812975561935175809026998255539107176833313317513848972730605036528904756917917864264902712037229787356315803900311513359786223608482257691077037880232467871241969148076333688947567209394797406433806660995567873388667276825508214841751661647730697145307317016997539461218641524177208768109440134674461055400662353755835428905704325653160205301583675197004968093428290198832117478224660829783958947562905474282201744241084676676543633182138198357307528229481124081557858028485617050683358526740426977516100928013220369361177924450245518512802115634303605538086366847503401952501889351751347444182614277348459432814949325665857676760751693205045721062696295104826218894948596229418777028886530249319276872384526533941937408603273040769542028000793478208353516677108811516268366097624991024558935382393795944777838328950249993362895074078016897617633090732058461651022773106146535194990169301668454906425271826346211463415120817036610064942144937003171854574120198145075068929133819250413320590038956071872730642395019763779169712309125948254599435495435608476259605067956306515270451343203196266642823722333404825499725708613166595776774705714930256452120683238239851508260272847521387459699223169310380141525257247207433859869993026921141311688323610163653312292588207326116606392674624700847608878560184193962782630562683827458041723382761179507905939735429213510382544824842893690046753351839165715121419204049642688714403852408546028220325567578394079453782952651309666878133548903354887553854168083826353325222439649475048435096999449034876832127641865926366487696294391428262625606965801306659333635604062094444545652712901267857981355006298911452153585599631496023545425046426987421850742570910501654552097486639577527760602585394640863779867493057028060701871646759654631186399456945933176060936791147657582597534893475095065179290604093894136327551790899932126912359421389785015560184032177210692491297473621103888131485397753373619596865538607132182153472462639381476379989225041002771838126353934452832688913807908780757178275574873154314846702416933718771521398995888684949885389379373178340915534328910674498208594953372721040478265802412787885082677140599389965016913574066675534477277445394190862311664764248080258974507682190038373384037614945473223921955908875722558904828061219721209914284743392414796590445002311227008928900950287537574293246339622932021795694590156297215519133613670562897216280049507429545095020820566565741553868160157715266567815092214911307328011059450931976153867795957579028009942363933839827104228749841189262464880809558800967941862082146587611945073499107686634105022747063555649778129276716724515767777242804505972229956956715589721123269704377436720107113384560057709076741692743430927474578960124462312987015226432500457781194592017985640304122603706641348167314181129889865045509935622004572787774986714180152134178565313620408505159452407851904954012028629085653599396323018541552886716883559944999337495454349741893231745955475339403549769308529112492783336579730677856608328825586962553707654477517949150592295643262052739951585551975943880507122650498545478952301600333288510677578600075062045140677282154197263107250890440391259314054145266913639433749838305345396582921169345689291279846923293252748600408705749338743683268442234003919562665815859004784266502544654479581094803754576328747749738232958467560382569099166404162057015921872305636117736083523593524964092131513810842935980682858339747197998409753957288826129839183441563320045020838569657523659722211492093665146015781661840630389700932420466743087041373323604107817373417595047861764692470843495095150057147605937109749178958907472278937061526486389053096197117858191493508681560376945614027820534450370270573147995412970162363264102781179610095625766197189564152078021238005147248162341611513114222078310967847976370171547747943236269686996274562446281231167486471209296262457157832310879644498948195147503286281870211620095152693032170775590318554010870347680452667433612081872540390763097600090637792977767060643487828758955056780907280027721851576255161684087866084536325218082971905206950577651432659170495882702182406706424479449827380985256738257666473340444344114046478748510607114848564369109170817236031652995944518985296224732932249999696686631044229802127510922451635210311152903045239279731579463953019048667747894394319511192799336558027048001718540106369215010046125140842296320085236699146756212865190222140491616629379669737074715671688599071970236175676968014520280238403826268415503604831067072134175860994557581705670745140199521779653018274078026600598896082179545055890695784542049334948509981696254543220437795419891796382783668569907817476416268361812088972184596274611370718382886710947304958488078957307791506587385903229223836593789731988707892878084153731834986483336827128854447395159032825808759950073028839962619587933798332644173778276508910005703239119867861252178123624530517411215150924375058000505451046194597033887657021779729770035285099973229104125946031107744305039900896709780631501893024897573488886574691075184056589874409068083307839797160172478651300721516338805276659138755545180317232487639129848150630629572847838818906395483459772077729297274584885396905589177781464020859622506380219130192216752486653948512649231669200598942270289885832535089179147765734679446339916180559944786135586908378092664902113447761773375789432041764945404647607097742221297253810432073697458940830180324434881602711959842447341970054228846565303599057331236420571347234474139019422400429010402259670317309507449796490347864859684680814407563282464047759197265554711767207514512625408395552553670776782206106276915629475337818995132641927741914351650986583007965150066284265547114011157111779827087174025610907926527400079071022768903159131501249508348309671914209073255212696142436820530821139286377399446782687324660174555034439875378737066968477463750798919722673383632483105040594773065311633355586044378015905094878523589437077788246285538985941404802828899012143327065126509798268958933455497358942904079514797758315000371465379721354157664601577832012287739403788683653745919813667705694855127197670950049914829017119184604323649568120498718488871277835278145859518126846782433441017333549012139441843135740177371028563670623868555841715033180756356569614285337848385872431173353072444491380467005016175953423406506582496970249093356761613450882357520134703303390072220160882937829617742073888595885748536572681682888337355047618761483183186585901228316333553135542062567554607420907134496443984577439918860583054657564077763689472849320652611535678435340258501481587254763848269263162987032963553802885106077146140886129168129307498933474625972537236393100834203179141205887335842853743054369100998784866789186115254641474625323701483919104631843411566150848901765516726823425473337148238848602605829414056570681452320125256226244665639844102529883417609863398257427543535109666977848130315175874009540534605802753487192997024055629357494608289988513424589777094401686514369254342858456797081524626207474850952339111394583589890868414885499311141023797982427215020425849682516864167971759748157356338261476526756638920195576436716905281152668038776036006307884191661772679012993051409623805607517205728197423809695524242997260154496562348058615715711573559194550269573071202566396522318271184819367192631768371024184929776355422998814073055526663889383129277599593328635010699576594898084699081574031249329631844908024706407740150265264464767185173609014209936445203647321124600443813534386328471573265126021213717546116315374711166869019673159115918167859711347583650921590410033497871527515657314027688984488684001103598906216459754538696239012071923531696829683707508577378583990046080995443610228567211931291886443930452500288221603355112367729483067655980678063808301467334448205617796899454815113205420493555508730268622028695412849844974518736141914681509927768525543652647989659134210446451196259221857920309429800619235884156600900040652400624455871252094460001225767045599638527301022983454119618146569514566151633660500376359235185648081937164287925383
Solution 4:
EEEDDDIIITTT: The five (primitively represented) smallest positive values and five smallest negative (in absolute value). The method was complete by the time of Lagrange, uses no computer memory at all, no decimal accuracy (only integer operations), no cycle detection, no guesswork. It also takes about one minute of human time to go through the full cycle of 3,861,006 neighboring forms. $$-1521, \; -1089, \; -900, \; -729, \; -225, \; 495, \; 621, \; 1053, \; 1395, \; 1845.$$
EDIT: I posted a proof of the "riverbend" property at Generate solutions of Quadratic Diophantine Equation
EEDDIITT:: a fair portion of the necessary material is in BUCHMANN_VOLLMER, especially a (revised) Lagrange method on pages 129-130, and the fact that the minimum occurs in the cycle is Corollary 6.16.2 on page 139. For some reason they do not prove the full Lagrange theorem, that all small values that are primitively represented occur as coefficients of forms in the cycle. Not my fault.
I finally wrote an implementation of Lagrange's cycle method with everything in C++ using GMP integers. Here is what happens, only the forms are printed that achieve a new low in absolute value, one comparison for negative values, one for positive. The key point is Lagrange's theorem, page 111, Theorem 85, in Introduction to the Theory of Numbers by Leonard Eugene Dickson, that, given and indefinite form $\langle a,b,c \rangle$ or $f(x,y) = a x^2 + b x y + c y^2,$ with discriminant $\Delta = b^2 - 4 a c$ positive but not a square, then all integers $n$ with $|n| < \frac{1}{2} \sqrt \Delta$ primitively represented by $f(x,y)$ occur as the first coefficient in the chain of reduced forms equivalent to $f.$ A comparison of Lagrange's method, put briefly in pages 21-24 of Binary Quadratic Forms by Duncan A. Buell, with Conway's topograph method, reveals that Lagrange reduced forms are precisely those with $$ ac < 0, \; \; b > |a+c| $$ and that furthermore, these are precisely the locations where the forms "cross the river." Marty Weissmann calls these riverbends.
For the example below, the discriminant and the floor of the square root of it are DISCRIMINANT 487730524450541076 DISC SQRT 698377064.
jagy@phobeusjunior:~$ date
Sat Jul 13 22:12:41 PDT 2013
jagy@phobeusjunior:~$
jagy@phobeusjunior:~$ ./indef_Binary
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2
123456789 0 -987654321
123456789 b 0 c -987654321
A -987654321 B 0 C 123456789
A 123456789 B 493827156 C -493827165
continue?
1
0 form A 123456789 B 493827156 C -493827165
2 form A 123456780 B 493827066 C -493827381
4 form A 123456465 B 493824024 C -493834725
6 form A 123445764 B 493720686 C -494084205
8 form A 123082245 B 490210236 C -502559181
10 form A 110733300 B 592424874 C -308767311
11 form A -308767311 B 642644370 C 60513804
12 form A 60513804 B 688659318 C -55685097
13 form A -55685097 B 647783010 C 305771652
17 form A -21823083 B 690335820 C 127926243
22 form A 26835705 B 681544296 C -216389853
40 form A 25032753 B 693227718 C -71564796
50 form A 18112023 B 672657678 C -486723276
61 form A -3389724 B 694535274 C 394669125
66 form A 9592524 B 687423006 C -395624115
80 form A 4696569 B 694689462 C -273448332
106 form A 2052108 B 697133610 C -211398993
559 form A -2164257 B 697795578 C 93779964
605 form A -1504620 B 696400506 C 458065773
761 form A -836676 B 696763278 C 672739173
1038 form A 1814724 B 695167830 C -616100931
1511 form A -716175 B 697643424 C 357516459
1636 form A 68508 B 698257746 C -608120955
3707 form A -15228 B 698359410 C 404828523
4890 form A 13005 B 698360544 C -443580057
18576 form A 495 B 698376636 C -302393871
25559 form A -11943 B 698353794 C 680374620
160443 form A -10404 B 698371866 C 174481695
268519 form A -4059 B 698373468 C 309413907
432575 form A -3447 B 698374458 C 264060324
435051 form A -1089 B 698375754 C 420265260
472621 form A -225 B 698376726 C 525591180
3861006 form A 123456789 B 493827156 C -493827165
=========================================
smallest positive 495 line number 18576
A 495 B 698376636 C -302393871
biggest negative -225 line number 472621
A -225 B 698376726 C 525591180
jagy@phobeusjunior:~$
jagy@phobeusjunior:~$ date
Sat Jul 13 22:13:41 PDT 2013
jagy@phobeusjunior:~$
============
Here are pages 99 and 111 from Dickson's Intro book:
============
I also put in some custom commands, here are the five smallest positive (primitively represented) values and the five smallest negative (in absolute value). I also told it to show the first 20 rows and the values of $\delta$ which show how to calculate the next "right neighboring" form, given $\langle a,b,c \rangle$ the new form is $ \langle c, -b + 2 c \delta, a - b \delta + c \delta^2 \rangle .$
==================
revised output
jagy@phobeusjunior:~$
jagy@phobeusjunior:~$ ./indef_Binary
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2
123456789 0 -987654321
123456789 b 0 c -987654321
A -987654321 B 0 C 123456789 DELTA 2
A 123456789 B 493827156 C -493827165 DELTA -1
continue?
1
Sun Jul 14 10:15:21 PDT 2013
0 form A 123456789 B 493827156 C -493827165 DELTA -1
1 form A -493827165 B 493827174 C 123456780 DELTA 4
2 form A 123456780 B 493827066 C -493827381 DELTA -1
3 form A -493827381 B 493827696 C 123456465 DELTA 4
4 form A 123456465 B 493824024 C -493834725 DELTA -1
5 form A -493834725 B 493845426 C 123445764 DELTA 4
6 form A 123445764 B 493720686 C -494084205 DELTA -1
7 form A -494084205 B 494447724 C 123082245 DELTA 4
8 form A 123082245 B 490210236 C -502559181 DELTA -1
9 form A -502559181 B 514908126 C 110733300 DELTA 5
10 form A 110733300 B 592424874 C -308767311 DELTA -2
11 form A -308767311 B 642644370 C 60513804 DELTA 11
12 form A 60513804 B 688659318 C -55685097 DELTA -12
13 form A -55685097 B 647783010 C 305771652 DELTA 2
14 form A 305771652 B 575303598 C -128164509 DELTA -4
15 form A -128164509 B 450012474 C 556353900 DELTA 1
16 form A 556353900 B 662695326 C -21823083 DELTA -31
17 form A -21823083 B 690335820 C 127926243 DELTA 5
18 form A 127926243 B 588926610 C -275346108 DELTA -2
19 form A -275346108 B 512457822 C 204395031 DELTA 2
20 form A 204395031 B 305122302 C -482681628 DELTA -1
18576 form A 495 B 698376636 C -302393871 DELTA -2
47864 form A 1395 B 698374404 C -666001467 DELTA -1
435051 form A -1089 B 698375754 C 420265260 DELTA 1
472621 form A -225 B 698376726 C 525591180 DELTA 1
719320 form A 1053 B 698375916 C -380912085 DELTA -1
722818 form A 1845 B 698374206 C -541035828 DELTA -1
796445 form A -729 B 698376906 C 76000140 DELTA 9
814403 form A -900 B 698375574 C 578358531 DELTA 1
1319754 form A 621 B 698376456 C -342252585 DELTA -2
1625099 form A -1521 B 698375466 C 367018380 DELTA 1
1759361 form A -900 B 698376726 C 131397795 DELTA 5
2101645 form A -900 B 698376474 C 229170519 DELTA 3
2235907 form A -1521 B 698374044 C 693477585 DELTA 1
2541252 form A 621 B 698376744 C -180310185 DELTA -3
3046603 form A -900 B 698375826 C 480585933 DELTA 1
3064561 form A -729 B 698376888 C 84622077 DELTA 8
3138188 form A 1845 B 698375664 C -265092561 DELTA -2
3141686 form A 1053 B 698375934 C -374943060 DELTA -1
3388385 form A -225 B 698376924 C 218305377 DELTA 3
3425955 form A -1089 B 698375646 C 454895460 DELTA 1
3813142 form A 1395 B 698374926 C -535337820 DELTA -1
3842430 form A 495 B 698376744 C -226207323 DELTA -3
3861006 form A 123456789 B 493827156 C -493827165 DELTA -1
=========================================
Sun Jul 14 10:16:20 PDT 2013
smallest positive 495 line number 18576
A 495 B 698376636 C -302393871 DELTA -2
biggest negative -225 line number 472621
A -225 B 698376726 C 525591180 DELTA 1
SMALL ABSOLUTE VALUES
-1521
-1089
-900
-729
-225
495
621
1053
1395
1845
Sun Jul 14 10:16:20 PDT 2013
jagy@phobeusjunior:~$
=====================