Page 2 of 4 FirstFirst 1234 LastLast
Results 11 to 20 of 38

Thread: Prime number support

  1. #11
    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.
    Last edited by zak; 06-04-2011 at 10:52.

  2. #12
    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.
    Last edited by zak; 06-04-2011 at 11:36.

  3. #13
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    56
    Posts
    95
    Rep Power
    25
    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...
    Boole and Turing, help me!

    Primary programming: 200 MHz ARM StrongARM, RISC OS 4.02, BASIC V, ARM assembler.
    Secondary programming: 3.16 GHz Intel Core 2 Duo E8500, Vista Home Premium SP2, thinBasic, x86 assembler.

  4. #14
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152
    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.)



    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.)

    Last edited by danbaron; 07-04-2011 at 23:24.
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

  5. #15
    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.wolfram.com

  6. #16
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152
    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.)



    Last edited by danbaron; 07-04-2011 at 09:03.
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

  7. #17
    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.
    mathe.PNG

    the exact timing is 31 seconds like this:
    mathTiming.PNG
    Last edited by zak; 07-04-2011 at 09:19.

  8. #18
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152
    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.)



    245825316648835246107086700746622739893249151204659010605619885962415420636650276193441794304209340332252152427318296859014402072732650302593371809176729893538427554644693797938667185584755297779200302381424976923320768252998452346192381338164546097080077718421061636131884014150976460657468696760679306211716680216225887314637541932777904158218149835489339571973703276029064127072720893102640412194311825528289010145307299064971915350548052663757807749521139082765544145936291705968079895123313227320381846809485893806169014400839353464343790903361394644861489087017213606605039279035041099524534364978648657701649145289519455533531838954628192863718427810229383736586846915017860956571202498855525174343303514262515296273812634223904988976122905294628376397501915597103930242031227785458514921047258676583889291457436977359516684278187826261956070695531239273461152618402620730952195609280212234560159438613657982488655590071795674104568322894574829879117254950163321820009357507744413806536843069635679984380800738603196109176366098686796815081725852733970835772414938822725755280481674945695355463770760263409993341363086851002614123335909447592930271543614985732615272613130572152772427120875289370112290675459235385121658236789731830925041292256057949462981812979669678255170860925991459896226659504484135242387925332457067578103073336921093306904978058889614591538632787757752710988792900145394494519911216492647009911020914299148338343521462876287414650273925784769553172315043687178083558839385215196042203281299065885607932335502091205244223948174418002100183906779773991760996312426103546985573469047818144279445747010619167321055091269747495611462030173800636014212816267856150735513505430584901646778709146063686624051721341620737959626727490766450268760703572286291795693674531658588819186571904150583816622345835510122499358019563567047520569348485896785099041078575481591381015543219190005216261259106374006515166417492536614328541177020312030556915658313983334262481774003557133868869590991616220090054721873323954766376718115297600945071904301589377577865047867033271875092345536059442695495797877904240696130038174839681656776273437506098580496689266126233889649354109508396964191574091002545974037667877599210166739856494076045584159398553511222048201945954839673780808086578960447886287822811744075119237526715358262528839714283028635891234156676087551395811093273362431249798126145323224679715616154981321704626852534912421740619986979569881742565383559703622341461852732564460369198795520055749481891619817842747803652275108825219000445672775770780019080302957904180349996303453580616492996766138417202269397826143108651808670758988738599462248606807906746117823193937566686628735618489819290622459946736890031265572632164314660602199147226574703442560249886457602248511547077781963448326966693098908110651315316137291028848998548319306014116169347251881769738729620029515323185727651051429134537063405508290002195415116843400559726938539512900345942243021191561647297649495904096107150966265804233576681017253013523270767682407793165783003449828687638349653091233818359724579834977579885016614408937720102845926759193075566282505719845910276502508148266820717928144246101495703977353808146861816763524873406505583681424947708427517998285620889901214507102047755980534903106127755887901649662400633475100999194186541493546253440639163560237865422555411843836046522305820390825440984579292735660185515078019813938623611314078854368516807044663984995902714170704034543511931668891231653743721565190660355387974576172154597402649455493184257113042496129420396894455429200713239380530521300795711364320399410436728430018724253687817266612842511662343045570709876295235129443879329509921783167480065092563023858125627861844737193796143537685851111332214455760302073866044436667686050729479755035806843621863385414781645059363177759690097913729925055617429810075420884324106143071349046761977349994633747254689040114192676949799541700837943631254089353966243170059288582127511021345447735488122946111376393635739798191941545421503010309091912069981453052169204055626689627481857191912883203124379809860095109872271955905318201976004217158442310635583922922966624014292090274747650408624307180597290743106629776980771400218400008606258461702613883504418532072807852109137115689658192935513927624055846782195977252908092752576252083323236675402393537146480748565204594819285892500669276249147421902971888047542349067207463055134509359881068661320910424651431466583015730520057320809223360353891886104982533002121075436685482377830881775429060328566006807230213816088610745400169083951677319868460887453616666610704038048278167259141188916779359137356932825716551032075686833604629209165723698073808417426231375369606978860868288536080162621394345769298886397768695152006906729443493164686568601634407325772244210326511609806650429461225698511676292457706363617978472187599153851919350408653337108551239380676204908670914109212135494457429678557304043817610439267890413336005802293081987700431810820254906572962837529579628786961288368497041208575013017643721603316064926894967783556586906259518676889627709953784796223319476584040016040200828479109818469533064455343169195874694337715799328344586865421223812978025766162580710433134606527188925735618790220996937137387581410597526523997224879016197236857938939538058806917897275862628133447798228708183860765056218331098832130456966465098367632042664034525907064033605697744245533194025077520096338688951086130720021983561734730603480823149071887865695652654140417994187733443787713655357389713964328313359905945942095522817852725353100586164126828586183551050067703130983981160116024901517971863150453214043087587707318830734301422281463151082215926413600345819478085064810776878950062939290226583335688898114339920005648692489738705789266689950140980896585730135982534291118395268217826011814607294396642605266526995731918176196168249255267434145174130685250481407728778991583210671340311113353671257332963226564846576299814095280698919993239985083803325468425613255808807246668078914837805640352146731989893960544251003418644240908373156736400119159917541468693788221145172919572372688793002997805811042863491288289005948031090770011766667642372630512011880437006516863924474625938410512421129466971233765648808419738560993306938105963772621903750760808239018868299987994306324889455390372719525772449667821378510788097508053312879562878321935891614064173519009898664704962467761052005162528951471903584579935062590662157220652729849907428741476646492505013014075071728641512769559249002213035782873751445781889568682371643601334848357175034673699822354521576416403752935259185156008557288199723740746392032261195807454688088074319994428256020724708858445826203962584076878074201276946770358642424979699011423607267945799845206854199792235508816638002542592346036815619115080091673799882214132974011670598794937849229756307975533673404718629683994853913488405818213105930809389255823724296548235225191249874622367955390465268849527310929917682765548934429953577757485571984985002541039881001795086497102511854795858100910338712150398663575603574837998692572295882528141186326986758604705257687569197460833836595141482722768067008409043544992594350691831096178234523036852904166429871237654053748037775525845316037678731569289043484723822938556342674118957412232412675211626466805423156855223190420032530378148088753618014195368095779974067993073549456450080302759458753319019147978193624171676246512725438388944779063638067863195141269596263851252169854529580195329355646742257441861000448814615705006320197596044236438285069688612155903875881016624169914721081909370290720214700151654763416936172125037333163919328846471401259242343597897302770107810691813802292524321175074504051061783654222879220070241372040735987749942037509774243346160830610416067082213618723869812831379117605059806180518559864859211362139521724002163391469936968174660361659509698289258906792246699915752753288445969158550758758092803610865956870353767172041926760824864630541462069205903631809320495828449517497035783507815731764546910895813360886959593215996134690650523463599062783201947551400697270579478050337433864382660346992343069164895997348146855679822453867930644910141775564802715862851584774112422543713374486037918991460049828425107176849698553341731620431748257506065946471136098147153416092995797115414636740650309019596681873009005323007812930254462464670012517106111771903065574416678519083282543040754644573817922699252950986844264029334248921295583811182577854417122012731971459220232796315289493299342204568975212680198707504495807520005578370314923333124505210021412385521187305777052007198270153850185241815595314863199708355798642058965805170483686363724192273683744173437789284152969753003182359628231809993718669705903999105988384364120393175240273245559224343796204190659602043826437308486263605410978044363628647290341640515081358140797838475266662062828433684577025465576196957726759884807948855087481150199934237918954896006386549382595357073578669202592199746077095102168068588948090606752156980532707353628567916900571208093142163855075990787842601922676380485470546446063803734533626547297954471575115529060497821579005484256391532531879509635569982396088540838464606135260660211956628385455039893596224367220491919579309480008613715190276919660965001208627656419554220198869217476501299423832619701084004398572752417613264133042710337447451702047543745708604758473970298349531393483774021537983002749291471662191596462267644379922493731676417228022749280570652159021057720207481856583883373712209436534950503785170097630158793815478372000072433581932517982993614403661850916620829656859646091357275136240421949506011129186373256318263487032554571111895563713552921958135181446444214718823993508780949580855924182321875661265784871802035035614144319123011211239943359201656981826695150239991963643274149429172130088518656544174331017051057738372636437275897890512545898043318145781482452585363377137255933139226733861431903683109631048215285144287931378176633832016522555547287873764242841428280428039875809724922843356698246597611195385116805008282899859165628077857071888492727457876141365753982079602274150609192868414206297040466684706063986457210842854055959539149260197483557433658429211427328113176953142928294746939069466876139900177618741878582385637887611797175353736589851267084111331479098332299736179101839177083242668114919052040906695379082055357803775642638516745125759455283757634607612572658334476374186916047147342972576864865228708191277949246301416362078462734433008277678412543841531828098081513094653822202422317098989563455683458239184318684887593359417572019599608152582509092580947012223721221008470883755683174243376455248584619457002868367607639877896219083720008829192951475946891821291585523746772844991413868438313095814145672041474356038866642271756657279815504422677713638245794454343744138048910082228919745652675025132054537872938310453334144357693974793119635240489470316446013300245916402267597793049495034274472613973775318163875739073671155316924371679331266516393272314597725204506732896683245520881812112062130398929822263671047165802042281769147137512069872023105473861010199546731695655996645420610094637156904361472860280650068687345320748384330668531037726008652663842084548500721708570857221275617554955552545986488342405818293035562509336978674801717430235412061369784562082957002122601647668022423435756180379697665722048287188620119424486415173389160217400093365019691970322875380676630402419185952347683103881229500191781588350553119595827618341368919346700422112938485637716308680670712664462978713413656114778139937255859955290823444470042988884489934867966701497150025009968953087002400201841490270782618710946175100813434623799473129655786045363984243315519649035303196627996383172175778298797648500647447523872735658223221662635812058891570386820295408829863180880815902552664842968182179776658889806681230697803524999434593804930394838988155986385979229902463926436216800438486864235430832285434131287050746925864494769041896409816374367104127735482008878425415329869623567537218553927510712672446622604518585825975506675632321280264016513170077719168327148734445319035010764400965093619661802898994764509992852868163543565728539735755467714290237971129249651504307195511099638937561027868130078155479695824948963891651016227185057679685497774248413621697972016751108199593047576686043563049334585819941930544582917886582953889587126589319004238940487658121513619189899698297042070007582157779257378945203147809417012874100262242850637580104426204648950708512200917513878091843269952372994775462331346884236078383775872987823533458225053359539984696707686758041922751780002336628432904832260779339401076766818817785365059662840126988233772787863038446076419104279286865123480391630942641161204435289985341664521138984624076511729365543467571831254316679343376976661851408570188189623697284358737229035184191716175950566527583622955439018449050738825866681484559702698643467476386033511986994560492626524157617250619245605015564216308708857204908012804188300056600217020667343700364242523288195257762905190871794674826986398918264167181479669262138847476183426920936508912379200670992988147533510406513045740024400472986870480562880664842844390411825463187757333956576911470944976716235246404737994567931047966439115050111712709167437261458825475066026801559044739669360490907525234805399882681747085153575356689826944336820178551450445476745720236379487019385101381088058145267019645078719201481022151120571029387371195317098541954365291444797016257360079322715764890688283805733850162386852991437530422679222834502897994765335309097793598412434283977717329657253838493677693996211320376276282333803604366603667519359407021876920692242675130724603677578419644396811518261182300464318942270362748719877542100621093035021881748320801942138397427196253837426327849290791286876653841216326881257622021032459100787263037706434468976746715093336085314604684047843730316316913955806513330838105775003080277592981364331001630294962525870517837145811198656075920218485413713775894131329437667646584665303282285719202844367529703442200467169150446893190565950879633895801375588253495332479950887221234865594129726896418066601077569490536901925454998801838142729701435322278981292767707312886014711734823527118448310613532291009344268552794265975529042576709820814149464241487353808859356722303082206224178724168816865564121018019234408009109868848649213265525784443047499382548196104142796480958470618414725748585988011449754737554596944147676507924722807742500032020511717087833062329340543484977163695261449862265946297016375837628588466560991121355284557120957008955300714383292570791751018366952778813576738643436010274437651759208991325512752446269088843910921853021791690372948207502003458108703796121222012172137236134037032703566490996869969731151826219435209976920328152231063489263873664369812404258472257932145414896310756317586599422947256082675693330723941255807636134349530236363579051621003129409046937167611788720503312667444476419599640593879445337625798547961139079915459203148239491405868202581276776383374998197095823046482562999645729873667322361782483185660343097626638631109377748079195521193847993937124479143835613620991665851720247247814238520276130631962795041090633981590911154913906907490506928660497122558778628138404816458000082159851496023162684668204769094929886304351542554077197851855397799826191380943779149562073206235478432297992481259164357640571426529144584240490303438857537379850827435114049139903466494302972321466228676819292659693583047834600649387430535781986064741980994722978597047732594727427213098112678097862054950476347300604265694196086338578990428561417228667637999638756864652467628564275982594741924147824646371504716456089330050767617811002116673304712547313729159786725730017993111273335076008077582147995802814044029369480188453045295114011049840419790315847323908627029441626664138125045784954280082982118988515891225643675843907594721822171487151609456896512878184960032158574876391000904216293623946516347892069133697037333848686910754405152423871770681705422171931582815610380462971309889168367034946425177220808050553442084628713053034655201105985601689940768462307314888600009331595867438379645620983460509569911724534263501374573789284047636518308980299131993921227793515911033989029359699220768999447713468781927025251924467743890218650238895323953999225223265244897965708844950266401407326011017452588611739350396067402360160682096652169232440493084170019650416304967579182518403041043023522373765744075792910926640482707023664721588109502881835295275152254565793704167834456107737846354517461022506748090789815876170328622010418239543188538995948434221408012046084168338254321873301580161651131409587468332696670856603843771576033687234999502851704557179119030560604916068745072759351278982901418746381407284588907872284574517008779740231277246940083579388534187778119635275150977286962753894192087607782513996382686791895133929850346248408533430193013912306964012917336974424279402215628395287318645062253142141587609774966724866908352104304887407598516820181179400857352611177440355969399792981154124398534485671383597461575687135822131373955945532927527257465868665328713391315987420137582228944910394936366754171953558240942916474079837456063428628952195745469924877877227489202279655394343651864037102286592526984644059671906769799557437092585718179386487013482557687410231009358332701219437382169714873364120044551339413991078495048166976647315205250134244244426130765589301710257778538711168106880843893355676948878613113357972754445645840543560490805495083697467352964118894038205038931180713049941377609061673046462249655739100344383524688523152846512743340434850947383917914572089598031462386131531971043616322331190788280523883515665887109187927635654909981467407877939311092380443426988131249977976009851066859841636235372073409575586228537772599088778991985323030168081446594390526275256487121017477199437085804781045116872946716893596189143619365093951363671805656925473909350526330492547098949675818587958357961728393351865323052331675331164649887523788936399114381385073115837028709288621834339570219094003034479529514475716222368664180447292204564381613462367132958953811670923072200502164480400623686153483787461019386382271750998074165839443704076889302584219783130162743584890671411720447572787785210663322874117611080355449057986848768087996025825711088714146381695095631764930762304746137858024868168334547733088736325696167127461327968225710789500177404542820939040873714818833380576742243079081870085308412106909881190730929030673715867114406811843121367150928622891368735526562588235772156256286354293593239824615422286443704918834021628038250904887094143482573017610714760770421839590078712437936764252811790246244814393854479524771678195446347446558302713507550003543025565146112568079444269394781097930586685118973669194771030189784607661302667922594089183347691511936877571519990510461369091458776560033086825158630005597374630792401927004213067886310082251317780852737860315346649132014530226299521979765810194224951068344227154441967773809244264406562127963047257474379782604492835548206756618665050554201384206964635598653915737608188382231510101615801508143918514302708993881992917560599225676041731057732724676929977413803279121878875449190060670406841113664528768528089892852906854714381178997931058063315461698215715839281250284518316431492288922692024563935757860325904917919320825456096854247267523954486031213615172543978493626960307806692205619718620594469011501970370820615938681376148771011953856593796423563051794707504407032027974867121579173376081057902529613125240924730284331900104771275783840004109354769530021905156013848894119432828674164008930127692554623817267605861517016900800075337703841943745290646687403924392801388294071306175219130929497847042011287971200407320751226482000470917927149056604412368657065165301294998858587111068980657097435236568953350324266756823644929907347744846577325693338640019257708022994963536201329447108676445770525275249059220969297088047096437365592302500545917261471801158714390210320248791362027378038170910458386622285104785058585470397451556971270170623540076025392989974271524617052532195982828700289491960998094268677011712942090537797746225124292119111319754260973437593451470509154947782099521718144313602045182810223278586665375711721974828399520874972964636829422393089758278296364447059849161527793475685857587123435236031602516667556581161790843147272016340440462243448440443384918063081427619736014118635158617617716752605396217332392686840450872913234237710982633463369493020520336738608175388829332730022240216036704887772138537920411927007556977891627341096397119592501474408871354585795279298831501949865665473582574858018375933606303023064011954001352453780246005014112146061981472970559735889144944918494713690600541464426781210247286720215292149201367862794437027129592409515842931850083975144954503882782312508947793842681155806569589886929702273436499325288231193152207757364702192100237229259166522253183428636099655212763748938016262084760440619953566665685717802511412141909814993928238766715363304308792386393368062845975260625336623965138245396613737169966521757692173553341007204053923336806663501662225967956081025292360949692725266783342372524399555363584012094910267355192819120207120590122579112215586635184590157822804973718724570639388520551296831387597706437258050029886398969414458031942541838844233441230972186312221984123268840455319795534200025393307023138542080625813681261998297719178148006438645680011188315798675022063611363123548980037330372483379596051431921165446745929487641342181260732962015333258927213628186974561304782437493431675122793302118441015100866548771498584083818784038462243164167072498925124081916086092977022727617721735887799794415079620440960057241962133529492888707179745050158999899705725143574613598047246133542955177075020748802605314558414308840364286726456466691720855791229690369059884557536137932941611439305776265624183601251465791038895670209699365315246223487961778799247243932472771495761613497254777258267401556089532607063520530926124412050380188168431318355988830792092591413174097463807661195528447941443546766158739575006704809561569482493704877077886152344755627043057032865444016258460624777567725553438632130536254236107201143093905305466174442456139427489736339441570317117945327943061559730545287169281960275147319866541012679011374447671043035083050414574910449386470569737026476593644122154315305931133026531028670231638049758235440339130579601702965922590001930171145644632021568668582991037691619362666522342974351853233945241803369159786705715894207536149484923849028661574481467029705287777469404318289644381435066231436229667571818907503098196822458705545638853252664235026815826219815857665219510937559045319461514423963308375230255747627092664744423700515723287474035846085624585648157802777717624788324584637939281805690837627234749174654284087983532906000938834098877756285104848673145057290715987400113116357621033614332809542039066809038313061003036592012244039654526877555163837657446280390674602600494329607269004055933138419349447408505741859782006560892859787644824461001688595461115855616003323360332241635143031313606797822673489082412133995201568030082099841662429419818228747712437297613919837074498818259445880727260259069372902705722196669465789855409393009094881086538447485779294494203647752760219463740741507727885618521892241202200897699909428778835762307382366391487035942088455033153887118847708187923651341660769642122796649010012506966020437649203324738173151668835845547649633449564072733439725766005466805426727648706900288466500403612949652686222204939144408695224229059863139764400561730346147549836715571537641228371622113535541024276265947279892115814466520183722053628061126147840814558131104534672997870219203966914199306294826752904600109342942277933522964819392613887899059743948712483619515499244846870544363454079527265229519151028343120378448953681262237127110681908883308288358019212010655525807318434080671350998352370274928376596620668828504176198057358418773519444250698409763857445746448317572017042285566986728346991470028761839024156514128668067201068315640710395367885081367040576038215327808410986040341502361843139817010102031324175166429783835886749044538135020995288423320135692606636484978031902344842049864347432886833445078242224492701231675238570004123929414502900026556138203384026593777751699613655114347464071039531181510692757684730046231312372903897846056930255598529700594467970450842061071143662207834739614815929999618262963871870124039837492593191338028597264210928634885015068295423158857801599035303995087171057116777830701556292597064635232207207486622248902202045087671530461941335700457811751492768223684257463797850328194746604515975905150919986450934899496924779678843985810497978404914747517093709603072654868599034332719720297959913882411072867800535171317872071928091380482163608645058204485412505827227186444492663974856154037544897578013801222216925669134637315850802400757062540185663618283990874508348731676546236007755209822787596814884668762026762001253019092965565603773814392229152993903999153347646841849695582202871449523969352943350487199749382397473766550422288574470075042724651175342106958957848842421326477236820535550087875638930975728256332535072404476435192883611917344919571411381596302281132121575661437351324575537730713904371461062203318355897560164633992111436475854644077488480027258465990878173820317161999265366139112779575482868143888987388802546318533608622959702908406138313739646468030485458742353240154219625443717547204525311626487192521248274260405768535795669016645343506102359215929393556205773270539417100221289807821854702022004808745712990648712315084023684079751958378627366067055738485320004219421218738903950944920815798482365520217152586731769730663062868456758683736192950105916775731350772000502681587126321378573044106386356340947721500560464810356037914635377947142383380543291943315571094499487599129415120286080778804191609252582465535040305066331977495432876989306610245482728632898318159473042328572912348293282434883101479185340868688758532028506861583756747556124764013752137683953486508274867585273950979288040792050747108061893336246337894117270453179151546559327236856264004497227625857187435905995440776715283773055959053433325546104295268888134771439075500164126963787699265983392423171463025060777783437173919914842284821646368433284692361276558544674847529766795453700078983355974063144127022015577850599759499158101586856658275278001203380318373269376249065695151421486809098944701384115151824438593181771189031549096311802024697310876723454341086544487717649107166724338185483839676544527596921746945768842682344859709366279000798163742928088733041302974845121743345964626563097136913855931133412664215287138063749853469355472283035391556533032394758708424214409347396413517666805676206885300811601024837734915537918563260382427459095173499080657126322453771159018172612694859085051865841247503383968158424805076459498730605911017975492713484578016690241191879461125748765635862184020969463888237130802116383492411390937903171014408863056359387019899960989111094666137860963778749297169294496564832930732464186721810592957541649041082970288519620498166919024548299320197597507275288674432905873455042562948950571903786604684037251434824074745549385580314216733683403018881861011991221586913798559053041025064369933532696149882235155974996516541555999088331030705748042193682677264199128186215359685654118764641421965765951680995864055016770295133214688374388907501681767078950041808769023052087520612844386869278185681086147788673567484312968776211705219634264905805980837527750242626733163232328642966648309662774230207677861833552674054569782813732249724178514603855972322785223727455411301963978271427099430141868650392247782742825696241550246368297491476610760516725174632000899173862775524469162334913883250089653221191988664475116954159341510920413689185057658590976349918865776219186669506386853042048716894900935198286449529210428799656590998199405169525259624203311605987677923757690591654083842981549271673897818428246663108883469195666100647922503217759201855441480645496574587110060685396829257002235096987433739523062569430783043142330661290780416786189715498917140788350557413152812280307719689742887708279489997512582485169420704415930549376441957871654658460068579971560505164182051626763689852261171169685425982259194137047509394975258067754731184254715950096613490866844401330544397054554219726319458282697266738871374320859153567305368916928999102081016965684181399995351098547715171552273368447333469482200116555953201030439875104785143722673839583228849601876779690554012608777694884582445574280638948578803880696862481053127321796671287587899485654634619250412136567635461037144616610283616869891701705658033631614113206866176728445674874347078649501836068718915398017460418724656069752027151895914119337493070640191003383755232782998582353862554707797399899022054179064497600624409687682486005332103426842483648665092455957977634015089798980442275196115947422854789890689949621889347305585213223398200316926404343586645137317897079645129560053602706982608834313047580840022016476814043144259004734237802966938733824646521586983257612734771828732740156851806756754913464430245529841557342139939984894404789634162216454774978978967243528647952743373587804771966903490353248974085096587566177675970473591275576762297110834284879492737336514008889552200472355187561379873682081497243728149265843448306672850331675483418328457939808611654280370688625384470250881709384382485406657094822138007875500109783690534997149365850723087956006233792050770214443232904195970887616907840274798576509112114998552966622220250049895363715352097119893982937626492872843053215008922872641297933515352388372577405167162609079901516191659523446611010610718145055980017238372484201553296456618454212581269453370821773730768540728021020865479423737730712755527189040893444439874473547931882177632531061585157214186592200271740314078033979712359735521455349117211716539293696556955489833516455898953563719508325499965845813161602501175019916286058636373146707389050970745901932130344554313048129552695608525968997133801969650276171647109235691215282094132509605772405345886197010906677897257593891520250297907166451044256873075171730412957931184326174256758047466785489523873887603504343803779424435812093895790941381463316531043891944777028724702429129619934983199703897633502136136198516339884821290691280844051015739541974358042506947584435356041425656532801626937727635143804548353079017630613236131395203549839050348483265450318752145026605846813734618903971301746312656660326382332630418890708982738694415300595772494607774736157617433989340134500993029885675981017573393388942320527425892626160954637126296804385360258169316393107018061252493429379012296177148420751717192062757157279144146351825412432844822920854982274643161313183953704545321053670744900613325452071665442023887967795140829361353487279045017839108906935951080560102755084062678976305310838881165869921802995457079191517158656566502373286683014630049236621263567118502931602126591830689453992245671661326020958411478826090220378761406444390841532596616929904530681189440617778241775072714278027067812793717517408950548378758249934270157551030695089856110466893843239303156309884504368011588036142112353819037715307160651273510733404181019419725317910690571806305254875475121255797244926701174057734235011983610515882403136963992148266488517974686852397432461827383779937286115753611932818961659919920322449682994285318082734527044944951432343263643773582336181454236620381033922507933703409612896667991266514683729663857513717638557145651967689877433219166877455565274593936202607742949130066869702902020361027699921027362009513004780293284694505218874120216362901135531949038976660524634661884233542496488183451038480768393081292712274629197008247148266167378726969340078502862401184051610567866077307052810866432919590339203049023168529241713160680976203175755572582846623066114124999907986680268741787412049831452464178918622627030686336187084753021373739261716414917156058310903097673265626380810470930088924481341370081285502279226547996781201189953292800172225930937446083012451295985922978596899676965763496665338089142523166176495911663684569666472029322509511461763395601558158054542892437483543891470510921339977524477812604975178833289248857712594166544911477248995598250071843517220339613888547077929295850162146780464499838875659617111277492914267870088770067935140859257226088785571160247827677000096191207912657357297858639481487464364477778086947098285365940258576075306098354670457957069950510296954838240404988611656220282362240838657352908391510740175453384584588461090243881315534592246051692095143722954407477833003455097278436154587483909755151879753540833382915407292656867924206446193019641423368208016245128383595187510753378011532732388261921776186057280389453939800203520238750723773789578334858892289768176490915249897212469630210426352290156460817370645912638503934222717822264787912125633242554763525953200682364484945457996204962915536820242977643127533459062364741752696852500758720708976892495691772160993910615029261919214343324862024071171035815957729088394119971469773398618479055670221055074571633395884169219277415571156881492132304089700983187236463305249688370434536839402006798470414513609377450230878963293031329648473990971347187592022110965406735920990651759613677165536273262113018097434740077105641060395040435991399771060635884928427590824324538446123242781862346902406233897354429969987876065710871411186567699111463788875959173555389947379271919698049248540169207222694191275736770289254643029113776495381223797607533096358537728365131022543879322063673418193746356399990444791556746999292596464912760107106615363365988496145742670658583168730079723650260189572487395231249274247521974599226409583987519454424472128101565023029163642089197364066458843865944531890544722511865688053447100420815424347804483814469552609314055883087283287565925683178682321869342049552549901165636973740545009042736016591634952288918437628735416743736521605865540118445422155463032130862543257263112211016098276303315381159723845688851807351237812481413948967715617368475924840916670720164344063276818190688326996795293220441705200841852661603283118620822463764347767402346327180468514377286495228960657416039457987572129089592364759015373173631898337994405318169965157639288018576577523213019586190755430043555915830830214685383728359159982704898770040391488808161964193958872167819699026971582608297733589601352180223867813098950261182965210611328099534692851573365253810219767311521531256812798719227728710705316670702586441531961871948424764468638787313431914126045514008536611299177682083540702129172362242748849013792185929521111611810352621511200824174783085261359090729572546259617340369507643467693718858427031770102535904567120053666441245537386992170474158310460860531735195885652586025681553705363775159196100887692516388436315695634711838180287813952312202638446551710743659858674890038457197315166906228141157962820817698696093949444210439609823602382622955547529784382742401072990691612095990863237762726474966100154932232509549344587485716488429583841061533430368844969631179041979016704895804614983289284463056985196643213582077820297336517937583655921265221259064429270845402261786166131711479409918338419926125677471051098676563215391921920586339705242463798807523518216548904857173990997617540892704160647972119639940845304941875696204739369581009088248955016202490890319485558667725297878680021749067728361353300885374236107904392858268182615314317026191297515293879507239861270527402976763045111864359641311036315693947819788655410775634552468946453609284089450798028006446121304144683034534439547861986308572373415268322451871832031660859106954779415176344067566805067106301240639623234277239200472868428948702628593433650984162231350989763534972537590546155023337979996432998920373825911002509627471693828741746654896749521337707274280357390017732091265245100043413398031808675239414090052078728013275035599222923773339548245527519655780259710700015399961259239637408158675271472450542582362692766231243528191439790391412571395327890329555699380596384047612989824906866314732961776726441108303454801566438880140743825361035545195717495528993305003197258233160953262584289453031581061816368677941653829181356985289874512117954841253969539780128913432372325198243187929786810122637007498293951418304990471375897074161640342405454753746618755962011065231622997975275457880988397548587367979107779928541663760959569768176659786335180046702515521734367402343872470863448629760049560646201046491567989046355367097467185410551464145555793729181702003491030260446817526925709708696169189825563230529699762288672576535744073392284625580723105972364990442895324152763315886553222840809613548700209142258038271949037615061714857532773942565668957707929136062517473762902794546841568599181816975331866225230422834288538157958697912477773178189160910946303

    Last edited by danbaron; 07-04-2011 at 10:00.
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

  9. #19
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152
    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.


    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

  10. #20
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    56
    Posts
    95
    Rep Power
    25
    Quote Originally Posted by danbaron View Post
    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...
    Boole and Turing, help me!

    Primary programming: 200 MHz ARM StrongARM, RISC OS 4.02, BASIC V, ARM assembler.
    Secondary programming: 3.16 GHz Intel Core 2 Duo E8500, Vista Home Premium SP2, thinBasic, x86 assembler.

Page 2 of 4 FirstFirst 1234 LastLast

Similar Threads

  1. prime numbers (1-1000)
    By Lionheart008 in forum Sources, Templates, Code Snippets, Tips and Tricks, Do you know ...
    Replies: 4
    Last Post: 05-07-2010, 17:31
  2. prime numbers spiral
    By zak in forum Math: all about
    Replies: 4
    Last Post: 08-06-2010, 09:02

Members who have read this thread: 0

There are no members to list at the moment.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •