Matematika | Tanulmányok, esszék » Haskó György - Egy páratlan egész szám legalább egy törzsosztójának megkeresése számjegyei összegének felhasználásával, ha a vizsgált szám összetett

Egy páratlan egész szám legalább egy törzsosztójának megkeresése számjegyei összegének felhasználásával, ha a vizsgált szám összetett. Törzstényezőkre bontás (Searching for any divisor of an odd composite integer making use of the sum of its digits. Factorization) A módszer alkalmas arra, hogy a nem túl nagy páratlan egész számok sorozatában a számok többségéről megállapítsa, hogy az összetett. (For the majority of the numbers belonging to an interval of not too large odd integers this method is applicable to determine whether these numbers are composite.) Készítette: Haskó György mérnök-tanár A módszer a 10-es számrendszernek arra tulajdonságára épül, miszerint ha bármelyik egész számhoz hozzáadjuk számjegyei összegének dupláját, akkor olyan számot kapunk, ami hárommal maradék nélkül osztható. Legyen a vizsgált szám a 0 . A számjegyeinek összege pedig legyen S(a 0 ). (Az „S” az összegzést jelöli) Akkor az „A

1 ” elnevezésű algoritmus lépései: (a 0 + 2*S(a 0 ))/3 = a 1 Ezután kiszámítjuk a 0 és a 1 legnagyobb közös osztóját, amelynek jelölése: LKO(a 0 ;a 1 ) (A legnagyobb közös osztó, „LKO” kiszámítása az Euklidészi algoritmussal történik.) 1 Ha LKO(a 0 ;a 1 ) = 1 és a 1 nem egyjegyű szám, akkor folytatjuk ezt a műveletsort, vagyis (a 1 + 2*S(a 1 ))/3 = a 2 az LKO kiszámításánál mindig a vizsgált számot „a 0 ” – t vetjük össze a kapott új egész számmal, vagyis kiszámítjuk LKO(a 0 ;a 2 ) - t. Ha LKO(a 0 ;a 2 ) = 1 és a 2 nem egyjegyű szám, akkor folytatódik ez az iteráció. Ha LKO(a 0 ;a i ) nem egyenlő eggyel, akkor a kapott szám a definíció szerint „a 0 ” – nak valamelyik osztója. Ha az összes LKO egyenlő eggyel és „a i ” már egyjegyű szám, akkor valószínű, hogy „a 0 ” prímszám, de ez még egyáltalán nem biztos! Megvizsgáltam az összes 1003 – nél kisebb olyan összetett páratlan számot,

amelynek nem osztója a három és/vagy az öt. (A hárommal és az öttel osztható számokat a hárommal és az öttel való oszthatóság egyszerű szabályai miatt zártam ki a vizsgálatból.) Összesen 100 db szám felel meg a feltételeknek az 1 – től 1003-ig tartó intervallumban. Az A 1 -es algoritmussal ebből a 100 darab számból 58 darabnak megtalálható valamelyik prímosztója, vagyis ez 58 %. Példa az A 1 algoritmusra: a 0 = 793 = 13 * 61 S(a 0 ) = 19 A1 LKO 793 277 103 37 19 13 7 831 309 111 57 39 21 21 277 103 37 19 13 7 7 1 1 1 1 13 1 1 2 Az A 1 algoritmus pici módosításával állítjuk elő az A 2 algoritmust: Az A 2 algoritmusnál az „a 1 ” – et a következő képlet adja a 0 + 2*S(a 0 ) = a 1 vagyis itt nincs hárommal való osztás. A 3-mal való osztást először az „a 2 ” előállításánál alkalmazzuk, vagyis (a 1 + 2*S(a 1 ))/3 = a 2 Az A 2 semmi másban nem tér el az A 1 -től. A vizsgált 100 darab páratlan összetett

számból az A 2 algoritmus 20 darab olyan számnak találja meg valamelyik prímosztóját, amelyik az A 1 -gyel nem ad eredményt. Ez 20 % Példa az A 2 algoritmusra: a 0 = 371 = 7 * 53 A2 371 393 141 51 21 9 S(a 0 ) = 11 LKO 393 423 153 63 27 27 393 141 51 21 9 9 1 1 1 7 1 1 Az A 3 algoritmust úgy állítjuk elő, hogy a hárommal való osztást először az „a 3 ” előállításánál alkalmazzuk, vagyis a 0 + 2*S(a 0 ) = a 1 a 1 + 2*S(a 1 ) = a 2 (a 2 + 2*S(a 2 ))/3 = a 3 Az A 3 algoritmus további 4 olyan szám prímosztóját adja meg, amelyek az A 1 és az A 2 algoritmussal nem nyújtottak eredményt. 3 Példa az A 3 algoritmusra: a 0 = 437 = 19 * 23 A3 437 465 495 177 69 33 15 S(a 0 ) = 14 LKO 465 495 531 207 99 45 27 * 465 495* 177 69 33 15 9 1 1 1 23 1 1 1 A fentiek analógiájára készíthető el az A 4 , A 5 , ., A 11 , A j stb algoritmus. A vizsgált szám nagyságától függően egy bizonyos „j” - nél nagyobb indexű „A” algoritmusok már nem

