Limieten van getaltheoretische functies

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Reageer

Limieten van getaltheoretische functies

Laat N(n,p) het aantal positieve natuurlijke getallen kleiner dan of gelijk aan het positieve natuurlijke getal n zijn, dat deelbaar is door het priemgetal p maar niet door priemgetallen kleiner dan p.

Bestaan dan de limieten:
\(\lim_{n \rightarrow \infty} \frac{N(n,p)}{n} \)
voor alle priemgetallen p? En zo ja, is hun uitkomst bekend?

Re: Limieten van getaltheoretische functies

\(\frac{1}{p}\prod_{p'<p}(1-\frac{1}{p'})\)

Re: Limieten van getaltheoretische functies

Dank je. Leuk dat die limieten bestaan, en bekend zijn.

Ik ben van plan ze voor een ander topic te gaan gebruiken. Maar ik moet nog even kijken of dat lukt.

Berichten: 39

Re: Limieten van getaltheoretische functies

... en bekend zijn.
Het is niet ZO moeilijk, want, een getal
\(m\)
voldoet aan criterium
\( \iff \)
alle getallen
\( \equiv m \pmod{p \prod p'} \)
We kunnen ons dus beperken tot het interval
\([1,p \prod p']\)
, omdat als
\(n\)
veel groter is dan ons product er een groot aantal hele intervallen kleiner dan n zijn en 1 deel van een interval, echter, de weging hiervan gaat natuurlijk naar 0 als n naar oneindig gaat en dit kunnen we dus verwaarlozen.

Het aantal getallen op bovenstaand interval wat aan de eis voldoet kunnen we met CRT berekenen: er zijn
\(p'-1\)
mogelijkheden modulo alle priemgetallen
\(p'\)
kleiner dan
\(p\)
(alle behalve 0) en er is slechts 1 mogelijkheid modulo
\(p\)
, namelijk, 0. Het totaal aantal mogelijkheden is dus
\(\prod(p'-1)\)
. Als je dit deelt door
\(p \prod p'\)
vind je (PP).

Ik hoop dat het duidelijk is ;)

Re: Limieten van getaltheoretische functies

Mijn vraag is heel snel beantwoord. Waarvoor dank!

Daarom stel ik ook maar gelijk mijn volgende vraag, waartoe mijn eerste vraag het aanloopje vormde.

We kunnen voor de verzameling
\(\nn\)
+ van alle positieve natuurlijke getallen vele deelverzamelingen D vinden zodat
\(\lim_{n \rightarrow \infty} \frac{D(n)}{n} \)
bestaat en ongelijk aan nul is. Onder D(n) verstaan we daarbij het aantal elementen van D die kleiner dan of gelijk aan n zijn.

Laat
\(\mathfrak{D}\)
de verzameling van al dergelijke verzamelingen D zijn.

Wat ik nu zoek is een handzame, aftelbaar oneindige deelverzameling
\(\mathfrak{H}\)
van
\(\mathfrak{D}\)
zodanig dat alle D uit
\(\mathfrak{D}\)
met behulp van doorsneden en verenigingen van een eindig of aftelbaar oneindig aantal verzamelingen H uit
\(\mathfrak{H}\)
gevormd kunnen worden.

Ik weet overigens niet of zo'n verzameling bestaat!

Gebruikersavatar
Berichten: 5.609

Re: Limieten van getaltheoretische functies

Dit zit ver, maar volgens mij is het zo dat gezien D een aftelbaar aantal elementen bevat, de verzameling van alle deelverzamelingen van D ook aftelbaar is.
\(\mathfrak{D}\)
is een deelverzameling van die laatste, en dus ook aftelbaar. Dus kan
\(\mathfrak{H} = \mathfrak{D}\)
bijvoorbeeld, toch? Dan is
\(\mathfrak{H}\)
aftelbaar, en zitten alle elementen van
\(\mathfrak{D}\)
in
\(\mathfrak{H}\)
.
What it all comes down to, is that I haven't got it all figured out just yet

And I've got one hand in my pocket and the other one is giving the peace sign

-Alanis Morisette-

Re: Limieten van getaltheoretische functies

Dit zit ver, maar volgens mij is het zo dat gezien D een aftelbaar aantal elementen bevat, de verzameling van alle deelverzamelingen van D ook aftelbaar is.
\(\mathfrak{D}\)
is een deelverzameling van die laatste, en dus ook aftelbaar. Dus kan
\(\mathfrak{H} = \mathfrak{D}\)
bijvoorbeeld, toch? Dan is
\(\mathfrak{H}\)
aftelbaar, en zitten alle elementen van
\(\mathfrak{D}\)
in
\(\mathfrak{H}\)
.


Dat kan ik niet helemaal volgen. Er zijn vele D mogelijk. En het aantal manieren om uit een aftelbaar oneindige verzameling D een deelverzameling te kiezen is overaftelbaar oneindig. Iedere keuze van een deelverzameling komt immers overeen met een binair getal.

Gebruikersavatar
Berichten: 5.609

Re: Limieten van getaltheoretische functies

En het aantal manieren om uit een aftelbaar oneindige verzameling D een deelverzameling te kiezen is overaftelbaar oneindig.
Inderdaad, je hebt gelijk. Mijn fout.
What it all comes down to, is that I haven't got it all figured out just yet

And I've got one hand in my pocket and the other one is giving the peace sign

-Alanis Morisette-

Re: Limieten van getaltheoretische functies

Laat ik nog wat meer toelichten wat mijn bedoeling is. We hebben de verzameling
\(\mathfrak{D}\)
. Daarin zitten dus precies die deelverzamelingen van
\(\nn\)
+, waarvoor de eerder aangegeven limiet bestaat en positief is.

Voor alle D uit
\(\mathfrak{D}\)
noemen we nu de uitkomst van de eerder aangegeven limiet de dichtheidsmaat d = d(D). Nu kunnen we ons afvragen hoe we voor A,B
\(\in\)
\(\mathfrak{D}\)
de dichtheidsmaten d(A
\(\cap\)
B) en d(A
\(\cup\)
B) kunnen uitrekenen, als we d(A) en d(B) weten. Ik denk dat daar iets analoogs als voor de kansformules uit moet komen...

Gebruikersavatar
Berichten: 5.609

Re: Limieten van getaltheoretische functies

Voor alle D uit
\(\mathfrak{D}\)
noemen we nu de uitkomst van de eerder aangegeven limiet de dichtheidsmaat d = d(D). Nu kunnen we ons afvragen hoe we voor A,B
\(\in\)
\(\mathfrak{D}\)
de dichtheidsmaten d(A
\(\cap\)
B) en d(A
\(\cup\)
B) kunnen uitrekenen, als we d(A) en d(B) weten. Ik denk dat daar iets analoogs als voor de kansformules uit moet komen...
Beter dan driehoeksongelijkheden zal je er niet uit krijgen, net zoals in kansrekenen.

Verder heb ik nog dat d(AUB)=d(A)+d(B)-d(A
\(\cap\)
B), wat eenvoudig aan te tonen is.
What it all comes down to, is that I haven't got it all figured out just yet

And I've got one hand in my pocket and the other one is giving the peace sign

-Alanis Morisette-

Re: Limieten van getaltheoretische functies

Beter dan driehoeksongelijkheden zal je er niet uit krijgen, net zoals in kansrekenen.


Niet aan gedacht... Ik ben nu zelf ook even de draad kwijt.

Re: Limieten van getaltheoretische functies

Even een stapje terug.

We hebben twee toevalsgeneratoren I en II, die positieve natuurlijke getallen uitwerpen. Verder bestaan er twee partities van
\(\nn\)
+, te weten één in de twee deelverzamelingen van positieve natuurlijke getallen A en B en één in de twee deelverzamelingen van positieve natuurlijke getallen C en D. Dus:
\(\nn\)
+ = A
\(\cup\)
B = C
\(\cup\)
D ,
\(\emptyset\)
= A
\(\cap\)
B = C
\(\cap\)
D .

Het enige dat we verder nog weten is dat de kans een getal uit A te trekken voor toevalsgenerator I gelijk aan a is, de kans een getal uit B te trekken voor toevalsgenerator I gelijk aan b is; de kans een getal uit C te trekken voor toevalsgenerator II gelijk aan c is; en de kans een getal uit D te trekken voor toevalsgenerator II gelijk aan d is. Voor de duidelijkheid: over de kansen een specifiek positief natuurlijk getal te trekken is niets gegeven!

Kunnen we met behulp van de toevalsgeneratoren I en II dan een nieuwe toevalsgenerator voor positieve natuurlijke getallen bouwen, zodanig dat de kansen op het trekken van een getal voor alle mogelijke doorsneden en verenigingen van A, B, C en D te berekenen zijn?

Gebruikersavatar
Berichten: 5.609

Re: Limieten van getaltheoretische functies

Kunnen we met behulp van de toevalsgeneratoren I en II dan een nieuwe toevalsgenerator voor positieve natuurlijke getallen bouwen, zodanig dat de kansen op het trekken van een getal voor alle mogelijke doorsneden en verenigingen van A, B, C en D te berekenen zijn?
Volgens mij zit het probleem hem in de onafhankelijkheid. Toevalsgeneratoren I en II kunnen volledig afhankelijk zijn (C=A bijvoorbeeld), of gedeeltelijk verband houden, of gewoon onafhankelijk. Hier dus elementen gemeenschappelijk hebben, of juist niet. Algemene formules (buiten de eerder vermeldde driehoeksongelijkheden en extra formule) die voor ze allemaal gelden kun je dus niet vinden, zonder extra definities in te voeren tenminste. Misschien dat je ook nog een soort stelling van Bayes kunt definiëren/bewijzen...
What it all comes down to, is that I haven't got it all figured out just yet

And I've got one hand in my pocket and the other one is giving the peace sign

-Alanis Morisette-

Re: Limieten van getaltheoretische functies

Volgens mij zit het probleem hem in de onafhankelijkheid. Toevalsgeneratoren I en II kunnen volledig afhankelijk zijn (C=A bijvoorbeeld), of gedeeltelijk verband houden, of gewoon onafhankelijk. Hier dus elementen gemeenschappelijk hebben, of juist niet.
Mijn bedoeling is te werken met onafhankelijke toevalsgeneratoren, dat wil zeggen dat de uitkomsten van I niets zeggen over die van II en omgekeerd. (Deze onafhankelijkheid staat los van de keuze van A, B, C en D. Dat zijn alleen de deelverzamelingen waarvoor de totale kansen bekend worden verondersteld.) De getrokken getallen van I en II zouden op de een of andere manier moeten worden gecombineerd tot één getrokken getal dat dan als de uitkomst van de aldus gevormde gecombineerde toevalsgenerator geldt. Zo nodig zou je daarvoor ook meerdere trekkingen van I en II kunnen gebruiken, de gecombineerde toevalsgenerator doet er dan gewoon wat langer over. Wel moet de manier waarop de nieuwe uitkomst wordt gevormd duidelijk en ondubbelzinnig gedefinieerd zijn.

Het gaat mij dus om het vinden van een dergelijke manier om uit twee toevalsgeneratoren één nieuwe te maken. Waarbij dus de eis is dat de kansen op de mogelijke doorsneden en verenigingen van A, B, C en D berekenbaar moeten zijn.

Re: Limieten van getaltheoretische functies

Het gaat mij dus om het vinden van een dergelijke manier om uit twee toevalsgeneratoren één nieuwe te maken. Waarbij dus de eis is dat de kansen op de mogelijke doorsneden en verenigingen van A, B, C en D berekenbaar moeten zijn.
Ter aanvulling: Ik ga uit van toevalsgeneratoren waarvoor slechts voor deelverzamelingen van
\(\nn\)
+ de kans bekend is dat het getrokken getal daarin valt. Door de uitkomsten van zulke toevalsgeneratoren tot één nieuwe uitkomst te combineren, maken we als het ware één nieuwe, gecombineerde toevalsgenerator. Voor die nieuwe toevalsgenerator die ook weer positieve natuurlijke getallen uitwerpt, heb ik graag dat voor veel méér deelverzamelingen van
\(\nn\)
+ te berekenen is wat de kans is dat de uitkomst daarin valt. Dit laatste uiteraard op basis van de kennis van de kansen a, b, c en d dat de getrokken getallen van de generatoren I en II in respectievelijk A, B, C of D vallen.

Gezocht is dus een op het bovenstaande toegesneden (niet triviale) manier om een nieuwe, gecombineerde toevalsgenerator voor positieve natuurlijke getallen uit I en II te bouwen.

Reageer