Limieten van getaltheoretische functies

[Bartjes]

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?

[PeterPan]

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

[Bartjes]

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.

[halb]

... 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

[Bartjes]

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!

[317070]

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}\)

.

[Bartjes]

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.

[317070]

En het aantal manieren om uit een aftelbaar oneindige verzameling D een deelverzameling te kiezen is overaftelbaar oneindig.

Inderdaad, je hebt gelijk. Mijn fout.

[Bartjes]

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...

[317070]

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.

[Bartjes]

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.

[Bartjes]

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?

[317070]

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...

[Bartjes]

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.

[Bartjes]

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.