adnak eredményt. Ezért az említett vizsgált intervallumhoz nem használható 11 darabnál több „A j ” algoritmus. Példa az A 7 algoritmusra: a 0 = 493 = 17 * 29 A7 493 525 549 585 621 639 675 237 87 39 21 S(a 0 ) = 16 LKO 525 549 585 621 639 675 711 261 117 63 27 * 525 549 585* 621 639 675* 237 87 39 21 9 1 1 1 1 1 1 1 29 1 1 1 Példa az A 11 algoritmusra: a 0 = 781 = 11 * 71 A 11 781 S(a 0 ) = 16 LKO 813 813 1 4 813 837 873 909 945 981 1017 1035 1053 1071 363 129 837 873 909 945 981 1017 1035 1053 1071 1089 387 153 837 873 909 945* 981 1017 1035* 1053 1071 363 129 51 1 1 1 1 1 1 1 1 1 11 1 1 Vagyis 781 esetében az összes j = 11 – nél kisebb indexű A j algoritmusban előállított „a i ” értékekkel az összes LKO érték egyenlő eggyel. Ha azt nézzük, hogy az említett intervallumba eső vizsgált számok legelőször melyik „A j ” típusú algoritmussal szolgáltatnak eredményt, akkor a darabszámra a következő eloszlást kapjuk. A1 58

A2 20 A3 4 A4 4 A5 2 A6 0 A7 5 A8 2 A9 1 A 10 0 A 11 1 Ez összesen 97 darab szám. Van tehát ebből az intervallumból 3 db olyan szám, amelynek az osztóját „A” típusú algoritmussal nem sikerült megkapni. Ezek a számok: 292 = 841 29 * 31 = 899 312 = 961 5 Ennek a három számnak az a közös jellemzője, hogy a prímosztója vagy azonos a szám négyzetgyökével, vagy megközelítőleg egy egésszel különbözik attól. Ezekre a számokra az „A j ” algoritmustól kissé eltérő „B j ” és „C j ” jelű algoritmusok használhatók. A „B j ”, és a „C j ” algoritmus lényege ugyancsak egy számsorozat előállítása. Majd a vizsgált szám „a 0 ” és a számsorozat egyes „a i ” elemei a LKO - jának megtalálása. A „B j ” jelű algoritmus felhasználja a 10-es számrendszernek azt a tulajdonságát, hogy ha bármelyik egész számból kivonjuk számjegyei összegét, akkor olyan számot kapunk, ami hárommal maradék

nélkül osztható. A „B 1 ” típusú algoritmus lépései: (a 0 - S(a 0 ))/3 = a 1 Ezután kiszámítjuk „a 0 ” és „a 1 ” legnagyobb közös osztóját, amelynek jelölése: LKO(a 0 ;a 1 ) (Az LKO kiszámítása az Euklidészi algoritmussal történik.) Ha LKO(a 0 ;a 1 ) = 1 és „a 1 ” nem egyjegyű szám, akkor folytatjuk ezt a műveletsort, vagyis (a 1 - S(a 1 ))/3 = a 2 az LKO kiszámításánál mindig a vizsgált számot „a 0 ” – t vetjük össze a kapott új egész számmal, vagyis kiszámítjuk LKO(a 0 ;a 2 ) - t. Ha LKO(a 0 ;a 2 ) = 1 és „a 2 ” nem egyjegyű szám, akkor folytatódik ez az iteráció. Ha LKO(a 0 ;a i ) nem egyenlő eggyel, akkor a kapott szám a definíció szerint „a 0 ” – nak valamelyik osztója. Itt is elmondható, hogy ha az 6 összes LKO egyenlő eggyel és „a i ” már egyjegyű szám, akkor nagyon valószínű, hogy „a 0 ” prímszám, de ez nem biztos! Ezzel a B 1 típusú algoritmussal mind a 292 = 841,

