Anteil der durch n teilbaren Produkte von zwei Ganzzahlen

23.03.2014, 22:50

Dobi

Anteil der durch n teilbaren Produkte von zwei Ganzzahlen

Hallo zusammen,

heute habe ich über folgendes Problem nachgedacht, hab es aber bisher nicht so weit lösen können, dass ich damit zufrieden wäre. Augenzwinkern

Also, man nehme alle ganze Zahlen größer 0.
[1,2,3,4,5,...]
und das ganze nochmal
[1,2,3,4,5,...]
Und dann bildet man aus allen Kombinationen die Produkte.

Wenn man sich diese dann als quadratische Tabelle vorstellt, sieht es so aus:
1*1, 1*2, 1*3, 1*4, 1*5, ...
2*1, 2*2, 2*3, 2*4, 2*5, ...
3*1, 3*2, 3*3, 3*4, 3*5, ...
4*1, 4*2, 4*3, 4*4, 4*5, ...
5*1, 5*2, 5*3, 5*4, 5*5, ...

Nun möchte ich gerne wissen, wie viele dieser Produkte durch 2, 3, 4, usw. teilbar sind.
Meine Implementierung ( http://ideone.com/z3MsU3 ,Haskell), gibt mir zwar eine experimentelle-circa-Antwort, aber ich würde es gerne auch analytisch/intuitiv verstehen.

Für primzahlige Teiler bin ich schon dahinter gekommen.
Bei der 3 ist beispielsweise in jeder dritten Zeile jeder Eintrag durch 3 teilbar, und von den anderen Zeilen jeder dritte Eintrag.
So lande ich dann bei 1/3 + 1/3*2/3 = 5/9
Verallgemeinert dann bei: n -> 1/n + 1/n * ((n-1)/n)
Das gilt aber halt nur für primzahlige n's.
Kann mir jemand verraten, wie ich auf die Formel, die für alle n's gilt, komme? smile

23.03.2014, 23:04

bijektion

Auf diesen Beitrag antworten »

Zitat:

Für primzahlige Teiler bin ich schon dahinter gekommen. Bei der 3 ist beispielsweise in jeder dritten Zeile jeder Eintrag durch 3 teilbar, und von den anderen Zeilen jeder dritte Eintrag. So lande ich dann bei 1/3 + 1/3*2/3 = 5/9

Das ist ja nicht weiter verwunderlich, aber das gilt auch für jedes $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$ .

Zitat:

Nun möchte ich gerne wissen, wie viele dieser Produkte durch 2, 3, 4, usw. teilbar sind.

Was soll das heißen? Du willst die Produkte vermutlich als Menge auffassen, dann musst du aber auch beachten, dass sehr viele Podukte die gleiche Zahl ergeben und somit doppelt gezählt werden würden.
Es ist doch nichts besonderes, dass jede n-te Zahl durch $\begin{eqnarray*} n \end{eqnarray*}$ teilbar ist.

23.03.2014, 23:27

Dobi

Auf diesen Beitrag antworten »

Als Menge will ich die Produkte nicht auffassen. Doppelte Einträge sollen erhalten bleiben.
Ja, es ist nichts besonderes, dass jede n-te Zahl durch n teilbar ist. Deshalb ist der Fall für primzahlige Teiler mit n -> 1/n + 1/n * ((n-1)/n) ja auch so trivial.
Nur wie sieht es für die anderen Teiler aus?
Wie kommt man beispielsweise auf 1/2 (experimentell ermittelt, s.o.) für n=4?

23.03.2014, 23:43

bijektion

Auf diesen Beitrag antworten »

Ich versuche grade ehrlich erstmal zu verstehen was dein Ziel ist.
Warum sollen Primzahlen etwas besonderes sein? Bei der Überprüfung ob Zahlen durch Primzahlen teilbar sind, verhalten sie sich doch nicht unbedingt besonders.

Zitat:

Deshalb ist der Fall für primzahlige Teiler mit n -> 1/n + 1/n * ((n-1)/n) ja auch so trivial.

Soll das eine Abbildung $\begin{eqnarray*} \mathbb{N} \to \mathbb{Q} \end{eqnarray*}$ darstellen?

Ganz allgemein: Ich nehme die Liste wie du sie definierst und ein $\begin{eqnarray*} m \in \mathbb{N} \end{eqnarray*}$ . Dann ist in jeder m-ten Zeile jedes Produkt durch m teilbar, und in jeder Zeile alle m-ten Spalten. Das ist aber nichts besonderes und lässt sich auch ganz einfach erklären.
EDIT: Somit gülte deine Formel auch für nicht- Primzahlen.
Mir ist sehr schleierhaft wie du auf diese rationalen Zahlen kommst. Was sollen die überhaupt ausdrücken? Eine Wahrscheinlichkeit, dass eine Zahl in der Tabelle durch m teilbar ist?

23.03.2014, 23:48

10001000Nick1

Auf diesen Beitrag antworten »

Zitat:

Original von bijektion
Dann ist in jeder m-ten Zeile jedes Produkt durch m teilbar, und in jeder Zeile alle m-ten Spalten.

Wenn ich das richtig verstanden habe, gibt es bei den Nicht-Primzahlen noch mehr. Z.B. sind ja in der 2., 6., 10. ... Zeile nicht nur jede 4. Spalte durch 4 teilbar, sondern sogar jede zweite.

24.03.2014, 09:03

Dobi

Auf diesen Beitrag antworten »

Tut mir leid, dass ich mich so unklar ausgedrückt habe.

Ich versuche es mal so:
Wenn ich mich auf Faktoren von von 1 bis 100 beschränke, erhalte ich 10000 Produkte.

1*1, 1*2, 1*3, 1*4, 1*5, ... , 1*100
2*1, 2*2, 2*3, 2*4, 2*5, ... , 2*100
3*1, 3*2, 3*3, 3*4, 3*5, ... , 3*100
4*1, 4*2, 4*3, 4*4, 4*5, ... , 4*100
5*1, 5*2, 5*3, 5*4, 5*5, ... , 5*100
...
100*1, 100*2, 100*3, 100*4, 100*5, ... , 100*100

Von diesen 10000 Zahlen sind 7500 durch zwei teilbar. 5511 sind durch 3 teilbar, 5000 sind durch 4 teilbar usw. Dass das so ist, weiß ich, weil ich meinen Computer das habe ausrechnen lassen ( http://ideone.com/z3MsU3 ) ;-)

1 -> 10000
2 -> 7500
3 -> 5511
4 -> 5000
5 -> 3600
6 -> 4100
7 -> 2604
8 -> 3075
9 -> 2563
10 -> 2700

Jetzt will ich verstehen, wieso das so ist.

Für 2 und 3 kann ich es durch die oben beschriebene triviale Herleitung nachvollziehen.
Dort gilt dann: n -> 1/n + 1/n * ((n-1)/n)
Wenn ich 2 einsetze, erhalte ich 3/4, was zu den 7500 passt.
Wenn ich 2 einsetze, erhalte ich 5/9, was zu den 5511 passt.
Bei der 4 gilt die Formel aber nicht mehr.
Bei der 5 gilt sie wieder, bei der 6 nicht, bei der 7 schon, bei der 8 nicht, bei der 9 nicht, bei der 10 nicht.
Sie gilt also nur für primzahlige Teiler.

Meine Frage ist, wie so eine Formel, die für alle Teiler gültig ist, aussieht.

24.03.2014, 09:16

bijektion

Auf diesen Beitrag antworten »

Jetzt verstehe ich worauf du hinnaus willst Augenzwinkern

Also ich würde vielleicht so ansetzen: Schau dir die Tabellenzeilen an, ist in einer Spalte ein Produkt durch deine Zahl teilbar, so ist jedes Produkt in der gleichen Spalte und eine nachfolgenden Spalte Teilbar.
Spontan würde ich auch instinktiv mal auf eine Primfaktorzerlegung schauen, dann könntest du bspw. zu 6 so vorgehen: Es ist $\begin{eqnarray*} 6 = 2 \cdot 3 \end{eqnarray*}$ , dann weißt du durch deine Formel, dass $\begin{eqnarray*} 5511 \end{eqnarray*}$ durch $\begin{eqnarray*} 2 \end{eqnarray*}$ teilbar sind, jetzt musst du noch prüfen welche von diesen Zahlen auch durch $\begin{eqnarray*} 3 \end{eqnarray*}$ teilbar sind.

24.03.2014, 10:26

HAL 9000

Auf diesen Beitrag antworten »

@Dobi

Ich würde erstmal seriös definieren wollen, um was für eine Wahrscheinlichkeit es hier geht:

Was heißt das denn, eine natürliche Zahl "zufällig" auswählen - per Gleichverteilung? Die existiert nicht auf der unendlich großen Menge der natürlichen Zahlen. unglücklich

Was du aber machen kannst (und vielleich auch meinst): Wir betrachten die endliche, $\begin{eqnarray*} m^2 \end{eqnarray*}$ Zahlenpaare umfassende Menge

$\begin{eqnarray*} \mathbb{N}_m^2 = \left\{ (j,k) \bigm| j,k\in\mathbb{N},\; 1\leq j\leq m\; 1\leq k\leq m \right\} \end{eqnarray*}$

und darauf dann die Gleichverteilung. Damit ergibt sich für deine Frage eine Abhängigkeit der gesuchten Wahrscheinlichkeit von $\begin{eqnarray*} m \end{eqnarray*}$ , und wir vermuten eine Konvergenz dieser Wahrscheinlichkeit für $\begin{eqnarray*} m\to\infty \end{eqnarray*}$ , was dann zumindest hier auch tatsächlich der Fall ist.

P.S.: Nicht immer ist eine derartige Sichtweise zufriendenstellend. Wenn wir etwa in gleicher Weise die Frage "Mit welcher Wahrscheinlichkeit ist eine natürliche Zahl eine Primzahl?" beantworten, dann kommt schlicht Null heraus. Augenzwinkern

24.03.2014, 10:49

Dobi

Auf diesen Beitrag antworten »

Eigentlich will ich gar nichts zufällig auswählen und auch keine Wahrscheinlichkeiten von irgendwas ausrechnen. Zumindest hab ich das bisher so gar nicht betrachtet.

Ich möchte wissen, wieso z.B. die Hälfte aller Produkte durch 4 teilbar ist, usw.
1 -> 100.00%
2 -> 75.00%
3 -> 55.11%
4 -> 50.00%
5 -> 36.00%
6 -> 41.00%
7 -> 26.04%
8 -> 30.75%
9 -> 25.63%
10 -> 27.00%

24.03.2014, 10:54

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Dobi
Eigentlich will ich gar nichts zufällig auswählen und auch keine Wahrscheinlichkeiten von irgendwas ausrechnen.

Doch, willst du, dir ist es nur nicht bewusst. Augenzwinkern

Gemessen an der obigen Definition dürfte sich für die Primfaktorzerlegung $\begin{eqnarray*} n=p_1^{r_1}\cdot \ldots p_s^{r_s} \end{eqnarray*}$ folgendes für die gesuchte Wahrscheinlichkeit ergeben:

$\begin{eqnarray*} P(n) = \frac{1}{n} \prod_{i=1}^s \frac{p_i + r_i(p_i-1)}{p_i} \end{eqnarray*}$ .

Für $\begin{eqnarray*} n=4 = 2^2 \end{eqnarray*}$ ist $\begin{eqnarray*} s=1,p_1=2,r_1=2 \end{eqnarray*}$ mit dann tatsächlich

$\begin{eqnarray*} P(4) = P(2^2) = \frac{1}{4}\cdot \frac{2+2\cdot(2-1)}{2} = \frac{1}{2} \end{eqnarray*}$

24.03.2014, 12:23

Dobi

Auf diesen Beitrag antworten »

Ah, super. Hat etwas gedauert, aber ich habe es verstanden.
Zur Überprüfung das Ganze nochmal in code: http://ideone.com/aAIu7N
Die Ausgabe passt zu den ursprünglich experimentell ermittelten Werten:

1 -> 1.0
2 -> 0.75
3 -> 0.5555555555555556
4 -> 0.5
5 -> 0.36000000000000004
6 -> 0.41666666666666663
7 -> 0.2653061224489796
8 -> 0.3125
9 -> 0.25925925925925924
10 -> 0.27

Vielen Dank.

24.03.2014, 13:40

HAL 9000

Auf diesen Beitrag antworten »

Dann will ich mal noch eine mögliche Erklärung der Formel nachliefern, möglichst "ohne" Stochastik, dafür mit etwas mehr (halbwegs) elementarer Zahlentheorie:

Der gesuchte Anteil für die durch $\begin{eqnarray*} n \end{eqnarray*}$ teilbaren Produkte ergibt sich, wenn wir eine $\begin{eqnarray*} n\times n \end{eqnarray*}$ -Matrix durchzählen: Denn mit $\begin{eqnarray*} n | (j\cdot k) \end{eqnarray*}$ ergibt sich auch automatisch $\begin{eqnarray*} n | ((j+un)\cdot (k+vn)) \end{eqnarray*}$ , d.h. wir pflastern die Ebene $\begin{eqnarray*} \mathbb{N}^2 \end{eqnarray*}$ mit $\begin{eqnarray*} n\times n \end{eqnarray*}$ -"Kacheln", wobei in jeder dieser Kacheln dieselbe Anzahl passender Paare zu finden sind.

Nach dieser Vorrede nun zur eigentlichen Anzahlbestimmung in der $\begin{eqnarray*} n\times n \end{eqnarray*}$ -Matrix. Für jeden Teiler $\begin{eqnarray*} t \end{eqnarray*}$ von $\begin{eqnarray*} n \end{eqnarray*}$ gibt es unter $\begin{eqnarray*} n \end{eqnarray*}$ aufeinander folgenden natürlichen Zahlen genau $\begin{eqnarray*} \varphi\left( \frac{n}{t} \right) \end{eqnarray*}$ Zahlen $\begin{eqnarray*} k \end{eqnarray*}$ mit $\begin{eqnarray*} \operatorname{ggT}(k,n)=t \end{eqnarray*}$ . Nehmen wir dieses $\begin{eqnarray*} k \end{eqnarray*}$ als Zeilennummer deiner $\begin{eqnarray*} n\times n \end{eqnarray*}$ -Matrix, dann muss zum Erfülltsein deiner Bedingung $\begin{eqnarray*} n\mid (j\cdot k) \end{eqnarray*}$ in der zugehörigen Spalte $\begin{eqnarray*} j \end{eqnarray*}$ die Zahl $\begin{eqnarray*} j \end{eqnarray*}$ mindestens durch $\begin{eqnarray*} \frac{n}{t} \end{eqnarray*}$ teilbar sein. Das trifft auf genau $\begin{eqnarray*} t \end{eqnarray*}$ der $\begin{eqnarray*} n \end{eqnarray*}$ Spalten zu. Damit haben wir Anteil

$\begin{eqnarray*} P(n) = \frac{1}{n^2} \sum_{t\mid n} t \varphi\left( \frac{n}{t} \right) = \frac{1}{n} \sum_{d\mid n} \frac{\varphi(d)}{d} \end{eqnarray*}$ ,

bei letzterer Gleichheit wurde über $\begin{eqnarray*} d:=\frac{n}{t} \end{eqnarray*}$ statt $\begin{eqnarray*} t \end{eqnarray*}$ summiert.

Wenn ich das richtig sehe, ist dieses $\begin{eqnarray*} P(n) \end{eqnarray*}$ multiplikativ, d.h. für teilerfremde $\begin{eqnarray*} n_1,n_2 \end{eqnarray*}$ gilt $\begin{eqnarray*} P(n_1n_2)=P(n_1)P(n_2) \end{eqnarray*}$ . Für Primzahlpotenzen $\begin{eqnarray*} n=p^r \end{eqnarray*}$ ergibt sich

$\begin{eqnarray*} P(p^r) = \frac{1}{p^r} \sum_{i=0}^r \frac{\varphi(p^i)}{p^i} = \frac{1}{p^r} \left( 1 + \sum_{i=1}^r \frac{p^{i-1}(p-1)}{p^i} \right) = \frac{p + r(p-1)}{p^{r+1}} \end{eqnarray*}$

was dann insgesamt für $\begin{eqnarray*} n=p_1^{r_1}\cdot \ldots p_s^{r_s} \end{eqnarray*}$ zu

$\begin{eqnarray*} P(n) = \prod_{i=1}^s P(p_i^{r_i}) = \frac{1}{n} \prod_{i=1}^s \frac{p_i + r_i(p_i-1)}{p_i} \end{eqnarray*}$

führt.

P.S.: Ich schätze mal, dass man bei entsprechenden (Vor-)Kenntnissen über die Dirichlet-Faltung das ganze auch kürzer und eleganter darstellen kann, aber so wie eben genügt es ja vielleicht auch. Augenzwinkern

Neue Frage »

Antworten »

Anteil der durch n teilbaren Produkte von zwei Ganzzahlen

Verwandte Themen