Rätsel und Spiele: Lange Periode

Wie lang ist die Periode der dezimal geschriebenen Zahl 1:10000019, und wie heißen ihre letzten fünf Ziffern?



Re: Lange Periode
von matroid am So. 06. April 2003 22:12:33


In erster Näherung: Die Periodenlänge ist kleiner als 10000019.

Gruß
Matroid

 

Re: Lange Periode
von Martin_Infinite am So. 06. April 2003 22:39:59


Die Nadel im Heuhaufen.... *lol*
0,0000000999998100003609993141013032075239057045
791612995935307722915326460879724328523775804825
970830655421754698666072534462184521849408486123
876364634907193676332014969171558574038709326452
279740668492729863813258754808365864104858200769
418538104777600922558247139330435272172982871332
544468165510485530077492852763579749198476522894
606500247649529465894014801371877393432952477390
292958443378957579980598036863729958913078065151
676211815197551124652863159559996836006011588577
981701834766513943623507115336480860686364695907
07777655222455077335353062829180624556813342054650
09616481728684715499040551822951536392080855046375
41188671741523691104986900524889002710894849299786
33040597222865276555974543648367068102570605115850
27988446821951038293027243248237828348126138560336
73536020281561465033216436888769911337168459379927
17813836153711307948514897821694138781136315840999
90210018600964658167149482415983409631521700108769
79333739265895394798749882375223487075374556788342
10215000591498876152135310942909208472503902242585
73908709573451810441560161035694032181338855456174
63326819679042609819041343821446739251195422728696
15476050595503868542649768965438965665965234666054
13449714445542553469148408618023625755111065288975
95094569320318291395246349031936839320005291989945
21910408370224096574216508988632921597448964846966
79076309755011465478215591390376358284919258653408
55852373880489627069708567553721647928868935149023
21685588797381284975558546438761766352643929976533
04458721528429095984717629036504830640821782438613
36663460339425355091825325531881489425170092176824
86403275833775915825759931056130993351112632885997
51660471845103494303360823614435132573248110828589
42568009120782670512926025440551662951840391503256
14381332675467916610958439178965559965436065671475
22419707402555935143723226925868840849202386515465
62061532083089042130819951442092260024705953058689
18849054186797045085614337332759067757771260234605
55424944692605084050340304353421728498715852439880
36422730796811486058176489464670017126967458761828
52526130200352619330023272955781384015370370796295
48703857462670820925440241663540839272405382429773
38343057148191418436304971020555060945384203770012
83697560974634148195118429274984377529682693602882
15452390640457783130212052597100065509875531236490
65066776373124891062706980856736372200892818303645
22307407615925529741493491162366791503096144117326
17708026354749925975140647232770257736510300630428
80218527584797588884581119295873337840658102749604
77575092607324046084312439806364367907700975368146
80052107900994988109522591907075376556784542109369
99219701482567183122352067531071690963787168804379
27167938380917076257555110645289773949429496083957
44048086308636013591574176009065582775392726753819
16774358128719555432844677595112569286118356375122
88726651419362303211623897914593962271471684203800
01277997571804613571234214654992155514904521681408
80532326988578721700428769185338547856759072157762
90025048952406990426718189235440452663139940034113
93518352315130601251857621470519206013508574333708
76595334468864509157432600878058331689169790577397
90294398440642962778370721095629918303155224005074
39035865831854919475652996259307107316496098657412
55091615325930880731326610479440089063830778721520
42911118468874909137672638421986998224703373063591
17917675956415682810202660614944831604819950842093
40002253995717408136924539843374297588834581214295
69283818360745114584282289863649259066407773825229
73206350907933274926777639122485667277232173258870
80814546452361740512693025883250821823438535466782
61311303508523333805665769235038453426938488816871
24794462890520508011034779033919835552312450606343
84794668890129108754693366082604443051558202039416
12510936229221164479787488403772032833137617038527
62679750908473273900779588518781814314552802349675
53561648232868357550120654770755935563722428927385
03796842785998706602457455330834871413744313885803
61697312775105727299118131675549816455348734837403
80893276302775024727453017839266105394399750640473
78309981211035699032171838873506140338333357166621
................

 

