Bemurzen

Neue Frage »

Sweetgirl Auf diesen Beitrag antworten »
Bemurzen
Bemurzen

Definiert ist Bemurzen :
Eine gerade ganze Zahl wird bemurzt, wenn man sie durch 2 teilt.
Eine u ngerade ganze Zahl wird bemurzt wenn man sie mit 3 vervielfacht und 1 dazu addiert,...

Frage : Kann man jede positive ganze Zahl durch bermurzen auf 1 zurückführen ?

Ich brauche den Beweis dafür, is voll wichtig !!!
m00xi Auf diesen Beitrag antworten »

Ahhha, da schlägt doch mein Gedächtnis Alarm:
Robert Sedgewick, Algorithmen in C++, Seite 208.
Dort geht es um rekursionen und dieses Programm wird als Beispiel für eine zweifelhafte Rekursion verwendet, da das Argument, mit dem sich die Funktion aufruft, nicht immer kleiner als das eigene ist. Es wird zudem hier angegeben, dass die Funktion für 16 Bit Werte (Integer) immer terminiert, jedoch seie es nicht bekannt, wie dies bei z.B. 64 Bit wäre. Da ich dieses Buch in keinster Weise anzweifle, denke ich, dass dies deine Frage beantwortet.

Ach ja, und zum Beweis steht dort, dass es nicht möglich wäre, dies induktiv zu beweissen, und das man nicht wisse, ob das Programm für irgendeine beliebig große Zahl terminiere oder nicht.
Sweetgirl Auf diesen Beitrag antworten »

ja aber mein mathelehrer hat gesagt das es den beweis dafür gibt, wir sollen das für die klausur wissen aber ich komm nicht alleine drauf, ich weiß nich wie cih das machen soll !
m00xi Auf diesen Beitrag antworten »

Sollt ihr den raussuchen oder selber rauskriegen? Ich kann es mir schwer vorstellen, sonst stünde der ja in meinem Buch auch drinne. Komische Sache..
juergen Auf diesen Beitrag antworten »

Ich weiß zwar nicht wie man das mathematisch löst, aber google hilft auch manchmal Augenzwinkern

Zitat:
Auszug aus dem Grips-Heft, Ausgabe 3/96:
Kann man jede (positive ganze) Zahl nur durch bemurzen dazu bringen, eins zu werden?

Dabei ist bemurzen folgendermaßen definiert:
Def. 1.1: Eine gerade Zahl bemurzt man, indem man sie durch zwei teilt, eine ungerade Zahl wird mit drei multipliziert, und dann wird eins addiert.

Beispiel 1.2: Wir bemurzen 17 und erhalten 52, dann 26, dann 13, dann 40, dann 20, dann 10, dann 5, dann 16, dann 8, dann 4, dann 2, dann 1. Juhuu, es hat geklappt.
Eins weiter zu bemurzen ist übrigens recht langweilig, man erhält 4, dann 2 und dann wieder 1.

Bisher wurde noch keine Zahl gefunden, die durch bemurzen nicht irgendwann eins wird (sondern z.B. immer größer, oder vielleicht irgendwann im Kreis rum). Es kann aber passieren, daß Zahlen sehr groß werden, bevor sie sich irgendwann mal dazu bringen, eins zu werden mit der eins.
Bei negativen Zahlen gibt es allerdings noch ein paar Beispiele, die nie eins werden: -3, -8, -4, -2, -1, -2, -1, -2, ...
Oder: -5, -14, -7, -20, -10, -5, ...
Aber auch da sind, so weit ich weiß, nur drei verschiedene "Schleifen" (d.h. vier insgesamt) bekannt, aus denen eine Zahl nicht mehr raus kommt.

Und zum Abschluß bemurzen wir noch die 42: 21, 64, 32, 16, 8, 4, 2, 1. Och, wie langweilig, das ging ja ganz schnell. Dann probieren wir wenigstens noch die 27: 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, etc. Aber leider, leider, irgendwann: ...8, 4, 2, 1. Schade eigentlich.

QUELLE



PHP-Programm zum Zahlen bemurzen :P

Einfach hinter dem "zahl=" eine Zahl eingeben.

Wenn die Zahl zu keiner Lösung kommt, dann hoffe ich,
daß zumindest irgendwann ein Timeout zuschlägt Gott :P
Sweetgirl Auf diesen Beitrag antworten »

ja diese seite hatte ich ja auch schon, aber wie man dsa rechnet weiß ich selber, ich soll ja beweisen, das das mit allen zahlen funktioniert und ich denke man könnte das eventuell beweiesn mit den zweierpotenzen,.. oder und wenn ja wie ?
 
 
Thomas Auf diesen Beitrag antworten »

Hi Jürgen,

würdest du uns dieses Tool für unsere Mathe-Tools-Section zur Verfügung stellen?

Gruß,
Thomas
juergen Auf diesen Beitrag antworten »

php:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
<?php
$zahl=0;

// Zahl auslesen
// wurde entweder per URL oder per Formular übergeben
if (isset($_POST['zahl'])) $zahlintval($_POST['zahl']);
if (isset($_GET['zahl']))  $zahl=intval($_GET['zahl']);

