Prime number support

[Johannes]

While watching male lizards (http://www.stephencresswell.com/HI7G6613.jpg) fight over females and slightly salted/cheesed biscuits during my vacation I've been pondering prime numbers.

Programming BigInt_IsPrime, _NextPrime and _PreviousPrime is not difficult. It is difficult to keep those functions fast for really big numbers.
As it turns out, I think the speed is acceptable.

I did some test just now, in (interpreted) thinBasic using the module as is, and checking if 100000000003 is prime (it is) takes 1.2 seconds (first attempt was 6.8 seconds) and finding the next prime number from that point (100000000019) also takes 1.2 seconds (first attempt was 6.9 seconds). This is of course in thinBasic, not as a module. Speed should increase significantly.

Working with prime numbers below 2^32 will be quite fast and up to 2^64 (my two examples mentioned above) I think the speed will still be acceptable. Above 2^64 (where the prime factors cross the magic 32-bit line) things will be slow. But that is of course up to the user.

So far I'm thinking of implementing BigInt_IfPrime, BigInt_NextPrime, BigInt_PrevPrime and BigInt_FactPrime. The last one will return an array with the prime factors of the given Big Integer. If anybody has suggestions for more functions dealing with primes, let me know in this thread.

[Johannes]

Prime number support has been added. See the release in the sticky topic.

[zak]

Hi Johannes
how to adapt this example about prime numbers to give a meaningfull results. i got only the first one to work, the other it displayed unwanted chars, only BigInt_IsPrime are working for me


Uses "console"
Module "BigInt"
String someprime=BigInt_FromInteger(53)
Dim prime As Long
prime = BigInt_IsPrime(someprime)
PrintL prime
Dim a As String
a = BigInt_FromInteger(89)
PrintL BigInt_NextPrime(a)
Dim s As String
s="9"
Dim pf(2) As String
BigInt_FactPrime(s,pf)
PrintL pf(1)
PrintL pf(2)
s = BigInt_FromString("9")
BigInt_FactPrime(s,pf)
PrintL pf(1)
PrintL pf(2)
WaitKey

[Johannes]

Zak,

Here is the changed script. Your main problem was that it is not possible to directly print Big Integers. You always need to use BigInt_ToString. Only conversion from string to Big Integer is automatic, not the other way around.


Uses "Console"
Module "BigInt"

' Define a prime.
String someprime=BigInt_FromInteger(53)
' Find out if it really is a prime.
Dim prime As Boolean
prime = BigInt_IsPrime(someprime)
If prime Then
PrintL "Prime"
Else
PrintL "Not prime"
EndIf

' Directly print a larger prime.
Dim a As String
a = BigInt_FromInteger(89)
PrintL BigInt_ToString(BigInt_NextPrime(a))
' Variable a is still 89, not 97.
PrintL BigInt_ToString(a)

' Determine prime factors for a number.
Dim s As String
Dim i,n As Integer
s="9"
Dim pf(2) As String ' The '2' is not necessary. Dim pf() is enough.
BigInt_FactPrime(s,pf)
' Determine how many prime factors were returned.
n = UBound(pf)
' Print all prime factors using BigInt_ToString.
For i=1 to n
PrintL BigInt_ToString(pf(i))
Next i

' The next code works the same as the previous example
' because BigInt_FromString is automatic there.
s = BigInt_FromString("9")
BigInt_FactPrime(s,pf)
n = UBound(pf)
For i=1 to n
PrintL BigInt_ToString(pf(i))
Next i

WaitKey

I'll try to make proper example functions as soon as possible but that takes a lot of time and I still have to do all the bit stream stuff.

The most important thing to remember is that you cannot print a Big Integer directly. You must always use BigInt_ToString.

[zak]

prime numbers functions is a valuable addition to thinbasic, i have tried to factor this number 123456789123456789 , and the results :
3*3×7×11×13×19×3607×3803×52579 so we can feel more freedom. thank you

[danbaron]

Hi Johannes.

(I admit, this is sort of a dirty trick.)

Dan :twisted:

****************************************

Programmer's Challenge

Code and perform the numerical calculation to determine with 100% certainty if the following integer is prime.

201487636602438195784363

****************************************

[Johannes]

Well, of course I used google to see if this was a particular type of prime, and it is.

The number 201487636602438195784363 is the 12th Waggstaff prime W79. (Why not the 13th Wagstaff Prime W101? I love 13. ;))

