---

Hej.

Da jeg skrev en besked news:b23ka1$d19$1@news.cybercity.dk kom jeg til at
tænke på noget.
I Hilberts hotel som mange nok har hørt om er det muligt at indskrive et
uendeligt antal personer, selvom hotellet i forvejen har udlejet alle sine
uendeligt mange værelser. Kort sagt:

uendeligt + uendeligt = uendeligt

Så var det at jeg kom til at tænke på pi (eller et hvilket som helst andet
irrationelt tal). Vil der i decimalrækken på et tidspunkt kunne forefindes
en uendeligt række ens cifre (f.eks. 0) hvor decimalrækken med "tilfældige"
cifre efterfølgende fortsætter.
Her vist lidt mere tydeligt måske:

Pi = 3,1415...2737182000000000000000000000...uendeligt antal
nuller...00012838917382...og så fortsætter det ellers derudaf

Jeg ved ikke hvorvidt det rent faktisk er et matematisk spørgsmål, men det
er i hvert fald ret interessant. Det er lidt svært at forestille sig
hvorledes decimalerne i pi "ender" i en uendeligt række nuller og alligevel
hinsides det uendelige fortsætter. Egentlig er tanken ligeså svær at forstå
som virkeligt at forstå at uendeligt + uendeligt = uendeligt. Egentlig tror
jeg ikke rigtigt at det kan lade sig gøre at der midt i pi forefindes en
uendelig række nuller. Nogen der kan opskrive et bevis for at det ikke er
sandt?

Jeg har selv en idé til et argument imod det, men jeg ved nu ikke om det
holder.
I Hilberts hotel er det nemlig muligt at indskrive et uendeligt antal
personer, fordi alle boende i hotellet flytter til et værelse med nummeret
der er det dobbelte af deres eget værelsesnummer. Det uendeligt antal nye
personer flytter så ind på alle de ledige værelser - allesammen med ulige
numre. Det er altså tilsyneladende ikke muligt i hotellet at indskrive
uendeligt mange personer og give dem værelser med fortløbende værelsesnumre
midt i det hele.
Dette vil i decimalrækken i pi svare til at man indsatte en uendeligt række
nuller ved at indsætte et nul efter hvert decimal i pi, f.eks.:
pi = 3,104010509020503090...30601060107020104090...
Og da hvert andet decimal i pi ikke er et konstant tal er dette ikke
tilfældet.
Og ligesom at man ikke kan indskrive et uendeligt antal personer på hotellet
og give dem fortløbende værelsesnumre er der heller ikke midt i pi en
uendelig række nuller.

Holder det? - og hvorfor kan man i øvrigt ikke indskrive et uendeligt antal
personer midt i det hele i Hilberts hotel ... måske er det aldrig bleven
modbevist, men er heller ikke bevist før der er nogen der rent faktisk
finder en metode til at udføre det?

Mvh. Bjarke

---

"Bjarke Walling Petersen" <bwp@bwp.dk> writes:

> Jeg ved ikke hvorvidt det rent faktisk er et matematisk spørgsmål, men det
> er i hvert fald ret interessant. Det er lidt svært at forestille sig
> hvorledes decimalerne i pi "ender" i en uendeligt række nuller og alligevel
> hinsides det uendelige fortsætter. Egentlig er tanken ligeså svær at forstå
> som virkeligt at forstå at uendeligt + uendeligt = uendeligt. Egentlig tror
> jeg ikke rigtigt at det kan lade sig gøre at der midt i pi forefindes en
> uendelig række nuller. Nogen der kan opskrive et bevis for at det ikke er
> sandt?

Hvis din uendelige række af nuller starter ved den N'te decimal, må
der på et eller andet tidspunkt komme en decimal der ikke er 0 (ellers
ville pi være rational). Denne decimal dukker så op på lad os sige den
M'te plads. Men så er rækken af nuller jo kun M-N lang, hvilket ikke
er uendelig. Samme argument besvarer dine spørgsmål om Hilberts Hotel.

I øvrigt er fordelingen af decimalerne i pi et ret omdiskuteret
emne. Man kan jo fx kigge på de første 1`000`000`000 decimaler, og så
kan man tælle hvor mange 1'ere, 2'ere,... 9'ere og nuller man
finder. Det viser sig at de er nogenlunde jævnt fordelt (altså ca. en
tiendedel til hver). Men man kan også interessere sig for, hvor mange
forekomster der er af cifrene 00, 01, 02, ... 57,... 99 ved siden af
hinanden, og det viser sig også at være nogenlunde 1/100 til
hver. Inspireret af sådanne empiriske undersøgelser af forskellige
irrationelle tal såsom sqrt(2), pi, e og nogle andre, har man
defineret hvad det vil sige at et tal er *normalt*:

Et tal siges at være normalt x hvis der i den uendelige
decimaltalsrepræsentation af x forekommer "lige mange" af hver
decimal, og "lige mange" af hver kombination af decimaler af en given
længde.

Her skal "lige mange" selvfølgelig tolkes med en passende
grænseovergang som kvotienten mellem antallet af forekomster af den
givne decimalfølge og det totale antal decimalfølger med samme længde.

Man ved ikke om pi er normalt, men mange matematikere tror det. Hvis
det viser sig at være rigtigt, vil det altså specielt betyde, at der
findes følger af nuller blandt pi's decimaler som er vilkårligt lange
(sekvensen 000...00 hvor der er N nuller skal jo optræde lige så
hyppigt som 123235...239 , som også skulle forestille at være en
sekvens på N decimaler), men det er ikke det samme som at der optræder
en følge af 0'er som er _uendelig_ lang.

Der er faktisk kun meget få tal som man med sikkerhed ved er normale,
og de fleste af disse er ret "kunstige" i den forstand at man kun har
skrevet dem op med det ene formål at vise, at der faktisk findes
reelle tal som er normale. Et eksempel på et sådant tal er
0,123456789101112131415..., altså hvor man skriver alle de naturlige
tal op i forlængelse af hinanden.

Jeg håber ikke det gjorde dig alt for forvirret. Se mere om normale
tal på http://mathworld.wolfram.com/NormalNumber.html (generelt er
www.mathworld.com en udmærket side).

Med venlig hilsen

Rasmus Villemoes

--

---

Rasmus Villemoes skrev:
[klip]
> Jeg håber ikke det gjorde dig alt for forvirret. Se mere om normale
> tal på http://mathworld.wolfram.com/NormalNumber.html (generelt er
> www.mathworld.com en udmærket side).

Nej, jeg blev langt fra forvirret. Tak for dit grundige svar!
Argumentet med at M-N ikke kan være uendeligt er jo egentlig ret åbenlyst.

Mvh. Bjarke

---

Jeg skrev:
> Argumentet med at M-N ikke kan være uendeligt er jo egentlig ret åbenlyst.

Jeg er dog bleven lidt i tvivl alligevel. F.eks:

L er antal decimaler i tallet. Følgende er givet:

N = 1/4*L
M = 3/4*L

Der gælder:
M - N = 3/4*L - 1/4*L = 1/2*L =>
For L -> Uendelig vil M - N = 1/2*L -> Uendelig

Hvordan kan man afvise ovenstående?

Hvis man nu kan opskrive sandsynligheden for at kunne udtage et tal på en
given længde i decimalerne på et normalt tal vil denne dog sandsynligvis gå
imod nul når længden af det udtagede tal går imod uendelig (har jeg ret?),
men nu er der dog ingen der har kunnet bevise at pi er normal. Selvfølgelig
ser det ud til at være det.

Mvh. Bjarke

---

"Bjarke Walling Petersen" <bwp@bwp.dk> writes:

> Jeg skrev:
> > Argumentet med at M-N ikke kan være uendeligt er jo egentlig ret åbenlyst.
>
> Jeg er dog bleven lidt i tvivl alligevel. F.eks:
>
> L er antal decimaler i tallet. Følgende er givet:
>
> N = 1/4*L
> M = 3/4*L
>
> Der gælder:
> M - N = 3/4*L - 1/4*L = 1/2*L =>
> For L -> Uendelig vil M - N = 1/2*L -> Uendelig

Ja, du kan sagtens konstruere en følge af reelle tal, som "midt" i sig
har en følge af nuller. Jeg tror du har tænkt på noget i den her
retning:

x1 = 0,1001
x2 = 0,11000011
x3 = 0,111000000111
x4 = 0,1111000000001111
....
Hver af disse har en (længere og længere) decimalfølge af nuller. Vi
kan jo så prøve at se hvad der sker, når vi fortsætter med at
konstruere tal på denne måde: Min påstand er, at følgen konvergerer
mod 1/9 = 0,11111111... , hvilket kan indses ved at udregne 1/9 - xn;
man får

1/9 - xn = 0,[n nuller][2n et-taller][n nuller][resten et-taller]

Da denne differens går mod 0 når n går mod uendelig (vælg et n så
stort at 2*10^(-n) er mindre end et givent epsilon), vil følgen
konvergere mod 1/9, som jo altså har decimalrepræsentaion
0,111111... Din ellers snedige ide til at konstruere et reelt tal med
en uendelig følge af 0'er 'inde i sig' virker altså ikke.

Nu vi snakker om et reelt tals decimaltalsekspansion: Ethvert reelt
tal kan _ikke_ på entydig måde skrives som et decimaltal (i
titalssystemet; heraf præfix'et deci-). Fx er 1 = 1,0000... =
0,9999... Hvorfor nu det? Der findes mange måder at argumentere for
dette på; en måde er at opfatte 0,9999... som værdien af rækken

sum(n=1)(uendelig) 9*10^(-n)

og da dette er en geometrisk række er den konvergent med sum
(9*10^(-1))/(1-1/10) = 1.

Hvis nu man forsøger at udregne 1-1 får man normalt 0, hvilket vist
ikke kan diskuteres. Men 1,000...-0,9999... kunne man umiddelbart
ledes til at tro skulle skrives som 0,000[uendelig mange nuller]["til
sidst" et 1-tal]. Men dette eksempel viser blot, at hvis en
decimalekspansion fra et vist trin består af uendelig mange ens cifre,
så _er_ der ikke nogen (andre) cifre "hinsides" det uendelige.

> Hvordan kan man afvise ovenstående?
>
> Hvis man nu kan opskrive sandsynligheden for at kunne udtage et tal på en
> given længde i decimalerne på et normalt tal vil denne dog sandsynligvis gå
> imod nul når længden af det udtagede tal går imod uendelig (har jeg ret?),

Næh, tværtimod. Det ligger jo netop i definitionen af et normalt tal,
at man for _enhver_ given følge af decimaler skal kunne finde et sted
i det normale tal hvor denne følge optræder. Dvs. sandsynligheden for
at man kan finde et sted hvor "2" optræder er 1, sandsynligheden for
at man kan finde et sted hvor "53" optræder er 1, ..., sandsynligheden
for at man kan finde et sted hvor "233464628346" optræder er 1 og så
fremdeles; således vil sandsynligheden for at man kan finde en given
følge af decimaler gå mod 1 når man lader følgens længde gå mod uendelig.

Med venlig hilsen

Rasmus Villemoes

--

---

Dit svar kastede lys over mange ting. Tak for det.

Har selv hørt følgende bevis for at 1,000... = 0,999...:

Man ganger 0,999... med 9 og dividerer efterfølgende med 9. En måde at gange
med 9 på er at gange tallet med 10 og trække selve tallet fra, dvs.:

9 * 0,999... = 10 * 0,999... - 0,999... = 9,999... - 0,999... = 9,000...

Divideres 9,000... med 9 fås 1,000...

Mvh. Bjarke

---

"Bjarke Walling Petersen" <bwp@bwp.dk> writes:

> Dit svar kastede lys over mange ting. Tak for det.
>
> Har selv hørt følgende bevis for at 1,000... = 0,999...:
>
> Man ganger 0,999... med 9 og dividerer efterfølgende med 9. En måde at gange
> med 9 på er at gange tallet med 10 og trække selve tallet fra, dvs.:
>
> 9 * 0,999... = 10 * 0,999... - 0,999... = 9,999... - 0,999... = 9,000...
>
> Divideres 9,000... med 9 fås 1,000...

Ja, det er faktisk et udmærket lille bevis, som i en vis forstand
faktisk er det samme som det jeg gav (men dit er nok mere intuitivt da
det stort set intet fordsætter af læseren). Jeg vil da ikke undlade at
vise dig hvordan du nemt generaliserer beviset til formlen for hvordan
man udregner summen af en endelig geometrisk række. Vi vil altså
finde, hvordan man kan udregne

a + a*r + a*r^2 + ... + a*r^n

Da det er en endelig sum, findes summen (der er ingen problemer med
konvergens), og vi kan kalde den S. Ganger vi nu S med r får vi

rS = a*r + a*r^2 + ... + a*r^(n+1)

Men så er S - rS = S(1-r) = a - a*r^(n+1), hvorved S kan udregnes som

S = a*(1-r^(n+1))/(1-r) = a*(r^(n+1)-1)/(r-1) .

Det er selvsamme formel som i grænsetilfældet n -> uendelig bruges til
at finde summen af den geometriske (uendelige) række a + a*r + a*r^2 +
....; man får at hvis |r| < 1 vil

S = a/(1-r)

Med venlig hilsen

Rasmus V.

--

---

Rasmus Villemoes skrev:
[klip]
> a + a*r + a*r^2 + ... + a*r^n
>
> Da det er en endelig sum, findes summen (der er ingen problemer med
> konvergens), og vi kan kalde den S. Ganger vi nu S med r får vi
>
> rS = a*r + a*r^2 + ... + a*r^(n+1)
>
> Men så er S - rS = S(1-r) = a - a*r^(n+1), hvorved S kan udregnes som
>
> S = a*(1-r^(n+1))/(1-r) = a*(r^(n+1)-1)/(r-1) .
>
> Det er selvsamme formel som i grænsetilfældet n -> uendelig bruges til
> at finde summen af den geometriske (uendelige) række a + a*r + a*r^2 +
> ...; man får at hvis |r| < 1 vil
>
> S = a/(1-r)

Den udregning af sumrækken er da faktisk ret genialt lavet. Egentlig bygger
det jo på samme idé som det bevis jeg skrev for 0,999... = 1. Men
sandsynligvis var mit bevis blot en udledning af ovenstående.

Mvh. Bjarke

---

"Bjarke Walling Petersen" <bwp@bwp.dk> writes:


> Den udregning af sumrækken er da faktisk ret genialt lavet. Egentlig bygger
> det jo på samme idé som det bevis jeg skrev for 0,999... = 1. Men
> sandsynligvis var mit bevis blot en udledning af ovenstående.

Netop. Derfor skrev jeg også at dit bevis i en vis forstand var det
samme som mit; jeg brugte den "generelle" teori for geometriske
rækker, mens du brugte den samme idé (at gange rækken igennem med en
faktor og trække de to udtryk fra hinanden, så kun et eller to led
står tilbage), men så at sige satte tal ind i formlen med det samme.

Mvh

Rasmus

--

---

> I øvrigt er fordelingen af decimalerne i pi et ret omdiskuteret
> emne. Man kan jo fx kigge på de første 1`000`000`000 decimaler, og så
> kan man tælle hvor mange 1'ere, 2'ere,... 9'ere og nuller man
> finder. Det viser sig at de er nogenlunde jævnt fordelt (altså ca. en
> tiendedel til hver). Men man kan også interessere sig for, hvor mange
> forekomster der er af cifrene 00, 01, 02, ... 57,... 99 ved siden af
> hinanden, og det viser sig også at være nogenlunde 1/100 til
> hver. Inspireret af sådanne empiriske undersøgelser af forskellige
> irrationelle tal såsom sqrt(2), pi, e og nogle andre, har man
> defineret hvad det vil sige at et tal er *normalt*:
>
> Et tal siges at være normalt x hvis der i den uendelige
> decimaltalsrepræsentation af x forekommer "lige mange" af hver
> decimal, og "lige mange" af hver kombination af decimaler af en given
> længde.