// nur positive Zahlen; und keine Null
if ($zahl>0) {
    echo "<b>".$zahl.": </b>";
    while ($zahl <> 1) {
        If (intval($zahl/2)==$zahl/2$zahl=$zahl/2;
        else $zahl=$zahl*3+1;
        echo $zahl.", ";
    }
}
?>
m00xi Auf diesen Beitrag antworten »

Da fehlt doch noch die Schleife bzw. die Rekursion:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
<?
function bemurzen($x)
{
   if ($x==1) return 1;
   else if ($x%2==0) return bemurzen($x/2);
   else return bemurzen($x*3+1);
}
?>
juergen Auf diesen Beitrag antworten »

Zitat:
Original von m00xi
Da fehlt doch noch die Schleife bzw. die Rekursion:

Unsinn,
da fehlt nix. Wenn etwas fehlen würde, dann würde es ja nicht funktionieren. :P
m00xi Auf diesen Beitrag antworten »

Ops, ich habe das <> übersehen :-) Tut mir leid. Nichts für ungut
Steve_FL Auf diesen Beitrag antworten »

wärs vielleicht möglich, das über "Zahlentheorie" zu beweisen?
Hab mir mal folgendes überlegt:
Jede Zahl ist ja durch Primzahlpotenzen zusammengesetzt.
Jetzt ist die Frage, ob man durch die Multiplikation und Addition von 3 und 1 alle anderen Primzahlpotenzen sozusagen killen kann.

Eine ungerade Zahl, die bemurzt wird ist sicher nicht mehr durch 3 teilbar. Die Frage ist jetzt, ob man durch diese Operation auch alle 5er-Potenzen rausbringt und dann die 7 und so weiter, bis nur noch 2er-Potenzen da sind (welche aber immer wieder nach und nach weggekürzt werden und zwar solange, bis bis keine mehr da ist...)

aber ich kenn mich mit dieser Zahlentheorie noch zu wenig aus. Da sollte man mal nach Irrlicht, sir Jective oder Leopold rufen Ansage

mfg
juergen Auf diesen Beitrag antworten »

Die Zahl, die bei einer ungeraden Zahl herauskommt ist eine Zahl, die sich als Summe zweier gerader Zahlen darstellen läßt.
Sweetgirl Auf diesen Beitrag antworten »

aber das bringt mich leider noch nicht viel weiter,....
das is alles noch nicht das wahre,...
ich mein das kann ich ihm so nich beweisen, leider !
juergen Auf diesen Beitrag antworten »

Zitat:
Original von juergen
Die Zahl, die bei einer ungeraden Zahl herauskommt ist eine Zahl, die sich als Summe zweier gerader Zahlen darstellen läßt.

Damit wollte ich sagen:

Das Ergebnis nach dem bemurzen einer ungeraden Zahl ist immer eine gerade Zahl. - Daher logisherweise durch 2 teilbar.
Ebenso ist die Zahl durch zwei benachbarte Zahlen teilbar: wenn die gerade Zahl y ist, so ist sie durch x*(x+1) darstellbar.

Wenn ich nun die Zahl durch 2 teile, so kann es zwar sein, daß ich eine Zahl erhalte, die Prim ist, doch im nächsten Schritt bekomme ich wieder eine Zahl für die obriges gilt.

So eleminiere ich nach und nach alle Primfaktoren und bekomme nach endlich vielen Schritten immer 1.

(Mag sein, daß ich hier jetzt einen riesigen Bock geschossen habe :P -- naja, sollen die Mathematiker mal grübel und halte besser meinen Mund.)
Sweetgirl Auf diesen Beitrag antworten »

ich glaube das das logisch klingt, also ich find es recht gut ! vielen dank !
Steve_FL Auf diesen Beitrag antworten »

@juergen:
Zitat:
Ebenso ist die Zahl durch zwei benachbarte Zahlen teilbar: wenn die gerade Zahl y ist, so ist sie durch x*(x+1) darstellbar.

Und wieso das?
Das hab ich noch nicht eingesehen...unglücklich

mfg
juergen Auf diesen Beitrag antworten »

Lies mal bei den Pythagoreer nach. :P
Steve_FL Auf diesen Beitrag antworten »

??? Nee...erklärs mal, gibt sicherlich noch andere, die sich auch dafür interessieren smile

mfg
Irrlicht Auf diesen Beitrag antworten »

Ihr versucht gerade das "Collatz Problem" zu lösen. Das ist meines Wissens bisher ungelöst:
http://mathworld.wolfram.com/UnsolvedProblems.html

Wer Englisch kann findet auf
http://mathworld.wolfram.com/CollatzProblem.html
einige Informationen.
juergen Auf diesen Beitrag antworten »

Zitat:
Original von Steve_FL
@juergen:
Zitat:
Ebenso ist die Zahl durch zwei benachbarte Zahlen teilbar: wenn die gerade Zahl y ist, so ist sie durch x*(x+1) darstellbar.

