Milyen extra infót kell tudni a Fibonacci számokról?
Egy olyan n > 10^30 természetes számot, és p prímet keresünk, amelyre igaz:
Fibonacci[n] mod p = 10^30
Ha nem volna kikötés n-re, akkor könnyű lenne, de így ... ?
Milyen "különleges" tulajdonságát kellene ismerni a Fibonacci számoknak?
Mert anélkül lehetetlen találgatással, nyers erővel megoldani a rengeteg variáció, és 2 ismeretlen miatt.
(Nem egy olyan programot akarok megíratni valakivel, ami soha nem hoz eredményt, hanem ötlet kéne.)
#9: "E nélkül a megkötés nélkül meg fogalmam sincs hogy meg lehet e oldani."
Ez nem kérdés, hanem TELJESEN BIZTOS, hogy meg lehet oldani. Nem kamu, vagy lehetetlen küldetés.
Tehát VAN olyan módszer, infó, ami alapján n > 10^30 feltétellel is könnyen, mp(-ek) alatt megoldható, gépidőben.
Nem kizárható (sőt!), hogy a Fibonacci számok és/vagy a prímszámok és/vagy a kapcsolatuk sokkal mélyebb ismerete szükséges.
válasza:@23:01
Erről meg vagy győződve? Honnan veszed?
válasza:Nem látom hogy segíthetne, de ezeket tudtad?
Fibonacci sorozat m-el osztott maradékának a periódus hossza legyen p(m).
Ekkor tudjuk, hogy p(m)<=m^2, ez triviális.
Viszont nem annyira az, hogy LNKO(a,b) esetén p(ab)=LKKT(p(a),p(b)).
És n>=3 esetén n|m => Fibonacci(n)|Fibonacci(m)
Bármelyik két szomszédos eleme relatív prím. (Szerintem az összes különböző elempár az, de ebben nem vagyok biztos most)
Nem tudom ezek miben tudnak segíteni, de hátha nem ismerted és eszedbe jut valami.
#12: Igen, meg vagyok győződve, hogy minden teljesen korrekt. De lehet, hogy matematikus kell a megoldáshoz. :C
Bizonyíték(?) a megoldhatóságra:
A "szupermódszerrel" gyorsan kapható eredmények egyike (nem a legkisebb):
n=2706075082469569338358691163510069334, p=2706075082469569338358691163510069157
Mondjuk van vele legalább 2 nagy probléma:
1) Ki a fene tudja ellenőrizni? (szvsz. 100% hogy jó)
2) Mire menne vele? Legfeljebb annyit látna, hogy O.K., meg hogy a két szám nagyon közel van egymáshoz, de a módszerhez nem jutna sokkal közelebb. Szerintem.
válasza:Húú a mindenit.
Hosszas keresgélés után annyit látok belőle, hogy jó, de nem értem hogy miért működik csak a gyors moduláris fibonacci algoritmust tudom.
például ha az n 1-el kisebb lenne mint amit írtál akkor
Fibonacci[n] mod p = 1033629323428189498226463595560281832 .
"p=2706075082469569338358691163510069157"
p-10^30 egy Fibonacci-szám!
válasza:Eltoltad mert 1033628...... az a fibonacci szám.
Te tudod mi hogy van csak itt szivatsz minket.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!