Re: Lange Periode
von matroid am So. 06. April 2003 22:43:48


@MI: welches Programm benutzt Du?

 

Re: Lange Periode
von Hans-Juergen am So. 06. April 2003 23:34:45


Hallo Martin,

die von Dir angegebenen Dezimalen - ein paar tausend Stück - stellen nur einen winzigen Bruchteil der Periode dar und beantworten auch nicht die gestellten Fragen. Ich habe das numerische Beispiel mit Bedacht gewählt, und es steckt mehr dahinter als die "Suche nach einer Nadel im Heuhaufen". So bin ich gespannt, wie die Antworten weitergehen. Selber benutzte ich bei diesem Rätsel das von manchen wenig geliebte Pascal, aber es muß sich schließlich auch mit C++ lösen lassen.

Schöne Grüße,
Hans-Jürgen

 

Re: Lange Periode
von matroid am So. 06. April 2003 23:42:35


@Hans-Jürgen: Die Frage ist echt interessant. Man suche also nach dem theoretischen Rüstzeug.

Gruß
Matroid

 

Re: Lange Periode
von Martin_Infinite am Mo. 07. April 2003 00:37:06


Ich habe keine Ahnung, wie ich die Aufgabe lösen
soll und wollte nur zeigen, das ein Ansatz ohne
Theorie nach hinten losgehen wird.
@Matroid:Derive

 

Re: Lange Periode
von Hans-Juergen am Mo. 07. April 2003 07:47:52


Hallo Matroid und Martin,

wie man die Aufgabe theoretisch löst, weiß ich nicht. Es geht mit dem Computer. Die einzige, dafür nötige "Theorie" ist das Programm - falls man nicht irgendwo ein solches fertig findet, das lediglich zwei Zahlen dividiert. Im übrigen braucht man nicht alle Dezimalen auszugeben und sich anzusehen; das würde zu lange dauern. Ich möchte nur wissen, wieviele es sind und wie die letzten fünf heißen.

Gruß, Hans-Jürgen

 

Re: Lange Periode
von MutenRoshi am Mo. 07. April 2003 11:40:18


Sie (die Periodenlänge) ist auf jeden größer als 8192000. Da hat mein Programm aufgegeben.

 

Re: Lange Periode
von Hans-Juergen am Mo. 07. April 2003 14:04:28


Da hast Du recht, MutenRoshi: sie ist größer. Ich weiß nicht, womit Du Deinen Rechner hast arbeiten lassen; unter Pascal geht das (wenn man sich das richtige Programm ausgedacht hat) problemlos bis ans Ende der Periode und auf Wunsch weiter darüber hinaus. Von den vier Grundrechenarten ist die Division am leichtesten zu programmieren. Man braucht nur das schriftliche Rechnen nachzuahmen.

 

Re: Lange Periode
von sastra am Mo. 07. April 2003 15:03:05


Wenn ich mich nicht täusche, sind die letzten 5 Ziffern 68421
(68421 * 10000019 = ...99999)

Gruss Sastra

 

Re: Lange Periode
von Eckard am Mo. 07. April 2003 15:22:12


Wow sastra, das sieht gut aus. Mein Programm rechnet noch (die ganze Periode aus). Hoffentlich ist es bald fertig. Ich wette 5 Euro, dass die Periodenlänge 10000018 beträgt. Wer hält dagegen?

Morgen mehr dazu (oder heute noch, wenn er endlich fertig wird, es ist halt bloss ein 500MHz-Rechner, *stöhn*).

Gruß Eckard

 

Re: Lange Periode
von Spooky am Mo. 07. April 2003 16:23:43 <


Also als letzte 5 Ziffern hab ich (auch) 68421, denn:

es muss gelten 10^p = 1 (mod 10000019), wobei p die Periodenlänge ist.

