Matroids Matheplanet Forum Index
Moderiert von Wauzi
Mathematik » Zahlentheorie » Warum spielen die Vielfachen von 15 als Maximum in 2^k+z eine Rolle?
Autor
Universität/Hochschule J Warum spielen die Vielfachen von 15 als Maximum in 2^k+z eine Rolle?
Taxi1729
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 07.01.2020
Mitteilungen: 71
  Themenstart: 2021-09-03

Hallo liebe Community, ich untersuche das Verhalten von Termen der Form $2^k+z$ bzgl. Primzahlsein unter konstantem $z$. Gegeben sei die Folge $P_k(z):=2^k+z$ Für $z$ gerade kann $P_k(z)$ höchstens bei einem $k$ prim sein. Das ist der Fall wenn $P_k(z)=2$. Ich definiere eine charakteristische Funktion $Q_k(z):=\begin{cases} 1, & \text{wenn }P_k(z) \text{ prim }\\ 0, & \text{ sonst } \end{cases}$ Die absolute Häufigkeit an Primzahlen unter den ersten $N$ Folgegliedern beträgt $H_N(z):=\sum_{k=1}^N Q_k(z)$ Die relative Häufigkeit an Primzahlen unter den ersten $N$ Folgegliedern beträgt $R_N(z):=\frac{H_N(z)}{N}\in[0,1]$ Für größere $N$ kann $R_N(z)$ nicht über $\frac{1}{2}$ gehen. Das lokale Maximum über die relative Häufigkeit an Primzahlen sei $M_N(B):=\max\{m=2j-1\le B,\;j\in\mathbb{N}|\;R_N(m)\;\text{maximal}\}$ Das heisst : ich schaue für ein festes, aber beliebiges $N$, welches ungerade $m\le B$ auf eine maximale Häufigkeit führt. Die Tabelle zeigt die Übersicht der lokalen Maxima. Für $N>4$ tritt ein Zeitpunkt ein, ab dem alle lokalen Maxima durch $15$ teilbar sind. Ist mein Quellcode fehlerhaft oder liegt da tatsächlich eine Gesetzmäßigkeit vor? Hier die Tabelle... Als maximale Schranke wird ganz willkürlich $70000$ angenommen. Der "/" trennt die erste restlos durch $15$ teilbare Zahl von den weiteren Gliedern, die ebenfalls restlos durch $15$ teilbar sind. N = 1 : 1 N = 2 : 1 N = 3 : 1 3 N = 4 : 1 3 N = 5 : 1 3 15 / N = 6 : 1 3 15 / N = 7 : 1 3 1605 / N = 8 : 1 3 15 / 1605 N = 9 : 1 3 9 165 / 19425 N = 10 : 1 3 9 19425 / N = 11 : 1 3 9 15 / N = 12 : 1 3 9 15 / N = 13 : 1 3 9 15 / 65835 N = 14 : 1 3 9 15 / 855 65835 N = 15 : 1 3 15 / 855 N = 16 : 1 3 15 / 65835 N = 17 : 1 3 15 / 855 65835 N = 18 : 1 3 15 / 345 65835 N = 19 : 1 3 15 / 165 345 65835 N = 20 : 1 3 15 / 165 345 65835 N = 21 : 1 3 15 / 165 7575 65835 N = 22 : 1 3 15 / 165 1995 65835 N = 23 : 1 3 15 / 345 65835 N = 24 : 1 3 15 / 165 855 N = 25 : 1 3 15 / 165 855 N = 26 : 1 3 15 / 345 855 N = 27 : 1 3 15 / 165 855 23055 N = 28 : 1 3 15 / 165 855 23055 N = 29 : 1 3 15 / 165 855 1995 N = 30 : 1 3 15 / 345 1995 N = 31 : 1 3 15 / 165 345 23055 N = 32 : 1 3 15 / 345 23055 N = 33 : 1 3 15 / 165 1995 23055 \sourceon Python import math def f(pot2, z) : func = pot2 + z return(func) def isPrime(n) : n = abs(n) if (n < 2) : return(False) for i in range(2, int(math.floor(math.sqrt(n))) + 1) : if ((n % i) == 0) : return(False) return(True) def frequency(z) : primes = 0 pot = 2 loopVar = 1 while (loopVar <= N) : if (isPrime(f(pot, z))) : primes += 1 pot <<= 1 loopVar += 1 frq = primes / N return(frq) for N in range(1, 34) : print("N =", N, ': ', end = '') maxFreq = -1 maxPlace = 0 fifteens = 0 for j in range(1, 70000, 2) : freq = frequency(j) if (freq > maxFreq) : maxFreq = freq maxPlace = j print(maxPlace, end = ' ') if ((maxPlace % 15) == 0) : if (fifteens == 0) : print('/', end = ' ') if (fifteens == 5) : break fifteens += 1 print() \sourceoff Gruß Taxi1729


   Profil
