Smallest known unfactored composite number?

Question

I'm trying to find examples of "small" numbers which are known to be composite, but for which no prime factors are known. According to this website the number $109!+1$ is a composite number of 177 digits, but no factors are known. However, I can't find anything more up-to-date; maybe that number has been factored now; maybe there is a smaller unfactored composite number.

Anyway: does anybody know the smallest known composite number for which no prime factors are known?

--

Addendum. With further exploration of the above pages I've found that the Wolstenholme number which is the numerator of

$$\sum_{k=1}^{163}\frac{1}{k^2}$$

has 138 digits and is composite, and no factors are known, as of July 16, 2012. This is the smallest such number I've found so far.

--

More: In the most recent (third) edition of the book of factorization of Cunningham numbers ($b^n\pm 1$) by Brillhart et al, the number $2^{1462}+1$ includes in its factorization a 130-digit composite number which at the time of publication had not been factored.

Answer 1

RSA numbers are semiprimes that are part of a challenge to factor them. They are known to be be composite because they were generated by multiplying two primes together.

It's hard to judge whether a number has been factored yet, someone could have done it in private. Publicly RSA-220

2260138526203405784941654048610197513508038915719776718321197768109445641817 9666766085931213065825772506315628866769704480700018111497118630021124879281 99487482066070131066586646083327982803560379205391980139946496955261

is within our current computational power but hasn't been factored yet. RSA-240 is beyond our capability currently (though it might be being factored right now)

1246203667817187840658350446081065904348203746516788057548187888832896668011 8821085503603957027250874750986476843845862105486553797025393057189121768431 8286362846948405301614416430468066875699415246993185704183030512549594371372 159029236099

Answer 2

Here's a number of 50 digits:

$$84286144766718574585896327097775856948442086719729$$

It's a good bet that nobody has yet considered this particular number (just because there are so many 50-digit numbers, and this one was chosen randomly).

Maple says it's composite, but since nobody else has considered this number and I don't know the factors, it's an example of a number that is "known to be composite, but for which no prime factors are known."

Oops: now I do know them: $178601959352247480503$ and $471921725116606004970765902743$. But you get the idea...

Answer 3

There are a huge number of composite numbers that have unknown factors, most because nobody has tried. I'll bet nobody had factored $20754285234059597221$ before I just tried PrimeQ(20754285234059597221) at Alpha. Unfortunately, Alpha not only told me it isn't prime, it factored it as $22892731 \times 906588437791$. I found it by typing a bunch of numbers on the keyboard, then appending seven zeros and finding the next number smaller that was $1 \pmod {19!!}$ I would just take some number with $20$ digits, find a near one that is $1 \pmod {19!!}$ and try the Fermat test at increments of $19!!$ until you find one that is composite. I'll bet it has never been factored (but could be easily). The $19!!$ guarantees it does not have a factor below $19$.

Answer 4

I'm going to be a little more explicit about the problem here, which other answers have only alluded to. The question you asked cannot be definitively answered, because it's related to something called the "interesting number paradox". Is there a smallest uninteresting number? If we found out what it was, wouldn't that suddenly make it "interesting "? The analogy isn't a complete match, but it gets us in the ballpark.

Was there a smallest unfactored composite number at the time you posted your question? Sure. Did we know what it was? Probably not. But even if we did, someone would have soon come along and factored it.

Barring some special cases, smaller numbers are generally easier to factor, especially since we can just let a computer do it for us. Once we know the factors of all the numbers below a particular one, that number's factorization will quickly fall to a sieve method. $345654323456756789365772498641397346521$ took Wolfram Alpha all of 5 seconds to factor.

Is there a smallest unfactored composite number right now? Yes, but only because no-one's gotten around to factoring it. I doubt any such number, once known, could hold the title for longer than a day.

(Maybe we could call this the "Big Yellow Taxi Paradox", because of the story of Ramanujan and taxi number 1729, and also the refrain of the Joni Mitchell song.)

Answer 5

What about the following number consisting of 85 decimal digits found on http://factordb.com/listtype.php?t=3&mindig=85&perpage=100&start=100 as the third number on the list:

$\dfrac{15019567^{17}-1}{33547074128942890979279691620109514914} = 3002765137097738438742260288410633997871343683756604808094241439840597239910460153959$

Put into https://www.alpertron.com.ar/ECM.HTM, it needs about 8 minutes to be factorised.

