Mínimo de $n$? $123456789x^2 - 987654321y^2 =$ n ($x$,$y$ y $$ n son enteros positivos)

Question

¿Cuál es el mínimo de $n$?

$x$,$y$ y $$ n son enteros positivos, encontrar el mínimo de $n$, tal que:

$123456789x^2 - 987654321y^2 =n$

Answer 1

Aquí hay algunos parcial de progreso.

Como ya se ha observado en los comentarios, $MCD(123456789,9876545321)=9$. Por lo que $9$ divide a la respuesta.

El primer fractorizations de los nueve dígitos $$123456789 = 3^2 \times 3607 \times 3803 \quad 987654321 = 3^2 \times 17^2 \times 379721.$$ Los residuos cuadráticos símbolos son $$\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 $$ Así que debemos tener $$\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. $$

El primer número divisible por $9$ y obedecer estas ecuaciones es de $117$, los próximos son de $342$, $468$ y $495$. Voy a adivinar la respuesta correcta es uno de estos.

---

Como la gente ya empezó a tratar en los comentarios, una manera de hacer $123456789 x^2 - 987654321 y^2$ pequeño es tomar $x,$ y muy cerca de us $\sqrt{987654321/123456789}$, y una buena manera de encontrar aproximaciones racionales a este número es el uso de convergents de la continuación de su fracción.

Esto continuó fracción comienza en $2+\frac{1}{1+\frac{1}{2+\frac{1}{\cdots}}}$. Después de la inicial de $2$, el resto de términos son periódicas con período $3861006$. (Este periódico parte es capicúa, por lo que sólo necesita para calcular la mitad de ella). El convergents parece que están creciendo de manera exponencial, con una tasa de alrededor de $3.6^n$. El uso inteligente de un gran número de la biblioteca, debe ser posible ejecutar a través de toda la lista, siempre que borrar la memoria como vamos. (Almacenamiento de un par de 8 millones de bits de los números y de la informática con ellos es buena, almacenamiento de 4 millones de ellos no lo es). No voy a hacer esto, sin embargo, suena como mucho trabajo.

Una interesante sugerencia es que el entero más grande en la lista de longitud $3861006$ es $3103897$, que se producen en la posición $472622$. Muy buenas aproximaciones racionales a menudo se producen justo antes de muy grandes términos, por lo que yo podría tratar de escanear hacia abajo a la posición para ver si le pasa a dar a uno de los números muy pequeños arriba.

---

La respuesta es muy probable $495$, que ocurren después de $18576$ términos de la continuidad de la fracción. Desde $x$ y $y$ probablemente tiene $20,000$ dígitos o menos, no voy a enumerarlos, pero en principio deberían ser computable el uso de este método. (Mientras estaba escribiendo esta respuesta, veo que Douglas Discontinuas ha calculado.)

Lo que en realidad hizo fue encontrar el menor valor positivo de $123456789 x^2 - 987654321 y^2$ ocurre $(x,y)$ convergente de la continuación de la fracción. No es la garantía de que este es el mínimo para cualquier $(x,y)$, pero yo no voy a trabajar más duro. La clave estaba recordando lo suficiente acerca de cómo fracciones continuas de trabajo cuenta de que podría calcular la respuesta sin almacenar cualquiera de esos miles de números de un dígito.

Deje de $a_0+ 1/(a_1+1/(a_2+1/(\cdots)))$ siendo una fracción con convergents $p_0/q_0$, $p_1/q_1$, etcétera. Es útil para definir formalmente $p_{-1}/q_{-1} = 1/0$ y $p_{-2}/q_{-2} = 0/1$. Luego tenemos la recursividad $$\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)$$

Queremos minimizar $$\begin{pmatrix} p_i & q_i \end{pmatrix} \begin{pmatrix} 123456789 & 0 \\ 0 & -987654321 \end{pmatrix} \begin{pmatrix} p_i \\ q_i \end{pmatrix}$$ Tenga en cuenta que esta es la parte inferior derecha de la entrada de $$\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 (\daga)$$

