mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-08-07, 20:37   #1
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default 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)?
Orgasmic Troll is offline   Reply With Quote
Old 2003-08-08, 00:42   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

22×3×7×139 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2003-08-08, 05:38   #3
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default

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
Orgasmic Troll is offline   Reply With Quote
Old 2003-08-08, 07:47   #4
c00ler
 
Jul 2003

52 Posts
Default

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.
c00ler is offline   Reply With Quote
Old 2003-08-08, 11:43   #5
toferc
 
Aug 2002

2×3×5 Posts
Default

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)
toferc is offline   Reply With Quote
Old 2003-08-08, 11:47   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

11×17×59 Posts
Default

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
xilman is offline   Reply With Quote
Old 2003-08-08, 14:05   #7
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default

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.
Orgasmic Troll is offline   Reply With Quote
Old 2003-09-14, 03:40   #8
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

45748 Posts
Default

I've read in a book that f(x) = x2 + x + 41 is a very good prime-generating polynomial.
ixfd64 is offline   Reply With Quote
Old 2003-09-14, 07:24   #9
andi314
 
andi314's Avatar
 
Nov 2002

2·37 Posts
Talking

yes, but it only works in the interval [1;39]

greetz andi314
andi314 is offline   Reply With Quote
Old 2003-09-14, 09:01   #10
HiddenWarrior
 
HiddenWarrior's Avatar
 
Jun 2003
Russia, Novosibirsk

2×107 Posts
Default

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...
HiddenWarrior is offline   Reply With Quote
Old 2003-10-21, 13:52   #11
HiddenWarrior
 
HiddenWarrior's Avatar
 
Jun 2003
Russia, Novosibirsk

2×107 Posts
Default

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
HiddenWarrior is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Error generating or reading NFS polynomials Brownfox Msieve 7 2018-04-06 16:24
Prime numbers norms of modulo cyclotomic polynomials carpetpool carpetpool 24 2017-10-29 23:47
prime generators for quadric irreducible polynomials bhelmes Computer Science & Computational Number Theory 122 2017-08-25 21:09
Prime generating polynomials that stop? Orgasmic Troll Math 61 2017-04-05 19:28
Prime generating series Citrix Open Projects 18 2013-08-24 05:24

All times are UTC. The time now is 05:09.


Wed Dec 8 05:09:07 UTC 2021 up 137 days, 23:38, 1 user, load averages: 1.95, 2.12, 1.85

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.