somit kann man rückwärts die Stellen errechnen: 


 ...

 68421130

 60000114     <- 6

 --------

  84210160

  80000152    <- 8

  --------

   42100080

   40000076   <- 4

   --------

    21000040

    20000038  <- 2

    --------

     10000020

     10000019 <- 1

     --------

            1 (Rest)


Die Länge der Periode bekommt man wohl wirklich nur per Brute-Force-Methode ;)

Gruß
Spooky

 

Re: Lange Periode
von Eckard am Mo. 07. April 2003 16:37:11


Mein Blechkumpel rechnet immer noch ...

Aber damit es zwischendurch nicht so langweilig wird, noch Folgendes dazu:

Wie zu vermuten war, hat Hans-Juergen den Nenner 10.000.019 tatsaechlich
mit Bedacht gewaehlt, denn er ist eine Primzahl, was man unter
Linux mit einem schlichten Aufruf von

> factor 10000019

bestaetigt findet. Nun findet gerade ein kleines, selbstgeschriebenes
C-Programm das Reziproke von dieser Zahl heraus. Ok, der Hauptteil der Arbeit steckt in
der GMP library
(GNU Multiprecision Arithmetic Library), aber deren Installation ist
unter Linux kein Problem :-)

Theoretisch ist das wirklich höchst interessant, weil noch nicht voll verstanden,
welche Primzahlen eine maximale Periode in ihrer Dezimalrepräsentation liefern.
Aber folgender Link hilft weiter:

Cyclic number

... und er rechnet immer noch.

 

Re: Lange Periode
von DieElemente am Mo. 07. April 2003 16:56:35


Bestimmung der Periodenlänge !
Z: 1
N: 10000019
************************************************

Treffer !!
Rest 10000018= 10 und Rest 0= 10 sind identisch!
PERIODENLÄNGE: 10000018
Vieviele Ziffen, des Anfangs und des Endes der Periode sollen ausgegeben werden? :1000
Anfang und Ende der Periode: 00000009999981000036099931410130320752390570457916129
95935307722915326460879724328523775804825970830655421
75469866607253446218452184940848612387636463490719367
63320149691715585740387093264522797406684927298638132
58754808365864104858200769418538104777600922558247139
33043527217298287133254446816551048553007749285276357
97491984765228946065002476495294658940148013718773934
32952477390292958443378957579980598036863729958913078
06515167621181519755112465286315955999683600601158857
79817018347665139436235071153364808606863646959070777
76552224550773353530628291806245568133420546500961648
17286847154990405518229515363920808550463754118867174
15236911049869005248890027108948492997863304059722286
52765559745436483670681025706051158502798844682195103
82930272432482378283481261385603367353602028156146503
32164368887699113371684593799271781383615371130794851
48978216941387811363158409999021001860096465816714948
24159834096315217001087697933373926589539479874988237
5223487075374556788342102150005914988761521353
...
04269331888269412288116652578360101115807879965028066
44667375131987249224226473969699457571030615041831420
52030101142807828665125536261481103185903946782501113
24788482901882486423275795775988025622751316772498132
25354871825743531087290934147225120272271482684182900
05248990026918948853997177405362929810433360176615664
43023758254859315767300042129919953152089011030879041
32982147333920065551875451436642270379686278596070667
46573181510955129185254548016358768918339055155795203
98911242068640069583867790651197762724250823923434545
47436359870916245259134007645385473767599841560301035
42803268673789519799912380166477683692400984438129567
55382164773886929614833731815909549771855433474676398
11484358179719458533028787245304233921955548284458259
52930689431690079788848401188037742728288816251249122
62666700933268226790369098298713232444858354769125938
66071654463856518672614522032408138424536993379712578
54610076240855142375229487063974578448300948228198366
4231037961027874047039310625309811911357368421

68421 sind also die letzen 5 Stellen.

Endlich, ich habs geschaft.
Nachdem deine Vorgängerversion dieses Programms mich um meinen 400MHz Prozessor bangen ließ (nach 1,5 Stunden hab ich dann abgebrochen-), kam mir die Idee, den Rechenaufwand zu verringern. Nun dauert es keine 10sec bis es diese Lösung ausspuckt. Ich hoffe, siwe ist richtig. Das Programm (C++ unter Linux)hat nochn paar Macken, aber die beseitige ich noch.
Hat jemand dasselbe Ergebniss ??

PS: man sollte nicht versuchen sich die gesamte Periode ausgeben zu lassen. Das sind je Schriftgröße und bei ausnutzung der gesamten Breite eines 17 Zoll Monitors locker 500 Meter. ;-)

volker

 

Re: Lange Periode
von Spooky am Mo. 07. April 2003 17:16:47


jup kann ich bestätigen, Periodenlänge ist 10000018
die Laufzeit meines Programms liegt unter 1sec ;)
(auf einem Duron 1,2 Ghz)

mal kurz der Code (in C, nur auf die schnelle gebastelt ^^), wen's interesiert: 


#define P_MAX 10000018



main() {

  long int p, r, i;

 

  init();

  r = 1;

 

  for (p = 1; p <= P_MAX; p++) {

    i = r % 10;

    r = (r + N[i]) / 10;

  }

  if (r == 1) {

    printf("korrekte Periodenlaenge: %ld", P_MAX);

  }

  else {

    printf("falsche Periodenlaenge: %ld", P_MAX);

  }

}


in N[x] befinden sich die Vielfachen von 10000019
(also N[x] = x*10000019)

Gruß
Spooky

 

Re: Lange Periode
von viertel am Mo. 07. April 2003 17:20:26


Hi Fans,
ich hab meinen Kasten auch grad mal rechnen lassen. Hier die letzten Stellen des Monstrums (hat die volle Periodenlänge):
8848290188 2486423275 7957759880 2562275131 6772498132 2535487182 5743531087 2909341472 2512027227 1482684182 9000524899 0026918948 8539971774 0536292981 0433360176 6156644302 3758254859 3157673000 4212991995 3152089011 0308790413 2982147333 9200655518 7545143664 2270379686 2785960706 6746573181 5109551291 8525454801 6358768918 3390551557 9520398911 2420686400 6958386779 0651197762 7242508239 2343454547 4363598709 1624525913 4007645385 4737675998 4156030103 5428032686 7378951979 9912380166 4776836924 0098443812 9567553821 6477388692 9614833731 8159095497 7185543347 4676398114 8435817971 9458533028 7872453042 3392195554 8284458259 5293068943 1690079788 8484011880 3774272828 8816251249 1226266670 0933268226 7903690982 9871323244 4858354769 1259386607 1654463856 5186726145 2203240813 8424536993 3797125785 4610076240 8551423752 2948706397 4578448300 9482281983 6642310379 6102787404 7039310625 3098119113 57368421

Sastra täuscht sich also nicht.

Das Programm ist selbst geschrieben. Rechnet ca. 4 Sek. auf meinem 850MHz Rechner.

Gruß
Dietmar das 1/4

 

Re: Lange Periode
von viertel am Mo. 07. April 2003 17:25:02


Au Backe, anscheinend hat sich gerade der halbe Planet auf die Aufgabe gestürzt...

 

Re: Lange Periode
von Rodion am Mo. 07. April 2003 17:25:50


Juhu, ich habe jetzt auch 68421, und die Periodenlänge ist...

10000018!!!

 

Re: Lange Periode
von viertel am Mo. 07. April 2003 17:53:44


Hi Spooky,
ich hab Dein Programm mal bei mir laufen lassen. Meldet "falsche Periodenlänge" für 10000019. Auch für 223. Allerdings für 17 meldet es richtig "korrekte Periodenlaenge".
Dietmar

 

Re: Lange Periode
von Spooky am Mo. 07. April 2003 18:12:21 <


hm, also init() enthält nur folgendes: 


void init() {

  N[0] = 0;

  N[1] = 10000019;

  N[2] = 20000038;

  N[3] = 30000057;

  N[4] = 40000076;

  N[5] = 50000095;

  N[6] = 60000114;

  N[7] = 70000133;

  N[8] = 80000152;

  N[9] = 90000171;

}

ich hoffe mal das hast du nicht vergessen irgendwie auf eine Weise hinzuzufügen :)

also für 10000019 sollte es auch falsche periodenlänge melden, da sie eben 10000018 ist. ,)
dass für 17, "richtige Periodenlänge" ausgegeben wird, kann ich nicht verstehn... hab hier mal von Anfang an durchlaufen lassen (um den "such-speed" zu testen)... er meldet mir für alle Periodenlängen <= 100000 nie "richtig".

meine Überlegung war wie die bei der "theoretischen" Berechnung (ohne PC) der 5 letzten Stellen... (s. mein obiges Posting)
r (im Code) ist jeweils die Zahl, die unter einem horiz. Strich steht, diese muss nach p (periodenlänge) Schritten 1 sein. dabei beginnt man von unten (Startwert Rest r = 1) und arbeitet sich nach oben in der "schriftlichen Division"...

Gruß
Spooky

 

Re: Lange Periode
von Spooky am Mo. 07. April 2003 18:19:26


übrigens, man kann natürlich die Werte (vielfachen) von N[] nicht beliebig ändern, da dann die Zuordnung mit dem Index nicht mehr stimmt!
man könnte sie nur durch Vielfache einer anderen Zahl, die ebenfalls mit 9 endet ersetzen.

hier hat man halt zufällig die praktische Situation, dass wenn die letzte Zahl des Restes r , x ist, man zur ergänzung auf "10", einfach nur x*N = N[x] braucht.
also zB.: r(=2) + N[2] = 2 + 2*10000019 20000040

 

Re: Lange Periode
von Hans-Juergen am Mo. 07. April 2003 19:25:31


Danke für die vielen richtigen Antworten – ich bin sehr froh, daß Euch diese Aufgabe anscheinend auch Spaß gemacht hat! Nun können wir, wenn Ihr wollt, noch ein Stück weitergehen.
Die Dezimalen folgen einander ohne erkennbares System, scheinbar zufällig. Interessant wäre dabei zu erfahren, ob in der Periode alle Ziffern nicht nur ungefähr gleich oft vorkommen, sondern ob sie auch einigermaßen gleichmäßig verteilt sind. Eine Möglichkeit von mehreren, letzteres zu testen, besteht darin, daß man die gesamte Periode in Dreierblöcke aufteilt und die relative Häufigkeit derjenigen Blöcke bestimmt, deren mittlere Ziffer größer ist als die beiden äußeren Ziffern. Was dabei herauskommt, ist zu vergleichen mit dem theoretischen Wahrscheinlichkeitswert, einen solchen Block beim Drehen eines idealen Glücksrades mit den Ziffern 0,1, 2,...., 9 zu erhalten.
Wer macht mit?
(Anm.: in einem alten Computerbuch aus der Basic-Zeit fand ich die Dreierblockmethode als Übungsaufgabe. Dort wurde die genannte theoretische Wahrscheinlichkeit mit 0,280 angegeben, was meiner Meinung nach nicht ganz richtig ist.)
Hans-Jürgen

 

Re: Lange Periode
von viertel am Mo. 07. April 2003 19:43:16


Das kommt bei mir raus: 0.285000
Dietmar

 

Re: Lange Periode
von Hans-Juergen am Mo. 07. April 2003 20:04:01


Ja, genau, Dietmar, bei mir auch, für den theoretischen Wert.

Gruß,
Hans-Jürgen

 

Re: Lange Periode
von viertel am Mo. 07. April 2003 20:46:12


Sorry, hätt ich dazu schreiben sollen: gezählt nach der Dreierblockmethode.
Dietmar

 

Re: Lange Periode
von Anonymous am Mo. 07. April 2003 21:55:26


