Van-e ennek a sorozatnak több prím eleme is?

Nem biztos, hogy sokat segít, de az OEIS szerint

[link]

3400 darab 9-esig ellenőrizték, odáig nincs több prím.

Nem írtad, hogyan jött ki a 2/3-os összetett szám arány, és hogy bizonyítani is sikerült-e. Lehet, hogy bizonyítottad, nem baj, leírom, nekem hogyan sikerült. (Az az érzésem, az én bizonyításom más, mint a tiéd.)

Aztán a végén írok olyat is, amivel a 2/3-ot 3/4-re, sőt, még többre emeltem.

Szóval erről a sorozatról van szó:

A₁ = 9901

A₂ = 99990001

A₃ = 999999000001

A₄ = 99 99 99 99 00 00 00 01         (Az első 4 elem prím.)

A_n = 100²ⁿ - 100ⁿ + 1

(Az alsó indexet nem tudom mindig kiírni; az aláhúzás után írt dolog alsó indexet jelent, pl. A_4 ugyanaz, mint A₄. Hasonlóan mondjuk x^2 felső indexbe írt kettest, x²-et jelent. Mindenesetre ahol tudok, indexet írok.)

Írjuk fel általánosabban, polinomként:

P_n(x) = x²ⁿ - xⁿ + 1

A legkisebb ilyen polinom a P₁(x) = x²-x+1. Ennek a (komplex) gyökei a másodfokú megoldóképlettel:

x₁₂ = 1/2 ± i·√3/2

Ezek éppen a ±60 fokos egységnyi hosszú komplex számok:

x₁ = e^(i·π/3)

x₂ = e^(-i·π/3) = e^(i·5π/3)

Az egyértelmű, hogy ha egy P_n(x) polinomnál P_n(x₁) = 0 és P_n(x₂) = 0, akkor annak a polinomnak osztója a P₁(x) = (x-x₁)(x-x₂) polinom, vagyis P_n(x) reducibilis.

x₁ és x₂-nek a 6-odik hatványa éppen 1. Ez pedig azt jelenti, hogy n = 6k+1 esetén P_n(x₁₂) = P₁(x₁₂) = 0

Tehát n = 6k+1 esetén a polinom reducibilis, vagyis A_n összetett szám.

Vegyük észre, hogy x₁⁵ = x₂ és x₂⁵ = x₁. Ez pedig azt jelenti, hogy P₅(x₁₂) = 0, vagyis a 6-os ciklust is beszámítva n = 6k+5 esetén is összetett számokat kapunk.

Vagyis prímek ezeknél az elemeknél lehetnek csak: n=6k+{2,3,4,6}, míg az n=6k±1 elemek összetettek.

Eddig tehát a sorozat elemeinek az 1/3-át ki lehetett zárni azzal, hogy P₁(x)-szel, vagyis A₁ = 9901-gyel osztható.

Az oszthatóságra fentebb belátott tulajdonság nem csak x=100-nál, hanem mondjuk x=100²-nél is teljesül a polinomra. Na most vegyük észre a polinom egy érdekes tulajdonságát:

P_n(x^m) = (x^m)²ⁿ - (x^m)ⁿ + 1 = x^(2mn) - x^(mn) + 1 = P_mn(x)

Vagyis pl. P₁(100²) = P₂(100)

A polinomról visszatérve az A sorozatra pedig: a P_n(x^m) polinomhoz a P_mn(x) polinom, így az A_mn sorozatelemek tartoznak.

A polinom oszthatósági tulajdonság pedig azzá alakul, hogy a P₁(x^m) polinom n=6k±1 esetén osztója a P_n(x^k) polinomnak, tehát a P_mn(x) polinomnak, ahol mn = m·(6k±1) = 6m·k ± m

Tehát x=100² esetén az oszthatósági tulajdonságból az következik, hogy P₁(100²) = P₂(100) = A₂ = 99990001 osztója 2n=12k ± 2 esetén az A_2n sorozatelemeknek.

Hasonlóan x=100³ esetén az jön ki, hogy A₃-mal oszthatóak a 18k±3 sorozatelemek.

x=100⁴ esetén pedig: A₄-gyell oszthatóak a 24k±4 sorozatelemek.

