Don't take life too seriously: it's just a temporary situation

Pseudoprimi di Perrin

Sequenze  Teoria dei numeri 

Nel 1876 Lucas, esaminando la sequenza definita come P0 = 3, P1 = 0, P2 = 2 e Pn = Pn – 2 + Pn – 3, (v. numeri di Perrin), dimostrò che se n è primo n divide Pn.

François Olivier Raoul Perrin nel 1899 suppose che tale proprietà potesse essere caratteristica dei numeri primi, cosa che avrebbe costituito un test di primalità piuttosto efficiente, e cercò un numero composto con la stessa proprietà, senza riuscire a trovarlo. Altri esperti cercarono senza successo tali numeri, infine nel 1982 William Adams e Daniel Shanks dimostrarono che 271441 = 5212 divide P271441 (“Strong Primality Tests That Are Not Sufficient”, Mathematics of Computation 39, n. 159, luglio 1982).

I numeri composti con tale proprietà vennero chiamati “pseudoprimi di Perrin” e sembrano piuttosto rari: solo 2 inferiori a un milione (l’altro è 904631) e solo 17 inferiori a un miliardo, tuttavia John Grantham dimostrò nel 2010 che sono infiniti.

 

Gli pseudoprimi di Perrin inferiori a 109 sono: 271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431.

Qui trovate gli pseudoprimi di Perrin minori di 1014 (Robert Harley e Dana Jacobsen, The Online Encyclopedia of Integer Sequences http://oeis.org).

 

Gli unici pseudoprimi di Perrin noti che siano quadrati sono 271441 = 5212 e 36366108601 = 1906992.

 

Il massimo pseudoprimo di Perrin noto è 21820010643719189348459243756555939707812045539175666608632803847478876160302774800531722057851833531884004126146210865090197070653868880189559625867459754727073713090924616711853613422828119114381617102058517546865375149628419568400010041988028399903901548800109516381024778515603321122142347214068118891892251874277003989968720315440226820296896247836608538801292951234794277476816520394592395797604896152067816147071618839138537548347177754556329233097993446947475927879595917904730731452471057039913228447069819231974147528469769361617147249845917324367153293616535621440301722048199576109531476597237957482794519212408555969198439180086612426677293791492214027335646994746538035843342471087224596048441559310405629793019219389285459958074207926519074011909871332364749649617141024864366985374867133374038568149858039921667907016960062202008122918206789921611813246803558884506737808271861739390207700909286209756228458238969578501971634812971706669207833255056753831144421193757564189425314326209050771331172971770648024245698776456512743169230308653394226661109617675061215430499075868542147459797368102792867066735398199032669816585264700339738266181367925685918390143879947505798932651278798924421917099215834736416036859340531715705703994259397974721448306416877937233634540255764552614068775077958720826049923203788725193830882428110766655120153321767162763402482571646729443535184738262902790223792682930259972646770066028255813046639125749771256788743514165965139691554159335359256096548231512043145662292584539908233630630623416686323891951515695041748835207019439549805800342926096899282260916686464680886351857190745335506539876151336016883855773158103762113814361518973909758734989194775781036920280653165835092015711042583063595692979056408307560965084104645943087850367750725513620664958937999640551494241505067973687946717625181329405671941018977389193943428126240943188567583057341489135970682608800922493890308296730929442011883795792175648954954181872799343490049628768370441672607185677720467521150708667751876125544569499435754902575963129390715770989789849330459963345038762428879760367628428833708346446787581813947419508552918309760403393336001255253524523250990084227944010945330223449780074366713322900933686598721646966824558633098521627861097911454737802331283982966879242569841462639176240538100471069132240022024999815261877155099328326233538506570393468310793807821070234336347574184496483617336881484518978392691487642952560376911973855825727758995534469302587266416154636575999776659249023372989829313323062443017702990460976623815318075933048424961154437107558241251231126564922878659780306931011149257666700962974043457120990040352730767662860730019992114778921176312285224644592166173374663104973515972020108030670776053896613226817335437080580038871344317356390928272677494701990041654473277426058616763183510082509259624844320380549921893892318471843871108109176039052744094900133626908010823719494355327604688257323913371454606507376646884319008228201004154992411941387896249068825523566890040592991334780411481021215235342677940980162869702039217052132582551 (Holger Stephan, 2020).

 

Negli anni ’80 Adams, Shanks e altri generalizzarono la sequenza di Perrin: scelti due interi r e s, definirono la sequenza di Perrin generalizzata come: P0(r, s) = 3, P1(r, s) = r, P2(r, s) = r2 – 2s e Pn(r, s) = rUn – 1(r, s) – sUn – 2(r, s) + Un – 3(r, s). La sequenza originale di Lucas e Perrin rappresenta il caso particolare r = 0 e s = –1.

La sequenza può essere estesa a indici negativi; definendo D = r2s2 – 4r3 – 4s3 + 18rs – 27 e considerando i resti delle divisioni di Pn – 1, Pn, Pn + 1, Pn – 1, Pn e Pn + 1 per n, si possono avere solo 3 casi per n primo, chiamate “firme” di n:

  • firma-S, se Pn – 1P–2, PnP–1, Pn + 1Pn – 1P0, PnP1 e Pn + 1P2;

  • firma-Q, se Pn – 1a–2 + 2a, Pns, Pn + 1Pn – 1 ≡ –ra2 + (r2s)a, Pnr e Pn + 1a2 + 2a–1, dove a è tale che a3ra2 + sa – 1 sia multiplo di n;

  • firma-I, se Pn – 1Pnr, PnPn + 1s, Pn + 1A’ e Pn – 1A, dove A’ + Ars – 3 e (A’ – A)2D.

Shanks propose di estendere la definizione di pseudoprimi di Perrin ai numeri composti tali che Simbolo di Jacobi (D | n) uguale a 1 e n ha una firma-S o una firma-I oppure Simbolo di Jacobi (D | n) uguale a –1 e n ha una firma-Q, dove Simbolo di Jacobi (D | n) è il simbolo di Jacobi.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.