Jeg stiller lige et par spørgsmål, som muligvis er dumme: Vil denne
fordeling ikke være afhængig af, hvilket talsystem, man bruger? Og kan det
ske, at et tal som forekommer normalt (for eksempel pi) i ét talsystem vil
have en række af gentagne decimaler i et andet talsystem?


ML-78

---

"ML-78" <dsl79866@NOSPAMvip.cybercity.dk> writes:

> > I øvrigt er fordelingen af decimalerne i pi et ret omdiskuteret
> > emne. Man kan jo fx kigge på de første 1`000`000`000 decimaler, og så
> > kan man tælle hvor mange 1'ere, 2'ere,... 9'ere og nuller man
> > finder. Det viser sig at de er nogenlunde jævnt fordelt (altså ca. en
> > tiendedel til hver). Men man kan også interessere sig for, hvor mange
> > forekomster der er af cifrene 00, 01, 02, ... 57,... 99 ved siden af
> > hinanden, og det viser sig også at være nogenlunde 1/100 til
> > hver. Inspireret af sådanne empiriske undersøgelser af forskellige
> > irrationelle tal såsom sqrt(2), pi, e og nogle andre, har man
> > defineret hvad det vil sige at et tal er *normalt*:
> >
> > Et tal siges at være normalt x hvis der i den uendelige
> > decimaltalsrepræsentation af x forekommer "lige mange" af hver
> > decimal, og "lige mange" af hver kombination af decimaler af en given
> > længde.
>
> Jeg stiller lige et par spørgsmål, som muligvis er dumme: Vil denne
> fordeling ikke være afhængig af, hvilket talsystem, man bruger? Og kan det
> ske, at et tal som forekommer normalt (for eksempel pi) i ét talsystem vil
> have en række af gentagne decimaler i et andet talsystem?

Det er absolut ikke dumme spørgsmål. Og svaret er ja, der kan godt
findes tal som er normale i en repræsentation, men som ikke
nødvendigvis er det i en anden. Dog gælder, at hvis et tal er normalt
når det repræsenteres i talsystem med basen b^m (altså en eller anden
potens af et tal b), så er tallet normalt i alle baser med grundtal af
formen b^k. Det vil fx sige, at pi er normalt i base 10 hvis og kun
hvis det er normalt i baserne 100, 1000 osv. Tilsvarende er et tal
normalt i det binære talsystem hvis og kun hvis det er normalt i alle
baserne 4, 8, 16, ... Dette står at læse på
http://mathworld.wolfram.com/NormalNumber.html . Men hvis du med
"række af gentagne decimaler" mener at tallet fra et vist trin har
periodisk decimaltalsrepræsentation, så er svaret nej. Det skyldes, at
hvis decimalbrøken for et tal fra et vis trin bliver periodisk i /en
eller anden/ base, vil tallet være rationelt, og dermed have periodisk
decimaltalsfremstilling i alle baser, så det altså ikke er normalt i
nogen base.

Med venlig hilsen

Rasmus Villemoes

--

---

> > Jeg stiller lige et par spørgsmål, som muligvis er dumme: Vil denne
> > fordeling ikke være afhængig af, hvilket talsystem, man bruger? Og kan
det
> > ske, at et tal som forekommer normalt (for eksempel pi) i ét talsystem
vil
> > have en række af gentagne decimaler i et andet talsystem?
>
> Det er absolut ikke dumme spørgsmål. Og svaret er ja, der kan godt
> findes tal som er normale i en repræsentation, men som ikke
> nødvendigvis er det i en anden. Dog gælder, at hvis et tal er normalt
> når det repræsenteres i talsystem med basen b^m (altså en eller anden
> potens af et tal b), så er tallet normalt i alle baser med grundtal af
> formen b^k. Det vil fx sige, at pi er normalt i base 10 hvis og kun
> hvis det er normalt i baserne 100, 1000 osv. Tilsvarende er et tal
> normalt i det binære talsystem hvis og kun hvis det er normalt i alle
> baserne 4, 8, 16, ... Dette står at læse på
> http://mathworld.wolfram.com/NormalNumber.html .

Tak for det hurtige og grundige svar. På Mathworlds website kan jeg dog kun
finde beskrivelser af, at pi forekommer normalt i base 10 (og derfor 10^k).
Man kan selvfølgelig ikke undersøge alle baser, men er der lavet
undersøgelser af, om pi ligeledes er normalt i andre baser?


ML-78

---

On Sat, 8 Feb 2003 20:20:41 +0100, "Bjarke Walling Petersen"
<bwp@bwp.dk> wrote:

>I Hilberts hotel er det nemlig muligt at indskrive et uendeligt antal
>personer, fordi alle boende i hotellet flytter til et værelse med nummeret
>der er det dobbelte af deres eget værelsesnummer. Det uendeligt antal nye
>personer flytter så ind på alle de ledige værelser - allesammen med ulige
>numre. Det er altså tilsyneladende ikke muligt i hotellet at indskrive
>uendeligt mange personer og give dem værelser med fortløbende værelsesnumre
>midt i det hele.

Flytter de ikke bare til værelsesnummer+1, så er værelse nr.1 ledigt.
Der kan så flytte en ny beboer ind, og så videre...


--

/Dan MOrtensen

---

Dan MOrtensen <dd@bagggesen.tld> writes:

> On Sat, 8 Feb 2003 20:20:41 +0100, "Bjarke Walling Petersen"
> <bwp@bwp.dk> wrote:
>
> >I Hilberts hotel er det nemlig muligt at indskrive et uendeligt antal
> >personer, fordi alle boende i hotellet flytter til et værelse med nummeret
> >der er det dobbelte af deres eget værelsesnummer. Det uendeligt antal nye
> >personer flytter så ind på alle de ledige værelser - allesammen med ulige
> >numre. Det er altså tilsyneladende ikke muligt i hotellet at indskrive
> >uendeligt mange personer og give dem værelser med fortløbende værelsesnumre
> >midt i det hele.
>
> Flytter de ikke bare til værelsesnummer+1, så er værelse nr.1 ledigt.
> Der kan så flytte en ny beboer ind, og så videre...

Så skal du ulejlige beboerne uendeligt mange gange hvis du vil have
plads til uendeligt mange flere gæster. Ved at bede alle gæster rykke
til værelset med det dobbelte nummer skaffer du på én gang (tælleligt)
uendeligt mange ledige værelser. Problemet med "bare" at rykke alle
beboere til detnæste værelse er at man så at sige aldrig bliver
færdig; efter n omrykninger har man kun fået plads til n nye beboere;
man har stadig uendelig mange gæster der venter på at blive anvist et
værelse.

Det er straks mere interessant at betragte det tilfælde, hvor Hilbert
modtager (tælleligt) uendelig mange rejseselskaber som hver tæller
uendelig mange rejsende. At det rent faktisk også i dette tilfælde
viser sig at være muligt at skaffe samtlige rejsedeltagere et værelse
(omend de omrokeringer der skal til kræver sin hotelvært at holde styr
på) er et vigtigt resultat. Argumentet er sådan set ikke så svært: Vi
kan lade som om, at gæsterne der i forvejen er på hotellet er
rejseselskab nummer 0; og vi skal således bare fylde uendeligt mange
rejseselskaber med uendeligt mange rejsende hver ind på et tomt
hotel. Hvis vi nu laver en tabel som denne

x01 x02 x03 ...
x11 x12 x13 ...
x21 ....
....

hvor første index angiver rejseselskabets nummer og andet index
angiver turistens nummer, kan vi fordele værelserne som følger

x01 - x02 - x11 - x03 - x12 - x21 - x04 - x13 - x22 - x31 - x04 -...

idéen er at tage en diagonal af gangen. Bemærk, at på den først
gennemløbne diagonal er summen af de to indices 1, og der er 1 gæst på
denne diagonal, på den anden diagonal er summen af indices 2, og der
er 2 gæster, og så fremdeles. Det er forholdsvis let at finde det
værelsesnummer, som gæst nummer n i rejseselskab nummer m får. Lad
nemlig d = m + n (altså nummeret på den diagonal som xmn står i). Før
vi er begyndt på at fordele værelser til den d'te diagonal, har vi
fordelt til de d-1 første, og hertil er brugt værelsesnumrene fra 1
til (d-1)*d/2 (da summen af de første k naturlige tal er
k*(k+1)/2). Derfor er det ret let at se, at gæsten xmn får
værelsesnummeret

(d-1)d/2 + 1 + m

Hvis ikke det efterhånden var blevet så sent, tror jeg også jeg kunne
finde en formel for index m,n på den gæst der får værelsesnummer k.

Med venlig hilsen

Rasmus Villemoes

--

---

Rasmus Villemoes <burner+usenet@imf.au.dk> writes:

> hvor første index angiver rejseselskabets nummer og andet index
> angiver turistens nummer, kan vi fordele værelserne som følger
>
> x01 - x02 - x11 - x03 - x12 - x21 - x04 - x13 - x22 - x31 - x04 -...

hvor det sidste selvfølgelig skulle have været x05 (efterfulgt af x14
- x23 og så videre, men nu vil jeg stoppe før jeg laver flere
bommerter).

Mvh Rasmus V.

--

---

On 08 Feb 2003 23:42:11 +0100, Rasmus Villemoes
<burner+usenet@imf.au.dk> wrote:


>Det er straks mere interessant at betragte det tilfælde, hvor Hilbert
>modtager (tælleligt) uendelig mange rejseselskaber

Hvad mener du med "tælleligt uendelig"? Man bliver jo aldrig færdig
med at tælle en uendelig størrelse.

---

R.A. wrote:
> Hvad mener du med "tælleligt uendelig"? Man bliver jo aldrig færdig
> med at tælle en uendelig størrelse.

Det giver god nok mening. Se
http://mathworld.wolfram.com/CountablyInfinite.html
samt
http://mathworld.wolfram.com/UncountablyInfinite.html
--
Jonas

---

R.A. <sinor1@lycos.com> writes:

> On 08 Feb 2003 23:42:11 +0100, Rasmus Villemoes
> <burner+usenet@imf.au.dk> wrote:
>
>
> >Det er straks mere interessant at betragte det tilfælde, hvor Hilbert
> >modtager (tælleligt) uendelig mange rejseselskaber
>
> Hvad mener du med "tælleligt uendelig"? Man bliver jo aldrig færdig
> med at tælle en uendelig størrelse.

I matematik skelner man mellem (mindst) to forskellige grader af
uendelig. En mængde som fx de naturlige tal {1, 2, 3, ...} er
uendelig, men det er mængden af alle reelle tal også. En uendelig
mængde siges i at være tællelig hvis elementerne i den kan sættes i
en-til-en-korrespondance med de naturlige tal; man skal altså kunne
nummerere elementerne i mængden. Det viser sig, at de naturlige tal
(selvfølgelig) er tællelige, og ligeså er de rationale. Men de reelle
tal er _ikke_ tællelige; der findes så at sige alt for mange reelle
tal til at de hver kan tildeles et nummer. En sådan mængde kaldes
overtællelig. Det mest udbredte argument for at de reelle tal er
overtællelige er det såkaldte Cantors diagonalargument, der nogenlunde
går som følger: Antag at vi har nummereret tallene mellem 0 og 1
(skrevet i det binære talsystem) i en liste

1 -> 0,a11 a12 a13 ...
2 -> 0,a21 a22 a23 ...
....

hvor a(mn) er den n'te bi-mal (eller hvad cifrene i det binære
talsystem nu kaldes) i det m'te tal i listen. Nu kan vi så opskrive
tallet

a = 0,(1-a11)(1-a22)(1-a33)...

Den første bi-mal vælges altså til at være den modsatte af den første
bi-mal i det første tal i listen, og så fremdeles. Så er a et reelt
tal mellem 0 og 1, og burde derfor have et nummer i listen. Men da a
ikke stemmer overens med nogen af tallene i listen (den n'te decimal i
a er forskellig fra den n'te decimal i det n'te tal i listen) har vi
fundet et tal mellem 0 og 1 som ikke er med i listen; altså er vores
nummerering af tallene mellem 0 og 1 ikke komplet, og vi må konkludere
at en sådan nummerering ikke findes. Da ikke engang tallene mellem 0
og 1 kan nummereres, kan de reelle tal så absolut heller ikke.

Den måde jeg angav til hvordan man kunne fordele værelser til
tælleligt uendelig mange gæster i tælleligt uendelig mange
rejseselskaber i et andet indlæg i denne tråd, er den samme måde som
man viser de rationale tals tællelighed på.

Med venlig hilsen

Rasmus Villemoes

PS: Jeg vil igen lige reklamere lidt for www.mathworld.com ; der står
næsten med sikkerhed også en masse om dette emne.

--

---

Rasmus Villemoes <burner+usenet@imf.au.dk> writes:

> I matematik skelner man mellem (mindst) to forskellige grader af
> uendelig.

Man skelner mellem så mange grader af uendelig at det ikke kan beskrives
ved nogen af dem. (Teknisk: Kardinaltallene udgør ikke en mængde.)

..Henrik

--
"Og jeg troede UENDELIG var et stort tal!"
-sagt efter en matematikforelæsning om transfinitte kardinaltal

---

Rasmus Villemoes skrev:
[klip]
> (d-1)d/2 + 1 + m
>
> Hvis ikke det efterhånden var blevet så sent, tror jeg også jeg kunne
> finde en formel for index m,n på den gæst der får værelsesnummer k.

Kan du det nu så?

Jeg kom kun frem til følgende som man vist ikke rigtigt kan bruge til noget:

m + n = 1/2 + sqrt(2*(i - m) - (1+3/4))

.... hvor i er værelsesnummeret.
Jeg er ikke engang sikker på hvordan jeg skal udlede det ... man skal vel
finde frem til et udtryk hvor der kun indgår m og i og ét hvor der kun
indgår n og i?

Mvh. Bjarke

---

"Bjarke Walling Petersen" <bwp@bwp.dk> writes:

> Rasmus Villemoes skrev:
> [klip]
> > (d-1)d/2 + 1 + m
> >
> > Hvis ikke det efterhånden var blevet så sent, tror jeg også jeg kunne
> > finde en formel for index m,n på den gæst der får værelsesnummer k.
>
> Kan du det nu så?
>
> Jeg kom kun frem til følgende som man vist ikke rigtigt kan bruge til noget:
>
> m + n = 1/2 + sqrt(2*(i - m) - (1+3/4))
>
> ... hvor i er værelsesnummeret.
> Jeg er ikke engang sikker på hvordan jeg skal udlede det ... man skal vel
> finde frem til et udtryk hvor der kun indgår m og i og ét hvor der kun
> indgår n og i?

Jeg ved ikke hvordan du er nået frem til ovenstående, men jeg tror nok
jeg har fundet en løsning, omend den ikke er så pæn. Først kræver det,
at vi lige indfører funktionen ceiling (forkortet ceil). "Loftet" af
et reelt tal er det mindste hele tal der er større end eller lig det
reelle tal; altså

ceil(1,5) = 2
ceil(0,7) = 1
ceil(3) = 3
osv.

Ideen er nu, at vi først vil finde den diagonal vi befinder os
i. Betragt ligningen

(D+1)*D/2 = S

Ved ukritisk anvendelse af formlen for løsning af andengradsligninger,
(og med det samme smide den negative løsning væk) finder man at

D = (-1 + sqrt(1+8S))/2

Hvis S er et af de såkaldte trekantstal (1, 3, 6, 10,...) vil D blive
et heltal; svarende til at når vi har fordelt henholdsvis 1, 3,
6,... værelser er vi færdige med at tildele den første, anden,
tredje,... diagonal værelser. Under alle omstændigheder definerer vi
nu

d := ceil( (-1 + sqrt(1+8k))/2 )

d ses så let at være den diagonal som vi befiner os i når vi tildeler
værelse nummer k; dvs. d er summen af m og n, som er de tal vi leder
efter (givet k).

Nu er det så bare at konstatere, at vi før vi begyndte at fordele
værelser til den d'te diagonal har tildelt d(d-1)/2 = V værelser, og
vi kan derfor skrive m og n som

m = k - (V+1)
n = d - m

Jeg har ikke kunnet finde en pænere måde at finde række- og
søjlenummer på på den gæst som får værelse nummer k, og det
ovenstående er da heller ikke et strengt bevis. Er der nogen der har
bedre ideer? Det ville være rart hvis man kunne udtrykke m og n ved k
i en mere lukket form(el) end ovenstående.

Mvh

Rasmus Villemoes

--

---

Apropos diskussionen om normaliteten af pi faldt jeg lige over denne
side om en måde at teste om tallet e = 2,71828... kunne være normalt.
Han kigger på hvor mange blokke a 10 decimaler der indeholder lutter
forskellige cifre:

http://www.mathpages.com/home/kmath519.htm

Naturligvis *beviser* den slags intet. Den første million cifre kunne
jo være ene nuller samtidig med at tallet er normalt.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Inspireret af posten omkring uendeligt antal ens decimaler i pi, kom jeg
til at tænke på primtalsørkener.

Der er et forholdsvis nemt og elegant bevis for at for at der findes et
uendeligt antal primtal.

Antag at mængden af primtal (MP) er endelig og skriv mængden op.
MP={P1,P2,...,PN}

Tallet PM= (P1*P2*...*PN)+1

er større end samtlige tal i MP

Tallet er derfor trivielt forskelligt fra alle tal i MP, og PM>1.

PM er derfor enten sammensat eller et primtal.

Hvis PM er et primtal, så findes der et primtal der ikke er med i MP,
hvilket er i modstrid med antagelsen.

Hvis PM er sammensat findes en primtalsopløsning af PM. Men da PM modulo
P er lig 1 for alle P i MP, kan primtalsopløsningen ikke indeholde
primtal fra MP. Der findes derved primtal i primtalsopløsningen af PM som
ikke er med i MP - i modstrid med vores antagelse.

Ud fra en endelig mængde primtal kan vi altså altid finde mindst et
primtal til. Der er derfor et uendeligt antal primtal.


Det betyder at vi kan finde et vilkårligt stort primtal.

Nu kommer så min pointe med primtalsørkener. En primtalsørken er en
fortløbende talrække, der ikke indeholder primtal. De første ørkener ser
således ud.

4
6
8 9 10
12
14 15 16
18
20 21 22
24 25 26 27 28
30
32 33 34 35 36
osv.

Man kan finde en ørken af vilkårlig længde.
En ørken af længde N kan findes ved at tage tallet (N+1)!, og så udvælge
de N tal
(N+1)!+2,(N+1)!+3,...,(N+1)!+N,(N+1)!+N+1
Der alle er sammensatte tal der hvert som minimum har 2,3,4,...,N+1 som
divisor henholdsvis.

Nu nærmer vi os den tidligere post omkring et uendeligt antal ens cifre i
"midten" af pi.

Det er klart at for N gående mod uendelig vil talrækken 1...N indeholde
vilkårligt store primtalsørkener, men det første resultat viser jo
entydigt at der aldrig er et sidste primtal.

Hm ja

Det var bare en tanke

Søren

---

Søren Kongstad skrev:
> Det er klart at for N gående mod uendelig vil talrækken 1...N indeholde
> vilkårligt store primtalsørkener, men det første resultat viser jo
> entydigt at der aldrig er et sidste primtal.

Måske kan jeg ikke helt følge det, men betyder det ikke blot at man både kan
finde vilkårligt store primtal og vilkårligt store primtalsørkener. Eller
noget i den stil.

I hvert fald lyder det spændende med primtalsørkener - jeg har ikke hørt om
dem før.
Men jeg har hørt om primtalstvillinger - dvs. to på hinanden følgende
primtal, hvor afstanden imellem dem er 2. Man har endnu ikke kunnet vise at
der findes uendeligt mange af disse.

Mvh. Bjarke

---

"Bjarke Walling Petersen" <bwp@bwp.dk> wrote in
news:b283j9$1pvq$1@news.cybercity.dk:

> Søren Kongstad skrev:
>> Det er klart at for N gående mod uendelig vil talrækken 1...N
>> indeholde vilkårligt store primtalsørkener, men det første resultat
>> viser jo entydigt at der aldrig er et sidste primtal.
>
> Måske kan jeg ikke helt følge det, men betyder det ikke blot at man
> både kan finde vilkårligt store primtal og vilkårligt store
> primtalsørkener. Eller noget i den stil.
>


Just præcis.

Jeg kom bare til at tænke på det i sammenhæng med den originale posts
"nul" ørkener i pi's decimaler.

Konklusionn om at man kan finde vilkårligt store primtalsørkener kunne
forlede en til at tro at der på et tidspunkt kom en uendelig lang
primtalsørken. Men dette argument falder - lidt på samme måde som
argumentet med uendelige lange nul ørkener. Hvis først en følge er uendelig
lang - så kan der ikke komme noget efter den.

Søren

---

Søren Kongstad skrev:
> Konklusionn om at man kan finde vilkårligt store primtalsørkener kunne
> forlede en til at tro at der på et tidspunkt kom en uendelig lang
> primtalsørken. Men dette argument falder - lidt på samme måde som
> argumentet med uendelige lange nul ørkener. Hvis først en følge er
uendelig
> lang - så kan der ikke komme noget efter den.

Ah ja - jeg kan godt se din pointe nu.

Mvh. Bjarke

---

Bjarke Walling Petersen skrev:

>Men jeg har hørt om primtalstvillinger

Jeg ved ikke om der er noget sjov ved det, men jeg fandt på
begrebet primtalskvartetter, f.eks. 11, 13, 17 og 19. Man er
naturligvis nødt til at springe dem over der ender på 5, og man
kan ikke 'løbe om hjørner' uden at ramme 3-tabellen. Dem er der
sikkert også uendeligt mange af.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

In <4fqf4vc86aukuqcnqm62nutcga1celfirh@news.stofanet.dk> Bertel Lund Hansen <nospamfor@lundhansen.dk> writes:

>Bjarke Walling Petersen skrev:

>>Men jeg har hørt om primtalstvillinger

>Jeg ved ikke om der er noget sjov ved det, men jeg fandt på
>begrebet primtalskvartetter, f.eks. 11, 13, 17 og 19. Man er
>naturligvis nødt til at springe dem over der ender på 5, og man
>kan ikke 'løbe om hjørner' uden at ramme 3-tabellen. Dem er der
>sikkert også uendeligt mange af.

16061, 16063,16067, 16069 har vaeret mine favorit primtal i mange aar.

/Martin

---

Martin Moller Pedersen wrote:

> 16061, 16063,16067, 16069 har vaeret mine favorit primtal i mange aar.

- og 16061 er dejligt nemt at huske.



--
Jens Axel Søgaard
(113/355)^-1 ~ pi

---

"Jens Axel Søgaard" wrote:
>
> Martin Moller Pedersen wrote:
>
> > 16061, 16063,16067, 16069 har vaeret mine favorit primtal i mange aar.
>
> - og 16061 er dejligt nemt at huske.

Et primtalspalindrom! Findes der andre?


--
Kristian Damm Jensen | Feed the hungry at www.thehungersite.com
kristian-damm.jensen@cgey.com | Two wrongs doesn't make a right,
ICQ# 146728724 | but three lefts do.

---

Kristian Damm Jensen <kristian-damm.jensenRE@MOVEcgey.com> writes:

> "Jens Axel Søgaard" wrote:
> >
> > Martin Moller Pedersen wrote:
> >
> > > 16061, 16063,16067, 16069 har vaeret mine favorit primtal i mange aar.
> >
> > - og 16061 er dejligt nemt at huske.
>
> Et primtalspalindrom! Findes der andre?

11

Simon

--
The good Christian should beware of mathematicians, and all those who
make empty prophecies. The danger already exists that the
mathematicians have made a covenant with the devil to darken the
spirit and to confine man in the bonds of Hell. -- St. Augustin

---

Kristian Damm Jensen skrev:

>> - og 16061 er dejligt nemt at huske.
>
> Et primtalspalindrom! Findes der andre?

Uendeligt mange, her er de 2205 (2201) primtalspalindromer i intervallet
1..199999991:

(2)
(3)
(5)
(7)
11
101
131
151
181
191
313
353
373
383
727
757
787
797
919
929
10301
10501
10601
11311
11411
12421
12721
12821
13331
13831
13931
14341
14741
15451
15551
16061
16361
16561
16661
17471
17971
18181
18481
19391
19891
19991
30103
30203
30403
30703
30803
31013
31513
32323
32423
33533
34543
34843
35053
35153
35353
35753
36263
36563
37273
37573
38083
38183
38783
39293
70207
70507
70607
71317
71917
72227
72727
73037
73237
73637
74047
74747
75557
76367
76667
77377
77477
77977
78487
78787
78887
79397
79697
79997
90709
91019
93139
93239
93739
94049
94349
94649
94849
94949
95959
96269
96469
96769
97379
97579
97879
98389
98689
1003001
1008001
1022201
1028201
1035301
1043401
1055501
1062601
1065601
1074701
1082801
1085801
1092901
1093901
1114111
1117111
1120211
1123211
1126211
1129211
1134311
1145411
1150511
1153511
1160611
1163611
1175711
1177711
1178711
1180811
1183811
1186811
1190911
1193911
1196911
1201021
1208021
1212121
1215121
1218121
1221221
1235321
1242421
1243421
1245421
1250521
1253521
1257521
1262621
1268621
1273721
1276721
1278721
1280821
1281821
1286821
1287821
1300031
1303031
1311131
1317131
1327231
1328231
1333331
1335331
1338331
1343431
1360631
1362631
1363631
1371731
1374731
1390931
1407041
1409041
1411141
1412141
1422241
1437341
1444441
1447441
1452541
1456541
1461641
1463641
1464641
1469641
1486841
1489841
1490941
1496941
1508051
1513151
1520251
1532351
1535351
1542451
1548451
1550551
1551551
1556551
1557551
1565651
1572751
1579751
1580851
1583851
1589851
1594951
1597951
1598951
1600061
1609061
1611161
1616161
1628261
1630361
1633361
1640461
1643461
1646461
1654561
1657561
1658561
1660661
1670761
1684861
1685861
1688861
1695961
1703071
1707071
1712171
1714171
1730371
1734371
1737371
1748471
1755571
1761671
1764671
1777771
1793971
1802081
1805081
1820281
1823281
1824281
1826281
1829281
1831381
1832381
1842481
1851581
1853581
1856581
1865681
1876781
1878781
1879781
1880881
1881881
1883881
1884881
1895981
1903091
1908091
1909091
1917191
1924291
1930391
1936391
1941491
1951591
1952591
1957591
1958591
1963691
1968691
1969691
1970791
1976791
1981891
1982891
1984891
1987891
1988891
1993991
1995991
1998991
3001003
3002003
3007003
3016103
3026203
3064603
3065603
3072703
3073703
3075703
3083803
3089803
3091903
3095903
3103013
3106013
3127213
3135313
3140413
3155513
3158513
3160613
3166613
3181813
3187813
3193913
3196913
3198913
3211123
3212123
3218123
3222223
3223223
3228223
3233323
3236323
3241423
3245423
3252523
3256523
3258523
3260623
3267623
3272723
3283823
3285823
3286823
3288823
3291923
3293923
3304033
3305033
3307033
3310133
3315133
3319133
3321233
3329233
3331333
3337333
3343433
3353533
3362633
3364633
3365633
3368633
3380833
3391933
3392933
3400043
3411143
3417143
3424243
3425243
3427243
3439343
3441443
3443443
3444443
3447443
3449443
3452543
3460643
3466643
3470743
3479743
3485843
3487843
3503053
3515153
3517153
3528253
3541453
3553553
3558553
3563653
3569653
3586853
3589853
3590953
3591953
3594953
3601063
3607063
3618163
3621263
3627263
3635363
3643463
3646463
3670763
3673763
3680863
3689863
3698963
3708073
3709073
3716173
3717173
3721273
3722273
3728273
3732373
3743473
3746473
3762673
3763673
3765673
3768673
3769673
3773773
3774773
3781873
3784873
3792973
3793973
3799973
3804083
3806083
3812183
3814183
3826283
3829283
3836383
3842483
3853583
3858583
3863683
3864683
3867683
3869683
3871783
3878783
3893983
3899983
3913193
3916193
3918193
3924293
3927293
3931393
3938393
3942493
3946493
3948493
3964693
3970793
3983893
3991993
3994993
3997993
3998993
7014107
7035307
7036307
7041407
7046407
7057507
7065607
7069607
7073707
7079707
7082807
7084807
7087807
7093907
7096907
7100017
7114117
7115117
7118117
7129217
7134317
7136317
7141417
7145417
7155517
7156517
7158517
7159517
7177717
7190917
7194917
7215127
7226227
7246427
7249427
7250527
7256527
7257527
7261627
7267627
7276727
7278727
7291927
7300037
7302037
7310137
7314137
7324237
7327237
7347437
7352537
7354537
7362637
7365637
7381837
7388837
7392937
7401047
7403047
7409047
7415147
7434347
7436347
7439347
7452547
7461647
7466647
7472747
7475747
7485847
7486847
7489847
7493947
7507057
7508057
7518157
7519157
7521257
7527257
7540457
7562657
7564657
7576757
7586857
7592957
7594957
7600067
7611167
7619167
7622267
7630367
7632367
7644467
7654567
7662667
7665667
7666667
7668667
7669667
7674767
7681867
7690967
7693967
7696967
7715177
7718177
7722277
7729277
7733377
7742477
7747477
7750577
7758577
7764677
7772777
7774777
7778777
7782877
7783877
7791977
7794977
7807087
7819187
7820287
7821287
7831387
7832387
7838387
7843487
7850587
7856587
7865687
7867687
7868687
7873787
7884887
7891987
7897987
7913197
7916197
7930397
7933397
7935397
7938397
7941497
7943497
7949497
7957597
7958597
7960697
7977797
7984897
7985897
7987897
7996997
9002009
9015109
9024209
9037309
9042409
9043409
9045409
9046409
9049409
9067609
9073709
9076709
9078709
9091909
9095909
9103019
9109019
9110119
9127219
9128219
9136319
9149419
9169619
9173719
9174719
9179719
9185819
9196919
9199919
9200029
9209029
9212129
9217129
9222229
9223229
9230329
9231329
9255529
9269629
9271729
9277729
9280829
9286829
9289829
9318139
9320239
9324239
9329239
9332339
9338339
9351539
9357539
9375739
9384839
9397939
9400049
9414149
9419149
9433349
9439349
9440449
9446449
9451549
9470749
9477749
9492949
9493949
9495949
9504059
9514159
9526259
9529259
9547459
9556559
9558559
9561659
9577759
9583859
9585859
9586859
9601069
9602069
9604069
9610169
9620269
9624269
9626269
9632369
9634369
9645469
9650569
9657569
9670769
9686869
9700079
9709079
9711179
9714179
9724279
9727279
9732379
9733379
9743479
9749479
9752579
9754579
9758579
9762679
9770779
9776779
9779779
9781879
9782879
9787879
9788879
9795979
9801089
9807089
9809089
9817189
9818189
9820289
9822289
9836389
9837389
9845489
9852589
9871789
9888889
9889889
9896989
9902099
9907099
9908099
9916199
9918199
9919199
9921299
9923299
9926299
9927299
9931399
9932399
9935399
9938399
9957599
9965699
9978799
9980899
9981899
9989899
100030001
100050001
100060001
100111001
100131001
100161001
100404001
100656001
100707001
100767001
100888001
100999001
101030101
101060101
101141101
101171101
101282101
101292101
101343101
101373101
101414101
101424101
101474101
101595101
101616101
101717101
101777101
101838101
101898101
101919101
101949101
101999101
102040201
102070201
102202201
102232201
102272201
102343201
102383201
102454201
102484201
102515201
102676201
102686201
102707201
102808201
102838201
103000301
103060301
103161301
103212301
103282301
103303301
103323301
103333301
103363301
103464301
103515301
103575301
103696301
103777301
103818301
103828301
103909301
103939301
104000401
104030401
104040401
104111401
104222401
104282401
104333401
104585401
104616401
104787401
104838401
104919401
104949401
105121501
105191501
105202501
105262501
105272501
105313501
105323501
105343501
105575501
105616501
105656501
105757501
105818501
105868501
105929501
106060601
106111601
106131601
106191601
106222601
106272601
106353601
106444601
106464601
106545601
106555601
106717601
106909601
106929601
107000701
107070701
107121701
107232701
107393701
107414701
107424701
107595701
107636701
107646701
107747701
107757701
107828701
107858701
107868701
107888701
107939701
107949701
108070801
108101801
108121801
108151801
108212801
108323801
108373801
108383801
108434801
108464801
108484801
108494801
108505801
108565801
108686801
108707801
108767801
108838801
108919801
108959801
109000901
109101901
109111901
109161901
109333901
109404901
109434901
109444901
109474901
109575901
109656901
109747901
109777901
109797901
109818901
109909901
109929901
110111011
110232011
110252011
110343011
110424011
110505011
110565011
110676011
110747011
110757011
110909011
110949011
110999011
111010111
111020111
111050111
111070111
111181111
111191111
111262111
111272111
111454111
111484111
111515111
111616111
111686111
111757111
111848111
112030211
112060211
112111211
112161211
112171211
112212211
112434211
112494211
112545211
112636211
112878211
112959211
112969211
112989211
113030311
113090311
113111311
113262311
113282311
113474311
113535311
113565311
113616311
113636311
113888311
113939311
114040411
114191411
114232411
114353411
114383411
114484411
114494411
114535411
114727411
114808411
114818411
114848411
114878411
114898411
115000511
115020511
115060511
115111511
115141511
115191511
115212511
115222511
115404511
115464511
115545511
115636511
115737511
115767511
115797511
115828511
115959511
116000611
116010611
116040611
116424611
116505611
116646611
116696611
116757611
116777611
116828611
116868611
116919611
117070711
117101711
117262711
117272711
117323711
117484711
117505711
117515711
117616711
117686711
117757711
117767711
117797711
117818711
117959711
118252811
118272811
118414811
118464811
118525811
118626811
118686811
118696811
118717811
118818811
118848811
118909811
118959811
119010911
119171911
119202911
119343911
119363911
119454911
119585911
119595911
119646911
119676911
119696911
119717911
119787911
119868911
119888911
119969911
120191021
120242021
120434021
120454021
120494021
120535021
120565021
120646021
120808021
120868021
120989021
121080121
121111121
121131121
121161121
121272121
121282121
121393121
121414121
121555121
121747121
121818121
121878121
121939121
121989121
122040221
122232221
122262221
122292221
122333221
122363221
122373221
122393221
122444221
122484221
122535221
122696221
122787221
122858221
122919221
123161321
123292321
123424321
123484321
123494321
123575321
123767321
123838321
123989321
124000421
124080421
124101421
124131421
124252421
124323421
124333421
124434421
124515421
124525421
124626421
124656421
124717421
124737421
124959421
124989421
125000521
125010521
125232521
125252521
125292521
125343521
125474521
125505521
125565521
125606521
125616521
125757521
125838521
125939521
125979521
125999521
126101621
126161621
126181621
126202621
126212621
126323621
126424621
126484621
126535621
126595621
126616621
126676621
126686621
126727621
126737621
126757621
126878621
127060721
127090721
127131721
127212721
127383721
127494721
127545721
127636721
127656721
127686721
127717721
127747721
127828721
127909721
127929721
128070821
128090821
128121821
128181821
128202821
128252821
128262821
128282821
128444821
128474821
128525821
128535821
128595821
128646821
128747821
128787821
128868821
128919821
128939821
129080921
129202921
129292921
129323921
129373921
129484921
129494921
129535921
129737921
129919921
129979921
130020031
130030031
130060031
130141031
130171031
130222031
130333031
130444031
130464031
130545031
130555031
130585031
130606031
130636031
130717031
130767031
130818031
130828031
130858031
130969031
131030131
131111131
131121131
131222131
131252131
131333131
131555131
131565131
131585131
131646131
131676131
131828131
132010231
132191231
132464231
132535231
132595231
132646231
132676231
132757231
133020331
133060331
133111331
133161331
133252331
133474331
133494331
133575331
133686331
133767331
133818331
133909331
134090431
134181431
134232431
134424431
134505431
134525431
134535431
134616431
134757431
134808431
134858431
134888431
134909431
134919431
134979431
135010531
135040531
135101531
135121531
135161531
135262531
135434531
135494531
135515531
135626531
135646531
135707531
135838531
135868531
135878531
135929531
135959531
135979531
136090631
136171631
136222631
136252631
136303631
136363631
136474631
136545631
136737631
136797631
136818631
136909631
136969631
137030731
137040731
137060731
137090731
137151731
137171731
137232731
137282731
137333731
137363731
137424731
137474731
137606731
137636731
137696731
137757731
137808731
137838731
137939731
137999731
138040831
138131831
138242831
138292831
138313831
138383831
138454831
138575831
138616831
138646831
138757831
138898831
138959831
138989831
139131931
139161931
139222931
139252931
139282931
139383931
139474931
139515931
139606931
139626931
139717931
139848931
139959931
139969931
139999931
140000041
140030041
140151041
140303041
140505041
140565041
140606041
140777041
140787041
140828041
140868041
140898041
141020141
141070141
141131141
141151141
141242141
141262141
141313141
141343141
141383141
141484141
141494141
141575141
141595141
141616141
141767141
141787141
141848141
142000241
142030241
142080241
142252241
142272241
142353241
142363241
142464241
142545241
142555241
142686241
142707241
142797241
142858241
142888241
143090341
143181341
143262341
143303341
143454341
143474341
143585341
143636341
143787341
143828341
143919341
143969341
144010441
144020441
144202441
144212441
144313441
144353441
144404441
144434441
144484441
144505441
144707441
144757441
144808441
144818441
144848441
144878441
144898441
144979441
144989441
145020541
145030541
145090541
145353541
145363541
145393541
145464541
145494541
145575541
145666541
145767541
146030641
146040641
146181641
146222641
146252641
146313641
146363641
146505641
146555641
146565641
146676641
146858641
146909641
147191741
147232741
147242741
147313741
147343741
147373741
147434741
147515741
147565741
147616741
147686741
147707741
147757741
147838741
147929741
148020841
148060841
148080841
148414841
148444841
148525841
148545841
148585841
148666841
148686841
148707841
148818841
148858841
148888841
148969841
149000941
149333941
149343941
149484941
149535941
149555941
149616941
149646941
149696941
149858941
149888941
149909941
149919941
149939941
150070051
150151051
150181051
150202051
150272051
150434051
150494051
150505051
150626051
150686051
150727051
150808051
150818051
150979051
151080151
151161151
151212151
151222151
151282151
151353151
151545151
151585151
151656151
151737151
151777151
151858151
151878151
151888151
151959151
151969151
151999151
152090251
152111251
152171251
152181251
152252251
152363251
152393251
152454251
152505251
152565251
152616251
152646251
152666251
152696251
152888251
152939251
153212351
153272351
153292351
153313351
153323351
153404351
153424351
153454351
153484351
153494351
153626351
153808351
153818351
153838351
153979351
154030451
154191451
154252451
154272451
154303451
154323451
154383451
154393451
154474451
154494451
154555451
154575451
154989451
155060551
155141551
155171551
155292551
155313551
155333551
155373551
155424551
155474551
155535551
155646551
155666551
155676551
155808551
155828551
155868551
156151651
156262651
156343651
156424651
156434651
156494651
156545651
156595651
156656651
156707651
156727651
156757651
156848651
156878651
156949651
157090751
157101751
157161751
157252751
157393751
157444751
157555751
157717751
157878751
157888751
157939751
157959751
157989751
158090851
158111851
158222851
158252851
158363851
158474851
158595851
158676851
158696851
158747851
158808851
158858851
158898851
158909851
159020951
159040951
159050951
159121951
159181951
159191951
159202951
159232951
159262951
159292951
159323951
159404951
159464951
159565951
159595951
159646951
159757951
159808951
159919951
159929951
159959951
160020061
160050061
160080061
160101061
160131061
160141061
160161061
160171061
160393061
160545061
160696061
160707061
160717061
160797061
160878061
161171161
161282161
161313161
161363161
161474161
161484161
161535161
161585161
161636161
161787161
161838161
161969161
162040261
162232261
162404261
162464261
162484261
162565261
162686261
162707261
162757261
162898261
162919261
162949261
162959261
162979261
162989261
163101361
163333361
163434361
163464361
163474361
163494361
163515361
163555361
163606361
163686361
163696361
163878361
163959361
164000461
164070461
164151461
164292461
164333461
164454461
164484461
164585461
164616461
164696461
164717461
164727461
164838461
165101561
165161561
165191561
165212561
165343561
165515561
165535561
165808561
165878561
165898561
165919561
165949561
166000661
166080661
166171661
166191661
166404661
166545661
166555661
166636661
166686661
166818661
166828661
166878661
166888661
166929661
167000761
167111761
167262761
167393761
167454761
167474761
167484761
167636761
167646761
167787761
167888761
167898761
167979761
168151861
168191861
168232861
168404861
168505861
168515861
168565861
168818861
168898861
168929861
168949861
169060961
169131961
169141961
169282961
169333961
169383961
169464961
169555961
169606961
169656961
169666961
169686961
169777961
169797961
169858961
169999961
170040071
170060071
170232071
170303071
170333071
170414071
170424071
170484071
170606071
170616071
170646071
170828071
170838071
170909071
170979071
171080171
171262171
171292171
171343171
171565171
171575171
171767171
171919171
171959171
172060271
172090271
172161271
172353271
172363271
172393271
172474271
172585271
172656271
172747271
172767271
172797271
172878271
172909271
172959271
173000371
173030371
173090371
173252371
173373371
173454371
173525371
173585371
173696371
173757371
173777371
173828371
173868371
173888371
173898371
173919371
174080471
174121471
174131471
174181471
174313471
174343471
174595471
174646471
174676471
174919471
174949471
174979471
174989471
175000571
175090571
175101571
175111571
175353571
175444571
175555571
175626571
175747571
175777571
175848571
175909571
176090671
176111671
176141671
176181671
176232671
176313671
176333671
176373671
176393671
176414671
176585671
176636671
176646671
176666671
176696671
176757671
176787671
176888671
176898671
176939671
177121771
177161771
177202771
177242771
177323771
177565771
177616771
177707771
177757771
177868771
178101871
178131871
178141871
178161871
178353871
178414871
178515871
178525871
178656871
178717871
178747871
178878871
178969871
178989871
178999871
179010971
179060971
179222971
179232971
179262971
179414971
179454971
179484971
179717971
179777971
179808971
179858971
179868971
179909971
179969971
179999971
180070081
180101081
180161081
180292081
180515081
180535081
180545081
180565081
180616081
180757081
180959081
181111181
181515181
181545181
181666181
181737181
181797181
181888181
182010281
182202281
182373281
182585281
182616281
182636281
182777281
182858281
182949281
183232381
183626381
183656381
183737381
183898381
183979381
183989381
184030481
184212481
184222481
184303481
184393481
184414481
184545481
184585481
184606481
184636481
184747481
184818481
184878481
185232581
185373581
185393581
185525581
185555581
185595581
185676581
185757581
185838581
185858581
185868581
185999581
186010681
186040681
186050681
186070681
186101681
186131681
186151681
186161681
186424681
186484681
186505681
186565681
186656681
186676681
186787681
186898681
187090781
187101781
187111781
187161781
187272781
187404781
187434781
187444781
187525781
187767781
187909781
187939781
187999781
188010881
188060881
188141881
188151881
188303881
188373881
188414881
188454881
188505881
188525881
188535881
188616881
188636881
188646881
188727881
188777881
188868881
188888881
188898881
188979881
189080981
189131981
189262981
189292981
189464981
189535981
189595981
189727981
189787981
189838981
189898981
189929981
190000091
190020091
190080091
190101091
190252091
190404091
190434091
190464091
190494091
190656091
190696091
190717091
190747091
190777091
190858091
190909091
191090191
191171191
191232191
191292191
191313191
191565191
191595191
191727191
191757191
191838191
191868191
191939191
191969191
192101291
192191291
192202291
192242291
192313291
192404291
192454291
192484291
192767291
192797291
192898291
193000391
193030391
193191391
193212391
193282391
193303391
193383391
193414391
193464391
193555391
193686391
193858391
193888391
194000491
194070491
194121491
194222491
194232491
194292491
194303491
194393491
194505491
194595491
194606491
194787491
194939491
194999491
195010591
195040591
195070591
195151591
195202591
195242591
195353591
195505591
195545591
195707591
195767591
195868591
195878591
195949591
195979591
196000691
196090691
196323691
196333691
196363691
196696691
196797691
196828691
196878691
197030791
197060791
197070791
197090791
197111791
197121791
197202791
197292791
197343791
197454791
197525791
197606791
197616791
197868791
197898791
197919791
198040891
198070891
198080891
198131891
198292891
198343891
198353891
198383891
198454891
198565891
198656891
198707891
198787891
198878891
198919891
199030991
199080991
199141991
199171991
199212991
199242991
199323991
199353991
199363991
199393991
199494991
199515991
199545991
199656991
199767991
199909991
199999991


// Klaus

--
><>    vandag, môre, altyd saam

---

Klaus Alexander Seistrup wrote:
>
> > Et primtalspalindrom! Findes der andre?
>
> Uendeligt mange,

Kan man mon *bevise* det?

Se også http://primes.utm.edu/links/theory/special_forms/palindrome/

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jeppe Stig Nielsen skrev:

>> > Et primtalspalindrom! Findes der andre?

>> Uendeligt mange,

>Kan man mon *bevise* det?

Det gav mig en idé. Jeg vil skrive i en note i en af mine
matematikbøger at jeg har fundet en vidunderlig formel der kan
beregne et vilkårligt primtal hurtigt. Måske er der så en om 300
år der finder sådan en formel ...

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen wrote:
>
> >Men jeg har hørt om primtalstvillinger
>
> Jeg ved ikke om der er noget sjov ved det, men jeg fandt på
> begrebet primtalskvartetter, f.eks. 11, 13, 17 og 19. Man er
> naturligvis nødt til at springe dem over der ender på 5, og man
> kan ikke 'løbe om hjørner' uden at ramme 3-tabellen. Dem er der
> sikkert også uendeligt mange af.

Bertel, der er »sjov ved det«, og din generalisation af primtals-
tvillinger er naturlig. Dens naturlighed betyder at der er folk der
har gjort den før:

http://primes.utm.edu/glossary/page.php?sort=PrimeConstellation

Og læg mærke til at den formodning du fremsætter (»sådan nogle er der
sikkert også uendeligt mange af«), svarer til det Caldwell kalder for
primtals-k-tupel-formodningen (k=4 kaldes primtalskvadrupelformodning).

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jeppe Stig Nielsen wrote:
>
> Bertel, der er »sjov ved det«, og din generalisation af primtals-
> tvillinger er naturlig. Dens naturlighed betyder at der er folk der
> har gjort den før:
>
> http://primes.utm.edu/glossary/page.php?sort=PrimeConstellation

Ja og http://primes.utm.edu/glossary/page.php?sort=Quadruple

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

"Søren Kongstad" wrote:
>
> Det er klart at for N gående mod uendelig vil talrækken 1...N indeholde
> vilkårligt store primtalsørkener, men det første resultat viser jo
> entydigt at der aldrig er et sidste primtal.

Hvis vi lader a_n betegne differensen mellem det (n+1)'te og det n'te
primtal, så er {a_n} en uendelig følge fordi der er uendeligt mange
primtal.

Med en modifikation af dit argument kan man indse at limsup a_n er
uendelig (limes superior). Og primtalssætningen siger faktisk også
at de »typiske« a_n bliver større når n vokser. Faktisk er den typiske
a_n af størrelsesordenen log p_n hvor log er den naturlige logaritme
og p_n er det n'te primtal.

Spørgsmålet er så hvad vi kan sige om liminf a_n . Primtalstvillinge-
formodningen siger at liminf a_n = 2 , altså at afstanden mellem to
på hinanden følgende primtal uendeligt ofte kommer ned på 2.

Mig bekendt er det ikke bevist at liminf a_n er mindre end uendelig.

Man kunne også spørge hvilke andre lige tal der rammes ofte af {a_n}.

Se endvidere http://www.utm.edu/research/primes/notes/gaps.html

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Simon Kristensen <spam_me_senseless@simonsays.dk> writes:
> Kristian Damm Jensen <kristian-damm.jensenRE@MOVEcgey.com> writes:
>
>> Et primtalspalindrom! Findes der andre?
>
> 11

Faktisk er 13 det første primtal der ikke er et palindrom.

--
"It's like David and Goliath, only this time David won!"

---

Bertel Lund Hansen <nospamfor@lundhansen.dk> writes:

> matematikbøger at jeg har fundet en vidunderlig formel der kan
> beregne et vilkårligt primtal hurtigt. Måske er der så en om 300
> år der finder sådan en formel ...

Hvad mener du lige med 'at beregne et vilkårligt primtal'?

Kan identitetsfunktionen bruges? Givet et vilkårligt primtal giver den
selv samme primtal hurtigt. Det er selvfølgelig udefineret hvad den
giver hvis man ikke giver den et primtal.

--
Peter Makholm | Emacs is the only modern general-purpose
peter@makholm.net | operating system that doesn't multitask
http://hacking.dk |

---

Peter Makholm skrev:

>Hvad mener du lige med 'at beregne et vilkårligt primtal'?

At hvis du beder om det mindste 1000-cifrede primtal, så bliver
det spyttet ud på et par sekunder.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen wrote:
>
> >Hvad mener du lige med 'at beregne et vilkårligt primtal'?
>
> At hvis du beder om det mindste 1000-cifrede primtal, så bliver
> det spyttet ud på et par sekunder.

Den funktion kan man kalde nextprime(x). Altså fx

nextprime(1000) = 1009

Det tal du spørger om, er så nextprime(10^999). Hvor lang tid tager
det at finde det i dag? Vistnok ikke særligt lang tid med passende
software.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jeppe Stig Nielsen skrev:
> Den funktion kan man kalde nextprime(x). Altså fx
>
> nextprime(1000) = 1009
>
> Det tal du spørger om, er så nextprime(10^999). Hvor lang tid tager
> det at finde det i dag? Vistnok ikke særligt lang tid med passende
> software.

Hvad gør man egentlig ved public key kryptering? - man skal jo bruge to så
store primtal at de er svære at finde og derved faktorisere
primtal1*primtal2 - men man skal jo selv finde disse. Hvordan gør man
dette? - prøver man sig frem eller er det blot sådan at krypteringsfirmaerne
har så store computere at de kan finde dem, men alle andre ikke?

I øvrigt tror jeg Bertel efterlyser en simpel formel eller algoritme der gør
at nextprime(x) kan findes lige nemt og hurtigt for alle givne værdier af x.
Dette ville i hvert fald kunne bruges imod diverse krypteringer, hvis jeg
har forstået det ret.

Mvh. Bjarke

---

Bjarke Walling Petersen skrev:

>I øvrigt tror jeg Bertel efterlyser en simpel formel eller algoritme der gør
>at nextprime(x) kan findes lige nemt og hurtigt for alle givne værdier af x.

Nej nej, jeg har fundet den ... jeg har skrevet den ned et eller
andet sted ...

(Jo, det var det jeg mente)

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen skrev:
> Nej nej, jeg har fundet den ... jeg har skrevet den ned et eller
> andet sted ...
[klip]

Så må fremtiden jo vise om du bliver ligeså kendt som Fermat. Held og lykke!

Mvh. Bjarke

---

"Bjarke Walling Petersen" <bwp@bwp.dk> writes:

> Hvad gør man egentlig ved public key kryptering? - man skal jo bruge to så
> store primtal at de er svære at finde og derved faktorisere
> primtal1*primtal2 - men man skal jo selv finde disse. Hvordan gør man
> dette? - prøver man sig frem

Essentielt ja. Man generere et tilfældigt stort tal, og undersøge om det
er et primtal (evt. kun med passende høj sandsynlighed), hvis det er så
bruger man det, ellers prøver man igen. I betragtning af at
sandsynligheden for at et tilfældigt 100-cifret tal er et primtal er
ca. 1%, er det en forholdsvis hurtig proces.

> I øvrigt tror jeg Bertel efterlyser en simpel formel eller algoritme der gør
> at nextprime(x) kan findes lige nemt og hurtigt for alle givne værdier af x.

Det er et polynomielt problem, og dermed kan det i en vis forstand
allerede løses hurtigt.

Desuden tror jeg Fermats påstand var gået i glemmebogen, hvis det ikke
var fordi han var en glimrende matematiker.

> Dette ville i hvert fald kunne bruges imod diverse krypteringer, hvis jeg
> har forstået det ret.

Det kan jeg ikke umiddelbart se. Du har et tal du ved er produktet af to
store primtal, og skal finde faktorerne, så kan jeg ikke se det kan
hjælpe at kunne finde nextprime. Du kan måske gøre et brute-force-angreb
marginalt hurtigere, men antallet af primtal der er mulige faktorer er
stadig urimeligt stort.

..Henrik

--
Jacob: Because the theoreticians told me.
Prof. Vassilicos: Why do you believe theoreticians?

---

Henrik Christian Grove skrev:

>Desuden tror jeg Fermats påstand var gået i glemmebogen, hvis det ikke
>var fordi han var en glimrende matematiker.

Lyseslukker!

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

In article <b2ohs1$2k9n$1@news.cybercity.dk>, bwp@bwp.dk says...

> Hvad gør man egentlig ved public key kryptering? - man skal jo bruge to så
> store primtal at de er svære at finde og derved faktorisere
> primtal1*primtal2 - men man skal jo selv finde disse. Hvordan gør man
> dette? - prøver man sig frem eller er det blot sådan at krypteringsfirmaerne
> har så store computere at de kan finde dem, men alle andre ikke?

Det er ikke svært at finde to store primtal - og så gange dem sammen for
at finde deres produkt. Det, der er svært, er kun at have produktet, og
så finde et af de oprindelige primtal.

http://mathworld.wolfram.com/PrimalityTest.html

Med venlig hilsen Sven.

---

Sven Nielsen skrev:
> Det er ikke svært at finde to store primtal - og så gange dem sammen for
> at finde deres produkt. Det, der er svært, er kun at have produktet, og
> så finde et af de oprindelige primtal.
>
> http://mathworld.wolfram.com/PrimalityTest.html

Nå ja - det giver mening.

Også tak for de andre svar!

Mvh. Bjarke

---

Bjarke Walling Petersen wrote:
>
> > Det er ikke svært at finde to store primtal - og så gange dem sammen for
> > at finde deres produkt. Det, der er svært, er kun at have produktet, og
> > så finde et af de oprindelige primtal.
> >
> > http://mathworld.wolfram.com/PrimalityTest.html
>
> Nå ja - det giver mening.

Pointen er altså at det skal være meget lettere at afgøre hvorvidt et
tal er et primtal, end det skal være at finde en primfaktor i et »ondt«
sammensat tal. Så længe dette er tilfældet, kan kryptering ved brug af
primtal fungere sikkert selvom algoritmen er offentlig (og programkoden
kan (og bør) være open source).

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jeppe Stig Nielsen skrev:
> Pointen er altså at det skal være meget lettere at afgøre hvorvidt et
> tal er et primtal, end det skal være at finde en primfaktor i et »ondt«
> sammensat tal. Så længe dette er tilfældet, kan kryptering ved brug af
> primtal fungere sikkert selvom algoritmen er offentlig (og programkoden
> kan (og bør) være open source).

Set fra matematikerens synspunkt (ham der finder en genial algoritme) ville
det da nok give mere i pengepungen at sælge den til et stort
krypteringsfirma, der sandsynligvis ville kunne lave langt kraftigere og
helt sikre (relativt selvfølgelig...) krypteringer med den, end "blot" at
modtage den million dollars eller hvor meget det nu er man kan få fra en
eller anden fond. Men om det ikke nager i moralen er selvfølgelig en anden
ting.
I øvrigt er public key kryptering egentlig ret genialt lavet ved nærmere
eftertanke.

Mvh. Bjarke

---

Scripsit "Bjarke Walling Petersen" <bwp@bwp.dk>

> Set fra matematikerens synspunkt (ham der finder en genial algoritme) ville
> det da nok give mere i pengepungen at sælge den til et stort
> krypteringsfirma, der sandsynligvis ville kunne lave langt kraftigere og
> helt sikre (relativt selvfølgelig...) krypteringer med den,

Det er ikke umiddelbart klart (for mig) at effektiv faktorisering kan
bruges som grundlag for et kryptosystem. Har du noget specielt i
tankerne?

--
Henning Makholm "That's okay. I'm hoping to convince the
millions of open-minded people like Hrunkner Unnerby."

---

Henning Makholm skrev:
> Det er ikke umiddelbart klart (for mig) at effektiv faktorisering kan
> bruges som grundlag for et kryptosystem. Har du noget specielt i
> tankerne?

Nå, måske har jeg misforstået noget. Jeg tænke nu blot på hvis en
matematiker fandt en algoritme til uanset længde at finde et hvilket som
helst primtal og som med 100% sikkerhed er et primtal.
Jeg ved ikke hvormange cifre primtalene man bruger til public key kryptering
nutildags er, men med en algoritme som beskrevet ville man kunne bruge
vilkårligt mange cifre. F.eks. kunne man benytte 100 gange flere cifre, hvis
man ville. Selvfølgelig går det ud over pladsforbruget ved lagring af
nøglen. Men set i betragtning af hvor svært det er at knække en nøgle er der
måske slet ikke vundet noget ved det.
Jeg har bare en idé om at krypteringsfirmaer gerne vil have fat i den
ultimative algoritme der kan finde ethvert primtal. Måske forkert antagelse.

Mvh. Bjarke

---

Scripsit "Bjarke Walling Petersen" <bwp@bwp.dk>

> Nå, måske har jeg misforstået noget. Jeg tænke nu blot på hvis en
> matematiker fandt en algoritme til uanset længde at finde et hvilket som
> helst primtal og som med 100% sikkerhed er et primtal.

Du bliver nødt til at bestemme dig til om du snakker om en algoritme
til til at faktorisere et givet sammensat tal eller en algoritme der
blot skal finde et eller andet vilkårligt primtal.

> Jeg har bare en idé om at krypteringsfirmaer gerne vil have fat i den
> ultimative algoritme der kan finde ethvert primtal.

Hvad mener du med det? Hvad er inddata til den algoritme? Hvad er
uddata?

--
Henning Makholm "Man vælger jo selv sine forbilleder."

---

Henning Makholm skrev:
> Du bliver nødt til at bestemme dig til om du snakker om en algoritme
> til til at faktorisere et givet sammensat tal eller en algoritme der
> blot skal finde et eller andet vilkårligt primtal.

Jeg taler om en algoritme til fremstilling af primtal. Jeg misforstod blot
Jeppes brug af algoritme - her mente han vist public key
krypteringsalgoritmen.

> Hvad mener du med det? Hvad er inddata til den algoritme? Hvad er
> uddata?

For mig at se ville det være ret ultimativt med en algoritme eller måske
blot formel der havde inddata af nummer i rækken og uddata var et primtal,
f.eks.: f(1) = 2, f(2) = 3, f(3) = 5, f(4) = 7, f(5) = 11, f(6) = 13, etc.

Mvh. Bjarke

---

Scripsit "Bjarke Walling Petersen" <bwp@bwp.dk>
> Henning Makholm skrev:

> > Hvad mener du med det? Hvad er inddata til den algoritme? Hvad er
> > uddata?

> For mig at se ville det være ret ultimativt med en algoritme eller måske
> blot formel der havde inddata af nummer i rækken og uddata var et primtal,
> f.eks.: f(1) = 2, f(2) = 3, f(3) = 5, f(4) = 7, f(5) = 11, f(6) = 13, etc.

Ok. Så backtracker vi lige et par indlæg: Hvordan mener du at sådan en
algoritme vil føre til et gennembrud i kryptografi som man kan sælge
og udnytte kommercielt?

--
Henning Makholm "Hør, hvad er det egentlig
der ikke kan blive ved med at gå?"

---

Henning Makholm skrev:
> Ok. Så backtracker vi lige et par indlæg: Hvordan mener du at sådan en
> algoritme vil føre til et gennembrud i kryptografi som man kan sælge
> og udnytte kommercielt?

Nu har jeg ikke den store tekniske kendskab til public key kryptering. Men
lad os sige at man nutildags bruger de største og bedste computere og bedste
formler til at finde de primtal man bruger. Det kan være man kan skaffe
primtal med 10.000 cifre - det ved jeg ikke. Hvis man havde den omtalte
formel ville det måske svare til at bruge 10^5000 (blot et gæt) som input.
Hvis man virkeligt havde denne formel ville man blot kunne indsætte
10^500000 i stedet for og få tilsvarende større primtal ud. Og man ville
kunne fortsætte. Det ville ikke kræve 10 års udvikling af de supercomputere
vi har nutildags at få et primtal der er selv 1.000.000 gange længere end de
største vi kender til nu.
Dog sagde jeg også tidligere:
"Selvfølgelig går det ud over pladsforbruget ved lagring af nøglen. Men set
i betragtning af hvor svært det er at knække en nøgle er der måske slet ikke
vundet noget ved det."

Mvh. Bjarke

---

Scripsit "Bjarke Walling Petersen" <bwp@bwp.dk>

> Det kan være man kan skaffe primtal med 10.000 cifre - det ved jeg
> ikke. Hvis man havde den omtalte formel ville det måske svare til at
> bruge 10^5000 (blot et gæt) som input. Hvis man virkeligt havde
> denne formel ville man blot kunne indsætte 10^500000 i stedet for og
> få tilsvarende større primtal ud. Og man ville kunne fortsætte.

Det er ikke noget problem p.t. at skaffe tilstrækkelig store primtal
til krypteringsnøgler.

Når folk bruger nøgler på fx 1024 bits i stedet for nøgler på 4096
bits er det ikke fordi det tager videre lang tid at *lave* en nøgle på
4096 bits, men fordi det tager for lang tid at *bruge* (henholdsvis
udføre beregningerne og trasmittere en krypteret session key eller
signatur) så lang en nøgle, set i forhold til hvilken ekstra sikkerhed
det giver.

Forskellen er noget i retning af om det vil tage samtlige
edb-ressourcer i alverdens efterretningsvæsener 100 år eller en
milliard gange universets levetid at knække nøglen. Under alle
omstændigheder er det sikkert nok til at det ikke længere er nøglen
der er det svageste led i sikkerhedsarkitekturen, og så er der ingen
grund til at forbedre den yderligere.

(Og tal i det just ovenstående afsnit er så vildt skønnede, at selv
deres størrelsesordener kan afvige fra virkeligheden med op til en
størrelsesorden).

--
Henning Makholm "En tapper tinsoldat. En dame i
spagat. Du er en lykkelig mand ..."

---

Henning Makholm skrev:
[klip]
> Forskellen er noget i retning af om det vil tage samtlige
> edb-ressourcer i alverdens efterretningsvæsener 100 år eller en
> milliard gange universets levetid at knække nøglen. Under alle
> omstændigheder er det sikkert nok til at det ikke længere er nøglen
> der er det svageste led i sikkerhedsarkitekturen, og så er der ingen
> grund til at forbedre den yderligere.
[klip]

Ja, okay - det var også noget i den retning jeg havde i baghovedet, at kunne
være tilfældet.

Mvh. Bjarke

---

---

In <b2tvm5$2cie$1@news.cybercity.dk> "Bjarke Walling Petersen" <bwp@bwp.dk> writes:

>Henning Makholm skrev:
>> Du bliver nødt til at bestemme dig til om du snakker om en algoritme
>> til til at faktorisere et givet sammensat tal eller en algoritme der
>> blot skal finde et eller andet vilkårligt primtal.

>Jeg taler om en algoritme til fremstilling af primtal. Jeg misforstod blot
>Jeppes brug af algoritme - her mente han vist public key
>krypteringsalgoritmen.

>> Hvad mener du med det? Hvad er inddata til den algoritme? Hvad er
>> uddata?

>For mig at se ville det være ret ultimativt med en algoritme eller måske
>blot formel der havde inddata af nummer i rækken og uddata var et primtal,
>f.eks.: f(1) = 2, f(2) = 3, f(3) = 5, f(4) = 7, f(5) = 11, f(6) = 13, etc.

Men der findes da allerede en saadan algoritme og jeg kan lave
et c-program paa faa linier, der kan finde de n'te primtal.

/Martin

---

Martin Moller Pedersen skrev:
> Jeg skrev:
> >For mig at se ville det være ret ultimativt med en algoritme eller måske
> >blot formel der havde inddata af nummer i rækken og uddata var et
primtal,
> >f.eks.: f(1) = 2, f(2) = 3, f(3) = 5, f(4) = 7, f(5) = 11, f(6) = 13,
etc.
>
> Men der findes da allerede en saadan algoritme og jeg kan lave
> et c-program paa faa linier, der kan finde de n'te primtal.

Okay - hvorfor er der ikke nogen der har fortalt mig det noget før! :)

Du må gerne sende det c-program til mig, hvis du har tid - koden. Eller blot
forklare princippet bag.

Mvh. Bjarke

---

Scripsit "Bjarke Walling Petersen" <bwp@bwp.dk>
> Martin Moller Pedersen skrev:

> > >f.eks.: f(1) = 2, f(2) = 3, f(3) = 5, f(4) = 7, f(5) = 11, f(6) = 13,

> > Men der findes da allerede en saadan algoritme og jeg kan lave
> > et c-program paa faa linier, der kan finde de n'te primtal.

> Okay - hvorfor er der ikke nogen der har fortalt mig det noget før! :)

Han tænker utvivlsomt på noget i retning af

bigint f(bigint n) {
bigint x = 2 ;
while( 1 ) {
if( is_prime(x) ) {
if( --n == 0 )
return x ;
}
x++ ;
}
}

som ganske rigtigt opfylder din specifikation. Men den er ikke videre
effektiv.

--
Henning Makholm "Nemo enim fere saltat sobrius, nisi forte insanit."

---

Henning Makholm skrev:
> Han tænker utvivlsomt på noget i retning af
>
> bigint f(bigint n) {
> bigint x = 2 ;
> while( 1 ) {
> if( is_prime(x) ) {
> if( --n == 0 )
> return x ;
> }
> x++ ;
> }
> }

Hvis blot x blev adderet 2 for hvert step efter den havde været 3 ville det
gå en del hurtigere.

> som ganske rigtigt opfylder din specifikation. Men den er ikke videre
> effektiv.

Nej, den er ikke effektiv, hvilket også skulle være et krav. Der skulle
omtrendt det samme antal beregninger til at finde alle primtal uanset
størrelse, hvilket måske slet ikke kan lade sig gøre - det lyder lidt
usandsynligt. Uden at blive for teknisk kunne man måske stille krav om at
antallet af beregninger ca. skulle være proportionalt med antallet af cifre
i det fundne primtal - og med en lille proportionalitetsfaktor. Det lyder
mere rimeligt.

Godt nok er det et stykke tid siden, men jeg skrev jo oprindeligt:
"I øvrigt tror jeg Bertel efterlyser en simpel formel eller algoritme der
gør
at nextprime(x) kan findes lige *nemt* og *hurtigt* for alle givne værdier
af x."
Jeg diskuterer stadig med den i baghovedet - at formlen skal være effektiv.

Mvh. Bjarke

---

In <b2ui57$30tm$1@news.cybercity.dk> "Bjarke Walling Petersen" <bwp@bwp.dk> writes:

>Henning Makholm skrev:
>> Ok. Så backtracker vi lige et par indlæg: Hvordan mener du at sådan en
>> algoritme vil føre til et gennembrud i kryptografi som man kan sælge
>> og udnytte kommercielt?

>Nu har jeg ikke den store tekniske kendskab til public key kryptering. Men
>lad os sige at man nutildags bruger de største og bedste computere og bedste
>formler til at finde de primtal man bruger. Det kan være man kan skaffe
>primtal med 10.000 cifre - det ved jeg ikke. Hvis man havde den omtalte
>formel ville det måske svare til at bruge 10^5000 (blot et gæt) som input.
>Hvis man virkeligt havde denne formel ville man blot kunne indsætte
>10^500000 i stedet for og få tilsvarende større primtal ud.

Hvis du vil have et stort primtal kan du bare gange alle
primtal under 1000 sammen og laegge 1 til. Hvis det ikke er
stort nok, saa gange alle primtal under X sammen og laeg 1 til, hvor
X er et stoerre tal.

Mvh
Martin

---

tusk@daimi.au.dk (Martin Moller Pedersen) writes:

> Hvis du vil have et stort primtal kan du bare gange alle
> primtal under 1000 sammen og laegge 1 til. Hvis det ikke er
> stort nok, saa gange alle primtal under X sammen og laeg 1 til, hvor
> X er et stoerre tal.

Det behøver ikke give et primtal, men dog et tal der har en primfaktor
du ikke havde med, f.eks. er 2*3*5*7*11*13+1 = 30031 = 59*509.

..Henrik

--
"Og jeg troede UENDELIG var et stort tal!"
-sagt efter en matematikforelæsning om transfinitte kardinaltal

---

Henrik Christian Grove <grove@sslug.dk> wrote in
news:7gbs18k43c.fsf@serena.fsr.ku.dk:

> tusk@daimi.au.dk (Martin Moller Pedersen) writes:
>
>> Hvis du vil have et stort primtal kan du bare gange alle
>> primtal under 1000 sammen og laegge 1 til. Hvis det ikke er
>> stort nok, saa gange alle primtal under X sammen og laeg 1 til, hvor
>> X er et stoerre tal.
>
> Det behøver ikke give et primtal, men dog et tal der har en primfaktor
> du ikke havde med, f.eks. er 2*3*5*7*11*13+1 = 30031 = 59*509.
>
> .Henrik
>

Ja men så skal du opløse et meget stort tal i primfaktorer - det er netop
ikke nødvendigvis en billig operation. Det er jo netop derfor public key
encryption fungerer(*

Søren

(*
Der anvender man godt nok et tal med en primopløsning p*q hvor p og q er
meget stor primtal - Et tal der er fremkommet efter din metode vil vel
kun sjældent have den form. Dog bliver problemet sværere og sværere jo
flere primtal du anvender til at generere dit ny tal.

---

"Søren Kongstad" <spamm@kongstad.net> writes:

> Henrik Christian Grove <grove@sslug.dk> wrote in
> news:7gbs18k43c.fsf@serena.fsr.ku.dk:
>
> > tusk@daimi.au.dk (Martin Moller Pedersen) writes:
> >
> >> Hvis du vil have et stort primtal kan du bare gange alle
> >> primtal under 1000 sammen og laegge 1 til. Hvis det ikke er
> >> stort nok, saa gange alle primtal under X sammen og laeg 1 til, hvor
> >> X er et stoerre tal.
> >
> > Det behøver ikke give et primtal, men dog et tal der har en primfaktor
> > du ikke havde med, f.eks. er 2*3*5*7*11*13+1 = 30031 = 59*509.
> >
> > .Henrik
> >
>
> Ja men så skal du opløse et meget stort tal i primfaktorer - det er netop
> ikke nødvendigvis en billig operation. Det er jo netop derfor public key
> encryption fungerer(*

Det viser jo bare at Martins metode ikke er en specielt nem måde at
finde nye primtal på.

..Henrik

--
"Og jeg troede UENDELIG var et stort tal!"
-sagt efter en matematikforelæsning om transfinitte kardinaltal

---

Martin Moller Pedersen wrote:
>
> Hvis du vil have et stort primtal kan du bare gange alle
> primtal under 1000 sammen og laegge 1 til. Hvis det ikke er
> stort nok, saa gange alle primtal under X sammen og laeg 1 til, hvor
> X er et stoerre tal.

I almindelighed giver produktet af alle primtal under en vis grænse
ikke nødvendigvis et primtal når man lægger én til. Eksempel:

2·3·5·7·11·13 + 1 = 30031 = 59·509

Det man kan sige, er at et tal lavet på denne måde kun kan indeholde
primfaktorer der hver er større end den grænse (her 13) som man gik op
til.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

"Jeppe Stig Nielsen" <mail@jeppesn.dk> skrev i en meddelelse news:3E539522.1FA55EED@jeppesn.dk...

> ikke nødvendigvis et primtal når man lægger én til. Eksempel:
>
> 2·3·5·7·11·13 + 1 = 30031 = 59·509
>
Det er nu 3. gang vi ser dette modeksempel. Er det noget
til Guinness som jeg også bør være med i ?

Mvh
Martin

---

---

In <ud6lok5wp.fsf@banach.algebra.dk> Stefan Holm <nospam@algebra.dk> writes:

> (i386-msvc-nt5.0.2195)
>X-Fnord: Denne header findes ikke
>Cancel-Lock: sha1:BMQamuvuL232yUYJ//G/Ggc+fyk=
>X-Authenticated: sh@aub.dk
>Xref: news.net.uni-c.dk dk.videnskab:60892

>tusk@daimi.au.dk (Martin Moller Pedersen) writes:

>> Hvis du vil have et stort primtal kan du bare gange alle
>> primtal under 1000 sammen og laegge 1 til.

>Det sikrer da kun mod primfaktorer under 1000. Hvordan slipper du af
>med de andre?

>Se eksempelvis på 2*3*5*7*11*13+1 = 30031 = 59*509 for det simpleste
>eksempel på at man ikke generelt kan gøre sådan.

Oops. Jeg taenkte paa noget andet nemlig primtalsoerkner dvs.
store omraader uden primtal.

1000!+1 giver en primtals-oerken paa mindst laengden 1000.

Mvh
Martin

---

Martin Moller Pedersen wrote:
>
> Oops. Jeg taenkte paa noget andet nemlig primtalsoerkner dvs.
> store omraader uden primtal.
>
> 1000!+1 giver en primtals-oerken paa mindst laengden 1000.

Ja, hvis længden defineres på rette måde. A priori kan man bare sige
at der er 999 sammensatte tal i træk (begyndende med 1000!+2 og slut-
tende med 1000!+1000), men det svarer jo så til at afstanden mellem de
to måske ikke-sammensatte tal der omkranser ørkenen, er på 1000.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

In <3E539687.D1E6C993@jeppesn.dk> Jeppe Stig Nielsen <mail@jeppesn.dk> writes:

>Martin Moller Pedersen wrote:
>>
>> Oops. Jeg taenkte paa noget andet nemlig primtalsoerkner dvs.
>> store omraader uden primtal.
>>
>> 1000!+1 giver en primtals-oerken paa mindst laengden 1000.

>Ja, hvis længden defineres på rette måde. A priori kan man bare sige
>at der er 999 sammensatte tal i træk (begyndende med 1000!+2 og slut-
>tende med 1000!+1000), men det svarer jo så til at afstanden mellem de
>to måske ikke-sammensatte tal der omkranser ørkenen, er på 1000.

Og 1000!+1 er sikkert heller ikke den foerste primtals-oerken med laengde 1000.

/Martin

---

Scripsit tusk@daimi.au.dk (Martin Moller Pedersen)

> Og 1000!+1 er sikkert heller ikke den foerste primtals-oerken med
> laengde 1000.

Garanteret ikke. Man kan nemlig (ses let) erstatte 1000! med produktet
af alle *primtal* under 1000.

--
Henning Makholm "Monsieur, vous êtes fou."

---

tusk@daimi.au.dk (Martin Moller Pedersen) writes:

> Hvis du vil have et stort primtal kan du bare gange alle
> primtal under 1000 sammen og laegge 1 til.

Det sikrer da kun mod primfaktorer under 1000. Hvordan slipper du af
med de andre?

Se eksempelvis på 2*3*5*7*11*13+1 = 30031 = 59*509 for det simpleste
eksempel på at man ikke generelt kan gøre sådan.

--
"Well did you try looking inside the sofa *in Hell*?"

---

Endnu en kommentar til spørgsmålet om normaliteten af pi. Jeg fandt
ikke følgende på MathWorld eller resten af denne tråd, så her er et
kuriosum om normale tal:

Næsten ethvert reelt tal er normalt (mht. Lebesgue-målet).

Bevis (for folk, der kender til sandsynlighedsteori):
Vi kan nøjes med at betragte tal i intervallet I = [0,1), idet der
alligevel kun er endeligt mange pladser før 'kommaet'. Denne mængde
har Lebesgue mål 1.

Se på tal i basis b. Disse kan skrives

0,a_1 a_2 a_3 ...

hvor a_i er et element i B={0, ..., b-1}. Vi kan betragte a_i'erne som
uniformt fordelte uafhængige stokastiske variable med udfaldsrum
B. Lad b være et element i B. Ifølge de store tals stærke lov er nu

lim_{n->oo} (X_(a_1 = b)(x) + ... + X_(a_n = b)(x))/n = 1/b

for næsten alle x i [0,1), hvor X_(a_i=b) er 1 hvis a_i=b og 0
ellers. Altså er næsten alle tal normale til basis b.

Tag nu de tal, der ikke er normale til basis b. Dette er en
nul-mængde. Altså er foreningsmængden af de tal, der ikke er normale
til basis b for b løbende over de naturlige tal også en
nulmængde. Derfor er næsten ethvert tal normalt til alle baser.
QED

Ovenstående sætning gør det i sandhed besynderligt at vi ikke rigtig
kender nogle tal, der er normale i enhver basis. Der er flere
forklaringer på dette. En har at gøre med entropien af den process,
der er på spil. En anden er, at mængden af de ikke normale tal har
Hausdorff dimension 1 (det er noget sværere at vise). Ikke desto
mindre er det et fantastisk skægt problem at forsøge art finde disse
tal.

Venligst

Simon

--
The good Christian should beware of mathematicians, and all those who
make empty prophecies. The danger already exists that the
mathematicians have made a covenant with the devil to darken the
spirit and to confine man in the bonds of Hell. -- St. Augustin

---

Scripsit Simon Kristensen <spam_me_senseless@simonsays.dk>

> Ovenstående sætning gør det i sandhed besynderligt at vi ikke rigtig
> kender nogle tal, der er normale i enhver basis.

Hm, og det er ikke engang så let at definere sig frem til et som jeg
lige troede. Det er ikke besværligt at definere et tal som er
"kvasinormalt" i enhver basis - hvor "kvasinormalt" er et begreb jeg
har defineret til lejligheden:

x er kvasinormalt i basis B hvis der for ethvert B-ært ciffer N
gælder at 1/B er fortætningspunkt for andelen af N'er i præfikser
af x's B-ærbrøk.

Man kan nemlig bruge en algoritme a la nedenstående til at udskrive en
følge der konvergerer mod et kvasinormalt-i-enhver-basis tal. Men det
er ikke oplagt (og måske endda forkert) at man kan erstatte
"fortætningspunkt" med "grænseværdi" og således opnå ægte normalitet.

L := 0
H := 1
gentag for B1 := 2 til uendeligt
gentag for B := 2 til B1
udskriv L
// invariant: grænseværdien for uddata er i intervallet [L,H[.
// (specielt: L < H)
Find det mindste K>=0 som opfylder
C := de første K cifre i B-ærbrøken for L, rundet *opad*
// dvs L <= (0.C)_B <= L + B^-K
K er stor nok hvis (0.C)_B + B^-K <= H
gentag K gange:
gentag for I := 0 til B-1
hvis der er færre end K I-cifre i C så
tilføj et ciffer I bag i C
L := (0.C)_B
H := L + B^(-BK)

--
Henning Makholm "But I am a Sunni Muslim," the bemused Arab said.