mind pedig 29 * 31 = 899 legalább egy osztója megtalálható. Példa a B 1 típusú algoritmusra: a 0 = 899 = 29 * 31 B1 899 291 93 27 873 279 81 18 S(a 0 ) = 26 LKO 291 93 27 6 1 31 1 1 (Bár a fent említett intervallumhoz a B 2 és B j (j>2) típusú algoritmusokra nincs szükség, de a B 2 szerkezete az A j típusú algoritmusok analógiájára a következő lehet: (a 0 - S(a 0 ))/3 = a 1 (a 1 + 2*S(a 1 ))/3 = a 2 stb.) Vagyis az „A j ” és a „B 1 ” típusú algoritmussal a vizsgált 100 darab számból 99 darab faktorizálható. Egy szám maradt még a 312 = 961. Ehhez a „C 1 ” típusú algoritmus használható, ahol a 0 + S(a 0 ) = a 1 Az „a 1 ” nem osztható maradék nélkül hárommal, tehát itt az első lépésnél nem oszthatunk hárommal. Az algoritmus második lépésétől kezdve azonban már a számjegyek összegének a kétszeresével 7 növeljük az előző lépésben kapott számot, és alkalmazzuk a hárommal való osztást. (a 1 + 2*S(a

1 ))/3 = a 2 Ha LKO(a 0 ;a 2 ) = 1 és „a 2 ” nem egyjegyű szám, akkor folytatódik ez az iteráció. (a 2 + 2*S(a 2 ))/3 = a 3 stb. Ha LKO(a 0 ;a i ) nem egyenlő eggyel, akkor a kapott szám a definíció szerint „a 0 ” – nak valamelyik osztója. Itt is elmondható, hogy ha az összes LKO egyenlő eggyel és a i már egyjegyű szám, akkor valószínű, hogy „a 0 ” prímszám, de ez még egyáltalán nem biztos! A „C 1 ” típusú algoritmus rámutat a 961 osztójára a 31-re. Példa a C 1 típusú algoritmusra: a 0 = 961 = 31^2 C1 S(a 0 ) = 16 961 977 1023 1035 351 123 45 21 977 1023 1035* 351 123 45* 21 9 LKO 977 1023 1035 1053 369 135 63 27 1 31 1 1 1 1 1 1 Ez a törzstényező keresési módszer természetesen 1003-nál nagyobb számok esetében is működőképes, bár nem állítom, hogy az összes összetett számot detektálja! Nézzünk példákat nagyobb számokra! a 0 = 90919 = 23*5967 S(a 0 ) = 28 A1 LKO 90919 30325 10117 90975 30351 10137

30325* 10117 3379 1 67 1 8 3379 1141 385 139 55 3423 1155 417 165 75 1141 385* 139 55* 25* a 0 = 1613789 = 97*127131 A1 1613789 1613859 537953 538017 179339 179403 59801 59847 19949 20013 6671 6711 1 1 1 1 1 S(a 0 ) = 35 LKO 537953 179339 59801 19949 6671 2237 1 131 1 1 1 1 Gyakran előfordul, hogy A j algoritmusok közül több is rámutat a szám osztóira erre példa 9946177: a 0 = 9946177 = 19 * 71 73 101 A2 9946177 9946263 3315447 1105167 368403 122817 40953 13665 4569 LKO 9946263 9946263 9946341 3315447 3315501 1105167 1105209 368403 368451 122817 122859 40953 40995 13665* 13707 4569 4617 1539 a 0 = 9946177 = 19 * 71 73 101 A3 9946177 9946263 9946341 3315471 1105173 368403 122817 40953 13665 S(a 0 ) = 43 1 1 1 1 1 73 1 1 19 S(a 0 ) = 43 LKO 9946263 9946341 9946413 3315519 1105209 368451 122859 40995 13707 9946263 9946341 3315471 1105173 368403 122817 40953 13665* 4569 1 1 1 19 1 1 73 1 1 9 a 0 = 9946177 = 19 * 71 73 101 A4 9946177 9946263 9946341

9946413 3315495 1105185 368409 122823 40953 LKO 9946263 9946341 9946413 9946485 3315555 1105227 368469 122859 40995 9946263 9946341 9946413 3315495* 1105185* 368409 122823 40953 13665* a 0 = 9946177 = 19 * 71 73 101 A5 9946177 9946263 9946341 9946413 9946485 3315525 1105191 368409 122823 1 1 1 1 1 1 1 73 1 S(a 0 ) = 43 LKO 9946263 9946341 9946413 9946485 9946575 3315573 1105227 368469 122859 9946263 9946341 9946413 9946485* 3315525* 1105191 368409 122823 40953 a 0 = 9946177 = 19 * 71 73 101 A6 9946177 9946263 9946341 9946413 9946485 9946575 3315555 1105203 368409 122823 S(a 0 ) = 43 9946263 9946341 9946413 9946485 9946575 9946665 3315609 1105227 368469 122859 9946263 9946341 9946413 9946485* 9946575* 3315555* 1105203 368409 122823 40953 a 0 = 9946177 = 19 * 71 73 101 1 1 1 1 1 1 1 1 73 S(a 0 ) = 43 1 1 1 1 1 1 1 1 1 73 S(a 0 ) = 43 10 A7 9946177 9946263 9946341 9946413 9946485 9946575 9946665 3315585 1105215 368415 122823 9946263 9946341 9946413 9946485

