El lehet-e dönteni egy általános 100-jegyű számról, hogy az felírható-e Fibonacci-számok szorzataként?

@13:10

( Ne viccelj! )

Egy véges tartományba nézd meg melyikből van több, Fibonacci számokból vagy prímszámokból! Nézd meg az eloszlásukat! Exponenciális rátával többségbe lesznek a prímszámok.

A fib(481) a legkisebb Fibonacci szám ami több mint 100 jegyű. Ha a naív módszer szerint is csinálom akkor is maximum 480 darab próbaosztással eldöntöttem ha a kérdésre adandó válasz a nem, egyébként elég lenne a négyzetgyökéig próbálgatni csak. Ha igen a válasz akkor erre egy felső becslés legyen az hogy csupa 9-esből álló 100 jegyű szám és mindig osztható 2-vel (ez tudjuk hogy nem igaz hogy osztható kettővel, de a valós legrosszabb eset is jobb ennél) fib(3) = 2. Vagyis log2(10^100-1) ~ 332.19 => 333 darab próbaosztásnál kevesebb osztásból biztosan mindig eldönthető.

Ja igen. Viszont nem kell fib(480)-tól keresni, hanem fib(3)-tól lehet backtrack kereséssel a próbaosztásokat, azzal a négyzetgyökös trükkel meg nem lehet optimalizálni. Ha talált fibonacci osztót és tovább nem folytatható abból az ágból (ahol mintegy fa a próbálkozások struktúrája) mindig visszalép a backtrack-nak megfelelően. Nem olyan nagy a komplexitása, géppel pik pak kiszámítható.

Ez meg jóval nehezebb feladat amit másodjára kérdezel, még gondolkodom rajta.

Én a máj. 24. 21:23-as hozzászóló vagyok. Lehetséges hogy van rá valamifajta megoldás, de már nem látok rá inspirációt több időt beleölni. Úgy mint az RSA challenge-eknél [link]

Sikerült olyan számokat faktorizálni matematikus számítógép tudósoknak amiket triviálisan tíz a sokadikon évig tartana. Viszont a most 2020-ban használt security minimum követelményt a 2048 bites RSA-t még csak meg se sikerült közelíteni azt törni.

Ez a fibonacci számos utóbbi kérdés is NP nehéz feladat lehet. Olyan nagy számoknál már nem elég sűrűn van hogy egyesével próbákkal végig lehessen brute force-olni értelmes időn belül (mínusz egy, plusz egy, mínusz kettő plusz kettő amíg találat van). Ahhoz meg nem elég ritka (a kombinatorikus robbanás miatt), hogy az egészet legeneráljuk egy tárolt adatszerkezetbe mondjuk egy keresőfába.

Néhány egyforma hosszú intervallumban előfordulási grafikonok, látszik hogy egyre ritkább egyre nagyobb számok esetében : [link]

Néztem nagyobb számokra is, ordóba lineáris ritkulás csak így szemre teszekre alapozva mondom, nem bizonyított numerikus analízis módszerekkel alátámasztva.