El uso de la recursividad $(\ast)$ y su transpuesta, tenemos $$(\daga) = \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)$$

La matriz de productos en $(\S)$ se llama reducción de la formas cuadráticas, y que tienden a ser mucho menor que $(x,y)$; sólo diez dígitos o menos. Decidí calcular estos. Aquí está mi código de Mathematica.

foo = ContinuedFraction[Sqrt[987654321/123456789]];

La variable foo es de la forma $\{3, L \}$ donde $L$ es una lista que contiene la totalidad del periódico parte. Puedo hacer esto en una sola lista:

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}])

He probado este código para resolver la Pell de la ecuación $x^2-13 y^2=1$, pero era demasiado perezoso para escribir un módulo general, acabo de alteración de las constantes a mano.

Las primeras líneas de salida son {-493827165,1}, {123456780,2}, {123456465,4}. Esto indica que los mejores valores positivos y negativos encontrados hasta la fecha son -493827165 y 123456465, con $1$ y $4$ convergents respectivamente. Saltarse un par de, {68508,1636}, {-15228,3707}, ... entonces, finalmente, {495,18576}. Después de un número más líneas, se encuentra el mejor valor negativo en {-225,472621}. Yo deje que se ejecute hasta el final a través de la totalidad de la blah, y nunca lo hizo mejor que estos.

Comparando mi respuesta a Doug, que parece que podría tener una valla de error de la post ($18576$ frente $18577$) pero yo soy de otra manera feliz con ella.

Answer 2

Personalmente, me gusta pensar en términos de Conway topograph. Una observación en el primer capítulo de Conway El Sensual (Cuadrática) de las Formas es el hecho de que el más pequeño de los valores (positivos y negativos) de un indefinido binario forma cuadrática se puede encontrar a lo largo del "río". Así que una manera de responder a esta pregunta es mover a lo largo del río y examinar los valores que nos encontramos.

Deje que $f(x,y) = 123456789x^2 - 987654321y^2$. Sabemos que un conjunto de valores a lo largo del río: $$\{ f(1,0), f(1,1), f(0,1) \} = \{ 123456789, -864197532,-987654321 \}$$ El conjunto de valores a la derecha de $\{ a, b, c \}$, donde $a > 0$ y $b < 0$, $ \ { c, b, 2(b+c) - a \}$ si $c > 0$ o $\{ a, c, 2(a+c) - b \}$ si $c < 0$. Hay sólo un número finito de triples que podemos obtener de esta manera, es decir, el río es periódica.

¿Cómo sabemos que es el momento de parar? Podemos iterar hasta que el inicial triple (o su permutación) muestra de nuevo o nos puede engañar, haciendo uso del hecho de que el período es 3861006. En el lenguaje de Conway topograph, hay 3861006 instancias de $c$ convertirse en positivo antes de que el río se repite.

Aquí es un ingenuo Mathematica implementación del algoritmo:

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]

Toda la cosa de unos 3 minutos en mi portátil, así que en definitiva, es menos eficiente que el método de fracciones continuas. Sin embargo, Conway topograph es muy versátil. Por ejemplo, proporciona también un sencillo algoritmo para resolver la representación problema: dado un entero $n$, para decidir si es un valor de la forma cuadrática.

Answer 3

La comprobación de la primera 50000 convergents, la minimización de la solución que he encontrado corresponde a la 18577th convergente. Esto ha $n=495$, en consonancia con @David de la respuesta. Hice el cálculo en PARI/GP, haga doble comprobación de la solución $(n,x,y)$ con python. Los valores de $x$ y $y$ son bastante miedo buscando:

