mersenneforum.org > Math Prime-generating polynomials
 Register FAQ Search Today's Posts Mark Forums Read

 2003-08-07, 20:37 #1 Orgasmic Troll Cranksta Rap Ayatollah     Jul 2003 641 Posts Prime-generating polynomials Could someone give me the details of the proof that there is no polynomial with integer coefficients that generates only primes? I think it was Goldbach who proved it, but I can't find any details of the proof online. I asked someone about it and he said that you use the fact that f(f(0)) is divisible by f(0), but what if f(f(0)) = f(0)?
 2003-08-08, 00:42 #2 ewmayer ∂2ω=0     Sep 2002 República de California 3×3,877 Posts Page 38 of Riesel, 2nd edition. It's a one-page proof, but too long for me to want to retype it here. If you're interested in number theory, it's one of the short list of books I consider must-haves.
 2003-08-08, 05:38 #3 Orgasmic Troll Cranksta Rap Ayatollah     Jul 2003 641 Posts Unfortunately, all my money is going towards studying and taking an actuarial exam and the local library doesn't have a copy, the local college has an older copy though .. hmm .. or I could drive 45 minutes to Davis .. In the meantime, if anyone could write up the proof or point me to another resource that would have it (the local library does have Hardy and Wright if the proof is in there) I would appreciate it! and thanks for the pointer, ewmayer
 2003-08-08, 07:47 #4 c00ler   Jul 2003 52 Posts Very short proof by contradiction: f(x) generates only primes. n-degree of f(x), so n>0 f(x)>1 for integer x (it must be prime). So f(0)>1, f(0) is prime. Then f(k*f(0)) is divisible by f(0) (k and x are integers). If there exists integer k: f(k*f(0))<>f(0) then f(k*f(0)) is not prime else there are more than n solutions of f(x*f(0))=f(0) so f(x*f(0)) is constant(equal to f(0)) and f(x) is that constant too so n=0. It's contradiction with n>0.
2003-08-08, 11:43   #5
toferc

Aug 2002

2×3×5 Posts

Quote:
 Originally Posted by c00ler Very short proof by contradiction: f(x) generates only primes. n-degree of f(x), so n>0 f(x)>1 for integer x (it must be prime). So f(0)>1, f(0) is prime. Then f(k*f(0)) is divisible by f(0) (k and x are integers). <snip>
Consider f(x) = 1.5x + 2.
f(0) = 2 (prime)
f(1*2) = 5 (not divisible by 2)

2003-08-08, 11:47   #6
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

1068310 Posts

Quote:
Originally Posted by toferc
Quote:
 Originally Posted by c00ler Very short proof by contradiction: f(x) generates only primes. n-degree of f(x), so n>0 f(x)>1 for integer x (it must be prime). So f(0)>1, f(0) is prime. Then f(k*f(0)) is divisible by f(0) (k and x are integers). <snip>
Consider f(x) = 1.5x + 2.
f(0) = 2 (prime)
f(1*2) = 5 (not divisible by 2)
Read up a few messages to find the phrase "with integer coefficients".

Paul

 2003-08-08, 14:05 #7 Orgasmic Troll Cranksta Rap Ayatollah     Jul 2003 641 Posts thanks cooler, the reason I wanted to know the proof is because I was wondering if it could be extended to show that there are no semiprime-generating polynomials too, and it looks to me like it does.
 2003-09-14, 03:40 #8 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 2·3·397 Posts I've read in a book that f(x) = x2 + x + 41 is a very good prime-generating polynomial.
 2003-09-14, 07:24 #9 andi314     Nov 2002 2×37 Posts yes, but it only works in the interval [1;39] greetz andi314
 2003-09-14, 09:01 #10 HiddenWarrior     Jun 2003 Russia, Novosibirsk 2×107 Posts I was thinking about polynomials that can generate Mersenne primes and I made some interesting investigations. I used La Grange interpolations and at the end of my research i came to the matrixes and Pifagor triangle. All my mathematical researches I'll put on my site next week! It's very interesting, but need some CPU work (to calculate matrix 40*41)! Now I'm approaching only to the 15th Mersenne prime... When i'll calculate 38 Mprime, I'll be able to predict 39th and then 40th! But still need some time to accomplish calculations...