Ixx
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 05.04.2020
Mitteilungen: 220
  Beitrag No.1, eingetragen 2021-09-03

Moin, wenn $z$ nicht durch 3 teilbar ist, dann sind doch die Hälfte der Zahlen $2^k+z$ schon einmal durch 3 teilbar, also für $k>1$ keine Primzahlen. Ist dagegen $z$ durch 3 teilbar, ist es keine der Zahlen dieser Form, sodass diese mit höherer a-priori-Wahrscheinlichkeit prim sind. Analog für die Teilbarkeit durch 5. Es ist also nicht verwunderlich, dass Vielfache von 15 in deiner Statistik zu mehr Primzahlen führen... btw: Es lässt sich zeigen, dass für $N\rightarrow\infty$ alle deine relativen Häufigkeiten gegen Null gehen müssen.


   Profil
Taxi1729
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 07.01.2020
Mitteilungen: 71
  Beitrag No.2, vom Themenstarter, eingetragen 2021-09-05

Hallo, \quoteon(2021-09-03 19:38 - Ixx in Beitrag No. 1) Analog für die Teilbarkeit durch 5. \quoteoff Wie steht es mit der $7$? Wenn $z$ restlos durch $7$ teilbar ist, ist es keine Zahl der Form $2^k+z$. Trotzdem sehe ich keine signifikante Zunahme an Primzahlen der Form $2^k+z$ für $z$ teilbar durch $3,5$ und $7$. Könnte das Phänomen zusammenhängen mit der Anzahl der unterschiedlichen Reste $\#R(m)$? $\begin{array}{c|c|c|c|} k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ \hline 2^k\mod3 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 \\ 2^k\mod5 & 2 & 4 & 3 & 1 & 2 & 4 & 3 & 1 & 2 & 4 \\ 2^k\mod7 & 2 & 4 & 1 & 2 & 4 & 1 & 2 & 4 & 1 & 2 \\ \end{array}$ Es gibt solche $m$, so dass $\#R(m)=m-1$ und solche, für die $\#R(m)Beitrag No. 1) btw: Es lässt sich zeigen, dass für $N\rightarrow\infty$ alle deine relativen Häufigkeiten gegen Null gehen müssen. \quoteoff Das überrascht mich aber jetzt. Ich dachte, die maximale relative Häufigkeit für $N\rightarrow\infty$ sei $\frac{1}{2}$. Kannst Du mir einen Ansatz nennen? Vielleicht gelingt mir der Beweis damit.😃


   Profil
Taxi1729
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 07.01.2020
Mitteilungen: 71
  Beitrag No.3, vom Themenstarter, eingetragen 2021-09-07

Weiß jemand, ob der Anteil an Primzahlen in $2^k+z$ mit der Anzahl der Reste $\#R(m_j)$ der Primfaktoren von z zusammenhängt? Der Beitrag von Ixx hat mir schon weitergeholfen. Aber warum ist $\forall z\in\mathbb{N}:\lim_{N\rightarrow\infty}R_N(z)=0$? (Achtung : bitte $\#R(m)$ und $R_N(z)$ nicht verwechseln)


   Profil
Ixx
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 05.04.2020
Mitteilungen: 220
  Beitrag No.4, eingetragen 2021-09-09

Zuerst zur 7: Da die 2 kein Erzeuger modulo 7 ist (die Zweierpotenzen also nicht alle von Null verschiedenen Restklassen modulo 7 durchlaufen), hat man eben auch nicht durch 7 teilbare $z$, sodass alle Zahlen der Form $2^k+z$ nicht durch 7 teilbar sind. Insofern heben sich hier die durch 7 teilbaren von den nicht durch 7 teilbaren nicht so sehr ab... Zum Beweis, dass für festes $z$ der Anteil der Primzahlen unter den Zahlen der Form $2^k+z$ mit $k\leq N$ für $N\rightarrow \infty$ gegen 0 geht, muss ich noch einmal nachdenken. Was ich recht schnell zeigen kann: Es gibt unendlich viele Primzahlen $q$, für die 2 ein Erzeuger ist, also die Zweierpotenzen alle von 0 verschiedenen Restklassen modulo $q$ durchlaufen. Was ich für den Beweis aber brauche, ist nicht nur deren Unendlichkeit, sondern, dass auch die Summe über ihre Reziproken $\tfrac{1}{q}$ divergiert. Und letzteres gelingt mir nicht ad hoc zu zeigen...


   Profil
