mikrocontroller.net

Forum: Offtopic Ist folgendes "Programm" eine Endlosschleife?


Autor: Frank (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo

folgender Sachverhalt ist gegeben, vll. fällt euch was dazu ein, das mir 
helfen könnte:

gegeben ist eine beliebige natürliche Zahl a (größer 1) und eine 
natürliche Zahl b (größer 1):
Man erhält die Zahl c, indem man die Reihenfolge der Ziffern von a 
umdreht.
(also wird aus a=123456  c=654321)


1. Berechne c/b

2.
Wenn c/b eine natürliche Zahl dann:
Ende;

wenn c/b keine natürliche Zahl, dann:
multipliziere a mit 2 und bestimme c neu
gehe zu 1.



Beweise, dass es sich nicht um eine Endlosschleife handelt (d.h. 
irgendwann ist der Quotient c/b eine natürliche Zahl).

Frank

Autor: Sumynona (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ist keine endlosschleife.

Beweis:

Sei A = 309
Sei B = 3

Es folgt: C = 903

und 903 geteilt durch 3 ist eine natürliche Zahl, nämlich 301.

Das gilt selbstverständlich nicht für jede beliebige Zahlenkombination 
A, B:

Sei C eine Primzahl, zB. 17, also abgeleitet von A = 71

Dann gehts schonmal nicht

Autor: Frank (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A und B sind natürlich zwei belibige natürliche Zahlen, die aber 
bestimmt sind.

Das ganze muss also für alle möglichen A und B stimmen.

Du hast aber recht, es stimmt nicht immer.

Was ist mit folgender Anpassung?
Man multipliziert A nicht immer mit 2, sondern mit irgendeiner Zahl, so 
wie man möchte.

Also:

gegeben ist eine beliebige natürliche Zahl a (größer 1) und eine
natürliche Zahl b (größer 1):
Man erhält die Zahl c, indem man die Reihenfolge der Ziffern von a
umdreht.
(also wird aus a=123456  c=654321)


1. Berechne c/b

2.
Wenn c/b eine natürliche Zahl dann:
Ende;

wenn c/b keine natürliche Zahl, dann:
multipliziere a mit irgendeiner beliebigen natürlichen Zahl und bestimme 
c neu
gehe zu 1.


Beweise, dass es sich nicht um eine Endlosschleife handelt (d.h.
irgendwann ist der Quotient c/b eine natürliche Zahl).


Frank

Autor: Sumynona (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> A und B sind natürlich zwei belibige
> natürliche Zahlen, die aber bestimmt sind.

Entweder sie sind beliebig oder sie sind bestimmt.

> Das ganze muss also für alle möglichen A und B stimmen.
Tut es nicht, wie ich oben demonstriert habe. Das funktioniert übrigens 
nicht nur wenn A -> C eine Primzahl ist.

> Was ist mit folgender Anpassung?
> Man multipliziert A nicht immer mit 2, sondern mit
> irgendeiner Zahl, so wie man möchte.

nicht immer? wurde sie denn vorher mit 2 multipliziert? Das stand in 
deinem originalbeitrag nicht


Generell kann man die Umwandlung A -> C ignorieren und gleich fragen 
"für welche natürlichen Zahlen (größer 1) gilt C/B = natürliche Zahl?"

Nachzulesen in jedem Grundkurs Mathe - Buch

Achja mir fällt noch ein:
C ist nicht in jedem Falle > 1
für die Zahl A = 10 ergibt sich genau C = 1
Das tut aber nichts zur Sache, denn 1 / (zahl größer 1) ist nie 
natürlich.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Witzige Fragestellung, wie kommt man darauf?

Der Beweis von Sumynona ist keiner ;)

Was heißt bei der modifizierten Variante "beliebige natürliche zahl", 
mit der man a multiplizierten soll? Zufallszahl? Dann wirds schwierig...

Ansonsten fällt mir gerade keine mathematische Beschreibung zur 
Umkehrung der Ziffern ein, deswegen finde ich auch keinen Beweis.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Teilbarkeit:
c/b nat. <=> b | c <=> Ex. q nat.: qb=c

Parität:
c gerade <=> Ex. d nat.: 2d = c
c ungerade <=> Ex. d nat.: 2d+1 = c

c ungerade => 2c gerade und von der Form 4d+2 = c

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn man geschickt multiplizieren darf statt mit immer nur mit Zwei und 
die Ziffernumkehr ersteinmal außer Acht lässt, so multipliziert man 
einfach mit b und das Ergebnis wird dann von b geteilt. Nur wie bekommt 
man diesen "geschickten" Faktor durch die Umkehrung der Reihenfolge der 
Ziffern geschleust? Die Ziffernumkehrung ist ja offensichtlich nicht mit 
der Multiplikation verträglich...

Autor: Sumynona (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das geht jetzt schon richtig tief in die Zahlentheorie. Bedenke bitte 
auch dass das Dezimalsystem ziemlich unkompatibel zur Natur ist...
Prinzipiell würd ich sagen, man kann nicht voraussagen, ob eine Zahl C 
durch B teilbar ist, wenn sie aus (A*X) berechnet wird, die Aussage 
stellt aber eher ne These als einen Beweis dar ;-)

Autor: Bobby (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ist zwar schon eine Weile her, aber ich versuche es mal:

Im Grunde sucht man nur ein gemeinsames Vielfaches von a und b.
Und das existiert zu allen natürlichen Zahlen.
Fertig.

(Das Vertauschen der Ziffernreihenfolge nennt sich Permutation.
Die tut aber nichts zur Sache, da es eine bijektive Abbildung ist.
In der Aufgabenstellung trägt sie nur zur Verwirrung des Kandidaten bei, 
mehr nicht.)

Autor: Bobby (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nachtrag:
Es muss ja nicht unbedingt das kleinste gemeinsame Vielfache sein.
Der Rest tut es auch, denn es gibt unendlich viele davon...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bobby wrote:

> (Das Vertauschen der Ziffernreihenfolge nennt sich Permutation.
> Die tut aber nichts zur Sache, da es eine bijektive Abbildung ist.
> In der Aufgabenstellung trägt sie nur zur Verwirrung des Kandidaten bei,
> mehr nicht.)

Da bin ich nicht ganz einverstanden.
Die Fragestellung würde ich nämlich so aufffassen.

Sei X eine Primzahl und n beliebig aus N
Ist dann Permutation( n * Permutation(X) ) ebenfalls eine Primzahl?

Autor: Bobby (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dass es zu zwei natürlichen Zahlen unendlich viele Vielfache gibt 
streitest Du aber nicht ab. Und irgendwann findet der Algorithmus die 
passende Zahl. Das hat mit Prim garnichts zu tun.

Autor: Bobby (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nochmal: Grundgedanke ist die Abzähhlbarkeit.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Zur ursprünglichen Fragestellung (mit konstantem Faktor 2):

Es gibt Zahlenkombinationen, für die die Schleife abbricht, bspw. a=2
und b=2, und solche, für die sie nicht abbricht, bspw. a=2, b=3.
Ein Beweis, dass die Schleife immer abbricht oder immer endlos ist, kann
also nicht erbracht werden.

Die Schleife ist mindestens dann endlos, wenn

  10|b                     (1)

oder

  3|b und nicht 3|a        (2)

oder

  11|b und nicht 11|a      (3)


Beweis:

zu (1): das umgedrehte a kann nie mit einer 0 enden.

zu (2): Der Dreierrest r3 von a ändert sich durch Umdrehen nicht.

zu (3): Der Elferrest r11 von a bleibt beim Umdrehen entweder gleich
        (ungerade Stellenzahl) oder wird zu 11-r11 (gerade Stellenzahl).
        c ist also nur dann durch 11 teilbar, wenn auch a es ist.

Vermutung: Alle anderen Fälle führen zum Schleifenabbruch. Der Beweis
ist aber sicher nicht ganz leicht ;-)

Vage Begründung: Nur bei der Division durch 3, 10 und 11 stehen die
Reste von a und c in einer einfachen Beziehung zueinander. Für alle
anderen Zahlen ist die Beziehung so kompliziert, der Divisionsrest
irgendwann einmal jeden Wert in [0,b-1] annehmen wird (also auch 0),
wenn man die Schleife nur lange genug laufen lässt. Ein Beweis ist das
natürlich nicht.

Für manche Zahlenkombinationen läuft die Schleife erstaunlioch oft
durch, bis sie abbricht. So wird bspw. für a=2 und b=865 die Schleife
11709mal durchlaufen, bis das dabei enstehende 3525stellige c endlich
durch b teilbar ist.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bobby wrote:
> Dass es zu zwei natürlichen Zahlen unendlich viele Vielfache gibt
> streitest Du aber nicht ab. Und irgendwann findet der Algorithmus die
> passende Zahl. Das hat mit Prim garnichts zu tun.

Kannst du das beweisen?

Genau darum geht es ja: Kannst du einen Beweis anführen, dass sich immer 
irgendwann eine passende Zahl ergibt?

Und ja, ich denke schon dass das mit Primzahlen zu tun hat. Letztenendes 
geht es um Teilbarkeit bzw. Nicht-Teilbarkeit.
Die 'Formel' die ich angegeben habe, ist nichts anderes als der 
Algorithmus in einer mathematischen Form (wobei der Begriff Permutation 
noch mathematisch eingefangen werden müsste). Kannst du die 
mathematische Form beweisen, hast du auch bewiesen dass der Algorithmus 
anhält.

Beweisen! Nicht vermuten, nicht glauben, nicht denken - sondern 
bewiesen.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Beweisen! Nicht vermuten, nicht glauben, nicht denken - sondern
> bewiesen.

Wie recht du hast...


Bin mir nicht sicher ob man hier von einer Permutation sprechen kann.

Mindestens kann man aber nicht behaupten, dass die Permutation hier nur 
zum Verwirren da ist und keine Rolle spielt, weil sie bijektiv sei.
Was passiert denn mit dem Fall, dass hinten eine Null steht? Schon ist's 
dahin mit der schönen Bijektivität.

Die Schwierigkeit ist hier wirklich, die Reihenfolgenvertauschung 
mathematisch zu fassen. Ich versuch mal:

Bestehe a aus den n Ziffern a_n,a_{n-1},...,a_1,a_0.
Dann ist a = a_n * 10^n + a_{n-1} * 10^{n-1} + ... + a_1 * 10^1 + a_0 * 
10^0
und c = a_0 * 10^n + a_1 * 10^{n-1} + ... + a_{n-1} * 10^1 + a_{n} * 
10^0

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.