2003-10-21, 13:52   #11
HiddenWarrior

Jun 2003
Russia, Novosibirsk

2·107 Posts

Quote:
 [i]OK, some accomplished calculations: [/B]
To get all primes from 1 to 38 You only have to put natural numbers from 1 to 38 instead of X (in 1..38:). Also I place here all available (for now) polynominals for those people who are interested in searching connections between polynominals. Maybe it'll give us possibility to predict 40th Mersenne Prime!!!

Here we go:

1..1: Y=X+1
1..2: Y=X+1
1..3: Y=[1*X^2+-1*X^1+4]/6
1..4: Y=[-1*X^3+9*X^2+-14*X^1+18]/24
1..5: Y=[5*X^4+-54*X^3+211*X^2+-306*X^1+192]/120
1..6: Y=[-15*X^5+250*X^4+-1545*X^3+4430*X^2+-5640*X^1+2760]/720
1..7: Y=[31*X^6+-741*X^5+6925*X^4+-32055*X^3+76924*X^2+-88524*X^1+38880]/5040
1..8: Y=[-41*X^7+1365*X^6+-18389*X^5+128835*X^4+-501914*X^3+1076880*X^2+-1155456*X^1+478800]/40320
1..9: Y=[29*X^8+-1372*X^7+26754*X^6+-278656*X^5+1681701*X^4+-5966548*X^3+12040636*X^2+-12421584*X^1+4999680]/362880
1..10: Y=[-3*X^9+396*X^8+-14958*X^7+269136*X^6+-2697723*X^5+15943284*X^4+-55869972*X^3+111883824*X^2+-114873984*X^1+46085760]/3628800
1..11: Y=[35*X^10+-1955*X^9+50160*X^8+-784830*X^7+8213415*X^6+-58549155*X^5+279025390*X^4+-853032220*X^3+1565213400*X^2+-1520742240*X^1+587865600]/39916800
1..12: Y=[-293*X^11+19723*X^10+-585530*X^9+10124070*X^8+-113358069*X^7+863152059*X^6+-4552524460*X^5+16546028180*X^4+-40223970688*X^3+61436314368*X^2+-52047509760*X^1+18162144000]/479001600
1..13: Y=[1405*X^12+-113106*X^11+4054061*X^10+-85383210*X^9+1174484355*X^8+-11092217598*X^7+73569099263*X^6+-344158854270*X^5+1121927942740*X^4+-2469378565896*X^3+3451076942976*X^2+-2713022363520*X^1+890942976000]/6227020800
1..14: Y=[-6909*X^13+646984*X^12+-27247857*X^11+682050512*X^10+-11297115687*X^9+130438929192*X^8+-1077165820731*X^7+6421024534496*X^6+-27523309797984*X^5+83382838505824*X^4+-172449641496912*X^3+228620718398592*X^2+-172086552933120*X^1+54604745395200]/87178291200
1..15: Y=[33587*X^14+-3623361*X^13+177160711*X^12+-5195326773*X^11+101904459657*X^10+-1411367000043*X^9+14199985921693*X^8+-105142309431159*X^7+573860272665680*X^6+-2288478836539896*X^5+6531929309055696*X^4+-12859491270011568*X^3+16372060426094976*X^2+-11929972438944000*X^1+3692523702067200]/1307674368000
1..16: Y=[-144959*X^15+17898885*X^14+-1008180635*X^13+34316456265*X^12+-788174207093*X^11+12916325597175*X^10+-155706335375305*X^9+1402769336077395*X^8+-9496408550340712*X^7+48153184706947320*X^6+-180688241518308160*X^5+490355895400665840*X^4+-925949409280796736*X^3+1139371662003621120*X^2+-807950316133094400*X^1+244947024241920000]/20922789888000
1..17: Y=[541393*X^16+-75948792*X^15+4888222660*X^14+-191368976400*X^13+5093528052886*X^12+-97583735331264*X^11+1389621925122860*X^10+-14974286303262000*X^9+123118058032189649*X^8+-772866863398525896*X^7+3680180344614355400*X^6+-13102532239001150400*X^5+34030713163321773072*X^4+-61958474245665042048*X^3+73989227001160846080*X^2+-51222250406047795200*X^1+15246604373704704000]/355687428096000
1..18: Y=[-1767335*X^17+279605936*X^16+-20399555484*X^15+910530685520*X^14+-27813188347770*X^13+616173334121072*X^12+-10236193954245428*X^11+130021900892231920*X^10+-1275949761165134055*X^9+9706872270331913248*X^8+-57095619387402660792*X^7+257373692142097148800*X^6+-874912018497669603440*X^5+2185559672871473823744*X^4+-3851540267468645719296*X^3+4477198615490422517760*X^2+-3032945776329102950400*X^1+887811115087024128000]/6402373705728000
1..19: Y=[5120313*X^18+-907385553*X^17+74495073006*X^16+-3760914973860*X^15+130694508335646*X^14+-3315730598145126*X^13+63558646138185432*X^12+-939808480784525820*X^11+10848170027271900609*X^10+-98290757620475165889*X^9+699134590170032720418*X^8+-3884454787980457880280*X^7+16681463194311358903392*X^6+-54414601232457051468432*X^5+131253339562948557738144*X^4+-224582035886463490007040*X^3+254742938833322798231040*X^2+-169170206830816762368000*X^1+48762757387863687168000]/121645100408832000
1..20: Y=[-13327575*X^19+2629525197*X^18+-241343499132*X^17+13684105553364*X^16+-536815601089290*X^15+15463479376269774*X^14+-338785506288604644*X^13+5769010297911165708*X^12+-77367005635908071655*X^11+822924034480328029821*X^10+-6957619233648694679016*X^9+46653922566131054379192*X^8+-246445209477880219457520*X^7+1013458909823556283418448*X^6+-3185344344252084176222208*X^5+7443472058898599659124736*X^4+-12398426439979890991656960*X^3+13751062164684629092085760*X^2+-8965950791383605583872000*X^1+2547726589450649198592000]/2432902008176640000
1..21: Y=[31407173*X^20+-6862057830*X^19+700049375335*X^18+-44300975367690*X^17+1948562136823938*X^16+-63257925040107660*X^15+1570951368825297470*X^14+-30523024904598511380*X^13+470604032230074582073*X^12+-5805687408280341761790*X^11+57524458969205569849755*X^10+-457693351166968737211170*X^9+2912698071255669064272848*X^8+-14707013781047667140211120*X^7+58166574519871365790480240*X^6+-176772066401678787790889760*X^5+401314387633230451905283968*X^4+-652208093087160336195801600*X^3+708558313926723552211507200*X^2+-454224369078254042634240000*X^1+127365106051864131010560000]/51090942171709440000
1..22: Y=[-67229827*X^21+16189640670*X^20+-1826529635105*X^19+128303645502690*X^18+-6290003035930782*X^17+228636755358073020*X^16+-6390127837515049810*X^15+140538769268367896580*X^14+-2468869195378814879567*X^13+34966200347082759515670*X^12+-401247524321035075266765*X^11+3735891107350327596458970*X^10+-28168277339761065211899712*X^9+171086128920596232437671920*X^8+-829519058849505998871647120*X^7+3167101250172233095472422560*X^6+-9335140096828617626434250112*X^5+20640907285432846835350878720*X^4+-32795914434765501094151731200*X^3+34956695758636036756327219200*X^2+-22059918159041915161067520000*X^1+6109502430560176696688640000]/1124000727777607680000
1..23: Y=[130657103*X^22+-34535303253*X^21+4289865494761*X^20+-332896719679755*X^19+18096054704693658*X^18+-732353423782424598*X^17+22893102536393368466*X^16+-566014243103568259110*X^15+11242558731734530421683*X^14+-181215893812157617002513*X^13+2384576162272285507223061*X^12+-25683081974632444954807215*X^11+226334555237600603931472148*X^10+-1626728801029266173351659668*X^9+9475469442145828219243927936*X^8+-44292251533282727054033904720*X^7+163789612331057313993590899008*X^6+-469520897969048484546926059968*X^5+1013406808612946536415328235776*X^4+-1577142308879005699309737139200*X^3+1651785858527988697947075686400*X^2+-1027346157349662912446361600000*X^1+281267732333637735066501120000]/25852016738884976640000
1..24: Y=[-230021511*X^23+66491050405*X^22+-9058064779005*X^21+773268473324039*X^20+-46397737848523446*X^19+2080338890265633690*X^18+-72342900848651808210*X^17+1998814818737847235774*X^16+-44593958174574547635171*X^15+812021196174479362742825*X^14+-12150127511440110647233065*X^13+149926187737846135112789019*X^12+-1526986776559737513618532176*X^11+12815200005930130439227528360*X^10+-88245940665553939586863077720*X^9+495054042367889043654902963984*X^8+-2238920049533089927092142735296*X^7+8042979508444440192956714603520*X^6+-22479365454702116078954409552000*X^5+47461836841198455064336180637184*X^4+-72474115022931707440505327462400*X^3+74688672171358406452139902771200*X^2+-45835000598827313999814205440000*X^1+12415677796349282688462028800000]/620448401733239439360000
1..25: Y=[368398881*X^24+-116040180564*X^23+17271157596270*X^22+-1615467308091120*X^21+106535962488833031*X^20+-5267921866577805204*X^19+202779965567668266360*X^18+-6227463261018890777040*X^17+155133883010566096334511*X^16+-3170344618208576776868604*X^15+53545847411076010587625350*X^14+-750701771222152571963008560*X^13+8752477061608715144212354521*X^12+-84823546451385307694422325724*X^11+681469596869086566507601541940*X^10+-4515581077690094800968388715280*X^9+24487426317554152160094940102896*X^8+-107484179920952792793406072375104*X^7+376092656966656356628785698105280*X^6+-1027159561014554378784714995808000*X^5+2125473324570567683518791153116160*X^4+-3189603578664827645127632750284800*X^3+3238676234998930256448656174284800*X^2+-1963120203314248305691225128960000*X^1+526548764029146654488380047360000]/15511210043330985984000000
1..26: Y=[-559293143*X^25+190980243500*X^24+-30893626321250*X^23+3149244498458000*X^22+-227014691974338785*X^21+12309586555410197900*X^20+-521430050528630441000*X^19+17689354843792540634000*X^18+-488839220367304829481305*X^17+11133919052155677147368900*X^16+-210671010101897125142770250*X^15+3328260429319561902050570000*X^14+-44017362831063749605007565695*X^13+487577203150989451469802440900*X^12+-4516722829171021244343815439500*X^11+34868131946859050940040138946000*X^10+-223030063188573858519158096453840*X^9+1172244643563564939988794230302400*X^8+-5005071328832774864388265208040000*X^7+17090621838943299868820073643872000*X^6+-45685103660791319979142482129887232*X^5+92776256607634944289404401529446400*X^4+-136977887190015152068621488703488000*X^3+137164776829429754021545504235520000*X^2+-82182638260527428980249595412480000*X^1+21839032517596419702489808896000000]/403291461126605635584000000

 Similar Threads Thread Thread Starter Forum Replies Last Post Brownfox Msieve 7 2018-04-06 16:24 carpetpool carpetpool 24 2017-10-29 23:47 bhelmes Computer Science & Computational Number Theory 122 2017-08-25 21:09 Orgasmic Troll Math 61 2017-04-05 19:28 Citrix Open Projects 18 2013-08-24 05:24

All times are UTC. The time now is 00:26.

Sun May 16 00:26:47 UTC 2021 up 37 days, 19:07, 0 users, load averages: 1.45, 1.73, 1.62