Taxi1729
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 07.01.2020
Mitteilungen: 71
  Beitrag No.5, vom Themenstarter, eingetragen 2021-09-12

Dann ist ja das, zu was ich "maximale Reste" sage, identisch zu dem Begriff des Erzeugers. Ich wusste nicht, dass das so genannt wird. Den Zusammenhang zwischen Erzeuger und Zunahme an Primzahlen muss ich mir noch mal auf der Zunge zergehen lassen. \quoteon(2021-09-09 13:03 - Ixx in Beitrag No. 4) Was ich recht schnell zeigen kann: Es gibt unendlich viele Primzahlen $q$, für die 2 ein Erzeuger ist, also die Zweierpotenzen alle von 0 verschiedenen Restklassen modulo $q$ durchlaufen. \quoteoff Das sieht mir nach Widerspruchsbeweis aus. Ich denke zur Zeit noch darüber nach. (Vollständige Induktion schließe ich aus. Mit direktem Beweis sehe ich auch keinen Ansatz)


   Profil
Ixx
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 05.04.2020
Mitteilungen: 220
  Beitrag No.6, eingetragen 2021-09-13

Hier zumindest einmal eine Heuristik: Sei $p$ eine Primzahl, die $z$ nicht teilt. Dann ist nach dem Satz von Lagrange die Ordnung von 2 modulo $p$ ein Teiler $ord_p(2)$ von $p-1$. Insbesondere zerfallen also die von Null verschiedenen Restklassen modulo $p$ in $t=\frac{p-1}{ord_p(2)}$ verschiedene Nebenklassen, für die gilt, dass das Produkt eines Elements einer solchen Nebenklasse mit einer Zweierpotenz in jedem Fall wieder in der gleichen Nebenklasse liegt wie das Ausgangselement. Da diese Restklassen alle gleich groß sind, beträgt die a-priori-Wahrscheinlichkeit dafür, dass $-z$ in der gleichen Nebenklasse wie die 1 liegt, $\frac{1}{t}=\frac{ord_p(2)}{p-1}$. Ist dies der Fall, so ist für von je $ord_p(2)$ aufeinanderfolgenden Exponenten $k$ gebildete Zahlen $2^k+z$ jeweils genau eine durch $p$ teilbar, sodass wir hier die bedingte a-priori-Wahrscheinlichkeit von $2^k+z$ durch $p$ teilbar zu sein, von $\frac{1}{ord_p(2)}$ erhalten. Ist dagegen $-z$ nicht in der gleichen Nebenklasse wie 1, so ist keine der Zahlen $2^k+z$ durch $p$ teilbar. Zusammen erhalten wir also die a-priori-Wahrscheinlichkeit dafür, dass eine Zahl $2^k+z$ durch $p$ teilbar ist, von $\frac{ord_p(2)}{p-1} \cdot \frac{1}{ord_p(2)} = \frac{1}{p-1}$. Anders formuliert: Für $N\rightarrow \infty$ sollte der Anteil der durch $p$ teilbaren Zahlen unter denen der Form $2^k+z$ mit $k\leq N$ gegen $\frac{1}{p-1}$ gehen. Da für jede endliche Anzahl an Primzahlen $p_i$, die alle keine Teiler von $z$ sind, die Ereignisse, dass die entsprechenden Zahlen durch $p_i$ teilbar sind, für $N\rightarrow \infty$ unabhängig sind, können wir die entsprechenden a-priori-Wahrscheinlichkeiten, dass die Zahlen nicht durch $p_i$ teilbar seien, miteinander multiplizieren, um die Wahrscheinlichkeit zu erhalten, dass eine der betrachteten Zahlen durch keines der $p_i$ teilbar ist. Anders formuliert: Der von dir betrachtete Anteil $R_N(z)$ lässt sich für festes $z$ und $N\rightarrow \infty$ mittels der oben gemachten Heuristik abschätzen durch $ \begin{align*} \lim_{N \rightarrow \infty} R_N(z) &< \prod_{p\text{ prim, } p\nmid z} \left(1-\frac{1}{p-1}\right) < \prod_{p\text{ prim, } p\nmid z} \left(1-\frac{1}{p}\right) < \prod_{p\text{ prim, } p\nmid z} e^{-\frac{1}{p}} \\ \quad & = \exp\left(-\sum_{p\text{ prim, } p\nmid z} \frac{1}{p}\right)=\exp(-\infty)=0. \end{align*} $ Die Summe über die Reziproken der Primzahlen $p$, die $z$ nicht teilen, ist natürlich unendlich, da ja nur endlich viele Primzahlen $z$ teilen und sich also diese Reihe nur um endlich viele Summanden von der divergenten Reihe der Reziproken über alle Primzahlen unterscheidet. Wenn man etwas genauer argumentiert, dann stellt man fest, dass man mit jeder endlichen Menge von Primzahlen, die $z$ nicht teilen, die entsprechende Rechnung machen kann und so den gewünschten Anteil an nicht durch mindestens eine dieser Primzahlen teilbaren Zahlen unter jede positive Schranke $\varepsilon>0$ drücken kann. Damit ist also zu erwarten, dass für jedes feste $z$ und über alle Schranken wachsenden $N$ deine relativen Anteile $R_N(z)$ gegen 0 gehen sollten. Der Spaß hängt natürlich an der oben gemachten Heuristik. Dass es unendlich viele Primzahlen $p$ mit $ord_p(2)=p-1$ gibt, für die es also nur eine Nebenklasse in obiger Konstruktion gibt, in der also sicher sowohl 1 als auch $-z$ liegen, genügt nicht für die weitere Argumentation. Man bräuchte schon, wie es dann hier gemacht wurde, dass die Summe über ihre Reziproken divergiert. Und dies gelingt mir derzeit nicht, zu zeigen. So viel also hierzu.


   Profil
