Milyen osztót kell alkalmazni, hogy a maradék érdekes legyen?

Valószínűleg mindre van megfelelő matematikai módszer, csak mindre másik.

Egyenként kéne végignézni.

Tetszik a téma, csak sajnos most nincs időm utánaszámolgatni, így szégyenkezve várom én is a megoldásokat.

Szerintem ki kéne pécézni elsőnek egy verziót, mondjuk ismétlődő szakaszos tizedes tört mint maradék.

A gond már ott kezdődik, hogy "érdekes". Ami az egyik embernek az, a másiknak nem.

Ott folytatódik, hogy mi a megfelelő motiváció a keresésre.

Ezután jön, hogy van-e elegendő ismert a kereséshez.

Végül, ha már mind összejött, általában felteszik a kérdést: mi a haszna? (közkeletűen, mire jó nekem). És erre csak kevesen tudnak értelmes választ.

Ez az oka annak, hogy kevés a vállalkozó.

@Wadmalac

Valamit félreértettél vagy ha nem akkor nem tudom hogy gondoltad. Itt maradékos osztásról van szó.

Vagyis amit a kérdező ír pl. 312190173402122873 = 515746862*605316670 + 333333333

@Kérdező

"Hogyan lehet olyan osztót találni hozzájuk, hogy a maradék érdekes legyen."

Ez azért félreérthető mert egész számok körében akkor osztója egy szám a másiknak, ha maradékos osztással elosztva vele 0 a maradék. A kongruens szó lett volna a megfelelő.

Az hogy mi az hogy érdekes maradék, ezt nem tudom megfogni, mint ahogy egy valaki ki is fejtette már. Jó hír azonban, hogy e nélkül is meg lehet oldani. Mint tudjuk, hogy példát írni rá könnyű mert csak veszünk 2 számot, hozzáadunk annyit amennyi maradékot akarunk és a maradékhoz és a számhoz megvan a megfelelő osztó. Viszont ha az a kérdés, hogy milyen másik osztó van hozzá akkor már "bajba" vagyunk. Illetve ha csak a "semmiből" kapunk egy számot és egy maradékot na akkor mond meg, hogy mikor jön ki ez a maradék! Ez esetben a megoldás visszavezethető az osztók keresésre. Úgy hogy n szám esetén n-modulo (maradék) számnak az osztóit keressük és ezek közül nekünk a modulo-nál nagyobb osztók kellenek, hiszen ekkor és csak ekkor fog teljesülni, hogy annyi legyen a maradék amennyit akartunk, de az is lehet hogy ez sose teljesül. Az osztók keresésén meg lehet gyorsítani a brute force-nál gyorsabb, ha az osztók keresését visszavezetjük a prímfaktorizációra. Itt a próbaosztást gyorsíthatjuk úgy hogy elég csak a prímekkel elvégezni, hiszen ha egy számmal osztható ami összetett akkor ennek a számnak a prímtényezőivel is osztható lesz, ellenkező esetben meg azokkal sem. Természetesen a négyzetgyökéig kell nézni maximum, hiszen ha a négyzetgyökénél nagyonobb prímtényezője van akkor bizotsan van négyzetgyökénél kisebb prímtényezője. Kis prímekkel érdemes még bepróbálni a gyorsítás miatt, a nagyobbakkal meg Pollard Rho Brent prímfaktorizációval, de persze lehet más különböző prímfaktorizációt is használni melyekről matematikus szakos szakdolgozatot is láttam már régebben. Ugye ez nagyon kemény feladat is lehet még géppel is, a különböző prímfaktorizációs gyorsító algorimtusokkal is, bár elég jó eredményt hoz ki a sima brute force-hoz képest. A prímtesztelésre érdemes Miller-Rabin prímtesztel ellenőrizni hogy prím e, gyorsabb mint prímtényezőjét keresni, hogy van e neki. Amikor megvannak a prímtényezők akkor ezekből kell képezni az összes szorzatot melyek mindegyike úgy van előállítva hogy el van hagyva valami a prímtényezők közül, kivéve amikor mind szerepel.

Egy online futtatható python kód hozzá : [link]

Használati utasítás:

STDIN-hez beírni szóközzel elválsztva az adott számot és az osztót, az Exceute-al lefuttatni és megkeresi az összes ilyen számot.

Pl.:

Bemenet:

283202450198951312 100000000

Kimenet:

198400504

396801008

713714039

1427428078

2854856156

5709712312

11419424624

17700153131184457

35400306262368914

70800612524737828

141601225049475656

283202450098951312

Nem én találtam fel a meleg vizet, feltüntettem, hogy melyik kódrészlet honnan származik, kivéve amit én írtam hozzá. Pl. a primesbelow függvény az a kis prímeket állítja elő gyorsítás miatt Eratosztenészi szitával egy stackoverflow-ról származó kód.

"@Wadmalac

Valamit félreértettél vagy ha nem akkor nem tudom hogy gondoltad. Itt maradékos osztásról van szó."

Bocsánat, tényleg törtet írtam, hülye beidegződés miatt. De ismétlődő számsort akartam.

"De ismétlődő számsort akartam."

Ha a periodikusan ismétlődő csupa nullákat is belevesszük akkor mindig ismétlődik. Ha meg a szokásos módon nem vesszük bele, akkor meg abban az esetben nem ismétlődik, ha 10^n-szerese a hányadosnak egész szám (ahol n tetszőleges pozitív egész).

Aki ért hozzá az tudja hogy így miért jobb, hogy egyetlen sort átraktam a kódba (a main-be keresd): [link]

Egyébként az előző se számol se lassabban se rosszul.

Ezt nem értem.

Mi az a factu?

"t: NEM" "t: JÓ" mik ezek?

"Ha van olyan prímtényező, ill. ezeknek szorzata, ami nagyobb, mint a kívánt maradék, és legfeljebb 10-jegyű, akkor jó."

"1616161:416689440589377370= 2*5*41668944058937737 t: NEM"

Ha ezt adom inputnak : 416689440589377370 1616161 akkor nem sorolom fel az összeset, de kiadja megoldásnak 12626952745083673 ezt is ami 17 jegyű ami van legalább 10 jegyű.

Ha 416689440589377370 - 1616161 kivonod vagyis 416689440587761209 1616161 lesz az input akkor ott van megoldásnak pl. 52086180073268131

De ha 416689440589377370 + 1616161 veszed vagyis

416689440590993531 1616161 akkor megoldás pl a 83337888117875474. Egyszerűen nem is értem mi az hogy nem jó. Miért nem jó?