Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
1  
@DominicMichaelis Indeed, the GCD of those two values is $9$. –  Thomas Andrews Mar 28 '13 at 12:33
3  
I think $\frac{x}{y}$ is going to be a convergent (truncation of continued fraction) of $\sqrt{\frac{987654321}{123456789}}$. –  Cocopuffs Mar 28 '13 at 12:41
1  
$x=3$, $y=1$, $n=123456780$ is a solution, not necessarily minimal. –  Douglas B. Staple Mar 28 '13 at 12:48
1  
Another not necessarily minimal solution: $x=3363, \ y=1189, \ \ n=110733300$. –  P.. Mar 28 '13 at 12:51
2  
@P and the race begins... –  Douglas B. Staple Mar 28 '13 at 12:52

4 Answers 4

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.

share|improve this answer
    
Thank you very very much, your comments are very helpful. –  mk168 Mar 28 '13 at 15:06
    
And as an additional hint, you might note that the $18577$th partial quotient is $1410862$, corresponding to a convergent $p/q$ for which $123456789p^2-987654321q^2=495$. From basic Diophantine approximation, it is easy to figure out what the $a/b$ corresponding to the larger partial quotient David notes leads to when you evaluate $123456789a^2-987654321b^2$, without actually doing any further computation. –  Mike Bennett Mar 28 '13 at 15:27
    
you get $-225$ when using that best approximation at position 472622. The smallest positive number you can get is indeed $495$. –  mercio Mar 28 '13 at 15:34
    
@MikeBennett Sounds like your idea of "basic Diophantine approximation" is more sophisticated than mine; care to explain? –  David Speyer Mar 28 '13 at 15:44
1  
I'm running around a bit today, but if we have $$ax^2-by^2=c$$ with corresponding ``large'' partial quotient $a_n$ to $\sqrt{b/a}$, we should have something like $a_n |c|=2 \sqrt{ab}$ (where the error here can be nicely bounded). For the example here, with the largest partial quotient noted, we have $$2 \sqrt{ab}/a_n =225.000077 \cdots$$ which is suggestive. –  Mike Bennett Mar 28 '13 at 17:03

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.

share|improve this answer
3  
I'm surprised this answer only got one vote (mine). As far as I can tell, this is the only answer which is a full proof that the answer is $495$: The minimum value of $x^2-D y^2$ is not always a convergent, if I recall correctly, but it is always found on the river. And I had not understood before reading this how easy the river is to compute. –  David Speyer Apr 8 '13 at 14:32
    
@DavidSpeyer +1. Two votes. –  Douglas B. Staple Apr 14 '13 at 3:16
    
I can assure you that I used more than 3 minutes of CPU time. –  Douglas B. Staple Apr 16 '13 at 20:05
    
Michael, there is another way, Lagrange's method gives the subset of forms along the river at which crossings occur; that is, $ac < 0, \; \; b > |a+c|$ where $b$ is the number along the edge, with the arrow pointing so that $b>0.$ –  Will Jagy Jul 14 '13 at 5:29

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
share|improve this answer
1  
As long as you've done this much, you might as well check that there are no better solutions that aren't convergents. If the convergents of $\theta$ are $p_1/q_1$, $p_2/q_2$, etcetera, then the best rational approximations to $\theta$ are either convergents themselves or elements of the list $(p_2-p_1)/(q_2-q_1)$, $(p_3-p_2)/(q_3-q_2)$, etcetera. –  David Speyer Mar 28 '13 at 15:43
1  
For those who are curious, that's 9648 digits each. –  David Speyer Mar 28 '13 at 15:47
    
@DavidSpeyer I misspoke -- I was checking all of the convergents, not just the best rational approximations. Also, I extended the search limit to 50000, which is where I'm stopping. –  Douglas B. Staple Mar 28 '13 at 16:22
1  
@DouglasB.Staple I edited, and linked to pastebin. It makes it more amenable to other answers and the full question page itself. Hope you don't mind. Feel free to make further edits to improve readability. –  Pedro Tamaroff Mar 28 '13 at 20:38
    
@DouglasB.Staple It was robjohn actually. –  Pedro Tamaroff Mar 28 '13 at 23:06

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:

enter image description here

============

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:~$ 

=====================

share|improve this answer
    
I don't think Dr. Weissmann has gotten to Conway's topograph yet in his blog. If he's written about it somewhere, I'd love to read it. My understanding is that he is the authority in the topograph method and its generalizations. –  Michael Wijaya Jul 14 '13 at 15:37
    
@MichaelWijaya, what he is doing is writing a book, in which he is doing all the graphics himself, after the "visual information" style of Tufte. Successful publication of the book will be another matter. So, the Coway stuff is mentioned only briefly in the blog. –  Will Jagy Jul 14 '13 at 16:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.