Taxi1729
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 07.01.2020
Mitteilungen: 71
  Beitrag No.7, vom Themenstarter, eingetragen 2021-09-16

Hallo Ixx, danke erstmal für Deine Darstellungen. Sie könnten für mein Verständnis ehrlich gesagt noch ein wenig ausführlicher sein. Ich habe nämlich nicht alles begriffen. Zum Beispiel : \quoteon(2021-09-13 20:06 - Ixx in Beitrag No. 6) Sei $p$ eine Primzahl, die $z$ nicht teilt. Dann ist nach dem Satz von Lagrange die Ordnung von 2 modulo $p$ ein Teiler $ord_p(2)$ von $p-1$. \quoteoff (was hat die Schlußfolgerung mit $p\not|\;z$ zu tun?) oder \quoteon(2021-09-13 20:06 - Ixx in Beitrag No. 6) $ \begin{align*} \prod_{p\text{ prim, } p\nmid z} \left(1-\frac{1}{p}\right) < \prod_{p\text{ prim, } p\nmid z} e^{-\frac{1}{p}} \end{align*} $ \quoteoff (Vermutlich wegen $1-x<\exp(-x)$ auf $[0,1]$) Was anderes : Ich habe im Internet Zusammenhänge entdeckt, die für Dich von Interesse sein könnten. Also für mich sind sie es : Zunächst filtere ich jene Primzahlen, modulo derer Zwei Erzeuger ist : $E:=\{p\;\text{prim}\;|\;ord_p(2)=p-1\}$ $E=\{3,5,11,13,19,29,37,53,59,61,67,83,101,\ldots\}$ Es gilt : $\circ\; p\in E\Rightarrow p\mod8\in\{3,5\}$ $\circ\; p\;\text{prim}\Rightarrow\frac{1}{p}$ hat im Binärsystem Periode $ord_p(2)$ insbesondere $\circ\; p\in E\Leftrightarrow\frac{1}{p}$ hat im Binärsystem Periode $p-1$ \quoteon(2021-09-09 13:03 - Ixx in Beitrag No. 4) Was ich recht schnell zeigen kann: Es gibt unendlich viele Primzahlen $q$, für die 2 ein Erzeuger ist, also die Zweierpotenzen alle von 0 verschiedenen Restklassen modulo $q$ durchlaufen. \quoteoff Ich habe Deine Posts mehrfach durchgelesen, finde aber jenen Beweis nicht. Bist Du vertraut mit dem Begriff der Primitivwurzel? Und vor allem : Kennst Du die Artinsche Vermutung?


   Profil
Taxi1729
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 07.01.2020
Mitteilungen: 71
  Beitrag No.8, vom Themenstarter, eingetragen 2021-09-24 10:58

Hallo Ixx, hast Du schon die Zeit gefunden, über meinen letzten Post nachzudenken? Eine Antwort würde mich sehr freuen. Gruß Taxi1729


   Profil
Taxi1729
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 07.01.2020
Mitteilungen: 71
  Beitrag No.9, vom Themenstarter, eingetragen 2021-09-28 15:54

Nun, keine Antwort mehr? Dann hake ich den Thread jetzt ab. G Taxi1729


   Profil
Taxi1729 hat die Antworten auf ihre/seine Frage gesehen.
Taxi1729 hat selbst das Ok-Häkchen gesetzt.
Taxi1729 wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]