Olyan számot keresek, ami legalább 3 számjegyű, és bármelyik 2 számjegyét bármilyen számjegyre lecserélve, egyik sem lesz prím. Tudsz ilyet?

Ötlet:

Keress egy olyan 100 hosszú tartományt, ahol nincs egyetlen prím sem. Onnan bármelyik páros szám jó lesz neked.

Persze a tartománynak 00-tól 99-ig kell mennie az utolsó 2 számjegyen.

Következő ötlet: ha 200 hosszú bárhol kezdődő tartományt keresel, azon belül tuti lesz legalább 100 hosszú, 00-tól induló tartomány.

Ugye ilyen tartományt nem gond találnod?

Persze ennél sokkal kisebb számok is lehetnek ilyen "erősen összetett szám" tulajdonságúak, csak azokat nehezebb keresni.

Tegyük fel, hogy a keresett szám k számjegyből áll, ekkor ebből a számból (k alatt a 2)*9*9 szám képezhető, ebből viszont le kell vonnunk azt az esetet, amikor 0-val kezdődik a csereszám, ebből (k-1)*9 van, tehát összesen

(k alatt a 2)*9*9-(k-1)*9+1 darabos számcsoportot tudunk képezni, ezt még szét lehet bontani polinommá:

9*9*k*(k-1)/2-(k-1)*9+1=40,5*k^2-40,5*k-9k+9+1=

=40,5*k^2-49,5*k+10 darab számból áll a halmazunk (indulószámtól függetlenül, csak a számjegyszám számít).

Készísünk egy táblázatot; egyik sorba (vagy oszlopba) kerülnek a kreálható számok számossága, mellé pedig az összes k számjegyű szám:

k=3

Összes kreálható háromjegyű szám: 226

Összes háromjegyűjegyű szám: 900

k=4

Összes kreálható négyjegyű szám: 460

Összes négyjegyű szám: 9000

k=5

Összes kreálható ötjegyű szám: 775

Összes ötjegyű szám: 90000

k=6

Összes kreálható hatjegyű szám: 1171

Összes hatjegyű szám: 900000

Érzékelhető, hogy adott számtartományon belül arányában nézve egyre kisebb lesz ez a számcsoport, tehát jó esély van arra, hogy tényleg van olyan szám, ami a kritériumoknak megfelel (ez persze nem precíz bizonyítás, csak megalapozott sejtés). Ehhez még kellene tudnunk a prímszámok eloszlását, amit nem tudunk.

Egyelőre ennyi. Ha eszembe jut még valami, akkor leírom.

Valszám alapú megközelítés:

Az x szám számjegyeinek a száma kb. lg x

Ezért x-ben 2 számjegyet ennyiféleképpen cserélhetünk meg:

N = (lg x alatt 2)·10·10

(megengedtem elől is a nullát, meg saját magára is lehet cserélni)

N = 100 · lg(x) · (lg(x) - 1) / 2

Nagy x-ek esetén:

N ≈ 50·lg²x = 9·ln²x

Az x számnál kisebb prímek száma közelíthető x/ln x módon.

Ezért annak a valószínűsége, hogy az 1..x tartományból választott szám prím:

p = 1/ln x

Nekünk az kell, hogy az összes módosított szám összetett szám legyen. Feltételezve, hogy a módosított számok tekinthetők véletlenszerűnek:

P = (1-p)^N

P ≈ (1 - 1/ln x)^(9·ln²x)

Ez a szám 0-hoz tart, ha x tart a végtelenhez.

Ha csak a párosra vagy 5-re végződő x-eket nézzük, akkor azok módosulatai között a többség tuti összetett, csak azokat az eseteket kell nézni, amikor az utolsó számjegyet is módosítjuk 1,3,7,9 valamelyikére. Ekkor N sokkal kisebb lesz:

N = 4 · (lg x - 1)·10

N ≈ 17 · ln x

P ≈ (1 - 1/ln x)^(17·ln x)

Ennek a határértéke már nem nulla, hanem 1/e^17, ami nagyon pici szám: 0,000000004