9946575 9946665 9946755 3315645 1105245 368469 122859 9946263 9946341 9946413 9946485* 9946575* 9946665* 3315585* 1105215* 368415* 122823 40953 1 1 1 1 1 1 1 1 1 1 73 a 0 = 9946177 = 19 * 71 73 101 A 11 9946177 9946263 9946341 9946413 9946485 9946575 9946665 9946755 9946845 9946935 9947025 3315699 1105257 9946263 9946341 9946413 9946485 9946575 9946665 9946755 9946845 9946935 9947025 9947097 3315771 1105299 S(a 0 ) = 43 9946263 9946341 9946413 9946485* 9946575* 9946665* 9946755* 9946845* 9946935* 9947025* 3315699 1105257 368433 1 1 1 1 1 1 1 1 1 1 1 71 1 Sőt ennél a számnál a B 1 elnevezésű algoritmus is ad eredményt. a 0 = 9946177 = 19 * 71 73 101 B1 9946177 9946134 3315378 3315378 3315348 1105116 1105116 1105101 368367 368367 368334 122778 S(a 0 ) = 43 LKO 1 19 1 19 Ennél a számnál viszont az A 1 , A 8 , A 9 , A 10 algoritmusok nem mutatnak rá egyik közös osztóra sem. 11 Az eddigi példáknál és az általam vizsgált összetett számoknál előálló

„a i ” értékek között nagyon gyakran található olyan 5-re végződő szám, amelyik legalább kétszámjegyű. Minden eddigi példánál csillaggal van megjelölve az összes 5-re végződő „a i ” érték. Ha sok ilyen szám van az a 1 , a 2 , . a i sorozatban, akkor nagy a valószínűsége annak, hogy a vizsgált „a 0 ” szám összetett annak ellenére, hogy az összes LKO(a 0; a 1 ) egyenlő eggyel. Ha az „a 0 ” prímszám, akkor ritkábban van az a 1 , a 2 , . a i sorozatban 5-re végződő legalább kétjegyű összetett szám. Nézzük például az a 0 = 127 prímet, akkor az 5-re végződő számok az „a i ” számok között: 3*5 = 15 és 55 = 25 a 0 = 127 S(a 0 ) = 10 A1 LKO 127 49 25 13 7 7 7 7 7 147 75 39 21 21 21 21 21 21 49 25* 13 7 7 7 7 7 7 A2 1 1 1 1 1 1 1 1 1 LKO 127 147 57 27 15 9 9 9 9 147 171 81 45 27 27 27 27 27 147 57 27 15* 9 9 9 9 9 A3 1 1 1 1 1 1 1 1 1 LKO 127 147 147 1 12 stb. 147 171 63 27 15 9 9 9 171 189 81 45

27 27 27 27 171 63 27 15* 9 9 9 9 1 1 1 1 1 1 1 1 Ha elkészítenénk egy bizonyos intervallumba tartozó összes szám statisztikáját, akkor az 5-re végződő legalább kétjegyű „a i ” értékeket megfigyelésem szerint gyakrabban találnánk az összetett számoknál, mint a prímeknél. Ha tudjuk egy számról, hogy összetett, de nem kapjuk meg egyik osztóját sem az A j , B j , és a C j típusú algoritmusokkal, akkor összeállíthatók a három már ismertetett algoritmus tetszés szerinti kombinálásával újabb algoritmusok is. Nem kizárt, hogy ezek az újabb algoritmusok alkalmasak lesznek az „a 0 ” valamelyik osztójának a meglelésére. Az fent ismertetett módszer természetesen azokra az összetett számokra is alkalmazható, amelyek oszthatók hárommal, és/vagy öttel. Példa: a 0 = 2479725 = 3*355103107 A1 2479725 826599 275559 91875 30645 10227 S(a 0 ) = 36 LKO 2479797 826677 275625 91935 30681 10251 826599 275559 91875* 30645* 10227 3417 3 3

75 45 3 3 13 Az ismertetett példákhoz a számolást a Microsoft Excel tábla segítségével végeztem. Felhasználtam az LKO függvényt, és egy képletet, ami kiszámítja a szám számjegyeinek összegét: Ha a vizsgált szám „a 0 ” mondjuk az C5 cellában van, és a számjegyeinek az összegét „S(a 0 )”-t a C6 cellában akarjuk megjeleníteni, akkor C6 = SZORZATÖSSZEG(--KÖZÉP(C5;SOR(INDIREKT("1:" & HOSSZ(C5)));1)) képletet használhatjuk. Budapest, 2016. 01 22 14