x=4796374766605282503351751872331201400923514120426944040967627635895376189601418923539122980895157374664840701673814442926552540950110675302241932397036814865796905552070726240909298020358907240712876027631647322548624116166278598207211011547039911490388065046726364851240786240562467619706111839428229492887119534077543062504528844364634429084617112712589998613538372632646378604177109793182506195813043013688120071995599323193029081409670048794508288607174522431393551581158558427298005457565041698052146269574901121936462960380240600575759622236478905582105658997024956906688655138326553310731328347782142203140496025298736391110641341918163225508533166231994089466007836295263362737010739445853682313066216318858915104915054082818901309962893599148888908463393887875683817371433497875955581790796715649286641999079900837031462064566582174974031560254535548966225036875388858154888745956910395100248147770918072510598807399461114514401727433139642591126885962029568842037358345656940944393297517269542962094981260534550443901317030039502623582107694568383203769486945394903721597154012301854613011837845226306301324794958637108921073597009648097428310677706603949270173152625046664079731920432970257342582578959326926434443862393342786359445295797242165763797571438374279547953126950618739121129649014745039342479783642015047707732383633174360075154898478366066961890465534999423196794196390435368874070758131640004751257941381389752339450145469787164985568191325100341281692658878664153249898882691360291958275209811406444142072282005346386511860400218419420644334391530788357432259542173620708561887159405383197983661659836142502078580437827863965446035100818287640465637842612829485733666840425353102856036719869507009388178428651136411102969764640891892438976138713103700048126390276890532033399956490131903143025319328750012377694310924560860559997368111699463640197364829418189624766781718349859466954556900122179789891280991191950439543052613839091244645254552209407747021747392838011796247603110851718541166876919436242891309039501135586164266406814368865660447179235222014341033133477075882322372419355029959035062552201387385130615649432892230377378796661117665448920554938459188632960110096508361887429069685150970111247580638130231825953322118852961337450435705493485942954415176560172855883991828618553244017499025490630574390447778377797948031638415868175605911894990895505514669138287382592381002931895524455005501086070531121579702736810630486473539433383559812185698590289975115507650221238391948036688269113824823132757493777534152688726244793416319781405690423201448687281477142177996675141914555985724360936569454149914166182126856547916262829685792432037430347834367772925519944920031179592741414867646898328182168549393232028282899638088511076934204572717947817314405822567728979390080528976147889560900169462086769838975394565609204376076394224931675675478377253453904652258123449838462135733101031254142579028433828400248928854764368899784494853288531782749230757625069671863810249108734982704606768624912018410394798302564495797370400220686019475224885900683867148942517907559760432470720584079626650390406173572951485631992388031235915732491347981126946417497850466907767735568954133752100451069588569888840916423142370777302742719984664482176424185168009139946482644845818044035741006465529606278696834968060129881416869083817218270806086777689501146051602335724225849858931294629695819435224150158399036452058129571903139836740395602837366049422506043207780424579804464502359436314914935286140328283153643706158533273263315592983527505192619774421807765179786080420150513656002134659234087987608277609468226847743728323678428853844690139327042878318709516634359277016708089865749636396934480600765157725448780424355909447760397090437974233673821354407187804530115665594452164482972837236319797216326916201759521254823653593699289136902727192316095641194480546200804532908239790999683931963821259587921849015848858361006355298476913354445153959160724878185422816680344177937528749660715207862433472233906061338837453108489440005931655028328274057664920454644408681175818444081061963801092223913977172997175477111304604640829993734949924953616778790972901631671332446134685467868959160028423655663198135071300874796984286112394014664061979033035773701400883742702960712563001760024954375920239314497888550074306844737136247726137680752773705343148129194878559555822939924412055236438331095688396431923858326877004943669211479531214587557845042068454183903171621216209151204862899991298425278691772548801084527005446886367844704922168995016425364252883581201211153365162706829984950138124069228915417237420027921250846131922243446452492501966746856019703923374597494785770430815877387396643664232300734642972044754959073813941928310188575487523817143289793872137719772538422884034603969978449842704468224183792767966199974390391035165393774820657036555846608778429846434093892441739048623607399422631841216608608808409349385454628166458354389814444299927054562909822242797442873851361516178837976734450965299967151212100391630177011766453469564478407481425537089857007924508926144281248857578994211514312145466590800115002080485187561462190176420515254054272067780347662940961487185722652548969748772388624680754780353526315495864194367002648640427401488936847908919277973778767844906273309876081735620764174197666080038695010061021572331794286120497980420484099505701655221487739049496043747759609490003097948869902988348728187860978277551733148621492540696794141751547015214178432692304956581334490848073936030030246896653229993401807007384299915799824207616881896436015384141801220942336433592872333964924171296991475946299100472858821080723361507593534870528839747235388888493635435626508348141027766353857480492814188213831596400580722476499930810487614943707174611848737618939787655521514267287211443894721226045303368023774637842147447432203080791339450226500897356934057360454714093572780877945075002854569163779384425785320831109094504498698033746130421981890578940743777640729993475143347957825500045540271621808269867618238646430080394381387043154434352857732235732702325966893434500347446622465473310094503868473817341767295000091293167385027239060722714391010006183519380610247775299658583043105786808167052469075824960559791940261094728973961599324540009156496742230568384636424844964931005291116083508493667535897492777523126106778828299095625011625636461997959947801367875956607483017940366204829916481080558536502210714784926126173740481145529875906872169572648674397670757832637183706490085798855457740102735463303411286114924589826503579272190726413802930946083533948191499019996600320305947631398348260100744998614722687792878996456551680219696029103854413247593870662402512282980163980269368742516153331324853416947475804656804422123702426773749600673764115424856955764274062483879436777290251632335331379481277781400955538399221450188918837661950924569013340987944789335092797995624833455174736552691418840673204811014281452914705647075707048640213084577642498978975335467654156241859334626800527393608885050682953490367992772559541450116744258150252593974293348193534047726145586591615196400419604393600941386340141043983064782077456867773435179149625708133130641820872442868289708902716582360882845469306265524472166675386777163980821116334656100655869851044483388844756288414959681122854385543723285032608506675930977314937015198707263830222082573603037308029091202735370958823128581535738258079985128399363210647560006250365562284844681026869554329131885723063561991628999593536426513986669151129783302445015108642500344397592715099276730485558644663246274543883198107437351636314612670793447905885365960093524565305886041372017813204680441481063992760315366187511211972195302300798192860242965661807781703685307682549496356593159580413104657303048043924977895215761348350716920818176570626979687942863148877806099239386163015512638250533308236036374885850571914618453464837748833150458125720605955316605137204703941708539416725858775026659173727049362616006752314407796102062122077525197645006996792789303171973586506190624067152402696734006464256019809219658867064203359084335777667503580704036149203089873370911459299924544810397685397343919575182309824734231471444017025222036246221437903255613974861597878233676500762393256982868140313044480670759910811119097269944068691221223030788282987185943823178473021776661723341077753772947060775064837963776696038392161385318141338354043992970486141384974686731688467489329481466481027931325595259678395604067440768986723512110172107800714914273058287203552637579610501752875552165897534298114964885105548895001131148144819214199601188451816962922444332922838208727675714943425525529556185789057258335881405562983836947537516991304190958410514740211779923526456951189138335057350664024017683239657007717248499940478202030098526893590264904311263098771157226405790205911907754613407112544661482382957538570167564878504460566145683301254171114432549081798615208230773191666670057590546135705976794185908963055337853936791213729971276562167032461011602009778508771017447312054403791552466226423835202026542171441622270789155154545657328334465328172822495971062303567176883686245737448241851298479588733603547879635022009379716863981536594619991818980809052535107566049682407888357519018722241682078832599509474831224781513049014303441529935497976755844872476577901867241495292962856192083482688073810618302164018875100495570478156740924132693054332943967058589845523196657477173621762356898321295448764635215980677404625874505820791631409362669604298803606083022198957502428402102256950596847770305377630567477796264235411789354450439544518474493623124