Vagyis mind a 4 prímszám, ami a sorozat elején van, osztja a sorozat bizonyos elemeit. Nagyjából az elemek 2/3-át, ahogy te is írtad. Pontosabb szám azzal jön ki, hogy 6, 12, 18 és 24 legkisebb közös többszöröse 72, vagyis 72-es ciklus lesz a sorozat elemei között. Ha felírjuk, hogy a 72 elem közül melyek a 6k±1, 12k±2, stb. elemek, kijön, hogy 50 összetett szám lett köztük, vagyis a sorozat elemeinek az 50/72-ed (0,69444...) része biztos, hogy összetett szám.

Valószínű neked is ugyanez jött ki, csak az egyszerűség kedvéért írhattál "kb. 2/3"-ot.

----

Viszont lehet ennél sokkal többet is csinálni:

Nem muszáj megállni a P₁(x⁴) polinomnál, mint osztónál:

P₁(x⁵)-hez tartozik az A₅ szám. Ez osztója az 5n = 30k ± 5 sorozatelemeknek. Az se lenne baj, ha A₅ nem prím lenne, az a lényeg, hogy osztó (de prím is...). Ez mondjuk nem hoz be új számokat, hisz 30 éppen 6-nak a többszöröse, vagyis már 6k+5 miatt kizártuk ezeket a számokat, mivel oszthatóak 9901-gyel.

Még tovább menve kizárhatjuk a prímek közül a 36k±6, 42k±7, 48k±8, stb, az összes 6m·k±m elemet. Ezek közül sok nem hoz be új elemet, pl. 42k±7 = 6·(7k+1)±1, vagyis ezeket már a 6k±1 mind kizárta. Viszont a 36k±6 nagyon hasznos, egyedül az is kizár a 72-es ciklusú szakaszokból még 4 számot (6, 30, 42, 66), vagyis a sorozat elemeinek legalább az 54/72 = 3/4 része biztos, hogy összetett szám.

----

Az A_n sorozat faktorizálását nézve (az első 36-ot néztem a WolframAlpha-val) feltűnt, hogy vannak ismétlődő prímtényezők az első 4 elemen (9901 stb.) kívül is. Pl. 61|A₅ és 61|A₂₅, aztán 3169|A₆ és 3169|A₃₀, aztán 226549|A₇ és 226549|A₃₅. Az a gyanúm támadt, hogy A_k-nak és A_5k-nak van közös osztója.

Mivel A₂₅-ről már bizonyítva lett, hogy összetett szám, (25 = 6·4+1, vagyis osztja a 9901), viszont A₃₀ még ismeretlen volt (természetesen a WolframAlpha megadta, hogy összetett szám, de nem tudtam hozzá szabályt rendelni), ezért azt néztem meg részletesebben. Meglepetésre azt találtam, hogy A₃₀/A₆ egész szám:

A₃₀ = A₆ · jónagyszám, csupa 9 meg 0, néhány 8 meg 1, amit kis gondolkodással fel lehetett így is írni:

A₃₀ = A₆ · (10⁹⁶+10⁸⁴-10⁶⁰-10⁴⁸-10³⁶+10¹²+1)

Ami polinom alakban ezt jelenti:

P₃₀(x) = P₆(x) · (x⁴⁸ + x⁴² - x³⁰ - x²⁴ - x¹⁸ + x⁶ + 1)

Az a gyanúm támadt, hogy általánosságban ennek kell teljesülnie:

P_5k(x) = P_k(x) · (x^(8k) + x^(7k) - x^(5k) - x^(4k) - x^(3k) + x^k + 1)

Ezt egyszerűen, beszorzással be is lehetett látni.

Tehát visszamenve a polinomról az A sorozatra azt kaptam, hogy A_k | A_5k, tehát a sorozat n=5k elemei (k>0) mind összetettek.

72 nem többszöröse az 5-nek, de nem akartam 360-ig számolni, úgyhogy csak nagyjából, 72-ig számolva még 3 újabb szám esik ki ezzel az n=5k szabállyal. Tehát a sorozat összes elemének kb. 57/72 = 0,791666... része összetett szám.

Itt tartok most...