Und wieso das?
Das hab ich noch nicht eingesehen...unglücklich

Ne ich sehe es auch nicht ein, das stimmt wohl nicht - sorry. Da hatte ich was falsches im Kopf traurig
Steve_FL Auf diesen Beitrag antworten »

ok, dann bin ich "beruhigt" Augenzwinkern

hm...ich hoff nur, dass das Sweetgirl das noch sieht und in der Schule keinen Müll erzählt und dann sagt, sie hätte das vom Matheboard und wir dann in einem schlechten Licht dastehen...

nur weil der juergen nicht richtig nachdenkt X( *g*

mfg
juergen Auf diesen Beitrag antworten »

Sorry Gott

Ich glaube es stimmt für:
2+4+6+8+10+...
Da läßt sich das Ergebnis als x(x+1) darstellen.

Ich glaub ich brauche mal :rolleyes:
Steve_FL Auf diesen Beitrag antworten »

wie du willst Augenzwinkern
:rolleyes: :rolleyes: :rolleyes:

@Sweetgirl:
hm, so wie es aussieht, hatte dein Lehrer Unrecht...anscheinend ist die Aufgabe echt noch nicht gelöst...

mfg
SirJective Auf diesen Beitrag antworten »

Zitat:
Original von juergen
Ich glaube es stimmt für:
2+4+6+8+10+...
Da läßt sich das Ergebnis als x(x+1) darstellen.


Genau. Wenn x eine natürliche Zahl ist, dann sind genau die Zahlen der Form 2+4+...+2n als x(x+1) darstellbar.
Sweetgirl Auf diesen Beitrag antworten »

ja und was machen wir dann mit den ungeraden zahlen ?
ich mein wir müssen ja das +1 berücksichtigen und daher kommen wir ja dann inmmer wieder auf ne gerade zahl, ich denke es muß was mit dem vielfachen von 2 zu tun haben,...
Mathespezialschüler Auf diesen Beitrag antworten »

Zitat:
Original von SirJective
Zitat:
Original von juergen
Ich glaube es stimmt für:
2+4+6+8+10+...
Da läßt sich das Ergebnis als x(x+1) darstellen.


Genau. Wenn x eine natürliche Zahl ist, dann sind genau die Zahlen der Form 2+4+...+2n als x(x+1) darstellbar.


Erst sagst du eine natürliche Zahl x, in der Folge benutzt du dann n un in der Formel wieder x Big Laugh
SirJective Auf diesen Beitrag antworten »

Ja, das habe ich so beabsichtigt. Ich sprach nämlich von einer Zahl der Form 2+4+...+2n, die auch in der Form x(x+1) darstellbar ist. Über den Zusammenhang zwischen n und x hab ich mich dabei nicht geäußert!

Hier ist offenbar x=n zu wählen, was aber mich nicht dazu zwingt, jedes Vorkommen von x durch n zu ersetzen.
juergen Auf diesen Beitrag antworten »

Zitat:
Original von Sweetgirl
ja und was machen wir dann mit den ungeraden zahlen ?
ich mein wir müssen ja das +1 berücksichtigen und daher kommen wir ja dann inmmer wieder auf ne gerade zahl, ich denke es muß was mit dem vielfachen von 2 zu tun haben,...

Denke ich auch, aber beweisen kann ich sowas nicht.

Also aus einer ungeraden Zahl x macht man eine neue Zahl y:

y= 3*x+1
oder anders gesagt:
y = (2*x) + (x+1)

(Ja die Kammern sind überflüssig - ich weiß)

Damit ist der erste Summand gerade und der zweite auch.
Und was sagt uns das? Keine Ahnung.

Mysterium mathematicae!
Guevara Auf diesen Beitrag antworten »

Man muss beweisen können das jede zahl n durch bemurzen auf eine zahl kleiner als n kommt.
Thomas Auf diesen Beitrag antworten »

Zitat:
Original von juergen
php:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
<?php
$zahl=0;

// Zahl auslesen
// wurde entweder per URL oder per Formular übergeben
if (isset($_POST['zahl'])) $zahlintval($_POST['zahl']);
if (isset($_GET['zahl']))  $zahl=intval($_GET['zahl']);

// nur positive Zahlen; und keine Null
if ($zahl>0) {
    echo "<b>".$zahl.": </b>";
    while ($zahl <> 1) {
        If (intval($zahl/2)==$zahl/2$zahl=$zahl/2;
        else $zahl=$zahl*3+1;
        echo $zahl.", ";
    }
}
?>


Vielen Dank, ich werde das demnächst einbauen. :]

Gruß,
Thomas
SirJective Auf diesen Beitrag antworten »

Zitat:
Original von Guevara
Man muss beweisen können das jede zahl n durch bemurzen auf eine zahl kleiner als n kommt.


Es würde ausreichen, das zu beweisen. Allerdings ist nicht klar, dass man das beweisen kann. Es könnte sein, dass es unbeweisbar ist - das kann durchaus vorkommen, man weiss es in diesem Fall noch nicht.
Neue Frage »
Antworten »



Verwandte Themen