y=1695774553562946861295259501185056916256944242172216626679092625881897531414164118050741057657721400429366054069593674925627385180460318164389471129155364372958213331714132453232324544818836245365128245079431272004151217935509723546830387185988582376662163002087012695954430617554877943127124146851455866770446121763445060762722398313238658201000195296955631807764310993221047022064098591376644904700284817649458764712735697622338588320080400985626390555222061429366131136345404059451677516539370271405033339519502123707254742643429654681607656337059170622288324702587077827918357339919282276548715981858991622489557370978659092013639664846187716062671764050045364779330341661240083844420203725226689155240966038920426750772295493447834448282984890024068837678660894515597545760212044500674993018015746901125065516600223891289427404366408478336391264592127121722245461776044147898393702269141964071154787829741225592498178844153210180795645192387535571499439643610073122941693334305848609508433531301834168666697608488718854026760170462502973309492095796848945247083671318632495065173899951112731078483956316002614381110712048853798006838144117357027293849652700869046425168142527200971932316921919608119588749140686228707754096500093558998664586326082009659440321537884868234486241593220528967592215083877323699194791392041715561061400076804647339209854727966423920207363638892602181762316261013785748159327978865609750934149204398370487639335012126314534470578018969776565935310459306314803756823838421881444414661356460902941048164812975561935175809026998255539107176833313317513848972730605036528904756917917864264902712037229787356315803900311513359786223608482257691077037880232467871241969148076333688947567209394797406433806660995567873388667276825508214841751661647730697145307317016997539461218641524177208768109440134674461055400662353755835428905704325653160205301583675197004968093428290198832117478224660829783958947562905474282201744241084676676543633182138198357307528229481124081557858028485617050683358526740426977516100928013220369361177924450245518512802115634303605538086366847503401952501889351751347444182614277348459432814949325665857676760751693205045721062696295104826218894948596229418777028886530249319276872384526533941937408603273040769542028000793478208353516677108811516268366097624991024558935382393795944777838328950249993362895074078016897617633090732058461651022773106146535194990169301668454906425271826346211463415120817036610064942144937003171854574120198145075068929133819250413320590038956071872730642395019763779169712309125948254599435495435608476259605067956306515270451343203196266642823722333404825499725708613166595776774705714930256452120683238239851508260272847521387459699223169310380141525257247207433859869993026921141311688323610163653312292588207326116606392674624700847608878560184193962782630562683827458041723382761179507905939735429213510382544824842893690046753351839165715121419204049642688714403852408546028220325567578394079453782952651309666878133548903354887553854168083826353325222439649475048435096999449034876832127641865926366487696294391428262625606965801306659333635604062094444545652712901267857981355006298911452153585599631496023545425046426987421850742570910501654552097486639577527760602585394640863779867493057028060701871646759654631186399456945933176060936791147657582597534893475095065179290604093894136327551790899932126912359421389785015560184032177210692491297473621103888131485397753373619596865538607132182153472462639381476379989225041002771838126353934452832688913807908780757178275574873154314846702416933718771521398995888684949885389379373178340915534328910674498208594953372721040478265802412787885082677140599389965016913574066675534477277445394190862311664764248080258974507682190038373384037614945473223921955908875722558904828061219721209914284743392414796590445002311227008928900950287537574293246339622932021795694590156297215519133613670562897216280049507429545095020820566565741553868160157715266567815092214911307328011059450931976153867795957579028009942363933839827104228749841189262464880809558800967941862082146587611945073499107686634105022747063555649778129276716724515767777242804505972229956956715589721123269704377436720107113384560057709076741692743430927474578960124462312987015226432500457781194592017985640304122603706641348167314181129889865045509935622004572787774986714180152134178565313620408505159452407851904954012028629085653599396323018541552886716883559944999337495454349741893231745955475339403549769308529112492783336579730677856608328825586962553707654477517949150592295643262052739951585551975943880507122650498545478952301600333288510677578600075062045140677282154197263107250890440391259314054145266913639433749838305345396582921169345689291279846923293252748600408705749338743683268442234003919562665815859004784266502544654479581094803754576328747749738232958467560382569099166404162057015921872305636117736083523593524964092131513810842935980682858339747197998409753957288826129839183441563320045020838569657523659722211492093665146015781661840630389700932420466743087041373323604107817373417595047861764692470843495095150057147605937109749178958907472278937061526486389053096197117858191493508681560376945614027820534450370270573147995412970162363264102781179610095625766197189564152078021238005147248162341611513114222078310967847976370171547747943236269686996274562446281231167486471209296262457157832310879644498948195147503286281870211620095152693032170775590318554010870347680452667433612081872540390763097600090637792977767060643487828758955056780907280027721851576255161684087866084536325218082971905206950577651432659170495882702182406706424479449827380985256738257666473340444344114046478748510607114848564369109170817236031652995944518985296224732932249999696686631044229802127510922451635210311152903045239279731579463953019048667747894394319511192799336558027048001718540106369215010046125140842296320085236699146756212865190222140491616629379669737074715671688599071970236175676968014520280238403826268415503604831067072134175860994557581705670745140199521779653018274078026600598896082179545055890695784542049334948509981696254543220437795419891796382783668569907817476416268361812088972184596274611370718382886710947304958488078957307791506587385903229223836593789731988707892878084153731834986483336827128854447395159032825808759950073028839962619587933798332644173778276508910005703239119867861252178123624530517411215150924375058000505451046194597033887657021779729770035285099973229104125946031107744305039900896709780631501893024897573488886574691075184056589874409068083307839797160172478651300721516338805276659138755545180317232487639129848150630629572847838818906395483459772077729297274584885396905589177781464020859622506380219130192216752486653948512649231669200598942270289885832535089179147765734679446339916180559944786135586908378092664902113447761773375789432041764945404647607097742221297253810432073697458940830180324434881602711959842447341970054228846565303599057331236420571347234474139019422400429010402259670317309507449796490347864859684680814407563282464047759197265554711767207514512625408395552553670776782206106276915629475337818995132641927741914351650986583007965150066284265547114011157111779827087174025610907926527400079071022768903159131501249508348309671914209073255212696142436820530821139286377399446782687324660174555034439875378737066968477463750798919722673383632483105040594773065311633355586044378015905094878523589437077788246285538985941404802828899012143327065126509798268958933455497358942904079514797758315000371465379721354157664601577832012287739403788683653745919813667705694855127197670950049914829017119184604323649568120498718488871277835278145859518126846782433441017333549012139441843135740177371028563670623868555841715033180756356569614285337848385872431173353072444491380467005016175953423406506582496970249093356761613450882357520134703303390072220160882937829617742073888595885748536572681682888337355047618761483183186585901228316333553135542062567554607420907134496443984577439918860583054657564077763689472849320652611535678435340258501481587254763848269263162987032963553802885106077146140886129168129307498933474625972537236393100834203179141205887335842853743054369100998784866789186115254641474625323701483919104631843411566150848901765516726823425473337148238848602605829414056570681452320125256226244665639844102529883417609863398257427543535109666977848130315175874009540534605802753487192997024055629357494608289988513424589777094401686514369254342858456797081524626207474850952339111394583589890868414885499311141023797982427215020425849682516864167971759748157356338261476526756638920195576436716905281152668038776036006307884191661772679012993051409623805607517205728197423809695524242997260154496562348058615715711573559194550269573071202566396522318271184819367192631768371024184929776355422998814073055526663889383129277599593328635010699576594898084699081574031249329631844908024706407740150265264464767185173609014209936445203647321124600443813534386328471573265126021213717546116315374711166869019673159115918167859711347583650921590410033497871527515657314027688984488684001103598906216459754538696239012071923531696829683707508577378583990046080995443610228567211931291886443930452500288221603355112367729483067655980678063808301467334448205617796899454815113205420493555508730268622028695412849844974518736141914681509927768525543652647989659134210446451196259221857920309429800619235884156600900040652400624455871252094460001225767045599638527301022983454119618146569514566151633660500376359235185648081937164287925383

Answer 4

EEEDDDIIITTT: Los cinco (primitivamente representado) más pequeño de los valores positivos y cinco negativo menor (en valor absoluto). El método se completa por el tiempo de Lagrange, no utiliza la memoria de la computadora a todos, sin decimales de precisión (sólo operaciones con números enteros), sin ciclo de detección, no conjeturas. También tarda alrededor de un minuto de tiempo humano para ir a través de todo el ciclo de 3,861,006 vecinos formas. $$-1521, \; -1089, \; -900, \; -729, \; -225, \; 495, \; 621, \; 1053, \; 1395, \; 1845.$$

EDIT: he publicado una prueba de la "riverbend" de la propiedad en Generar soluciones de la ecuación Cuadrática Ecuación Diophantine

EEDDIITT:: que una parte considerable del material necesario es en BUCHMANN_VOLLMER, especialmente un (revisado) sobre el método de Lagrange en las páginas 129-130, y el hecho de que el mínimo se produce en el ciclo es Corolario 6.16.2 en la página 139. Por alguna razón que no demuestran la completa teorema de Lagrange, que todos los pequeños valores que son primitivamente representado ocurrir como coeficientes de las formas en el ciclo. No es mi culpa.

Finalmente me escribió una implementación de Lagrange del ciclo método con todo en C++ utilizando GMP enteros. Aquí es lo que sucede, sólo que son las formas impresas que lograr una nueva baja en valor absoluto, una comparación de los valores negativos y uno positivo. El punto clave es la del teorema de Lagrange, en la página 111, Teorema de 85, en Introducción a la Teoría de los Números por Leonard Eugene Dickson, que, dado y de forma indefinida $\langle a,b,c \rangle$ o $f(x,y) = a x^2 + b x y + c y^2,$ con discriminante $\Delta = b^2 - 4 a c$ positiva, pero no un cuadrado, a continuación, todos los números enteros de $n$ con $|n| < \frac{1}{2} \sqrt \Delta$ primitivamente representado por $f(x,y)$ ocurrir como el primer coeficiente de la cadena de formas reducidas equivalente a $f.$ Una comparación de Lagrange del método, puesto brevemente en las páginas 21 a 24 de la Formas Cuadráticas Binarias por Duncan A. Buell, con Conway topograph método, revela que Lagrange formas reducidas son precisamente los que tienen $$ ac < 0, \; \; b > |a+c| a $$ y que, además, estos son precisamente los lugares donde las formas "cruzar el río". Marty Weissmann llama a estas riverbends.
Para el ejemplo de abajo, el discriminante y el piso de la raíz cuadrada de que se DISCRIMINANTE 487730524450541076 DISCO 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:~$ 

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

Aquí están las páginas 99 y 111 de Dickson Introducción del libro:

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

También puse en algunos comandos personalizados, aquí están los cinco positivo menor (primitivamente representado) y los valores de los cinco negativo menor (en valor absoluto). También le dije a mostrar las primeras 20 filas y los valores de $\delta$ que muestran cómo calcular el siguiente "derecho vecinos", dado $\langle a,b,c \rangle$ el nuevo formulario es de $ \langle c, a-b + 2 c \delta, a - b \delta + c \delta^2 \rangle .$

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

revisado salida

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

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