Binomiális együttható nem triviális visszafejtése?

Minden ilyen alakú szám felírható n*(n-1)*...*(n-k+1) alakban.

Nézzük, mi a helyzet akkor, hogyha ez a szám mondjuk 5 egymást követő egész szám szorzataként áll elő:

n(n-1)(n-2)(n-3)(n-4) = 999999999008613538005453732267103943423289429966599316680850

Most csináljuk azt, hogy a bal oldalon minden tényezőt n-re cserélünk, ekkor értelemszerűen a bal oldal legalább akkora lesz, mint a jobb oldal, tehát:

n*n*n*n*n >= 999999999008613538005453732267103943423289429966599316680850

n^5 >= 999999999008613538005453732267103943423289429966599316680850

n >= 999999999801,7

Most ugyanezt megcsinálhatjuk lefelé is, tehát ezt kapjuk:

(n-4)^5 <= 999999999008613538005453732267103943423289429966599316680850

n <= 999999999805,7

Ezt a két egyenlőtlenséget egybevetve láthatjuk, hogy n-nek milyen értékei lehetnek.

Természetesen nem tudjuk, hogy 5 szám szorzatát látjuk-e vagy sem, de innen a megoldási mód ugyanúgy megy bármennyi tényezőre; veszel egy k tényezőből álló szorzatot, ekkor fel tudod ugyanazt írni, mint az előbb:

n*(n-1)*...*(n-k+1) = 999999999008613538005453732267103943423289429966599316680850, erre azt kapod, hogy

n >= (999999999008613538005453732267103943423289429966599316680850)^(1/k) és

n <= (999999999008613538005453732267103943423289429966599316680850)^(1/k) + k-1

Látható módon itt n-re k különböző számot kapsz, így azokat kell végigpróbálgatnod. Persze ha a kapott szám nem esik 10^6 és 10^12 közé, akkor nem kell vele foglalkoznod.

Még egy dolog; a számod 0-ra végződik, tehát 10-zel osztható, vagyis vagy pontosan 1-szer osztható 2-vel és legalább 1-szer 5-tel, vagy legalább 1-szer 2-vel és pontosan 1-szer 5-tel. Nyilván 2-vel mindig többször lesz osztható, mint 5-tel (legalább 3 tényező esetén), ezérz az 5-tel való oszthatóságra kell koncentrálnunk. Ha már 10 tényeződ lenne, akkor abban már biztosan lenne két 5-tel osztható szám, így biztosan 00-ra végződne. Tehát a szorzat legfeljebb 9-tényezőjű lehet, de még ott is láthatjuk, hogy a legkisebb 5-ös maradéka 1 kell, hogy legyen. Més tényezőszámra más-más szabály mondható, csak hogy ne kelljen mindent végigpróbálni.

Illetve ha a tényezők között van olyan, amely 00-ra, 25-re, 50-re vagy 75-re végződik, akkor biztosan 00-ra fog az eredmény végződni, tehát azon esetek is kihúzhatóak, ahol ilyenek vannak.

Valóban, igazad van. Lemaradt a /k! a bal oldalon, amivel fel lehet szorozni. Már késő volt, és nem gondoltam át eléggé.

A másik sejtésedre nem tudok mit mondani. Ha így is van, be kell bizonyítani, viszont az ilyen "ha közel van az egészhez, akkor az a jó" kijelentések ritkán jönnek be.

Jelöljük a számodat B-vel.

Ha ekkora számról, illetve pontosan erről a számról van szó, akkor viszonylag szerencsésebb a helyzet. Vannak olyan módszerek, amik esetén egy ekkora szám prímtényezőkre bontása meglehetősen gyorsan – 0.0 másodperc alatt – elvégezhető. Lásd: [link]

Ebből az jön ki, hogy a számunk prímtényezős alakja:

2 × 3 × 52 × 37 × 73 × 89 × 127 × 557 × 1979 × 8101 × 19441 × 1362089 × 2465621 × 14156543 × 125993233 × 209988721

Ugye:

b(n,k) = ∏ {i=1...k} (n+1-i)/i = n * (n-1)/2 * (n-2)/3 * … * (n-k+1)/k

Valahol ebben a szorzatban kell lennie egy olyan tényezőnek, ami osztható 209988721-el. Nyilván belátható, hogy a szorzat legnagyobb tényezője n.

Tehát n-re van egy alsó becslésünk:

n ≥ 209988721

Ha n ennél kisebb lenne, akkor a szorzatban sehol nem szerepelne tényezőként 209988721 vagy annak egész számú többszöröse.

(Jelöljük ezt a továbbiakban „N”-nel, azaz N = 209988721 )

~ ~ ~

Ebből tudunk adni k-ra is egy felső becslést.

b(n,k) = n! / (k! * (n-k)!)

b(n,k) = [n! / (n-k)!] / k!

Egy kicsit jobban belegondolva belátható, hogy:

n! / (n-k)! ≤ (n-k)^k

Tehát:

b(n,k) ≥ (n-k)^k / k!

Mivel van egy alsó becslésünk n-re, így:

b(n,k) ≥ (N-k)^k / k!

Ha vesszük B és N logaritmusát, vagy máshogy nézve megnézzük a nagyságrendet, akkor gyanítható, hogy k nem lesz túl magas. B = N^7,32

Próbáljuk k=8-ra:

B ≈ 9,99 * 10^60

(N-k)^k / k! = (209988721-8)^8 / 8! ≈ 9,37 * 10^61

Ez már túl sok.

Nézzük k=7 esetén:

(N-k)^k / k! = (209988721-7)^7 / 7! ≈ 3,57 * 10^54

Tehát:

2 ≤ k ≤ 7

(Ha nem a triviális – pl. a k≠1 – megoldásokat keressük.)

~ ~ ~

Ebből már könnyebb elindulni, a valódi n közel lesz a (B*k!)^(1/k)-hoz, sőt inkább (B/k!)^(1/k)+k/2-höz.

Ha k=7 esetén van megoldás, akkor

n ≈ 1259932327,999999 ≈ 6,0000000095 * N ≈ 6 * N

Némi keresgélés után ki is jön, hogy egészen pontosan:

B = b(1259932331, 7)

k=6 esetén n ≈ 29937951650,292409 ≈ 142,569331 * N. Erről már látszik, hogy itt nem lesz megoldás.

k=5 esetén n ≈ 2605171084180,805623 ≈ 12406,242924 * N

k=4 esetén n ≈ 2213363838852068,448151 ≈ 10540393,923595 * N

k=3 esetén n ≈ sok ≈ 865341997216,912461 * N

k=2 esetén n ≈ több ≈ 673…212,126691 * N

Egyik esetén sem eléggé kerek a becsült n.

Így tehát az egyetlen nem triviális megoldás:

B = b(1259932331, 7)