Puzzle 526. p2^2-p1^2 = n!
Puzzle 526. p2^2-p1^2 = n!One wonders what factorials are the difference of two
squared primes. One has:
7^2 - 5^2= 4!
31^2 - 29^2 = 5!;
181^2 - 179^2 = 6!;
73^2 - 17^2 = 7!
223^2 - 97^2 = 8!
What other factorials are like this?
A small search made by Carlos Rivera found that you can easily find primes as the asked by Bergot for all factorials from 9! to 20!. I won't bore you with all the details. I will give just the primes for 20!
20! = 1613360743^2- 412348007^2
I can not see any reason for not finding primes for any factorial larger than 3!
Q. Please send only your largest n! and the associated primes p2 & p1? 数据越大后面0越多 如果穷举所有的(p1,p2)对，应该可以算到100！
一个简单的算法：
p^2-q^2=n!
=> (p+q)(p-q)=n!
=> x*y=n!( p=(x+y)/2, q=(x-y)/2 )
p,q均为素数，因此，x,y除2之外，无其他公共真因子。
所以，我们只需要将n!写成素数幂连乘的形式，然后，二分素数集合，然后，再检验得到的p,q是否是素数就可以了。 n=99 :
p2=521813108076414978881066592821220402553807871740019249735831667417592777923702284173459987
p1=521813108076414978881065698571785121240959561556623220495037333429767222076297715826540013 n=128 :
p2=69411778573195187726946483386834014484665030842538924585728949147534287994492314687905651051848145983277103337
p1=69409000743505276244241810130475828364423896268004171044830666092990833949021594687905651051848145983277103337 本帖最后由 medie2005 于 2010-2-21 15:52 编辑
for 300 : found:
p2=255776988487045897543375160573676706384273241233422831993675677065212467569105449842343280310902076071572022625407678523169343853371542845351616162004608833848338235835514327007729920163102289451350017044971920815368201575929530580723184506273892825941075814790496670408289564831594448754854481513185990077339766496598715593671388138830828110744333697816290244866997372664164680585054503
p1=255776988487045897543375160573676706384273241233422831993675677065212467569105449842343280310902076071572022625407678523169343853371542845351616162004608833847739946063578996613369263246456856685906622330416897420774198409641012408065547862951532355808647200015045951408468233018679449220861302590040989720559324896598715593671388138830828110744333697816290244866997372664164680585054503
===================
for 300 : found:
p2=40341568214780603461640800391705301415655486430598336567623080307212520790085927758377107169025355836408301348205702563694272692129871467172897132523941783435199123315205267052748594870785893428791546655079586864108443936376327213178973504865253010850415589670736558333966842613083022158433359761757076491294579637943
p1=40341568214780603457847473486477242947707012632765363716147491349421181620311132468472043592692391150191072833182697051012339127809597647939143260301404716835793760631122761540020716038808128745910489893089971226436116915755994290045443822648346989149584410329263441666033157386916977841566640238242923508705420362057
===================
for 300 : found:
p2=96984480134291086401330993549078911501924104080769619426202418861726805370010454520775190683689729081128285862448859353303388763886241038545901957974865266207832632855952891486913533727146077742991125109118006417812288318319442802897577501675469813232632404908332683078015903839868821790842174374658109340341617629372088452589227009320740718751409771450823774787
p1=96984480134291086401330993549078911501924104080769619426202418861726805370010454520775190683689729081128285860870990854175212347707850082843038673644730154519586395142819644647676508499272393301472755891438660441406164656498376574132997737171661837614266164609604433587477672086520743239557825625341890659658382370627911547410772990679259281248590228549176225213
===================
for 300 : found:
p2=496477811909238551295150536078026998011397582031667453674528446232632913979948203538027625508728592483599430527018254787379877123807121454092010828809138141569668640103245928439958911499945405582147073433134345074201919325346639201618295633483351316625258788676878449464056516083038066240779952763130391918568513085402509235518150405501265720709014458773763254061933030055742148534978482100344747
p1=496477811909238551295150536078026998011397582031667453674528446232632913979948203538027625508728592483599430527018254787379877123807121454092010828809138141569668640103245928439650682708169720731014608771093234251185568849075780044721894750960690173021031313619037213536133159578942835057420321976506952571293051615725237491011707938647371519489305780397091847188633555373316068427289578291750997
===================
for 300 : found:
p2=137196548839037656885575139231444283258182791758957269787646256069872801222601399541226656570976579599520971316792859465613126733494361343962630124519391473913125040236560233391680439440632253580435835099749054513582128663746132432485595580705200165953503035737735284062001681114925706556134588097949233288108476647446514113718825349386005640652560444206461019244713776588418824277645107645487092769107100160309514913551404867592871808082027
p1=137196548839037656885575139231444283258182791758957269787646256069872801222601399541226656570976579599520971316792859465613126733494361343962630124519391473913125040236560233391680439440632253580435835099749054513582128663746132432485595580705200165953503035737735282946603681652436358399793443318552169088982655889364422457715882266250148833434168106415238610423764021159417282098038141291175639706512172494879892192857235465470374249488277
=================== 由 n! =(p_2-p_1)(p_2+p_1)>=2(p_2+p_1)>4p_1 =>3<=p_1 <(n!)/4，又 p_2=\sqrt{n!+p_1^2}，
可知对于指定的 n，其解的数目是有限的。
medie2005 给出了这么多这么大的数据，肯定是编写了非常高效的程序。
想问一下：是否存在某些无解的 n？已知的有哪些？ 无解的n应该是不存在的，因为按概率来说，几乎不可能有无解的情况。
现在我觉得可以用格雷码序来重新设计程序，也许可以算到1000! 你是穷举所有的解还是只要找出部分解就可以了？
如果只要找到任意一个解，我觉得随机构造一个应该很快的。
首先，分解n!=x*y中，由于n!是偶数，我们需要让x,y同时是偶数，而且它们中一个不是4的倍数。
也就是可以x的2的次数为1。利用这种方法构造出来的数p,q必然没有小于n的素因子，其中一个数是素数的概率估计大概在1/n,两个数都是素数概率应该在$1/{n^2}$ 对每个n只要找一个就可以了。
页:
[1]