When you go higher, you can find numbers consisting of 90 decimal digits that need about 40 minutes to be factorised.

Answer 6

Here's a list of strong composite numbers I generated that WolframAlpha wasn't able to factor.

52986776794233104832103328295666315744399016136413

125681040986139881700727689895300981699173595577201

168861431835669186517515000338598383885529852174827

463769236157671275351576687781967472368144150669381

687972099419308066030619542876905698122539438815219

3656215393426085129658496618604901548693514426498659

4540919006515236569326813555006327895821300770654839

4408167669613682029224450112081421332499684841877778391607

2941657190913618745298300136349828639577968228570259228960361071

20773714564010095581676880611364685804279493068373795444698868313n

1588430987664078386142739962974425445160160166615144458298782747199

7292827053970765589518644051003093693843516760297764601847267608123

2839855737805806547263992321376864954612491117910249969272720066377357

23687787087484698732717686291047568270271994936863558037108273887965699

1313181809867521344351494326738378783009929726893498791912351853064888803

3551223626657365549809422649570790845849085474081767342121042286337830759

60502172339915979496415523579397823613337567367274203191696825259050841681

9410385019442547634791266053442557068932258909712494513313930878334690660251

1063047130960134914849578606555528171640168213954366848164737546556501792251

18111045033337927486414336373691934015810923488621117203207381127752351733039

21197290363973319966184981941038295641098289308372821681656129470406689891547

7436133771624523141683289958502032151158871971885519189917039909912754402897773

48169572629459002453078510749498374183081874112462479552910990415546105281085655059

176391650368983445335441835498415629413846563707181413885553058263217213205173342047

504035100605408320660153014963003692873096485887262197195951742035106570899595229027

1054168582940175225771640489397578155991356092237152405892108735745741051135015674117

47393741040284544790844251290036943452762674139371770999340979724503665207865591643878689

2283326574880586255406955471275752356902719303155504979480877756637867949790375972653875273
    
149886278512357647210378571020214966037868563657254478056013277596455314299176196683643411221

3320352942648796206108367536552943770577798721334859727355696878025061734507857818067316418057

12574100060092749525041369821839501277151442959513704826140122009323926351983639241671276719891

15124098661429765900250951586418142629400348435319919744401149982599749578840505416333828552871

9000591613215532269625613361270053719131402640876278564326686820488741761293301164293625265931490895121

Over-achievers can try their hand at some larger composite integers generated with openssl below after they finish the warm-up problems:

30079290468142356909939767031680294181411399386403961735929304786824389869076730640174907774273082097535465681049173

25478775895059580647317599233503851866352792376032117776202041815344427640048038048973845601740387841670896767992735313

165259765018745288221860340460120287204804477350832220495634082953363901664664819157176421273917488861021993790536740179614739952938879941515228346325633247318289926451372167

1795719038953119625830381691562527906682841374897344024138884742190794999986249951597224544734862306772651916149548630721127359909188907667846593461152244636251441233330285915990768622355447100501445849818321802829011

117022876190705301461606908470773909044647940370642887347030582728539067824459603546358707979702586940996165715761892655433532706404631919410996517588410378252082592073153455407439892090968435721413841043004283522265136359

43365567427512711710624154352840826552674087157059729424864407917680158734440448423441343840185517940454530872090970737874676175892019258814019761524658280530635698872286622165923103753982548149953139212222052994542818556877321308760252041994518246647537

491033873312554304025113420773585529995678143020012232330344052462486751916482279222941021157085900450840191317598566128849203877553558384691505159431030263469755622741186232542056841626959885276743973023759136396935502572145205446639033275357122014963382121068231369906404204303

154687696156819819238548755393817144030686752159745820656113505375449883168830603345299309237586537676976497506111365988711232112353787937075907426522422151968605986922288700368609870138798368993311441863335930720113262403797941158260715582412128528234175343680190291476269670110687518537041693917809652731254903127465364851869

260555767783101334659323262763469923700377127073255983594677389178649117978665102608339399811342399888017031344060389341957446760103441860720607392717404626515444765291415336048729142745981778590623683096775347542366972781505912402891665320640425313323634337168567933363661845037954288992041501960513422723027219848251640522404334808207723200387927656714846359178857187175692535809

