Первые 100

[nnosipov]

Эпиграф. Этимъ полукресломъ мастер Гамбсъ начинаетъ новую партiю мебели. 1865 г. Санктъ-Петербургъ. И. Ильф, Е. Петров. Двенадцать стульев.

Рассмотрим рациональное выражение

$$\frac{(a+b+1)^2}{ab}$$

с двумя переменными $a$ и $b$, принимающими только натуральные (целые положительные) значения. Легко найти множество всех целых значений этого выражения, и оно оказывается конечным --- это $\{5,6,8,9\}$. А каким будет, к примеру, множество полуцелых значений этого выражения? Вот несколько примеров полуцелых значений: $75/2$, $81/2$, $121/2$. Гипотетически множество полуцелых значений бесконечно, однако непонятно, как это доказать (мне удалось это сделать лишь по модулю другой недоказанной гипотезы, правда, довольно правдоподобной).

В настоящей задаче предлагается найти первые 100 полуцелых значений указанного выражения. Честно говоря, я не уверен, что это возможно (однако прошу строго не судить, ибо тема все-таки юбилейная). В чем могут быть проблемы? Вот, например, есть такое возможное полуцелое значение как $2025/2$ (хорошо бы заодно определить его номер в списке полуцелых значений, мне он неизвестен). Но как это подтвердить? Дело в том, что наименьшая пара $(a,b)$, доставляющая это значение, выглядит, мягко говоря, не очень оптимистично:

$$ \begin{array}{l} a=44999539709699302763081486345495779014689601386888,\\ b=44531997802090968110207001909255304366066384401. \end{array} $$

Остается уповать на системы компьютерной алгебры и мощные компьютеры. Ну и, естественно, спортивный интерес участников форума.

ЗЫ. К модераторам: видимо, я ошибся с выбором раздела и по привычке запостил в "Олимпиадную математику". А нужно, наверное, в раздел "Загадки, головоломки и ребусы". Или еще куда-нибудь.

[dmd]

Пусть $\dfrac{(a+b+1)^2}{ab}=\dfrac{d}{2}$

Для удобства решения Пелля перейдем к переменным $u,v$:

$a = u + v - 1, b = u - v$

Тогда получается нужно решать $d u + 8 u^2 - d u^2 - d v + d v^2=0$ или

$d (d - 8) (2 v - 1)^2 + 8 d = (2 (d - 8) u - d)^2$

(код (неверный) pari/gp)