Quoth Wikipedia (http://en.wikipedia.org/wiki/Wagstaff_prime):

Currently, the fastest algorithm for proving the primality of Wagstaff numbers is ECPP.And this is what Wikipedia has to say about elliptic curve primality testing (http://en.wikipedia.org/wiki/Elliptic_curve_primality_testing).

This would take me a year to program, assuming I am that good. So doing a BigInt_IfPrime and waiting the week (or two) would be faster.

Either way, I don't think so Dan. :)

[jack]

never cease to be amazed at the unexpected turns while surfing the net,
just now while searching for the prime number that Dan posted above
found out about sexy primes http://en.wikipedia.org/wiki/Sexy_prime

[danbaron]

Just for fun.

When someone gets some extra time.

Factor the following composite integer.

:p

21130819027319923178509622632727980622577522491335986162202750512019525136688895741633235387039306968582318693021114825649130164135868576427684517893

[Johannes]

That's a 111-digit number. Let me guess, does it consist of two 56-digit primes? :D

This is why at first I was reluctant to add the prime number support. I told myself this would happen. ;)

Although I am convinced of the usefulness of BigInt, the one obvious drawback is that certain operations will be so slow as to be unusable. Multiplication, division, powers and roots of extremely large numbers are very, very slow. But anything having to do with prime numbers larger than, say, 15 decimal digits is just unworkable.

Maybe I'll put the factoring of that 111-digit number in my will. :)

[zak]

going to http://www.wolframalpha.com
and writing primeq 2113081902.... gives the result "no prime"
but writing factors 2113081902.... gives no result so they fails to factorize it, it may be of the sort of numbers used in ciphers which is impossible to solve.

[zak]

Johannes, your prime numbers functions in your module is useful and it gives more than other languages gives if any. and we can use it from within thinbasic with more digits than normal, such as drawing primes spirals and more. it is said that prime numbers is a gold stones in the desert.
some times i am using a console program factor.exe from:
http://www.shamus.ie/uploads/File/factor.exe
http://www.shamus.ie
its usage can be like this factor.exe 123 >> result.txt
to output result to a text file, or without ">>" to output to screen
like
factor 201487636602438195784363
gives the result "this number is prime.

i forgot to say that with very big numbers the program hangs, or may continue to calculate for eternity as it should be with very big numbers, and the only way to stop is by ctrl-del-alt many times.

[Johannes]

Zak,

A single-purpose program such as factor.exe is most likely written in C or even assembler. I will never be able to beat that in something like a general Big Integer module.

I myself have written a program to calculate n decimals for PI. First in pure thinBasic, then with certain subroutines in assembler, and finally in pure assembler.

' Execution times for 2500 decimals.
'
' Pure thinBasic ________________ 4,64 s
' Set number in assembler _______ 4,60 s
' Addition in assembler _________ 3,74 s
' Subtraction in assembler ______ 2,98 s
' Multiplication in assembler ___ 2,97 s
' Division in assembler _________ 0,0541 s
' Zero skip in assembler ________ 0,0472 s
' Check word instead of string __ 0,0455 s
' Calculation loop in assembler _ 0,00653 s

The speed increase from pure thinBasic to pure (32-bit) assembler is a factor of 710. But even between "Division in assembler" and full assembler there is speed increase of factor 8.3. I'm certain that if I were to write a single-purpose prime factoring program in pure assembler I would see a speed increase of factor 10 or more. But writing in assembler is extremely time-consuming and defeats the purpose of the Big Integer module. If you need to factor extremely large numbers using a program like factor.exe is the best option.

In the end I was able to optimise the PI program to run in 0.102 seconds per 10.000 decimals squared. In other words, calculating the first 10,000 decimals of PI takes 0.102 seconds, the first 20,000 decimals takes 0.408 seconds, the first 50,000 decimals takes 2.55 seconds, and so on. I have a file with the first 1,000,000 decimals and that took 17 minutes to calculate.

I could do 100,000,000 decimals in only 118 days...

[danbaron]

REVISION: Stuff in red, is wrong.

No, the 112 digit composite consists of 3 primes.

http://en.wikipedia.org/wiki/List_of_prime_numbers

359334085968622831041960188598043661065388726959079837 (Bell)
43143988327398957279342419750374600193 (Leyland)
1363005552434666078217421284621279933627102780881053358473 (Padovan)

Actually, where is the average person going to find those really big primes from which to form unfactorable composite integers? It seems to me that most likely he will get them from lists of famous primes. So, in that case, the best way to factor such a composite would be to make a list of lots of famous big primes, and multiply various dyads and triads together, and hopefully one of the multiplications will give the number you are trying to factor. (But, who wants to do that, unless he is being paid?)

It's good that you made the module. It's not your fault that humans can think of computations which are far far beyond the current capabilities of any computers to solve. I think that part of the fascination with such problems, is that they deal with numbers that are much much bigger than the total number of particles in the universe. So, they are not really comparable to anything about which we know. They are pointers to the infinite, which humans are naturally drawn to. (But, if I was making the module, I would have anticipated the same troubles - "jokers", easily constructing problems which no computer on Earth could ever solve.) The important thing is not how fast your module is, but, the fact that it works correctly. Additionally, you, like Eros, are handicapped by doing everything yourself - you don't have dozens of people all working on the same thing. Anyway, now thinBasic can find primes and factor integers, while before it could not.

I never previously paid much attention to Number Theory, primes, and factoring. But now, I see that they are interesting. For instance, we know that the sequence of primes is infinite. So, there is no limit on the number of digits a prime can have. It seems unbelievable that a million digit integer, could have no factors except 1 and itself, but, it's true.

It is also interesting seeing the various methods developed to determine primality. And to realize that (as far as I am aware), no one has found a fast way to factor composites. (When you factor a number, A, you first try to divide it by 2, then by 3, then by 5, .., following the prime sequence from the beginning, right? When you find a prime which divides the number without a remainder, then you have found one of the factors, and the quotient is a new smaller number, B. Then, you repeat the process for B. The last quotient in the set of quotients will be unfactorable, it will be prime, and, the factorization will be complete. Of course there is no guarantee that the last quotient will not be 50 digits long, correct? In that case, you'll probably never know if your factorization is complete, yes or no? And, how do you know if a number is unfactorable, i.e., a prime? If it is not exactly divisible by 2, and it is not exactly divisible by 3, and so on; then, if your test prime divisor exceeds the square root of the number, the number must be prime, right or wrong?)

http://en.wikipedia.org/wiki/Integer_factorization

And, if you think about it, you can see that it's easy to build giant composite integers which are easy to factor. Just multiply together the sequence of primes, 2, 3, 5, 7, 11, 13, 17, 19, 23, .. - you can make the number as big as you want. Additionally, from the proof that the prime sequence is infinite, we know that if we multiply the sequence, 2, 3, 5, 7, etc., and stop anywhere we want, and then add 1 to the total, then that number is prime (I know I am not teaching you anything, Johannes).

For instance,
2 * 3 + 1 = 7, is prime.
2 * 3 * 5 + 1 = 31, is prime.
2 * 3 * 5 * 7 + 1 = 211, is prime.

Why is the number one not prime?

http://primes.utm.edu/notes/faq/one.html

Below is prime number 5471, from

http://primes.utm.edu/primes/lists/all.txt . (The list was updated today - maybe, everyday.)

It is equal to, 7911 * 2^15823 - 1 (4,768 digits).

(Maybe zak can see what Mathematica (Wolfram) has to say about it.)

:twisted:

1246960727254209790387723579944578027302422003781509348503447323762475755173375244229550995867793645537545707286945509846966992771567951909913727489880115890646648041084352251368946450984551401239294760128446119108745511061333429892413564649516277469667788551464086423150878887320321746524584154391078893771656421508583123681615124121209893052315387614429855284548372514322098934273072682343443264845392694411453014180586746916318510688843451594444309735447066581723660977279435745206923637972688840286436731662278887967084585641033238200695458063582412324793266473619894777773535770067653147777370232404158890756835744630841415460047706813636023258119008312231220513550639574273348385465714214575028069456338269717947511453962719604798141954524491069573776978943660209920217545841323558118292154793464304655468898218811787785193670489578489234017465337674951672614885353089996365437504933317226563305660415429788203003521422802603146198333405957317502783313353766476327612318895552568378224052997673208959589558344708007246268628048504468852626730487766922791987516686660480424982149916033748626425405790944375213551878048117297253957550648473930922044034179652947565368831202390064249960139312370665296813930030995435109575829663497629941538270810359794967077848031038593484194221036578013473630344836507333962141288394566380487299463979343518449201461817083543501176829592689364354187233049009007861424601477405915705910816649757120341670855720870019605115841474412657161427770160634224056956169703432147767402776293550682470783431174623220605895152390450115989649530293013110376855071050276234607480337678067248719318853207102286273587649357762062429224383925615142065619817812037319469086352091861392578954093133664302134614858869332852032759088478737616072826991598161931096209845116298969191591567954560251779251082353462046525273927116216661473449648454552099332294793707759367266075984446121839355768115306511453637663695560046057880275997004276141568653067796729006641013243897331134137089780459921316215797242115141228284578300889980954245325514446696379634747108318850938644763918001236007797216298144889217135459681229088798101368405486520232628988022829434644349888689736651966250669502680320244032110647624218536383498823678430432529690485983466352207596477570206369187988782433128192901629041498478069261136595860774869820911469018766767582063402658063048215944975902100603119286795186680209512184219835988749067879794595551543980682169854177770591347678985578452213954457630483338379970026507816228033610323205492144654291746331655156179490126424375460956072118839743870451974719972610619650283999421086500197159619650071305733491222204103496120012681337873577243601532128027323309966196909818642534864611741033258610307550364100297451318354694419724567628063531886493017065092157635844400881600028232912155717844677191843509512357307488708476336081132206709806307041783165008707827566573868765294241313106662484992736820423797542656595774826192976843342158023931258294114037299002161747370235164286500946157401150403617025989422981295218965287006352432821934123405687055299421927086191589057381273035017444444514984840738908314056633103053809914554220456934165467371298588094156471010276807095313056449055210095668810869121560663058690196809710854764785666326804033001453469764410760283546442890478371893717153951624638285020510065512584984810495976202467715981436013270100469638802300732464163202702170840286947150214516151486381218062322264585036020575880190692319622404864424687150560986163247107734007091894941220986627570945416385792722772597270465228853886349730219772301992424603372223449354085317904065372641145190464619658082701193867984401924897351648274593928241826059823289182813888510340229562603728125425157810791338298927276780560693922483512529141460026247576165369402161873979977354597913541530007584717912233179089012699023461881288418173162845933032728166960068593846338611403169324702160760071557831237949532982427474974973927938054968327626526038573839069904971294846149088115794010255149108054346113031254214841661585787253013506381816829232936842085232666946537186482951167677159294869452805751715789894635118072961717424548524459207497252890072781660614102803931146420202753151488190966097886033617164689086047862769597876747251236121871953357498221524395129849254523136907590754519467382208190276932324328741599143726306370900277881315642819350336370709541003576211513304582714511684424649877969975592569148143563817102763308432529439932629747027978116575222205771632146277091973257984202848499303657173996272482812848803276122767380783040347464829147451739007248522233466766984146752981677096652646107316406625267311881989938038708638402666346951158260044878535563092323869250281383878865571387729504834701425134610455461887

(One more thing. From the list,

http://primes.utm.edu/primes/lists/all.txt ,

the largest known prime has 12,978,189 digits. The sequence of known primes must have gaps (missing primes). Otherwise, you could multiply the entire sequence together and add 1, and that would give you the largest known prime.)

[zak]

it says True, as a respose to PrimeQ[7911*2^15823 - 1]
or PrimeQ[12469....610455461887]
it lasts about 20 seconds to gives the results of this gigantic numbers.
you can download a working mathematica from here to enjoy the above result:
http://www.wolfram.com/mathematica/trial/
i am amazed by how much powerfull and versatile this software, and it deserve to pay for this software (the home edition) but after i got my first credit card may be within a year, do not smile, i am not alone, look here in quick basic 64 forum:
http://www.qb64.net/forum/index.php?topic=2632.0
someone wants to donate, and from the amusing discussions it appears that all the users don't have credit cards, they are old fashion good people .
links for mathematica version 8:
http://www.wolfram.com/mathematica/features/
http://blog (http://blog.wolfram.com).wolfram.com (http://blog.wolfram.com)

[danbaron]

I went to,

http://www.wolframalpha.com/

I tried to enter, "PrimeQ[12469607272..455461887]".

It wouldn't take it.

It would only take 200 characters.

It stopped at the 193rd digit of the number (..455401) - it wouldn't take any more.

So, I don't see how you entered the entire number.

And, I wonder if Mathematica would be so fast with the answer if it had to use the number, and not the formula.

I'm pretty sure that Mathematica will use any trick it can.

-------------------------------------------

I think that anyone with a brain does not want to have a credit card. It is a million times better to pay with cash. And now, a person can use PayPal. The goal of every credit card company is to put you in so much debt to it, that you can never escape.

-------------------------------------------

At least now Mathematica has a home edition, for $295. Previously, it was amazingly expensive.

-------------------------------------------

One more thing about prime numbers. I have read that mathematicians believe there is something very deep about the prime distribution, about which, they currently know almost nothing.

-------------------------------------------

I tried, "PrimeQ[1]", --> no.

And, I tried, "PrimeQ[2]", --> yes.

(I agree with these results.)

:skull:

[zak]

yes wolframalpha does not accept input more than 200 digits, and input PrimeQ[7911*2^15823 - 1] gives the answer Unkown. so this is bad for wolframalpha, i will post them for this limitation.
but using mathematica 8 it gives the answer like the picture below. in mathematica ide you can input numbers long as you want.
7143

the exact timing is 31 seconds like this:
7144

[danbaron]

I don't see how Mathematica does it so fast.

OK.

From,

http://primes.utm.edu/primes/lists/all.txt ,

Attached as a text file is, prime number 5077, 2 * 23^93337 + 1.

It has 127,100 digits.

Try it.

No. It won't upload the file.

It says the file is 124.1 KB, and it will only take 19.5 KB.

I'll have to try something else.

Try this one.

Prime number 5154, 33759183 * 2^123459 - 1, 37,173 digits.

(That's all for me tonight.)

:x

245825316648835246107086700746622739893249151204659010605619885962415420636650276193441794304209340332252152427318296859014402072732650302593371809176729893538427554644693797938667185584755297779200302381424976923320768252998452346192381338164546097080077718421061636131884014150976460657468696760679306211716680216225887314637541932777904158218149835489339571973703276029064127072720893102640412194311825528289010145307299064971915350548052663757807749521139082765544145936291705968079895123313227320381846809485893806169014400839353464343790903361394644861489087017213606605039279035041099524534364978648657701649145289519455533531838954628192863718427810229383736586846915017860956571202498855525174343303514262515296273812634223904988976122905294628376397501915597103930242031227785458514921047258676583889291457436977359516684278187826261956070695531239273461152618402620730952195609280212234560159438613657982488655590071795674104568322894574829879117254950163321820009357507744413806536843069635679984380800738603196109176366098686796815081725852733970835772414938822725755280481674945695355463770760263409993341363086851002614123335909447592930271543614985732615272613130572152772427120875289370112290675459235385121658236789731830925041292256057949462981812979669678255170860925991459896226659504484135242387925332457067578103073336921093306904978058889614591538632787757752710988792900145394494519911216492647009911020914299148338343521462876287414650273925784769553172315043687178083558839385215196042203281299065885607932335502091205244223948174418002100183906779773991760996312426103546985573469047818144279445747010619167321055091269747495611462030173800636014212816267856150735513505430584901646778709146063686624051721341620737959626727490766450268760703572286291795693674531658588819186571904150583816622345835510122499358019563567047520569348485896785099041078575481591381015543219190005216261259106374006515166417492536614328541177020312030556915658313983334262481774003557133868869590991616220090054721873323954766376718115297600945071904301589377577865047867033271875092345536059442695495797877904240696130038174839681656776273437506098580496689266126233889649354109508396964191574091002545974037667877599210166739856494076045584159398553511222048201945954839673780808086578960447886287822811744075119237526715358262528839714283028635891234156676087551395811093273362431249798126145323224679715616154981321704626852534912421740619986979569881742565383559703622341461852732564460369198795520055749481891619817842747803652275108825219000445672775770780019080302957904180349996303453580616492996766138417202269397826143108651808670758988738599462248606807906746117823193937566686628735618489819290622459946736890031265572632164314660602199147226574703442560249886457602248511547077781963448326966693098908110651315316137291028848998548319306014116169347251881769738729620029515323185727651051429134537063405508290002195415116843400559726938539512900345942243021191561647297649495904096107150966265804233576681017253013523270767682407793165783003449828687638349653091233818359724579834977579885016614408937720102845926759193075566282505719845910276502508148266820717928144246101495703977353808146861816763524873406505583681424947708427517998285620889901214507102047755980534903106127755887901649662400633475100999194186541493546253440639163560237865422555411843836046522305820390825440984579292735660185515078019813938623611314078854368516807044663984995902714170704034543511931668891231653743721565190660355387974576172154597402649455493184257113042496129420396894455429200713239380530521300795711364320399410436728430018724253687817266612842511662343045570709876295235129443879329509921783167480065092563023858125627861844737193796143537685851111332214455760302073866044436667686050729479755035806843621863385414781645059363177759690097913729925055617429810075420884324106143071349046761977349994633747254689040114192676949799541700837943631254089353966243170059288582127511021345447735488122946111376393635739798191941545421503010309091912069981453052169204055626689627481857191912883203124379809860095109872271955905318201976004217158442310635583922922966624014292090274747650408624307180597290743106629776980771400218400008606258461702613883504418532072807852109137115689658192935513927624055846782195977252908092752576252083323236675402393537146480748565204594819285892500669276249147421902971888047542349067207463055134509359881068661320910424651431466583015730520057320809223360353891886104982533002121075436685482377830881775429060328566006807230213816088610745400169083951677319868460887453616666610704038048278167259141188916779359137356932825716551032075686833604629209165723698073808417426231375369606978860868288536080162621394345769298886397768695152006906729443493164686568601634407325772244210326511609806650429461225698511676292457706363617978472187599153851919350408653337108551239380676204908670914109212135494457429678557304043817610439267890413336005802293081987700431810820254906572962837529579628786961288368497041208575013017643721603316064926894967783556586906259518676889627709953784796223319476584040016040200828479109818469533064455343169195874694337715799328344586865421223812978025766162580710433134606527188925735618790220996937137387581410597526523997224879016197236857938939538058806917897275862628133447798228708183860765056218331098832130456966465098367632042664034525907064033605697744245533194025077520096338688951086130720021983561734730603480823149071887865695652654140417994187733443787713655357389713964328313359905945942095522817852725353100586164126828586183551050067703130983981160116024901517971863150453214043087587707318830734301422281463151082215926413600345819478085064810776878950062939290226583335688898114339920005648692489738705789266689950140980896585730135982534291118395268217826011814607294396642605266526995731918176196168249255267434145174130685250481407728778991583210671340311113353671257332963226564846576299814095280698919993239985083803325468425613255808807246668078914837805640352146731989893960544251003418644240908373156736400119159917541468693788221145172919572372688793002997805811042863491288289005948031090770011766667642372630512011880437006516863924474625938410512421129466971233765648808419738560993306938105963772621903750760808239018868299987994306324889455390372719525772449667821378510788097508053312879562878321935891614064173519009898664704962467761052005162528951471903584579935062590662157220652729849907428741476646492505013014075071728641512769559249002213035782873751445781889568682371643601334848357175034673699822354521576416403752935259185156008557288199723740746392032261195807454688088074319994428256020724708858445826203962584076878074201276946770358642424979699011423607267945799845206854199792235508816638002542592346036815619115080091673799882214132974011670598794937849229756307975533673404718629683994853913488405818213105930809389255823724296548235225191249874622367955390465268849527310929917682765548934429953577757485571984985002541039881001795086497102511854795858100910338712150398663575603574837998692572295882528141186326986758604705257687569197460833836595141482722768067008409043544992594350691831096178234523036852904166429871237654053748037775525845316037678731569289043484723822938556342674118957412232412675211626466805423156855223190420032530378148088753618014195368095779974067993073549456450080302759458753319019147978193624171676246512725438388944779063638067863195141269596263851252169854529580195329355646742257441861000448814615705006320197596044236438285069688612155903875881016624169914721081909370290720214700151654763416936172125037333163919328846471401259242343597897302770107810691813802292524321175074504051061783654222879220070241372040735987749942037509774243346160830610416067082213618723869812831379117605059806180518559864859211362139521724002163391469936968174660361659509698289258906792246699915752753288445969158550758758092803610865956870353767172041926760824864630541462069205903631809320495828449517497035783507815731764546910895813360886959593215996134690650523463599062783201947551400697270579478050337433864382660346992343069164895997348146855679822453867930644910141775564802715862851584774112422543713374486037918991460049828425107176849698553341731620431748257506065946471136098147153416092995797115414636740650309019596681873009005323007812930254462464670012517106111771903065574416678519083282543040754644573817922699252950986844264029334248921295583811182577854417122012731971459220232796315289493299342204568975212680198707504495807520005578370314923333124505210021412385521187305777052007198270153850185241815595314863199708355798642058965805170483686363724192273683744173437789284152969753003182359628231809993718669705903999105988384364120393175240273245559224343796204190659602043826437308486263605410978044363628647290341640515081358140797838475266662062828433684577025465576196957726759884807948855087481150199934237918954896006386549382595357073578669202592199746077095102168068588948090606752156980532707353628567916900571208093142163855075990787842601922676380485470546446063803734533626547297954471575115529060497821579005484256391532531879509635569982396088540838464606135260660211956628385455039893596224367220491919579309480008613715190276919660965001208627656419554220198869217476501299423832619701084004398572752417613264133042710337447451702047543745708604758473970298349531393483774021537983002749291471662191596462267644379922493731676417228022749280570652159021057720207481856583883373712209436534950503785170097630158793815478372000072433581932517982993614403661850916620829656859646091357275136240421949506011129186373256318263487032554571111895563713552921958135181446444214718823993508780949580855924182321875661265784871802035035614144319123011211239943359201656981826695150239991963643274149429172130088518656544174331017051057738372636437275897890512545898043318145781482452585363377137255933139226733861431903683109631048215285144287931378176633832016522555547287873764242841428280428039875809724922843356698246597611195385116805008282899859165628077857071888492727457876141365753982079602274150609192868414206297040466684706063986457210842854055959539149260197483557433658429211427328113176953142928294746939069466876139900177618741878582385637887611797175353736589851267084111331479098332299736179101839177083242668114919052040906695379082055357803775642638516745125759455283757634607612572658334476374186916047147342972576864865228708191277949246301416362078462734433008277678412543841531828098081513094653822202422317098989563455683458239184318684887593359417572019599608152582509092580947012223721221008470883755683174243376455248584619457002868367607639877896219083720008829192951475946891821291585523746772844991413868438313095814145672041474356038866642271756657279815504422677713638245794454343744138048910082228919745652675025132054537872938310453334144357693974793119635240489470316446013300245916402267597793049495034274472613973775318163875739073671155316924371679331266516393272314597725204506732896683245520881812112062130398929822263671047165802042281769147137512069872023105473861010199546731695655996645420610094637156904361472860280650068687345320748384330668531037726008652663842084548500721708570857221275617554955552545986488342405818293035562509336978674801717430235412061369784562082957002122601647668022423435756180379697665722048287188620119424486415173389160217400093365019691970322875380676630402419185952347683103881229500191781588350553119595827618341368919346700422112938485637716308680670712664462978713413656114778139937255859955290823444470042988884489934867966701497150025009968953087002400201841490270782618710946175100813434623799473129655786045363984243315519649035303196627996383172175778298797648500647447523872735658223221662635812058891570386820295408829863180880815902552664842968182179776658889806681230697803524999434593804930394838988155986385979229902463926436216800438486864235430832285434131287050746925864494769041896409816374367104127735482008878425415329869623567537218553927510712672446622604518585825975506675632321280264016513170077719168327148734445319035010764400965093619661802898994764509992852868163543565728539735755467714290237971129249651504307195511099638937561027868130078155479695824948963891651016227185057679685497774248413621697972016751108199593047576686043563049334585819941930544582917886582953889587126589319004238940487658121513619189899698297042070007582157779257378945203147809417012874100262242850637580104426204648950708512200917513878091843269952372994775462331346884236078383775872987823533458225053359539984696707686758041922751780002336628432904832260779339401076766818817785365059662840126988233772787863038446076419104279286865123480391630942641161204435289985341664521138984624076511729365543467571831254316679343376976661851408570188189623697284358737229035184191716175950566527583622955439018449050738825866681484559702698643467476386033511986994560492626524157617250619245605015564216308708857204908012804188300056600217020667343700364242523288195257762905190871794674826986398918264167181479669262138847476183426920936508912379200670992988147533510406513045740024400472986870480562880664842844390411825463187757333956576911470944976716235246404737994567931047966439115050111712709167437261458825475066026801559044739669360490907525234805399882681747085153575356689826944336820178551450445476745720236379487019385101381088058145267019645078719201481022151120571029387371195317098541954365291444797016257360079322715764890688283805733850162386852991437530422679222834502897994765335309097793598412434283977717329657253838493677693996211320376276282333803604366603667519359407021876920692242675130724603677578419644396811518261182300464318942270362748719877542100621093035021881748320801942138397427196253837426327849290791286876653841216326881257622021032459100787263037706434468976746715093336085314604684047843730316316913955806513330838105775003080277592981364331001630294962525870517837145811198656075920218485413713775894131329437667646584665303282285719202844367529703442200467169150446893190565950879633895801375588253495332479950887221234865594129726896418066601077569490536901925454998801838142729701435322278981292767707312886014711734823527118448310613532291009344268552794265975529042576709820814149464241487353808859356722303082206224178724168816865564121018019234408009109868848649213265525784443047499382548196104142796480958470618414725748585988011449754737554596944147676507924722807742500032020511717087833062329340543484977163695261449862265946297016375837628588466560991121355284557120957008955300714383292570791751018366952778813576738643436010274437651759208991325512752446269088843910921853021791690372948207502003458108703796121222012172137236134037032703566490996869969731151826219435209976920328152231063489263873664369812404258472257932145414896310756317586599422947256082675693330723941255807636134349530236363579051621003129409046937167611788720503312667444476419599640593879445337625798547961139079915459203148239491405868202581276776383374998197095823046482562999645729873667322361782483185660343097626638631109377748079195521193847993937124479143835613620991665851720247247814238520276130631962795041090633981590911154913906907490506928660497122558778628138404816458000082159851496023162684668204769094929886304351542554077197851855397799826191380943779149562073206235478432297992481259164357640571426529144584240490303438857537379850827435114049139903466494302972321466228676819292659693583047834600649387430535781986064741980994722978597047732594727427213098112678097862054950476347300604265694196086338578990428561417228667637999638756864652467628564275982594741924147824646371504716456089330050767617811002116673304712547313729159786725730017993111273335076008077582147995802814044029369480188453045295114011049840419790315847323908627029441626664138125045784954280082982118988515891225643675843907594721822171487151609456896512878184960032158574876391000904216293623946516347892069133697037333848686910754405152423871770681705422171931582815610380462971309889168367034946425177220808050553442084628713053034655201105985601689940768462307314888600009331595867438379645620983460509569911724534263501374573789284047636518308980299131993921227793515911033989029359699220768999447713468781927025251924467743890218650238895323953999225223265244897965708844950266401407326011017452588611739350396067402360160682096652169232440493084170019650416304967579182518403041043023522373765744075792910926640482707023664721588109502881835295275152254565793704167834456107737846354517461022506748090789815876170328622010418239543188538995948434221408012046084168338254321873301580161651131409587468332696670856603843771576033687234999502851704557179119030560604916068745072759351278982901418746381407284588907872284574517008779740231277246940083579388534187778119635275150977286962753894192087607782513996382686791895133929850346248408533430193013912306964012917336974424279402215628395287318645062253142141587609774966724866908352104304887407598516820181179400857352611177440355969399792981154124398534485671383597461575687135822131373955945532927527257465868665328713391315987420137582228944910394936366754171953558240942916474079837456063428628952195745469924877877227489202279655394343651864037102286592526984644059671906769799557437092585718179386487013482557687410231009358332701219437382169714873364120044551339413991078495048166976647315205250134244244426130765589301710257778538711168106880843893355676948878613113357972754445645840543560490805495083697467352964118894038205038931180713049941377609061673046462249655739100344383524688523152846512743340434850947383917914572089598031462386131531971043616322331190788280523883515665887109187927635654909981467407877939311092380443426988131249977976009851066859841636235372073409575586228537772599088778991985323030168081446594390526275256487121017477199437085804781045116872946716893596189143619365093951363671805656925473909350526330492547098949675818587958357961728393351865323052331675331164649887523788936399114381385073115837028709288621834339570219094003034479529514475716222368664180447292204564381613462367132958953811670923072200502164480400623686153483787461019386382271750998074165839443704076889302584219783130162743584890671411720447572787785210663322874117611080355449057986848768087996025825711088714146381695095631764930762304746137858024868168334547733088736325696167127461327968225710789500177404542820939040873714818833380576742243079081870085308412106909881190730929030673715867114406811843121367150928622891368735526562588235772156256286354293593239824615422286443704918834021628038250904887094143482573017610714760770421839590078712437936764252811790246244814393854479524771678195446347446558302713507550003543025565146112568079444269394781097930586685118973669194771030189784607661302667922594089183347691511936877571519990510461369091458776560033086825158630005597374630792401927004213067886310082251317780852737860315346649132014530226299521979765810194224951068344227154441967773809244264406562127963047257474379782604492835548206756618665050554201384206964635598653915737608188382231510101615801508143918514302708993881992917560599225676041731057732724676929977413803279121878875449190060670406841113664528768528089892852906854714381178997931058063315461698215715839281250284518316431492288922692024563935757860325904917919320825456096854247267523954486031213615172543978493626960307806692205619718620594469011501970370820615938681376148771011953856593796423563051794707504407032027974867121579173376081057902529613125240924730284331900104771275783840004109354769530021905156013848894119432828674164008930127692554623817267605861517016900800075337703841943745290646687403924392801388294071306175219130929497847042011287971200407320751226482000470917927149056604412368657065165301294998858587111068980657097435236568953350324266756823644929907347744846577325693338640019257708022994963536201329447108676445770525275249059220969297088047096437365592302500545917261471801158714390210320248791362027378038170910458386622285104785058585470397451556971270170623540076025392989974271524617052532195982828700289491960998094268677011712942090537797746225124292119111319754260973437593451470509154947782099521718144313602045182810223278586665375711721974828399520874972964636829422393089758278296364447059849161527793475685857587123435236031602516667556581161790843147272016340440462243448440443384918063081427619736014118635158617617716752605396217332392686840450872913234237710982633463369493020520336738608175388829332730022240216036704887772138537920411927007556977891627341096397119592501474408871354585795279298831501949865665473582574858018375933606303023064011954001352453780246005014112146061981472970559735889144944918494713690600541464426781210247286720215292149201367862794437027129592409515842931850083975144954503882782312508947793842681155806569589886929702273436499325288231193152207757364702192100237229259166522253183428636099655212763748938016262084760440619953566665685717802511412141909814993928238766715363304308792386393368062845975260625336623965138245396613737169966521757692173553341007204053923336806663501662225967956081025292360949692725266783342372524399555363584012094910267355192819120207120590122579112215586635184590157822804973718724570639388520551296831387597706437258050029886398969414458031942541838844233441230972186312221984123268840455319795534200025393307023138542080625813681261998297719178148006438645680011188315798675022063611363123548980037330372483379596051431921165446745929487641342181260732962015333258927213628186974561304782437493431675122793302118441015100866548771498584083818784038462243164167072498925124081916086092977022727617721735887799794415079620440960057241962133529492888707179745050158999899705725143574613598047246133542955177075020748802605314558414308840364286726456466691720855791229690369059884557536137932941611439305776265624183601251465791038895670209699365315246223487961778799247243932472771495761613497254777258267401556089532607063520530926124412050380188168431318355988830792092591413174097463807661195528447941443546766158739575006704809561569482493704877077886152344755627043057032865444016258460624777567725553438632130536254236107201143093905305466174442456139427489736339441570317117945327943061559730545287169281960275147319866541012679011374447671043035083050414574910449386470569737026476593644122154315305931133026531028670231638049758235440339130579601702965922590001930171145644632021568668582991037691619362666522342974351853233945241803369159786705715894207536149484923849028661574481467029705287777469404318289644381435066231436229667571818907503098196822458705545638853252664235026815826219815857665219510937559045319461514423963308375230255747627092664744423700515723287474035846085624585648157802777717624788324584637939281805690837627234749174654284087983532906000938834098877756285104848673145057290715987400113116357621033614332809542039066809038313061003036592012244039654526877555163837657446280390674602600494329607269004055933138419349447408505741859782006560892859787644824461001688595461115855616003323360332241635143031313606797822673489082412133995201568030082099841662429419818228747712437297613919837074498818259445880727260259069372902705722196669465789855409393009094881086538447485779294494203647752760219463740741507727885618521892241202200897699909428778835762307382366391487035942088455033153887118847708187923651341660769642122796649010012506966020437649203324738173151668835845547649633449564072733439725766005466805426727648706900288466500403612949652686222204939144408695224229059863139764400561730346147549836715571537641228371622113535541024276265947279892115814466520183722053628061126147840814558131104534672997870219203966914199306294826752904600109342942277933522964819392613887899059743948712483619515499244846870544363454079527265229519151028343120378448953681262237127110681908883308288358019212010655525807318434080671350998352370274928376596620668828504176198057358418773519444250698409763857445746448317572017042285566986728346991470028761839024156514128668067201068315640710395367885081367040576038215327808410986040341502361843139817010102031324175166429783835886749044538135020995288423320135692606636484978031902344842049864347432886833445078242224492701231675238570004123929414502900026556138203384026593777751699613655114347464071039531181510692757684730046231312372903897846056930255598529700594467970450842061071143662207834739614815929999618262963871870124039837492593191338028597264210928634885015068295423158857801599035303995087171057116777830701556292597064635232207207486622248902202045087671530461941335700457811751492768223684257463797850328194746604515975905150919986450934899496924779678843985810497978404914747517093709603072654868599034332719720297959913882411072867800535171317872071928091380482163608645058204485412505827227186444492663974856154037544897578013801222216925669134637315850802400757062540185663618283990874508348731676546236007755209822787596814884668762026762001253019092965565603773814392229152993903999153347646841849695582202871449523969352943350487199749382397473766550422288574470075042724651175342106958957848842421326477236820535550087875638930975728256332535072404476435192883611917344919571411381596302281132121575661437351324575537730713904371461062203318355897560164633992111436475854644077488480027258465990878173820317161999265366139112779575482868143888987388802546318533608622959702908406138313739646468030485458742353240154219625443717547204525311626487192521248274260405768535795669016645343506102359215929393556205773270539417100221289807821854702022004808745712990648712315084023684079751958378627366067055738485320004219421218738903950944920815798482365520217152586731769730663062868456758683736192950105916775731350772000502681587126321378573044106386356340947721500560464810356037914635377947142383380543291943315571094499487599129415120286080778804191609252582465535040305066331977495432876989306610245482728632898318159473042328572912348293282434883101479185340868688758532028506861583756747556124764013752137683953486508274867585273950979288040792050747108061893336246337894117270453179151546559327236856264004497227625857187435905995440776715283773055959053433325546104295268888134771439075500164126963787699265983392423171463025060777783437173919914842284821646368433284692361276558544674847529766795453700078983355974063144127022015577850599759499158101586856658275278001203380318373269376249065695151421486809098944701384115151824438593181771189031549096311802024697310876723454341086544487717649107166724338185483839676544527596921746945768842682344859709366279000798163742928088733041302974845121743345964626563097136913855931133412664215287138063749853469355472283035391556533032394758708424214409347396413517666805676206885300811601024837734915537918563260382427459095173499080657126322453771159018172612694859085051865841247503383968158424805076459498730605911017975492713484578016690241191879461125748765635862184020969463888237130802116383492411390937903171014408863056359387019899960989111094666137860963778749297169294496564832930732464186721810592957541649041082970288519620498166919024548299320197597507275288674432905873455042562948950571903786604684037251434824074745549385580314216733683403018881861011991221586913798559053041025064369933532696149882235155974996516541555999088331030705748042193682677264199128186215359685654118764641421965765951680995864055016770295133214688374388907501681767078950041808769023052087520612844386869278185681086147788673567484312968776211705219634264905805980837527750242626733163232328642966648309662774230207677861833552674054569782813732249724178514603855972322785223727455411301963978271427099430141868650392247782742825696241550246368297491476610760516725174632000899173862775524469162334913883250089653221191988664475116954159341510920413689185057658590976349918865776219186669506386853042048716894900935198286449529210428799656590998199405169525259624203311605987677923757690591654083842981549271673897818428246663108883469195666100647922503217759201855441480645496574587110060685396829257002235096987433739523062569430783043142330661290780416786189715498917140788350557413152812280307719689742887708279489997512582485169420704415930549376441957871654658460068579971560505164182051626763689852261171169685425982259194137047509394975258067754731184254715950096613490866844401330544397054554219726319458282697266738871374320859153567305368916928999102081016965684181399995351098547715171552273368447333469482200116555953201030439875104785143722673839583228849601876779690554012608777694884582445574280638948578803880696862481053127321796671287587899485654634619250412136567635461037144616610283616869891701705658033631614113206866176728445674874347078649501836068718915398017460418724656069752027151895914119337493070640191003383755232782998582353862554707797399899022054179064497600624409687682486005332103426842483648665092455957977634015089798980442275196115947422854789890689949621889347305585213223398200316926404343586645137317897079645129560053602706982608834313047580840022016476814043144259004734237802966938733824646521586983257612734771828732740156851806756754913464430245529841557342139939984894404789634162216454774978978967243528647952743373587804771966903490353248974085096587566177675970473591275576762297110834284879492737336514008889552200472355187561379873682081497243728149265843448306672850331675483418328457939808611654280370688625384470250881709384382485406657094822138007875500109783690534997149365850723087956006233792050770214443232904195970887616907840274798576509112114998552966622220250049895363715352097119893982937626492872843053215008922872641297933515352388372577405167162609079901516191659523446611010610718145055980017238372484201553296456618454212581269453370821773730768540728021020865479423737730712755527189040893444439874473547931882177632531061585157214186592200271740314078033979712359735521455349117211716539293696556955489833516455898953563719508325499965845813161602501175019916286058636373146707389050970745901932130344554313048129552695608525968997133801969650276171647109235691215282094132509605772405345886197010906677897257593891520250297907166451044256873075171730412957931184326174256758047466785489523873887603504343803779424435812093895790941381463316531043891944777028724702429129619934983199703897633502136136198516339884821290691280844051015739541974358042506947584435356041425656532801626937727635143804548353079017630613236131395203549839050348483265450318752145026605846813734618903971301746312656660326382332630418890708982738694415300595772494607774736157617433989340134500993029885675981017573393388942320527425892626160954637126296804385360258169316393107018061252493429379012296177148420751717192062757157279144146351825412432844822920854982274643161313183953704545321053670744900613325452071665442023887967795140829361353487279045017839108906935951080560102755084062678976305310838881165869921802995457079191517158656566502373286683014630049236621263567118502931602126591830689453992245671661326020958411478826090220378761406444390841532596616929904530681189440617778241775072714278027067812793717517408950548378758249934270157551030695089856110466893843239303156309884504368011588036142112353819037715307160651273510733404181019419725317910690571806305254875475121255797244926701174057734235011983610515882403136963992148266488517974686852397432461827383779937286115753611932818961659919920322449682994285318082734527044944951432343263643773582336181454236620381033922507933703409612896667991266514683729663857513717638557145651967689877433219166877455565274593936202607742949130066869702902020361027699921027362009513004780293284694505218874120216362901135531949038976660524634661884233542496488183451038480768393081292712274629197008247148266167378726969340078502862401184051610567866077307052810866432919590339203049023168529241713160680976203175755572582846623066114124999907986680268741787412049831452464178918622627030686336187084753021373739261716414917156058310903097673265626380810470930088924481341370081285502279226547996781201189953292800172225930937446083012451295985922978596899676965763496665338089142523166176495911663684569666472029322509511461763395601558158054542892437483543891470510921339977524477812604975178833289248857712594166544911477248995598250071843517220339613888547077929295850162146780464499838875659617111277492914267870088770067935140859257226088785571160247827677000096191207912657357297858639481487464364477778086947098285365940258576075306098354670457957069950510296954838240404988611656220282362240838657352908391510740175453384584588461090243881315534592246051692095143722954407477833003455097278436154587483909755151879753540833382915407292656867924206446193019641423368208016245128383595187510753378011532732388261921776186057280389453939800203520238750723773789578334858892289768176490915249897212469630210426352290156460817370645912638503934222717822264787912125633242554763525953200682364484945457996204962915536820242977643127533459062364741752696852500758720708976892495691772160993910615029261919214343324862024071171035815957729088394119971469773398618479055670221055074571633395884169219277415571156881492132304089700983187236463305249688370434536839402006798470414513609377450230878963293031329648473990971347187592022110965406735920990651759613677165536273262113018097434740077105641060395040435991399771060635884928427590824324538446123242781862346902406233897354429969987876065710871411186567699111463788875959173555389947379271919698049248540169207222694191275736770289254643029113776495381223797607533096358537728365131022543879322063673418193746356399990444791556746999292596464912760107106615363365988496145742670658583168730079723650260189572487395231249274247521974599226409583987519454424472128101565023029163642089197364066458843865944531890544722511865688053447100420815424347804483814469552609314055883087283287565925683178682321869342049552549901165636973740545009042736016591634952288918437628735416743736521605865540118445422155463032130862543257263112211016098276303315381159723845688851807351237812481413948967715617368475924840916670720164344063276818190688326996795293220441705200841852661603283118620822463764347767402346327180468514377286495228960657416039457987572129089592364759015373173631898337994405318169965157639288018576577523213019586190755430043555915830830214685383728359159982704898770040391488808161964193958872167819699026971582608297733589601352180223867813098950261182965210611328099534692851573365253810219767311521531256812798719227728710705316670702586441531961871948424764468638787313431914126045514008536611299177682083540702129172362242748849013792185929521111611810352621511200824174783085261359090729572546259617340369507643467693718858427031770102535904567120053666441245537386992170474158310460860531735195885652586025681553705363775159196100887692516388436315695634711838180287813952312202638446551710743659858674890038457197315166906228141157962820817698696093949444210439609823602382622955547529784382742401072990691612095990863237762726474966100154932232509549344587485716488429583841061533430368844969631179041979016704895804614983289284463056985196643213582077820297336517937583655921265221259064429270845402261786166131711479409918338419926125677471051098676563215391921920586339705242463798807523518216548904857173990997617540892704160647972119639940845304941875696204739369581009088248955016202490890319485558667725297878680021749067728361353300885374236107904392858268182615314317026191297515293879507239861270527402976763045111864359641311036315693947819788655410775634552468946453609284089450798028006446121304144683034534439547861986308572373415268322451871832031660859106954779415176344067566805067106301240639623234277239200472868428948702628593433650984162231350989763534972537590546155023337979996432998920373825911002509627471693828741746654896749521337707274280357390017732091265245100043413398031808675239414090052078728013275035599222923773339548245527519655780259710700015399961259239637408158675271472450542582362692766231243528191439790391412571395327890329555699380596384047612989824906866314732961776726441108303454801566438880140743825361035545195717495528993305003197258233160953262584289453031581061816368677941653829181356985289874512117954841253969539780128913432372325198243187929786810122637007498293951418304990471375897074161640342405454753746618755962011065231622997975275457880988397548587367979107779928541663760959569768176659786335180046702515521734367402343872470863448629760049560646201046491567989046355367097467185410551464145555793729181702003491030260446817526925709708696169189825563230529699762288672576535744073392284625580723105972364990442895324152763315886553222840809613548700209142258038271949037615061714857532773942565668957707929136062517473762902794546841568599181816975331866225230422834288538157958697912477773178189160910946303

[danbaron]

I don't know how Mathematica does it.

I am mostly ignorant.

The only thing I can think of is that, Mathematica is doing probabilistic primality testing, and is not testing for absolute certitude.

:oops: :( :x

[Johannes]

Additionally, from the proof that the prime sequence is infinite, we know that if we multiply the sequence, 2, 3, 5, 7, etc., and stop anywhere we want, and then add 1 to the total, then that number is prime (I know I am not teaching you anything, Johannes).

For instance,
2 * 3 + 1 = 7, is prime.
2 * 3 * 5 + 1 = 31, is prime.
2 * 3 * 5 * 7 + 1 = 211, is prime.

Actually, I hadn't realised that particular one. :)

But even using the Sieve of Eratosthenes you can prove it. I have a complete list of all primes smaller than 65536 (a program to very quickly factor 32-bit values) and multiplying all those primes and adding one gives a gynormous prime.

Doing this for all primes up to 1,000,000 results in a prime of 433,637 digits. I've just started the script to see what the result is for primes up to 10 million...

[zak]

i have tried it for 15 minutes,
Timing[PrimeQ[33759183*2^123459-1]]
and when my cpu begins to heat more than 50 Cel. degree i stopped the program, because i have a previous experience of another pc damaged from heating the cpu. and the 50 degree indeed more than that, and my pc begins to slow down. someone may said 50 C. degree is normal, but this heating is specific to every pc alone, when i got 50 or more i have problems. also this heating does not refer to the ram memory which can be heated to the damaging point since there is no Fan over the ram memory.
if you zipped or rared the txt file it may be uploaded, try it as an experiment.
the curent modern i7-... cpu's are more efficient.
that number discovered in 2009, they may used universities super computers.
7146

[Johannes]

Doing this for all primes up to 1,000,000 results in a prime of 433,637 digits. I've just started the script to see what the result is for primes up to 10 million...
If you multiply all primes smaller than 10 million and add one you get a prime of 4,340,852 digits. The last 23 digits are 12222286177766366668971. Don't know how long it took exactly. Less than two hours, obviously.

Up to 100 million should finish in a couple of days. My guess is that the result would have more than the (almost) 13 million digits in the currently largest prime known. The problem is that I would have to mathematically prove my program (as well as the PowerBASIC compiler) for anybody to accept such a number as prime.

[danbaron]

Sorry, Johannes, I was wrong.

2 * 3 * 5 * 7 * 11 * .., + 1, is not necessarily prime.

Stop your calculation.

See this reference.

http://primes.utm.edu/notes/proofs/infinite/euclids.html

:cry:

(If you never do anything, then, you'll never make a mistake, right?)

[danbaron]

Zipping the file only reduced it by 48%, zak.

Anyway, if you did the calculation, your computer would melt.

:twisted:

[Johannes]

Sorry, Johannes, I was wrong.

2 * 3 * 5 * 7 * 11 * .., + 1, is not necessarily prime.

Stop your calculation.

See this reference.

http://primes.utm.edu/notes/proofs/infinite/euclids.html

:cry:

(If you never do anything, then, you'll never make a mistake, right?)
I should have checked this myself. :(

2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 59 * 509

Duh. :p

[danbaron]

I went to zak's site,

http://www.wolframalpha.com/ ,

and tested the 14th Wagstaff prime,

56713727820156410577229101238628035243,

http://en.wikipedia.org/wiki/List_of_prime_numbers

for primality,

"PrimeQ[56713727820156410577229101238628035243]".

Super-Mathematica didn't hesitate, it immediately verified that the number is prime.

(I call it Super-Mathematica, because, my suspicion is that the calculations are not being performed by computers like ours.)

:cry:

[Johannes]

"PrimeQ[56713727820156410577229101238628035243]".

Super-Mathematica didn't hesitate, it immediately verified that the number is prime.

(I call it Super-Mathematica, because, my suspicion is that the calculations are not being performed by computers like ours.)

Sounds to me like they maintain a database of extremely large (non-)primes. That's what I would do. If you haven't encountered the number before do the calculations and store the result, otherwise return the result.

Sure, it'll take up some storage, but that's what terabyte-drives are for. ;)

[danbaron]

If they're doing that, then, I don't think they should.

It seems like a deception to me.

Anyone could just make a list of big primes, using the internet.

But, that's not doing any mathematics.

Their main goal is to sell Mathematica.

I think, the web page,

http://www.wolframalpha.com/ ,

is basically an advertisement for Mathematica.

If a person enters a big prime there, and immediately receives verification, he might think that Mathematica is super-powered; when actually, it just looked up the number. I would classify that as a form of false advertising.

But, I can't stop them - (or, can I ?!?!!!)

:evil5:

[zak]

i don't think they use pre built tables, i have desconnected from the web so local mathematica installed in my hard disk will not consult the main site, then i run the PrimeQ[56713727820156410577229101238628035243]
and it gives the result immediately. i asked next prime , and the same .

http://i56.tinypic.com/20ieu5y.png

[Johannes]

Zak,

I'm a little suspicious of the execution time given for the NextPrime. The first time, zero seconds, is logical if the internal timer hasn't had time to progress. But a time in the order of 10^-17 seconds? That's impossible. Clock speeds these days are in GHz which would give a resolution of 10^-9 seconds. Even if the internal clock runs ten times as fast we're still seven orders of magnitude away from the time given by Mathematica.

On this page (http://math.stackexchange.com/questions/2655/is-it-possible-to-find-the-position-of-a-prime-number-online) people say Mathematica has certain limits for prime calculations.

How big is the installation of Mathematica on your hard drive?

[zak]

sorry for the delay, i was in a funeral. i will install it again on windows 7 without download anything. and will post a report in a few hours

[zak]

i must say that i don't use mathematica normally, some times years lapsed without using it until i buy a new pc, to see how much my new pc are speedy in calculating Pi to a million digits, and to a 10 million digits. but this may change after the new features.
mathematica v8.0.0 installation file size = 883 MB
i have checked the size of the installed mathematica on windows xp and it was 2,78 GB, and most of it is a documentation in the .nb file format. the main exe's are math.exe (158 KB), mathematica.exe (1.25 MB), MathKernel.exe (459 KB), Documentation files 1.49 GB,
systemFiles 1.25 GB, AddOns (33 MB), Configuration (107 kb).

before installing it on windows 7 (installed on another primary partition in the same pc) i have disabled the web connection.
after installation it askes for the register or register later so i choose register later, and it works (may be for 15 days).
the timings differ slightly but in practice it is approaching zero. the timings on all programming languages when dealing with less than milli seconds are not absolutly correct because many factors intervene here such as the operating system internal other actions. the 10^-17 seconds can be the result of time calculations algorithm and not the reality.

the same in windows 7 the mathematica size
2.78 GB, 17,073 files, 1,667 Folders

i have tried also Timing[N[Pi,10000000];] and it calculate it in 45 seconds. the ";" after N[Pi,10000000]; is to disable displaying the result which takes more time.
attached the picture from windows 7. i suggest if possible to try it, since it runs for may be 15 days without register.
the 1+1 before the calculations is to force the mathematica to launch its kernel, so the kernel will be available when using Timing.

http://i54.tinypic.com/14wy3rl.png

[danbaron]

The installed version of Mathematica, could also have lists of big primes, yes or no?

:angry2:

[Johannes]

Dan, I was thinking much the same. Calculating a 125-bit next prime in zero seconds is too fantastic for words. You still have to try to factor the number to be absolutely certain and I can't see how they can do that this quickly for such a large number.

Hold the phone.

Zak, are you working with a 64-bit Windows? If so, ask Mathematica to find the next prime after 2^130. Another test would be to repeat the NextPrime for that big number several times. See if the next (say) 100 primes are all determined that quickly.


Having said that, since the approximate number of primes smaller than n is considered to be n/(ln n - 1), there are already 193,600,000 primes smaller than 2^32. Without too much trouble that list can be stored in 122,700,000 bytes (48 bits for every 210 numbers) and with some extra coding that can be decreased even further. But storing all IfPrime bits for 64-bit primes takes a couple of hundred of PETAbytes.


I've looked into the digits of pi thing and those are calculated directly. I downloaded PiFast which uses the Chudnovsky algorithm (How do they come up with these algorithms, let alone prove them to be correct?) and compared to that one Mathematica runs at a snail's pace. Ten million decimals of pi took 24.6 seconds on my machine. My own code, using a fairly optimal Machin-like formula would take (ahem) 104,000 seconds for the same task.

Maybe, if I really am bored I'll try to do the Chudnovsky algorithm as well. There's a square root in there...

[jack]

I also have the home edition of Mathematica but the home edition comes in 32-bit version only.

[danbaron]

I think zak already did this, but, I did it again.

I went to,

http://www.wolframalpha.com/ ,

and, I entered,

"FactorInteger[21130819027319923178509622632727980622577522491335986162202750512019525136688895741633235387039306968582318693021114825649130164135868576427684517893]" .

Super-Mathematica, "choked".

First, it calculated (maybe 10 seconds), and then said,

"Timed out. Try again with more time."

So, I clicked on, "Try again with more time.".

Then, it calculated some more (maybe 20 seconds), and finally gave up, saying,

"Computation timed out. No more results available.".

Apparently, it isn't going to be doing any one hour calculations for you!

(If it could factor numbers like this one, then, governments could use it to break prime number encryption, yes or no? (The number, 211308.., is 493 bits - three factors, but still, 493 bits.))

So, our experience is that it is easier for Mathematica to verify that a large prime, is prime, than it is for it to factor a large composite. What exactly, does that imply?

:comp1:

[zak]

i have tried Dan example , and no it does not factor it quickly, so i interrup it after half a minute. factorizing numbers is known that it is a hard problem in mathematics, and all the economy will collapse if someone discover a way to factor big numbers.
now to Johannes question, my OS is 32bit , either winxp or win 7.
regarding NextPrime of 2^130, i have to remember the looping instruction, so looping the program to 1000 it gives the result in about 4 seconds it is the time of printing the results, i attach the results in a rar file.
the mathematica code like this:

primenum = 2^130;
n = 1;
While[n < 1000, primenum = NextPrime[primenum]; Print[primenum]; n++]

attached a picture from windows xp
http://i51.tinypic.com/furfiw.png

[Johannes]

(If it could factor numbers like this one, then, governments could use it to break prime number encryption, yes or no? (The number, 211308.., is 493 bits - three factors, but still, 493 bits.))

So, our experience is that it is easier for Mathematica to verify that a large prime, is prime, than it is for it to factor a large composite. What exactly, does that imply?

Answer to your first question: yes. Every single encryption scheme that is half decent uses the product of (at least) two very large prime numbers. If there was a way to factor that product encryption would die a quick death.

I'm with you on the second question. If they can say whether or not a number is a prime very quickly, but they can't factor at the same speed, then they're not factoring to determine primality. In other words, they must have a list of some sort. Factoring, in one way or another, is required to determine primality.