Schaut euch mal folgende Page an!!

http://www.mathematik-online.de/F103.htm#dezi

Gruß N.

 

Re: Lange Periode
von Eckard am Di. 08. April 2003 08:59:57


Mittlerweile ist mein Programm auch fertig geworden...

Hier Links von zwei Files, die alle Dezimalstellen der Periode enthalten:

bzip2 file (4.703.050 Bytes)
gzip file (5.168.091 Bytes)

Wer will, kann damit etwas Ziffernstatistik betreiben. Die Ziffern stehen in dem File in einer Zeile ohne CR/LF hintereinander weg. Viel Spaß damit!

Gruß Eckard

 

Re: Lange Periode
von Hans-Juergen am Di. 08. April 2003 23:40:26


Also dann (weil sich nach der stürmischen Anfangsbeteiligung keiner weiter mehr meldet) ein bißchen Ziffernstatistik:

Insgesamt gibt es unter den 3333339 gebildeten Dreierblöcken 950283, deren mittlere Zahl größer als die beiden anderen ist. Das sind (gerundet) 28,51 Prozent, in sehr guter Übereinstimmung mit dem theoretischen Wert 0,285. Auch die relativen Häufigkeiten anderer Dreierblöcke sowie von Vierer-, Fünfer- und Sechserblöcken mit gleichen oder verschiedenen vorgegebenen Ziffern liefern gute Ergebnisse. So kommt etwa die von uns betrachtete fünfstellige Zahl 68421 vom Ende der Periode in deren Innern noch 100 weitere Male vor (wer es genauer wissen möchte: an 24783., 80118., 413545., .... , 10000013. Stelle) – theoretisch zu erwarten wäre 100-mal.

Das gewählte Beispiel – sicherlich kein Einzelfall – zeigt, daß man ohne die Verwendung komplizierter Algorithmen, allein mit einer einfachen Division, über zehn Millionen Pseudozufallsziffern erhalten kann!

MfG Hans-Jürgen

 

Re: Lange Periode
von Anonymous am Mi. 09. April 2003 08:44:00


Wie kaputt seid ihr denn im Kopp? Habt ihr nix besseres zu tun als so einen scheiss zu machen?!
An eurer stelle würde ich die weltherrschaft an mich reißen , bundeskanzler werden oder ne katze grün anmalen !!! macht was aus eurem wissen , ihr könnt reich werden damit !

 

Re: Lange Periode
von Hans-Juergen am Mi. 09. April 2003 09:43:43


Hallo Anonymer!

Dich als Bundeskanzler oder Weltbeherrscher - das könnte Dir so passen!

Warum beschimpfst Du uns? Bist Du neidisch?

"Die Mathematik ist eine Art Spielzeug, welches die Natur uns zuwarf zum Troste und zur Unterhaltung in der Finsternis."

Jean-Baptist le Rond d'Alembert
(Guck 'mal nach, wer das war; kannst was lernen.)

Im Internet fand ich an einer Stelle den Hinweis:
"Dem Enzyklopädisten und Mathematiker d'Alembert verdanken wir auch die Formulierung der Menschenrechte."

Hans-Jürgen

 

Re: Lange Periode
von Eckard am Mi. 09. April 2003 12:37:21


@Hans-Jürgen: Es gibt einen Haufen Bekloppte auf dieser Welt, man sollte sich nicht allzu sehr darum kümmern, solange sie nur so'n Blech schreiben.

@Anonymous: Deine Meinung geht in die große runde Ablage!

Gruß Eckard

 

Re: Lange Periode
von Anonymous am Mi. 09. April 2003 16:25:20


Hallo! Hat irgendwer auch das Programm mit Delphi geschrieben??? Wenn ja, würde ich das mal gerne sehen!

 

Re: Lange Periode
von Anonymous am Di. 17. Juni 2003 10:19:10


Wie viele nutzlose Dinge tun wir sonst! Die Mathematik schult wenigstens den Geist!

Zurück zur Themenübersicht