40833954546124407775671051527454808704388672591831905178049788324499893395749450956895115172174841152567999112892258550025303755824237548560200660715994889531959660499682793298702208376424447603074420956130050761673114575239476166276506005686428479173242712956053018760838956223631036786329202092229265200335900608756869638188805979833301117887443608566454319540881634297002477483709026451824529274669871147560215796301305111

798197847139640879345812518013654485350115262249335277009377911253837271906769806076451919102068961653550089828712887915781981036349911327162019248062670916890334735158419047009100900591712760716393420461845571814552374884096445808209841440330227658636678089985440525926236348137828118435399017468405700065778700258141406181929865093866992153259068182702321512457340053274272970990547228948095126003364610622861992572669201769785207464405867468215971173

1150139784965787515455715703023222600198078030049588697821093259238715563192411653462920137339702977220453514546487733988722611726397055799940353758779563368290834106089158426971816854387555970839574536167045216815939844214248716313958034015946736252341589469047804253847438029086983276260986423909216503695207604688997926550998732979500493239543335003554830426265888085108444728552962783903416135297281597300782016964686541364597740762837486961542096265083159698208090128777121324904704760269

23861427565112076210504709273602570427992760344634190574152882358398497081867864025584939723985372434384265484912657809958033012625246989307307485619222254937233408651687776827320274559918288710156254820926901750393500155209356178275223778823159158497048193089600235748991732430910262746247721548802553282841622129225246338740404281130979097743053149785837470113660978096473774492425039715847103046090490538730703954582863087926503242350127081493504356715219308198031006272248548863817316565912834257424984906506391268590307

493759220050744557021214586146350347105496179094187527742212094619409026925547131180321211827537810847986517877057629089876245361374457601218836536950193576420509914473126511203174005455445356325481375430124210533890099205100530879990258266221138685660895450354783839279888344663199007573992336126649533469469071180534018057247292126597221795174760453957320738255338505816789422966650432332927369534896931003237684185554455403668262543916861164586036568183697673203099847897505556348506149253618882345414827742872727542334137023905586003453194402611035322065034977309

225315919728127390628433643170996264388442122208751797391741108251500022403026282792345955616317070410923675735260192705181147571913621278152814872324858930902651132653363005584368281738308192590592002733803119722905014152663023754886872679390775149739524793676376910495900521122907314122999016688225496565488372159937991226576204042268402336309933382197550255562659519857418869740400648067242095544940584135345853337537968421875776201578248043708583921879718363421147940500588319807484735679911721280962998289089389438571063833401721477219239283888837953842746593241980797

2755324385634219764151569604079948691900449879059213813453527431929938377619981160554115965299820439050059710634259719596855782887321807300996688126462156508807035188434818384476154125021780169022898191649587633398782949671216321905250655220441163659889843417444307795805172234859838207545493468624793051075610088049010403231369810885617402594594320253186926559022781505341583260832424630010569558005680146828521769390939551035796667251697649061503455241103787312057547181970133706640322949899581154482552982690113593047049435249682064110328199722689556977459182296786444088181756600876685157809257500867351

1008553070122856147285879230966204336807793674155489269741958511083225972345511709397663966928134099263082286968770169435183475555094061476875903544701218424536227478260500501963911941474136249636889805624887314646126170594845410685387295101036835243690174860162629003458491460000059591984396714374089779362010477507706492779008515229841120336034049509180175039814972591226916562428700832728574145006531627866415207967854134709770644408107459425652356222383591036740561721222326487450485594513687498513881350269632703830777181710169835256455234584823787536544243098365273736533498340786903682838199453416277829549194971590152256594866518718659459

If you really think you cracked the integer factorization problem, then you should at least be able to find the three prime factors (a 2466-digit normal prime, a 1233-digit safe prime, and a 921-digit safe prime) of the following 5545-digit composite integer:

40606069335023536593731144418912168996240039902243661153376036904891218547049964
24445064197608356997801020105302672356997226635893967680354969558269662564450160
53174875946993373364903527099516121467943177029279832207465521933104270339458512
92149350425892616626784816351427688420621797695791403012786320382105273031272401
89391636898702380713339319830108005053247655994019638972578811984948894724648652
14780848489472870359962256806929080950187638730671520528372003740596772061557777
32492508073380993916929015185286447546978829117398431496717152933834082489655028
12246173053196040891236606489273158932022217569413132307360444983449403835468526
00356796933739577072867469442175613805495801766179784896296496818432246934917246
49250424565355035311057322354616857355544788784940738390451777329491113846726803
59374610070981506160720948037040228827853309028573125836517835970798293340724740
01086135825549540099036682021999225310004073055316233303249974778356983955934147
58121830333307755096113320838430185562377086176283079407134577524761804421488513
44708653381930685356377610586146953330046280181793977347468889446286237328298282
47029824031675166045285304545008458854948661570640576681737574156549228778506116
93036754078781955748575198462236519031844592674899175108867140072399151791354214
64916440062567466637862493976053402135569599276529751091586766105395064123074142
71227815034376275811234991304521219143889025465570100183788059425782658868481148
78309627297920750517608546691963809135562795241448595050805102092795917932986714
71678209985799971337820593328368813032522247587809735819479319703231622389675400
54710824777318713616239878246555465654610243863461604215043909933580589462535550
95854160513868178651071468224898508417058550995691008951573337572284943411332665
90792880339339352393465773413748964771410539609637294894398433132916051501510898
40979822626021322415947835644061363169897127830352649136451433255147316693917429
17026408727510658395002336572521945518553139690632002304760487108742251887392314
56978542664434876175588083639694185161476153010534481100585350814084354605557879
67716656205581337698219083616905347416649611437250964157222026764672057010377777
27281322455626663559942680940880383382643479091702308476731164915684736706848779
49054626649164878137187632762873894300430496641068317423871075189561521560687272
89901164804248054315809188732237675864186612701655261653932739391481407072037063
41679920662313795577384217009113505185561184540740537772822409213646487262935706
38611947847532615443952038532871294059787363395106252558168504872911729987218934
65377071045561204279269891290485175745584847226321082695110681648789916188172633
10539814875309390109703212103423316676429422562472553466926193953671338050314095
73431578187109035313511045390340587787821281634234346849736087337378440523362812
64623902968582692584686123264872714644856486085677336158113356143139190440403049
95365988285977584450872077059275068647892951467022057685214310444700796222518630
60192976350536866437500588591086241966864433330574627826522465092645875778007201
63115888756230100661756744096041056016262466877207574748291818830494540773979412
06626963418276274748684345914048775222178313896573440486620028231015678323829250
81687512307297419622200309149791793461654122737371498602640689982911487977639429
20180598300954365314262254980900555028051829976956463145866268875394645885375179
67265048656702438622998121883285239427263895494513883208820243963793325082145009
64604060490438341626225392751161254880756634140183080681872750557825418264180275
58219717035419351043854689313090061928648557938355145430011714644204469258766737
75799521813869012997186355473822674722708812667468674880991509058244084081599270
00210786945619432283703422542579627538251569964567714925874047379082783725470786
27817825666718755258397093291655764757386333157458648277030409127626955038288687
56824900797255820209489037151735849230986221691984986232402844546746533728855197
96176074856545386643200798935718177680734506970778235168237337510910105030995272
82923941874462726899393827913406418833423197411882831518341426475285282978155028
59897839263040291855640702009453609934925222088839980132093917227983201435923546
28868290688477220429308183375646307690423930352051023772146069874866401713521611
91126177380057514771847832537523844740680405834876374859679525236858154055748073
85403413091981077695420209972608111464018919278913230248149792376406545389446272
99882970793915210237817320182317484202900886142543930290999433068731932402923164
40873745467545497635904557366119954822947497530819398365517585640864678244836610
83292991923783511249257731676518429400178442995691236655019718700191642839065197
11060893018492602556009673440454742437268196527947031154698732381722517672195326
09735263149956312138279225636886678752129415654179717911093033828898980512056044
08974171794352699290790705359910552547539351836620499773209360878846084107137696
63866452689436563698649235134889208637282366422807348448937312156413974148312561
12629214594625422243614680911249124759726522373218095581909169731051019755745926
58083932201734548759563732659996420375806397429783879073213391153574090152212869
23606903868525421324807706135746141830533122583182771190797531064003560708489838
13960442778124596074072848760389819746845278929753430850528405381316792101216102
27096098567832134365407988990372844881046963828126041751278348707374815845175931
66080560979316720353283500754946806714469092472258052374922574932178578416513434
90047337314405457426459563143473195373532915844838376515206395638232495446147138
1517807439810354027124033

Happy factoring!