1.経緯
数学のお勉強中にとても大きな自然数に出会ったので、これを算出するコードと結果をメモしておきます。
ペラン数の定義と性質
以下、Wikipedia ペラン数より引用
ペラン数（英: Perrin number）とは、以下の漸化式で定義される数である。
$P(0) = 3, P(1) = 0, P(2) = 2$
$P(n) = P(n-2) + P(n-3) n > 2$
（・・・中略・・・）
素数、整除性
$P(n)$ が $n$ で割り切れるような $n$ を列挙すると以下のようになる。
$n = 1, 2, 3, 5, 7, 11, 13, ...$
$1$の後にはしばらく素数が続いている。全ての素数 $p$ に対して、 $P(p)$ が $p$ で割り切れることが証明されている。しかし、その逆は成り立たない。すなわち、$P(n)$ が $n$ で割り切れるような合成数 $n$ が存在する。このような $n$ をペラン擬素数（Perrin pseudoprime）と呼ぶ。「ペラン擬素数は存在するか」という疑問はPerrin自身も考察しており、後にAdamsとShanksが最小のペラン擬素数 $271441 = 521^2$ を発見し肯定的に解決された。
上記にある、最小のペラン擬素数が $271441$ であることを確認し、かつ、$P(271441)$ を求めるコードをPythonで書いてみたら、$P(271441)$ が思いのほか大きな数だったので、これをメモしておくことにした。
2.ペラン数列を作る関数
Pythonでざっくり書いてみた。
def perrin_numbers(n=100):
"""与えられた整数 n に対して、n より小さいペラン数を漸化式による生成順のリストで返す。
- n のデフォルト値は100とする。
- はじめの3項は、3, 0, 2 である。
- n が整数ではない場合、TypeError例外が発生する。
- n が3以下の場合、ValueError例外が発生する。
"""
if not type(n) is int :
raise TypeError('引数は整数でなければなりません。')
if n <= 3:
raise ValueError('引数は4以上でなければなりません。')
# 初期設定
a, b, c = 3, 0, 2 # はじめの3項
result = [] # 数列を格納するリスト
# result にペラン数を詰めていくループ
while a < n:
result.append(a)
a, b, c = b, c, a + b
# 作成したリストを返す
return result
上記のコードの中で、はじめの3項を入れておくa, b, c = 3, 0, 2 のところは、フィボナッチ数列だと、2項でよく a, b = 0, 1 で、 a, b, c = b, c, a + b のところは a, b = b, a + b だった。（ちなみに、フィボナッチ数列を作るときのa, b = b, a + b はPythonチュートリアルにも載っている。）
上記を引数なしで実行してみると、100未満のペラン数のリストが返される。
In [100]: perrin_numbers()
Out[100]: [3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90]
先のWikipediaの説明に記載されていた、オンライン整数列大辞典の数列A001608 にいくと、漸化式による生成順にペラン数のいくつかが並べられており、上記のプログラムの出力が正しいことを確認できる。
3.素数の判定プログラム
素数の判定プログラムは随所でサンプルを入手できるので、とり急ぎ以下のようなもので間に合わせる。
def is_prime(n):
"""与えられた整数nが素数ならばTrue を返す。
n が整数ではない： TypeError
n が負： ValueError
n が0または1の場合: False
n が2以上の場合： n が素数ならばTrue 、それ以外ではFalse
"""
if not type(n) is int:
raise TypeError('引数は非負の整数でなければなりません。')
if n < 0:
raise ValueError('引数は非負の整数でなければなりません。')
if n <= 1:
return False
for m in range(2, n):
if n % m == 0:
return False
return True
確認として
for n in range(100):
if is_prime(n):
print(n, end=', ')
で試すと、 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, と出力された。
4.最小のペラン擬素数を求めるコード
さて、本題。最小のペラン擬素数を求めるコード：
N = 10 ** 35000
for n, p in enumerate(perrin_numbers(N)):
if n <= 1:
continue
if (not is_prime(n)) and p % n == 0:
print('P({}) = {}'.format(n, p))
break
上記のコード中、 N = 10 ** 35000 というのは、上述のperrin_numbers() に与える引数で、これぐらいにしておくと、生成されるペラン数列の長さが30万弱になり、$P(271441)$を得ることができる。
実行すると、以下が出力された。なお、結果が出るまでに、体感5分ぐらい待たされた。（iMac Core i5 3,4GHz メモリ24GB を使用）
P(271441) = 201457073802614865627084800584613290061498293215532795108637680542039636796914828821643988874649933788778325016035694088943830527563059976814857098785526005838224453673408107150271385574892254428798457737927479633840816839617860087365802432258566514570408418254960463248818324755529371025575468741262166875462013650030842844060246410092716180254852666548433552507712800186963818835006644823850064977752394853016254014341776772499516478297332919332970838857704265391168090363868351777924109704351927355388729565633766598690787886714990928837199314570480130473063930790646073066885473741392552943198198279806335289710679049948629385324504945676758656726271787313145908280161956464399207139083896430852486949362648455666007040470715407225585610541063599234495540373565140428919333123532602175059038230906355901868390758986124141368821926492211066985381552959964859652310220695672323827850815455445463128743236848512199922170531419225569149762447676716133808485920309126050212553154429309503264230429132377432757226314122037525735626414460174163657853293725940305892638571101066366363438719304473954631895083375943436272604459481183504070431731243351364604420644585511431610594632106850503483141563243432208426754493159053527726911610783689656443628469145657362183952332750258269379436770776810819821781203929234511131018520031599337976629373855144396413897909819257709009359807694799332817773985737039458752125486507359012164940026779663068239401304431788449657341397097107110510746079071397434161903361596497655252550684984128051433244252270792128208155269718495863321998152487927727932363102707698707368154480875582347697065389247583964289632524054671441957402828735444951782054600399689216535232246568763304878838441427036456761435549014109197120308537632479049577261515817032635760743416099032969644210751286305815805632816059492089661543045620720667567663466151932748239937059283057247928900635890029694148729329728900031337080942454081944233528911206122215465205485863813916275143559390968236782183169665536330465139830093378021220146481314455903733552711378098573355615853310544130698819429108466858327140456536632634400063987562763236273629080261151572808860478681697100857037379790331945776857718509025630901345989008693554336696442572474779569594877707961394518975488307517005744702936429610870231267983079227238482213516762674511880576307102946001639532034916792601958402132812660449144431626255251783245840935840578125294755781982611947500558528956805664597001392867116350528600811559971581245482423816900226347905697712520262940917036486094843084208414554001302974184802648159934660328810907114760982787555462310129115645985455560853250207673704394458635057943670259591159755635010790200050874486447705089124399203021755760724634998299470992175919418286629079520576475470515788687279409267222311779449259358289220205826586078628842623835013215821473683813143590697906309317305954483891497787220673121064731237993085364771987083190589194422044153648678285699194710655511045589385974461792190857460839782959703787263163733463959765582923265171121802136092930957251108064452151404040236532160463257618126503482199628987737074746324055835605696135758658055678138805898198434504924164530845523810468243850109378398401098476739805871823493797548873472971563983327732114060882337952969109235158094800665097356307418557467243268504927762756932059684427801056724819208589024577675187033870296153207432933015791001332565772796098578921202651190483247586553420672206270087970719080187305070010743909176303167692537823846972783278014467446486696864528051425485529119306226508511018196767947275674053463679282419237275540488983226115159046323648221586988142012781225555942504229374951967343026446309508898271352871652932954661725996811623229287737161751590469604184617021143175713265997439955569964989349727476126023906691339346025951796476280181365591186908386384485109355507353940034957057574802404797755116500006701024628072879291780102380935566167504406591493278614192170849627210511952403178246183077014468930853521025833538922675559433679218512791280337994345140482846204425035740520094999804249508914638513255911134768288053497477934083419806634658207481073099812680881134115303388089609836492705444142292710028166849282884248481901463108496407885913920443277854395758974307407274991138630626725480473122162936968204383319816058481349189644449586546070989949160276726841034318590241447007204604680766988618405526930040540876377326888835538842515490394340478922751365557842390248352542841549144201988389372698002238655588323681874366351611849548833239986194432881020067592228573031717757846727703133845662631372674608802847688604127125409021398234804480381079673005464722990387429932155777030202516079664830182179516976666572392523165854516214715004368850991371901042497753736991267528236674155216662593277054553964612125631468188454994068049552380887559280516204791552713851216937857827543386637981944163425102008243072344380863977671488281693864589070450063008153048394216373228772346290283305905659153599399228507997041896614414136975415914057188697434602430008676829507816634618216149130572730713455565010215146262952458965117531407849870341566617793463546182971894642810317345878219098955990056585703983144266506971893619246939081624150091688666073550932507510578433180599454695570034769566674636224492997592867727033037865858640172642706057761099838505731848183158335160719354826180779752018363555629600912461502269706194485041549376460513286671613029707287443567415053678932879482228995712571714384433705634232732880185329236925956547311709036952937282531610823210331229732881184532479141923207878384876628052976375897508848153287268005014332063670818443775714538535518674813001638224300681992850155386432758677824577484903455058486345808667231329595492372001618109739740726666333801332614438724019615732304946188413463880287667662920466897333387850498838727990458153535790066152166491727676433371011661625342104452066305975492301838120240501211007021981155827267266372976068331209398795541971982832414959689584009117353649871993771650895518827602443711425163130430047750664209091706667105648738358175314850884940193036090622503031408258366770596894606824791423126387125251421534845317993396858459457383052805838806544771162988010315902264132608886569175535047524324702847533290256205626579490242267970297425722400778746016670696130996873911278531396227099923473295249418315766559361928180613299004611988248655458162617748887662999465785605664082614555038863721851360801596959085657585125772229554320682598723177097347905785230861321181701525564702559479006354996775153631613725249359977091943955037668113225050540001132245084838828921365355395528861831881890728304955262955524520572866627984300553604451602741814801163887204299642755918885350282132524028939527612192932502574695873192851258922183599811377576047975492047493896435033413062622521536888824839533333793219933330550554936933934483146869880411298234125385760844027590867516719977219112775878154214786199694385818304288803614487803293617595943929583942322966798408194543651280618888351993142972648983138635967975663765013137286226310228259062424453545181264448103808158191107579567681913814925349004388616732361985475086230273960891014085711705806055451999931686477062769448928962294483162587157170405226539069346227141744514604625869506980865251292429469664881299116034511465909480620244600086044053410843457475069671814836382426517618494434469087328777075910932276906418644967115634886059963429713470081273465728356211869375057604077755541623434788781398998416122580775700451239752120470330002916720886395829821827065746993509811088193144755122654879460043187668794957114660385080276307782523807300423864064591681282857217409961106447011428282775775526075932417133265382880487242117012908870867106628960186127846348904231454574943268604219728826467266252925233146892760482762284712446849626218313947633946391999638291045934856071474145377455833438200746455748108112384479511407124934458665663812633383281334611748510421862815988811358405361278041859055607086114558043631850181791696207055798530243304838835921503000759476753033701367068403565920477944111978642224496393205738190170075525787956678580182581642554226758219063732451125323844833101678158731512706818405574277400746020140447398211537936534862875571350259038147639113040042465405758453769298022866238519855147937663328639601416089363722117572343567848792235692621419706712844297128557442089398126785221366964743818926407391971391354840898864251496047807256019810631777194873698054296236135538487712778286423649499375347165531462798898272568068126526565172911262805686020596072307120355092509382555611380634295975355244410206790080267723227338971784019353177407116612312937543330575660017579214501437646356166265071459224084343008915575908529424450851541816367914742643286298819435643659231844807036293818613420377068331543766290550645869715290122160776347985917562439571220030847931460853948833579723760565373767747364804534010342839662058142566841060259962188384824702745705586785809430556825179489011555008634890618578689744837244121402104302992172656367778681855390049998553953303307072941248802050498900787183313314845003670718897369982170701992577635554726667419131130138547223594536462076316519830821485000330261315592048685649412534633746353693797124166767719198763847125729787548784983513555503883968819510655017689272824743424111710104930488508033703580491452903772277513210862135592388171764401419068732892877763850233239227370057798716895603547628055117300500736700516107604270701944143040816390708837657381378450338091293328429869619240734564031949840283262855171714444946535476240183602832938511787601264884788570238133828146663318201502614647289615399057936417781005163951260448761050313320321503401956211546572410532188463210563055645045038678894414970584128469935702081686923057071655146722137982275734743445118591181580231140946028371173553225865116171479528048745781417145015089712275977851163966235782480673233019551914816262522314260529687147833311678750751878450202770267150936635580837463795123043298356205361558596778652597506362909919679426050488383791002181465189950888898437494124536248717424394554295168266258547453595648488246273133510884130660082307390321539611538885521743035594835575047927680209721090428408204020976411154690398538097470665139302262932277896760350292705603686741986269156191958619791891187538377129894817894055084534637296242063114967478206236150378487142604730385706439340625582289130727258736456108905138027014964914189354724485145242699644408413090345325622607421365666982045080364900764632928906659692663695256766325198059900497163578818585010649230427507187754132317902447202019261705644936414486179853192492939040545125560617620383920500083745686207176871479209771272058307641148743039899020731546223799910013403242556437800449268854086235417070118222553078581649480572543554873279954734433706886626618842288851603912607730877657076015234633962206236042716613275426815393457167310946124021383168257535692725654625296692529922080707741730198424240711627444088225982741332263147539296853097930949253421617843282151805545596092292008253884438035971368586251283095647310862417459981018912396618954178415743282450140201803518253779170167712796775252055400088319409516888919285411280091335985233633869359711912349900217654145992997804916563262822940344971393442546996118162295707239194427484129922298611572912742809662563820128055153867894328509224685804070987376606986995790708041997869695366449375507569639673254844839398809515520277378464434792295850650771390171218407933515731318775286472056013452907899793532194790414246771780367005596203973745864172768191707087720986559987504958518374311283337503688482244252534298726121949687997393254106827650675170275340701506465013706677792160303818141330598803972933394078969469246700666758145449565901379004666596316828077922213396419387962274243359138990574858922428436287013814356464159522687839616309826262155176927832182527442424408338533202629062933809202826918826184315731891132639025955265949273265126692551893980623401863247433382286906860961145133832008112321061239456117368531060636047731290591460848793601566379149292469477910986676374653560370522947481183482521721663791665324118314094917900050876290950702395166182938513978956264012722742146951967558371186759162546362234882884233441042818739009110573266818731909374447721552377444916140040640156700604967759581543165335989966639867602793098834774035539768533313919828459913257602158171629572492538799068573896720997307398399276343825342923922237519716752169864086614389238849041151180457988955412649948274441455815889835744912669490243601617764090250145402035835578781883042222988754174423257484600230067351014489350675898437909737905332745454353621879931762812484563985419762323329713531906641781046215446164639801516221299889255997572117946748953638942188914531241108643081080066667519356662367257593632817706768889454227618813968740719600907925470032241490959805972777688964861915598070088814998783008053426475541100720408404194148279990961933172782840181496441790138942663765140264226673569813386198615017347652460607026762608567707159318331263306109200656909928629351079777933935037101394339182567894888565493945934838223840080610012214007314536180163880918237938594919830742445477687206213144697960224389005903533813528441239450908300533180025572795513947823423301856709895528904371729273377191295238939209790015441966663343270893200735132901066225095495302796451347221849811693964468452258161885197556674403852934267749554060590179957648521230031621316922578990153956094840309905119088468636521924211289718001402340701993277839587151748236196972181761285913775372865375345455520546034942969117119888701271413502812025714494008347254072089800344838286637028266135281896546434629957123479944732732875606944150458034614023015723092835048208400693956853174435753461846305906217154281186445560779353592557862785764318215171330589434736569934867374994845366471193478901567862586996480771394069057066469631994693010706156988282913985363381347816630052704915437453420867796879684666004850393119850562889838522218160375446127956496416487799205382557834235448762120031202479576168406080379019050455537652564526402690830088030570778678168873842054135448174693459884472015547057443157996491330272338849633962693934984316796912281243456162834793583054757250740620641455246548167555011945501147322826544835732135517607974549047727015778961513575483485574862414711387076615100705283195987424631404323836132796244906626286728960365867920080007131456744745893030125576351207015190547034642731653744036639437241929969103840321155354294141575389343843313270245636960659160343967545802110918118167363301187985124773586584225464886241967539974608830221633386606812777078907045161987977996109252267858536327140960258901824878576642649945166112535279378481171737589211403829060412506226617704888351884558258107756541693485824784723540273443683417342278420687373277325387797269546884199571122581083962412941240174242125095898941837451852943638469642425828257221736392622079356023623748795991911426982307191192170423279344141673214597379410372983084316062194816040509861028558022121015717997577780275698275606455242665438087736052567664208115295581863646632627560128481425906981273155114357152219363008082266100701975489175306423587352330692042513729860760955482442696062344245293665510805295902429158935632497862915476236716535868421393315318944228832112339031805445794429209822411354093350838307102985321218519963699922473674239837393353570344714182491161644679167987271471132588047152466938694305930221972292909900699853267220200899534651264428624238934164336951246433594060564620865300143506892349888345069672901103441961098769141413313297202166824609907827431856956280849722558521107494583498363248517992052710584606364572355697164614446237900581851443619113248389663050766713343393522610438622882274668868686227661953548981672378062582435736340417635247786753649240202952761449299476460695731696184731671133348838094119770798528567001141817702199958696663929439478862335477963229788891268554471249196395257010701348784708357324867395950580194354930867930722686107634039813045189558321987820794017770490340332452926539684912153534603867461546428215852084394858660228607341522175337230518489884676207418698108705365037294510341623098158866764415564282194859217700196141142426824466829450511358229232138502940469282814912821692304224256506324953250715292204767376029316528316548242159333592118230565471990328296094562646876096399834528364280724791117562388683503333892693956573789345702033108285246963221242084195452037965562359442874594420913980290859853673709870079122702286064341403605685895733626215502184956595751054527234104500239545507311372824334191255580436782933443994557839755041340610907988560890602804301262396268665097311334089204787927321361449675955669785943508868324667869230874012806055361469643176810697740592512586872754546562477281860422068848502270584615041355045648255765117866517679243388647791534117352907030993969773498135586594923902429207926056497451571277787101464596987362803424251795361119164510210898047748769679526926623648132123274336546978796121264323423585391444902498788788218039266356797224752018794027601702023861090149012531069784934427987965402606024254254868733539400903721333813207266514232636113654334005636810095244076718544697629148468001099225997903103151555406794472693237824887747540827233537779001022163519285952169917195833044291141243180118841743499110086598337583991310161503066107236288653077682195475930351984255780291697008433843073433074601889515577836624970796740587397592460130213371218328386231264557513990977768970374188663028891407913278664560320782421269228972276425165664214339199842313246256713838189508942456994912962432552811401183901965103673296419202275000301225114435476721030380997547435864952354248059596899055760756034885926441024088437341295723231840985772140582862127012476602847301280111335538717512240777231806958701100803177954483254789540327331885072038398470482543527616181908366304736353621003016160927217289584014346512557306343472629474328700901108630015682997058185035681265393950991469139560186102049093032348651350437156119780322449547281451304874966230421776236166164310393564949321048105802871165753280456861101967294475380045480141088618879689428970796985166844859316436959517001339410684596644746882151165428823431346617226276979398836168951905251043627836419987645395754583137752391812157923613641822812256916836935788735543852224141118088976283090206170239430144393204604967358679554143078770740751046550355373586838184313367249930706971843162111425117122488408146835378154617332323408201757936693854237404793525052049738896775674090875320991301556058474779893842309277903543692452022563584757065215292945265033614447511323758932811358927423319243865076908787290247658459302352240776781820315613246705852124438522759953531531919501858200233118618980909522409074411111357865492738620078576257406160491318145953676853380127611877268859197026329983875448565469639030274308464089778048663883789597069874503458977803595993550219428038008238874622009784761333246458270194802905091824225279515144180650101703829462247699661042621220963957171482129137268810198958586824948563268269639260156898806748251833184320221886656734967899610901890216734691376507089533073165356996131308780800109241432161858733017946085091560452360874601925519920161534103161515898314875226556878202927548215375384192631270687147040439159818037592863893922340052025682245549407307931063867954171747897701150924273403922366585837624827903333782711690754985802721579316721292837304169555258055322767586889475462901941938543350498355686228398937707905153963062661578743525221827301361893596024700178586399254380106436833321889352926374347262945297822004906389882657615697369580248140471439671157692721743860106393030437272590708194328178900674401242535034675333366425555139849391217599080003338214592107604900061363164067989020474389086192077095584653382324183899321297501416237974926033731393584702848185370012780136649525894298886792799325181246683448991686756027753725617838750996397103468225168417780416539903367661617767239948082332836539936074263688619876922934371072395768401180074799860874308657463508535160724331846365355319819312729583447779080192442714464447751537825555815094737152244971084976233190683409271839454337629856414097314061720526074015952450161078911344693751755130039349680373199599254747132213019844660346010579611469760246840727588479479073602120366659751848892419246209783003723272299111313691745928406091455393370774545055893451970708877848965544161987794235016232067950581909864177442096429323060750469034458202561108454148220246641752715826490286543813955365519564416871042819017269848991228087992400576104821430532344907909110173648615424590448989719927313846595112150605407750486773134125235196754532193000221265567499346675669167727711600682566736809455832645964800782777517361764287975892080279001194328380628100577509737189015566615825195966609575813646966602703084100988334691430682146737698187648774452840946652757332051522676109161464708644154627089669278268510283013409561222076212941966565953044804499599369135886260191165441690238744776455607919753735587157492970984920386180888105206036257223941787106267935809297702955583161313113672220699072903258058017483367462775926882335055915241616439293147550098566829545668131037270639495826638932777289494339505882895536416601674214778536092737984952063623617540489136478305996634279253402096550738347511592487821455009576727326763572367989216883620228621398179722223873738227069943520999295291415579759832641071497123001160378662540012207001156631511537112473290977599260246646332912323982254391460524161807153590309695261723700699659072953645296252832438379204246287869552724034186639158448995655206745776459276757569566934475424540082019261495979460829255170832330594119902850158209146739063208620089830605187118024138501455837836489369088648727587834419074093548077696376052551255341049296736424758727409573641001506173318655571732432343430026670566730420750809653814355762213913064054360053560297945122907184988722790107614575240330121845680480569323427969236302937872822576678462498401625732788475462876421212566787542725401738496527711681877317937789194804521574407573340688666352562165600206642301081450663182179018497520733521549668536476140795950771199906430398315548451876243289406594469844982464701329945546427126995147448836479239004325067516891303070354633114384098440257425477731011258534164709890651001983894117414417996618918484443361597215989525362344546227283762965133400604123922498581550706562884293675351506793508331391097089638702916277596771252777776478068745697890604386743076133049847572728979703193384585712674508529236194093026960701862734929523543509398978885445518617685958768268083273933173936520986869239495684432842089643246834212505653382136543219805142209601871611378148671735001588173032105740382336030520246394139573848514176936858961335792643371787873043941982905138882721190322779321918324765390241531225413449460368083893523202140633081418048798581168274053729258015932373069637059432915587535253049845513526581075728967263280597655163717432283495115724645141710986383124789053282457927639884990273511048016463017460849339019085527493655422546445801380119798171897360018269410609804792308069254779027168466505224707266652627580145523029467870600790476676289800901781561669319844411757563248982283272840812646836175182414761382764388145203821895191151595218696518691872406981168318241201332370692222060383936237636117201165526156957863155583701860616561949305437320873833910675170670306821228507615798177817646859595896320706822428427509801872378290764184516963833483596480719951109537612113060273147929452814441182360175967957993798297641864703073587083021887402757452878814759235255878828829450967469161159167235383240170513187056226418719545829065734457474838495121459385173935677788888049943533786181918892017885638146796172878789590289145517968689525343868885772954306788971222382036524640670285569505128348695009978414590463867073370236958681727384035361211362353637349573713717960694874357490694075959311524426361340521893957162462287039988035147548019025061129651869574366752008620573813230160191202295951795588142997319284085438208430336949701304898220726192882601484990791653703871277923102807815226586002707394906101616844429481327828900505182139251350188930443688915639968259408181947131267308957632581016217764258424928165300520237945697816317732927385799663862565497326983790175021251319429888726750155829559307487271998656173203764085185766234966218383583837144367946653000278404227312931449229410045710362825681100924490018064872684952777634459696479632214081852088847854566687585314795724655262903411835507248675299956949223079832960928989026912141995586090753958799648603558019365017842272654905607626189067184669032603846854101285467298742973407972217296328084747890042362433635164165528980198938784122239624857284082414157100988469101505445436826679080557877885246463468869853851930055722577154170691028639024419404620231756218856935483007347695202939433183696177701812155576531940276674696067546658587672958123128853937735334964276459060914064349842335664313043613695315820400286549360101379318106821244480331817104676839042826022335089627853190630584761668797810219281643576420737271577420163885762392627281731376727000653085470637597037174626219879898385374786636070847654177980140421796087418258214840017018164650781645619528696473771084032141305148775584605475575261632968622758261223104974227712510442008923565643718604523491642166663803304815161606323379791838677709303305930948670123385888617159760038871536655293883755808622965690102918868022824215469117097977034150817344201199669402397100346905334152323726923550456857747626327625280725572918369714000517373628225335739095953676003316374425859910261765441525364723553533723434952162189667220973669771730817756908834252753540741407935757257659089417805853792692946463031264266020032997879343797349421400722863175730512452785383794356363786125028263257569800223672542311502481830094008337359077047657168445144324456700902139215411530892298582441208032029102675467042765437531044576254375344389985940660067557310940404532862802463545039771311804387573950950861548139630077619029000145295184008164628375420210717227057819208339526646801876374545823351663693479587691354815065914399742320995312243152226777839933172055774175981589070808884040913064717750251917736122249860274226342590623771895518656523695198764989682144211646752772845837794677341321552867864293206231444106547751081893958487119434752575897002594823298248655825418203964192785845144898215597279696392000616672902208845834059798009529974969661248182900295965195771120222525454887248863754524774558292159015438066579914654927964373165125981971570616307473171261362836347627181769023280220543280695205051356334292389942519481591088561577994948770903383610318430423023643125881354813015714891805646251942932744689254090056228504820061548285993994012182460381770919949960964688896258124101646242653067871382392788795960515252952503759863004126975272291995231268932158585812619813044502137905249325693784131120515470993707393107770082154690356505338258267202247049110218765273510080203443409787211388420478897553499612737686134746591828454148776740710349384507302173940415369000365436372958477595545133031065480438971825010437106603013659298856622987369305434336458274681442880906359241328188519678953865350028732315930348834076133205727964386536523631602544016699793101803505057780688865434708695556103485171273087403358988894530678371316758209901929683888396224568717872463916352742032707895177958370323471052617784122789381070986347215980579931745496763972704394555646902088454566377548731502219648587373656630174916895864874279703102718301630729979898285867225153481149538823191061988074671152352088191500570535987347518561577508946974921956627069400031286073404236655019235041371431175733134797832753881964049042345925154652083029050796289119683783612018112560311429641609919775388784525469357985150569482248288638512543978328868863589258504970500537810176914334882333021705900262712319680593640372125765788580476170975746013402039022542338454052739470595506339261331984614720879127455851901941198902408093620626172442406295371804639666823531179292085279612764019500434408215411437540133215610931189871252574578354485232403236540275526597297713562615259956647333395279119915621210701784382389249127730572072423411204755994395522103428446272456657529365783752148525616871909054243710655518335541765173623979230356464861015746518415822844961365703040651605418003505505780656717122426786267703316701166755383501238851140044073449072622222263131886893460347069768393617041097174859813640000542210004850977984435886960421095793602946466439770701514991684731490074523852359636312250424556870729424992686901920327203764258486288760365144947826981462904512002127757750950170389796054075626077254586655428043404052599670263264035105964128091940463054001295327011464297479132682829030952800257101813907945703635881570585179593772684196438383415168094644233886146238905998637191882832442510342098588967226369880575288027585476823792355959127720162549533681545782505920973028209980729902859315659396644582824591178805210500670712113854403437316008452567496653280311804153842800552015952469361461961325714783559559346622889490068035832697264146016087145107885066376051428267873658497374459089793781292208419319132057533931784102158442245604469597906935165539674593047257918423450699362871657543977802313180118196458587000390629593628917089388505361062189604909864782021012331677118564447717154294383816699813822027118939962585557314021079766015336064718627146652351945399087873443653643589332726764507097875810973885934021605878459502805205881833111392650907669072886252092773094801229096596210228677079453091484636627185129497164980826869064824379781130095829308239185284995925882955920916323651420985913815583364415301076016745508503097429276591986169852653780884632976837286297751484913613116332050162061717702250105297989859753165538382713065318237528205270255637455446705423418694479792846505904117277262975067979834042567430231348867520479610033041650664417274223704632303900575123466454263528756789971847440247038888717783162086959739361219977772305598639264893899827715051989037751730358085483095649031658936088098084890401644569092713576759691612454685034656003133390087542438570185853699101852778839027426821362509905708582763626296362697818305985013797260210366628782369250950453880457967581189394341150495524929365683304815285212914628041548683804957446458106847335799198272909069824062232644324413379981396565182884410990078451908121489729520959948554114607057798069520710271747073681932535191791082019344376269551779704651453094725561532240969136806909590183293482204297916675039384080088382527876941258002456477086893123896028991251735233427056691210346182844110310949236017941251318013931483512048257937587866107180038511569490666944153067925096952409119103491203475523979550473606108251630270063009889340799527059278100211508381579120150825703769896545422209364044764962526303644007408711898334974708945765937948445688880592697362568400273982423283733387474851406393210255352970085804396635775343304335214193072287036896693497641072056997309042423883093422808685399151588037766494982383059113350000283936236629246214883925747928146609434649171569560589280904056767116587674501065180556058547255929534985766825011700978579410020115111379758917366620289922909813067257445888941616051468063236795491641940888034868774693998721229688914756338996038067133748173096685477512027236071404148763517999690286293618571492489480996107380176172289767379701813155946421478569839858777349629120369749191390757318192622703102622144999315366565083000796294691220091919488967536938943777282096796898377706558205115152690878300630666554968973628115325823595214074099810590318876238242786448779629174619032885368144019730801195773111264788011904776041924136686980407024993769069438515411073027144343500314451571675280514472983395199993713037760231407362946498277210924838678113234937345660237481511497751288337896346807828650412800290324498586308025110003008428983732206576613914428123219240753565400586410540401079858061721430596606688693293576476315948217855801859726791338863161111842163482125837441550366830584085940884475313608350547201052981933061967614046645172622216643719552324004459816448204798774276204651813529810297099328507558871717363880456469149866927815750536694898305538143063223956078001197146131539017590443828690475221863875858283693472302217830423391280527350252815670104431784548806559534283121510781010476396651417858920470224967113851171600493216279327730301239055048547347755966096317461147728163862748564450489376040190560037415174508521647171818153808571222598992178878690933196382424866269579220026510152553873787223850341412244845380117396852955931566150524419247222914194430412573480060255408386732226249253933110937296002342984100910995076248522877490557896377860457558169268959661867254735060532948852504945572052817351792375219036300
コードの実行結果から、Wikipedia に記載のとおり最小のペラン擬素数が $271441$ であることが確かめられた。また、$P(271441)$ は、上記右辺の$2014$で始まり$6300$で終わる数で、これの桁数は、33,150桁ある。
追記
最小のペラン擬素数を求めるためには、ペラン数列のリストを作る必要はなく、メモリに優しいジェネレータにした。
from helper import is_prime # 素数判定関数はどこかに用意しておいて、import する。
def gen_perrin_numbers(end_index=100): # デフォルトでは P(0)からP(99)までの100個をyieldする。
a, b, c = 3, 0, 2
while end_index > 0:
yield a
a, b, c = b, c, a + b
end_index -= 1
if __name__ == '__main__':
for n, p in enumerate(gen_perrin_numbers(1000000)):
if n <= 1:
continue
if (not is_prime(n)) and p % n == 0:
sp = str(p)
print('p({})={}...{}: len={}'.format(n, sp[:4], sp[-4:], len(sp)))
break
上記を実行すると、以下が出力される。
p(271441)=2014...6300: len=33150