nno()=
{
 forstep(d=9, 200, 2,

   D= d*(d-8);

   Q= iferr(bnfinit('X^2-D), E, 0); 

   if(Q,

    U= iferr(Q.fu, E, 0);

    if(U, for(j=1, #U, u= U[j];

     u1= abs(polcoeff(lift(u), 1)); u0= abs(polcoeff(lift(u), 0));

     if(u1==floor(u1) && u0==floor(u0),

      N= iferr(bnfisintnorm(Q, 8*d), E, 0);

      if(N, for(k=1, #N, n= N[k]; 

       for(l=0, 48,

        nu= lift(n*u^l);

        n1= abs(polcoeff(nu, 1)); n0= abs(polcoeff(nu, 0));

        if(n1==floor(n1) && n0==floor(n0),

         a= u0; b= (u0+1)*n0/n1; c= u1;

         xc= (n0+d)/(2*(d-8)); x1= n0; y1= n1;

          if(xc==floor(xc),

           yc= (sqrtint((n0^2-8*d)/D)+1)/2;

           if(yc==floor(yc),

            u= xc; v= yc;

            a= u+v-1; b= u-v;

            print("d = ",d,"\na = ",a,"\nb = ",b,"\n");

            break(2)

           )

          )

        )
       )
      ))
     ))
    ))

 ) 
};

(решения (неверные) для d=9..200)

? \r nno.gp
? nno()
d = 11
a = 32
b = 11

d = 13
a = 441
b = 104

d = 15
a = 125
b = 24

d = 19
a = 16928
b = 2299

d = 21
a = 1875
b = 224

d = 37
a = 9334071769
b = 567794600

d = 39
a = 128354043
b = 7358624

d = 41
a = 5209992
b = 282449

d = 51
a = 2738592032
b = 116747619

d = 55
a = 9153643499
b = 359520160

d = 59
a = 96845765408
b = 3526333299

d = 61
a = 4876734638889
b = 171324682472

d = 67
a = 564554169021624608
b = 17940453408620163

d = 73
a = 3723365000
b = 108014449

d = 87
a = 193993733784725
b = 4677265168344

d = 91
a = 1128462776
b = 25955397

d = 97
a = 31020426188960072
b = 667414749214233

d = 105
a = 703473504
b = 13935635

d = 107
a = 383111521369877792
b = 7441865594921403

d = 109
a = 113065350979092897555034936310863849
b = 2154407661233853450750040295345000

d = 111
a = 15109083136080760844326347
b = 282511506003301267093664

d = 115
a = 19859363064
b = 357942605

d = 131
a = 6247623011067247392
b = 98412176278115171

d = 137
a = 12112786057352
b = 182188366193

d = 145
a = 535702322783430461000
b = 7600143942440924449

d = 157
a = 1710338798771660541436099888157549752489
b = 22361191528014475670985956691669415400

d = 159
a = 2267676772140210004241605133
b = 29265218719445549747111064

d = 165
a = 255880667077739
b = 3179132490720

d = 171
a = 3358369206912209791623200
b = 40225760738495091683019

d = 179
a = 202893076658639648
b = 2319080958898859

d = 181
a = 164752441696780427577477895620593179465777780290807467508747721
b = 1861847256560739726576340520676312054043333949336214974939432

d = 187
a = 2942300812222903328
b = 32160134766085227

d = 189
a = 2139004991316843
b = 23127081546464

d = 193
a = 35947767748317905301704
b = 380442265008495704001

?

В коде точно где-то ошибка. Быть может сумеем вместе подправить программку?

[nnosipov]

dmd
А какой командой в PARI решаются уравнения Пелля (или вообще уравнения 2-й степени)? Если такая опция есть, то, в самом деле, давать ей последовательно нечетные значения $d$ и смотреть, что она выдает.

Здесь проблема вот в чем будет: при любом $d$ есть решения в целых числах (например, $(a,b)=(0,-1)$), но вот в натуральных числах --- отнюдь не при любом. Как отфильтровывать такие случаи?

[dmd]

уравнения X^2=D*Y^2+N решаются командами Q= bnfinit('X^2-D) и bnfisintnorm(Q, N). Дальше вывод этих команд нужно правильно отфильтровать.

[nnosipov]

dmd
Спасибо, будем думать.

-- Пт апр 26, 2019 17:51:05 --

nnosipov в сообщении #1389497 писал(а):

Вот несколько первых полуцелых значений: $75/2$, $81/2$, $121/2$.

На самом деле начало списка таково: $11,13,15,17,19,21,25,27,33,35,45,49,75,81,121,\ldots$ (указаны числители).

[dmd]

(Оффтоп)

одну глупую ошибку нашел:

- u= xc; v= yc;
- a= u+v-1; b= u-v;
- print("d = ",d,"\na = ",a,"\nb = ",b,"\n");

+ print("d = ",d,"\na = ",xc+yc-1,"\nb = ",xc-yc,"\n");

но код всё равно не верный

-- Пт апр 26, 2019 16:43:47 --

хотя для d=41 правильно посчиталось, проверил в Вольфраме
d = 41
a = 5209992
b = 282449

Ориентировался на d=2025 для которого ответ не посчитался, вот и подумал что код не верный. Может таки верный? Просто все d в Вольфраме не проверить, не знаю как.

[nnosipov]

dmd в сообщении #1389543 писал(а):

хотя для d=41 правильно посчиталось, проверил в Вольфраме
d = 41
a = 5209992
b = 282449

Так, выясняется, что у меня много значений в первой сотни пропущено (что неудивительно, так как я считал примитивно, перебором до какой-то границы). Но и Вас почему-то отсутствуют значения $d=17,25,27,33,35,45,49,75,81$ (здесь есть решения с $a+b+1<130000$). Т.е., с кодом что-то не так по-прежнему. С другой стороны, появилась надежда, что задача все-таки решаема.

[dmd]

nnosipov

а теперь правильные значения?:

(d=9..595, 2025)

d = 11
a = 11
b = 32

d = 13
a = 104
b = 441

d = 17
a = 153
b = 968

d = 19
a = 2299
b = 16928

d = 21
a = 27
b = 224

d = 33
a = 7776
b = 112211

d = 35
a = 2645
b = 40824

d = 37
a = 567794600
b = 9334071769

d = 39
a = 421875
b = 7358624

d = 41
a = 282449
b = 5209992

d = 45
a = 1000
b = 20449

d = 49
a = 200
b = 4489

d = 51
a = 116747619
b = 2738592032

d = 55
a = 14120579
b = 359520160

d = 57
a = 1124192
b = 29748603

d = 59
a = 3526333299
b = 96845765408

d = 61
a = 171324682472
b = 4876734638889

d = 67
a = 17940453408620163
b = 564554169021624608

d = 73
a = 3723365000
b = 128348078049

d = 75
a = 30752
b = 1090827

d = 81
a = 3249
b = 125000

d = 87
a = 112770701549
b = 4677265168344

d = 91
a = 25955397
b = 1128462776

d = 97
a = 667414749214233
b = 31020426188960072

d = 105
a = 13935635
b = 703473504

d = 107
a = 7441865594921403
b = 383111521369877792

d = 109
a = 2154407661233853450750040295345000
b = 113065350979092897555034936310863849

d = 111
a = 5282435095856945184675
b = 282511506003301267093664

d = 115
a = 357942605
b = 19859363064

d = 121
a = 729
b = 42632

d = 129
a = 24254768741745993179097800
b = 1515534870660825357282546129

d = 131
a = 98412176278115171
b = 6247623011067247392

d = 133
a = 3858575061364366419
b = 248818254202282931936

d = 137
a = 182188366193
b = 12112786057352

d = 145
a = 535702322783430461000
b = 37759413612289406576049

d = 153
a = 866761
b = 64562056

d = 157
a = 22361191528014475670985956691669415400
b = 1710338798771660541436099888157549752489

d = 159
a = 377678616820101159502325
b = 29265218719445549747111064

d = 165
a = 39498425219
b = 3179132490720

d = 171
a = 40225760738495091683019
b = 3358369206912209791623200

d = 181
a = 1861847256560739726576340520676312054043333949336214974939432
b = 164752441696780427577477895620593179465777780290807467508747721

d = 187
a = 32160134766085227
b = 2942300812222903328

d = 189
a = 23127081546464
b = 2139004991316843

d = 193
a = 380442265008495704001
b = 35947767748317905301704

d = 201
a = 19211041587
b = 1892092540256

d = 209
a = 1324333742372077358038323569
b = 135731287033934362913695177800

d = 215
a = 2390222548822205
b = 252145820726927064

d = 219
a = 122339372939836773379618466079099
b = 13150344451858524716504546148020000

d = 221
a = 877073248204425
b = 95154363118988264

d = 229
a = 3622294253467082996648
b = 407475902799449776373929

d = 231
a = 7776906178135325
b = 882610326901500504

d = 235
a = 6887554669537751929962508805
b = 795452927352859463486722908984

d = 237
a = 2236557889444268900406233003006875495827
b = 260539794783752946817916768646155622876128

d = 241
a = 118856710300224437001
b = 14083517088924889569992

d = 247
a = 157115770484112998899894988020053
b = 19088272892297064627233240953811672

d = 249
a = 349705210726948388674469010159563
b = 42836033387375225814924760603511904

d = 257
a = 9203423751441066554610993
b = 1164160345672263771329284808

d = 265
a = 172755731224106120
b = 22543299048297825889

d = 275
a = 30706384928
b = 4160488530011

d = 277
a = 3172245533030831241910516627752939933663990035789435684670244904
b = 432988274117265662596830740539508916676599293068228341087675859225

d = 289
a = 225991089
b = 32202144200

d = 295
a = 155558342609740952102344619
b = 22632669669708558765462759840

d = 297
a = 943483497
b = 138213891848

d = 303
a = 43949972167385472987149414720724285581
b = 6570226846122702919764399142412040525336

d = 309
a = 229547452606947967889531413996978645185943683
b = 35004481228632933845381877461952934927717060064

d = 313
a = 8164069814012593126831749896
b = 1261295942175228578003487515169

d = 315
a = 89259420361005
b = 13879265826830264

d = 319
a = 822189886257949737878437569425791957229
b = 129489686621922985043801683811754290491800

d = 321
a = 244325959691011562092888697964227
b = 38724123060956271849880506394153824

d = 335
a = 6727003732406814985462445
b = 1113278469681008723156232984

d = 351
a = 461742906353615067
b = 80109732821536524704

d = 357
a = 1085365782768216223422542393
b = 191560911079974345229886173608

d = 361
a = 644809
b = 115094792

d = 373
a = 4029563253490403919708066776037764184185547695225957833572302344776761877988136
b = 743432579176096729272129855302884358371281795903197474200640675391135725185967529

d = 375
a = 18115986245
b = 3360417785304

d = 393
a = 110236958791475
b = 21440521698962784

d = 397
a = 279090849100458828986765816181911277661004651681407229048190406968828433878082664
b = 54839931501789707581312938381419335062829160005399382778164521885803868435684284025

d = 399
a = 419370860121673347909
b = 82823621422830238244888

d = 409
a = 2787514027738404770346782312360808227041732147246229597863845397665800
b = 564457824779946281344108072646537860365475036473569614153492038836423329

d = 417
a = 37420823275579763809477998382364187
b = 7727218787516812123493273261125095008

d = 425
a = 45762194161646425352
b = 9632724468523123862457

d = 427
a = 28169555115515778557676820272230386579037149
b = 5957727714568084931789439122568123605291315000

d = 435
a = 14465262245663045
b = 3117196888308180984

d = 441
a = 965957578330593032
b = 211057309914150183201

d = 445
a = 139978197736681180384768769
b = 30864557766122484365160609640

d = 455
a = 22789398859931734835
b = 5138908379291349182624

d = 457
a = 8081330774897360212642705283795207003682483835250558600
b = 1830385740654186109994611117803872329657829758495716846769

d = 465
a = 1033662214412448546384264127089222904355
b = 238254655902891978652974959444025016474464

d = 467
a = 23338708160015696880689125330592118111579366456336237772567888051142883
b = 5402810122008372943110624096201462993107975794585525479199922717789594912

d = 471
a = 30980343291635250618147
b = 7233777478033545503459744

d = 483
a = 34875060794916235928774015864
b = 8352431441723496465156860515725

d = 495
a = 9464807396844679778379403877099092908960
b = 2323571662098723206864529410945304304090259

d = 507
a = 180494739488
b = 45393709296963

d = 529
a = 253062813819848
b = 66428024564904409

d = 539
a = 8463979104800
b = 2264082769048419

d = 541
a = 677934390806237380672388392140755878912866007057504024680392660442827491077043369396
52842472
b = 182022859001140382689607917791010210189463076178868598272499465984956909059369288824
37427944729

d = 551
a = 2303712623314180112753300575369781013309
b = 630056979282930972525021916232115356445272

d = 565
a = 244551123194518742930347203596115892933210246871859810777737000
b = 68595718204970038364504690477985748642586591835475551077591198649

d = 585
a = 4187765238409
b = 1216531385871880

d = 595
a = 14272757400601510181168186666674269429515
b = 4217551510961139314410904106059903839251744

.
.
.

d = 2025
a = 44999539709699302763081486345495779014689601386888
b = 45471990344653343351125731745121575439039476135065921

только для d=2025 почему-то значение b отличается от Вашего

[nnosipov]

dmd
Буду проверять, надеюсь, что да. В принципе, технология понятна, просто руки не доходили, а с Вашей помощью дело сдвинулось. Спасибо!

Другое значение $b$ --- это потому, что при фиксированном $a$ уравнение квадратное, есть два корня (у Вас нашелся больший).

[Yadryara]

nnosipov, с активным возвращением Вас!

nnosipov в сообщении #1389537 писал(а):

На самом деле начало списка таково: $11,13,15,17,19,21,25,27,33,35,45,49,75,81,121,\ldots$ (указаны числители).

А $9$-ка чем не годится? $a=8$, $b=9$.

[nnosipov]

Yadryara в сообщении #1389582 писал(а):

с активным возвращением Вас!

Спасибо! За годы отсутствия накопилось, вот и ... Приятно, что здесь народ такой отзывчивый, на других форумах вообще никакой реакции.

Yadryara в сообщении #1389582 писал(а):

А $9$-ка чем не годится? $a=8$, $b=9$.

А здесь не Пелль (конечное число решений в целых числах $a$, $b$, единственный такой случай).

[dmd]

(более корректный код)

nno()=
{
 forstep(d=11, 2025, 2,

   D= d*(d-8); D2= 2*(d-8); D8= d*8;

   Q= iferr(bnfinit('X^2-D), E, 0); 

   if(Q,

    U= iferr(Q.fu, E, 0);

    if(U, for(j=1, #U, u= U[j]; \\print(u);

      N= iferr(bnfisintnorm(Q, D8), E, 0); \\print(N);

      if(N, for(k=1, #N, n= N[k];

       for(l=0, 48, \\print("\n",l);

        nu= lift(n*u^l); \\print(nu);

        n0= abs(polcoeff(nu, 0));

        if(n0==floor(n0),

         xc= (n0+d)/D2; yc0= (n0^2-D8)/D;

         if(xc==floor(xc) && yc0==floor(yc0),

          yc= (sqrtint(yc0)+1)/2;

          if(yc==floor(yc),

           a= xc-yc; b= xc+yc-1;

           b0= (a*(d-4)-4-sqrtint(a*d*(a*(d-8)-8)))/4;

           if(b0==floor(b0) && b0<a,

            b= a; a= b0;

            print("d = ",d,"\na = ",a,"\nb = ",b,"\n");

            break(2)

           )
          )
         )
        )
       )
      ))
    ))
   )
 ) 
};

[nnosipov]

Для данного нечетного $d \geqslant 11$ алгоритм проверки разрешимости уравнения

$$\frac{(a+b+1)^2}{ab}=\frac{d}{2}\eqno(*)$$

в натуральных числах $a$, $b$ состоит в следующем. Пусть $(l_j,\pm m_j)$ --- все базисные (попарно неассоциированные) решения уравнения $l^2-(d^2-8d)m^2=8d$, включая тривиальные $(l_1,\pm m_1)=(d,\pm 1)$. Эти решения находятся исходя из условия

$$1 \leqslant m_j<2\sqrt{\frac{l_0-1}{d-8}}, \quad l_0^2-(d^2-8d)m_0^2=1, \quad l_0=\min. $$

Уравнение $(*)$ разрешимо в натуральных числах $a$, $b$ тогда и только тогда, когда имеет место хотя бы одно из сравнений

$$l_j+8 \equiv 0 \pmod{d-8}, \quad l_0l_j+8 \equiv 0 \pmod{d-8} $$

для некоторого $j \geqslant 1$.

Пример. Пусть $d=23$. Для уравнения $l^2-345m^2=184$ имеем $(l_0,m_0)=(6761,364)$. Базисные решения суть $(l_1,\pm m_1)=(23, \pm 1)$. Так как

$$l_1+8 \not\equiv 0 \pmod{d-8}, \quad l_0l_1+8 \not\equiv 0 \pmod{d-8},$$

то уравнение $(*)$ не имеет решений в натуральных числах.

Начало списка значений $d$, для которых уравнение $(*)$ не имеет решений в натуральных числах: $23,29,31,43,47,53,63,65$. Соответственно, список значений $d$, для которых есть решения в натуральных числах, начинается так: $11,13,15,17,19,21,25,27,33,35,37,39,41,45,49,51,55,57,59,61$.

[maxal]

nnosipov в сообщении #1390040 писал(а):

Начало списка значений $d$, для которых уравнение $(*)$ не имеет решений в натуральных числах: $23,29,31,43,47,53,63,65$. Соответственно, список значений $d$, для которых есть решения в натуральных числах, начинается так: $11,13,15,17,19,21,25,27,33,35,37,39,41,45,49,51,55,57,59,61$.

Имеет смысл добавить в OEIS.

[nnosipov]

maxal в сообщении #1390049 писал(а):

Имеет смысл добавить в OEIS.

Да, попробую это сделать. Надо освоиться с PARI. В Maple вытаскивать базисные решения как-то не очень удобно.