---

Hej.

Jeg er ved at designe et program, der bruger en hash-tabel. Hash-
tabellen bliver først genereret efter jeg har oversat programmet. Jeg
skal konstruere hash-tabellen ud fra et array, som er gemt inde i en
objekt-fil (eksekverbar fil). Hash-tabellen overskriver array'et. Det
er derfor ikke muligt at allokere mere plads til tabellen. Da jeg ikke
kan være sikker på at generere en minimal perfekt hash, så sørger jeg
for at der er plads nok at tage af. Hvert element i array'et optager
to elementers plads. Jeg har altså n elementer og har allokeret plads
til 2*n elementer. Det er rammerne for hash-tabellen. En typisk metode
til at fordele elementerne bedre er at sørge for antallet af "huller"
i tabellen er et primtal. Nu kommer mit spørgsmål: Er det altid muligt
at finde et primtal i intervallet [n; 2*n]? Problemet kan omformuleres
til om det gælder for alle x >= 1 at next_prime(x) <= 2*x. Jeg synes
jeg har læst et sted at primtal fordeler sig eksponentielt, så min
intuition siger mig at det må være rigtigt, men jeg kan ikke bevise
det. Er der nogen her i gruppen, der kan?

Problemet er rent teoretisk og for min egen nysgerrigheds skyld. Jeg
får ikke mere end et par tusinde elementer, og der kan jeg altid finde
et primtal.

Mvh.
Bjarke

---

"Bjarke Walling" <bjarke.walling@gmail.com> skrev i meddelelsen
news:33a02973-9325-42ad-9cc2-200669d4c247@z1g2000yqn.googlegroups.com...

Er det altid muligt
at finde et primtal i intervallet [n; 2*n]? Problemet kan omformuleres
til om det gælder for alle x >= 1 at next_prime(x) <= 2*x. Jeg synes
jeg har læst et sted at primtal fordeler sig eksponentielt, så min
intuition siger mig at det må være rigtigt, men jeg kan ikke bevise
det. Er der nogen her i gruppen, der kan?

-----

Ja, det kunne være sjovt at se.
Bertrand-Chebyshev theorem
http://en.wikipedia.org/wiki/Bertrand%27s_postulate

Mvh
Martin

---

Bjarke Walling <bjarke.walling@gmail.com> writes:

> Er det altid muligt at finde et primtal i intervallet [n; 2*n]?

Ja. Det kaldes Bertrands formodning og blev bevist af Chebyshev i
1850. Se http://en.wikipedia.org/wiki/Bertrand's_postulate for flere
detaljer.

   Torben

---

On 11 Feb., 16:26, "Martin Larsen" <mlar...@post7.tele.dk> wrote:
> Ja, det kunne være sjovt at se.
> Bertrand-Chebyshev theoremhttp://en.wikipedia.org/wiki/Bertrand%27s_postulate

Tak for jeres svar! Så min intuition havde ret, men jeg er da godt nok
kommet på arbejde, hvis jeg skal forstå detaljerne i det her bevis:

http://en.wikipedia.org/wiki/Proof_of_Bertrand%27s_postulate

Dog kan jeg sove trygt og vide at min algoritme til at generere hash-
tabellen virker i alle (også urealistiske) tilfælde.

Mvh.
Bjarke