增乘法在算法优化中的作用

蔡家雄

用公式法求解特殊佩尔方程

设 \(p=4k+1\) 是素数，

求 \(x^2 - p*y^2=1\) 的最小解，

设 \(x=2p*r^2 -1\) , 求 最小的 \(r=?\) ,

使 \(y=((2p*r^2)*(2p*r^2 -2)/p)^{1/2}\) 是整数。

推论：此时，

设 \(p=4k+1\) 是素数，

求 \(x^2 - p*y^2= -1\) 的最小解，

得 \(y=r\) ,  \(x=((2p*r^2)*(2p*r^2 -2)/p)^{1/2}/(2*r)\) .

蔡家雄

Treenewbee 发表于 2023-3-15 22:12
(101, [201, 20])
(102, [101, 10])
(103, [227528, 22419])

测试梅森合数 2^9 -1=511 的性质，

求 x^2 - 511*y^2=1 的最小解，

Treenewbee

蔡家雄 发表于 2023-3-16 16:46
测试梅森合数 2^9 -1=511 的性质，

求 x^2 - 511*y^2=1 的最小解，

511, [4188548960, 185290497]

蔡家雄

Treenewbee 发表于 2023-3-16 17:45
511, [4188548960, 185290497]

测试梅森合数 2^11 -1=2047 的性质，

求 x^2 - 2047*y^2=1 的最小解，

这个计算量 比 上一个自然要大几倍，

白新岭

蔡家雄 发表于 2023-3-16 20:24
测试梅森合数 2^11 -1=2047 的性质，

求 x^2 - 2047*y^2=1 的最小解，

除了你的奇思妙想，其他的猜想，我都有能力给出判断，和结论，以及相关公式。

蔡家雄

设 \(d=2^{2n+1} -1 \) ，

求 \(x^2 - d*y^2=1\) 的最小解，

设 \(x=d*r^2+1\) , 求 最小的 \(r= ?\)

使 \(y=((d*r^2)*(d*r^2+2)/d)^{1/2}\) 是整数。

蔡家雄

设 \(d=8k+3\) 是素数，

求 \(x^2 - d*y^2=1\) 的最小解，

设 \(x=d*r^2 -1\) , 求 最小的 \(r= ?\)

使 \(y=((d*r^2)*(d*r^2 -2)/d)^{1/2}\) 是整数。

设 \(d=8k+7\) 是素数，

求 \(x^2 - d*y^2=1\) 的最小解，

设 \(x=d*r^2+1\) , 求 最小的 \(r= ?\)

使 \(y=((d*r^2)*(d*r^2+2)/d)^{1/2}\) 是整数。

蔡家雄

设 \(d=2^{2n+1} -1 \) ，

求 \(x^2 - d*y^2=1\) 的最小解，

设 \(x=d*r^2+1\) , 求 最小的 \(r= ?\)

使 \(y=((d*r^2)*(d*r^2+2)/d)^{1/2}\) 是整数。

蔡家雄

设 \(d=2^{2n+1}+11 \) ，

求 \(x^2 - d*y^2=1\) 的最小解，

设 \(x=d*r^2 -1\) , 求 最小的 \(r= ?\)

使 \(y=((d*r^2)*(d*r^2 -2)/d)^{1/2}\) 是整数。

构造正确与否，关键测试 \(d=2^{11}+11=2059\) 能否通过，，

Treenewbee

蔡家雄 发表于 2023-3-16 22:40
设 \(d=2^{2n+1} -1 \) ，

求 \(x^2 - d*y^2=1\) 的最小解，

1 (7, [8, 3])
2 (31, [1520, 273])
3 (127, [4730624, 419775])
4 (511, [4188548960, 185290497])
5 (2047, [5566204448, 123026943])
6 (8191, [137168708703221032895073625802589931406141894540466576152225731961377054107539335040, 1515606947046439809691055132298479939258772521204671748899078157656970867149893633])
7 (32767, [4989395453057620761318437024, 27563196825452342280188415])
8 (131071, [68012246112042192848000, 187859780807502143487])
9 (524287, [46997567320561778145191353610962878307987934593756793094427946763383336928816934242481086061476715595745859044117929495717576882495512013272009350122748657837297172805929900209856744164860003129102095470554027278444403614698310930195231667607295884200937188090279571190579061930767996574039047421403571939359840263187167295467057381580417022064357611621451352561562440161111807908201761856905236583371614657642824269432164359502751873003576866612568082872108067683541142293147523053373426326394532201231880879016720914034037527494035878025515276564347843206711912343432348946721305069707108143792557407643740316164224, 64906895008741122476222937583214609214243799343511042599770186693462505668024604821997293668498982744884496689072778902714164446881210975097103993081187378767551871768967055215221731508471912677599134669670778307686638503086861330068780326391434525717635311171812276918961490673285815482166096497112496202129039439516524661906563996866258177830913974661644392881180263757110495349973522174642669167999546080787182227944467163959051276031077066053223740563434912973906942490225545215546942556046567271856598842966734789024069142174111721341814056011491824374521545759295523871629793392166520592149699929568200351745])
10 (2097151, [94716390224614473408540822118113461048452313411820973215983824757335816500342324560789047374282847806009714778621972049086083922828444965267321229715897075070580677225533794783475554185165522956179202380273231115554458953955517542095864979978481990501635325801973427056692681449780979129744252153653028410826103368612341846012894446748561572667652160, 65404900180987526520505029585445844658185900613734410857615652737952867201530958096058535800003294047733713613634131099428721918752038293902093037577350108052529075142957670861394586353233358311356186212004814489737922917832914662488617368055701767664767158479023604548319172656813646225620266344943525094720499185141955249955405063452172806391807])