Aus zwei Zahlen mache Eins und wieder Zwei.

Neue Frage »

Dukkha Auf diesen Beitrag antworten »
Aus zwei Zahlen mache Eins und wieder Zwei.
Richard möchte gerne die Information von natürlichen Zahlen und speichern, hat aber nur Speicherplatz für eine Zahl (Diese kann aber beliebig gross sein). Wie kann Richard das Problem mathematisch lösen, ohne das Einführen von neuen Symbolen wie einem Trennungssymbol ?

Beispielsweise die Konkatenation funktioniert natürlich nicht, weil ich bei nicht weiss, ob es sich um und die Zahl handelt, oder um und die Zahl handelt.

Edit X: Nicht erlaubt sind jegliche Art von Trennungssymbolen. Das heisst in Binärzahlen und dazwischen eine ist nicht erlaubt. ( ist nicht erlaubt)

Edit X2: Die Reihenfolge spielt eine Rolle, d.h. das Eingabe-Tupel ist nicht dasselbe wie !
Dopap Auf diesen Beitrag antworten »

wenn gilt, dann lässt sich doch x und y rekonstruieren. Oder nicht ? verwirrt
Dukkha Auf diesen Beitrag antworten »

Was sind ?

PS: vielleicht hast du eine Lösung gefunden, ich gehe aber davon aus, dass es nicht stimmt. Tipp: Denke mengentheoretisch.

Edit:

ist offensichtlich nicht eindeutig?

Edit 2: Die Operation ist nicht kompliziert. Denke mengentheoretisch.
Dopap Auf diesen Beitrag antworten »



ist doch eine übliche Darstellung der Primzahlfaktorenzerlegung.

die sind der Reihe nach die Primzahlen 2,3,5,7...

k ist "letzte" Index



und

das ergibt sich doch aus dem Zusammenhang.
Dukkha Auf diesen Beitrag antworten »

Und weshalb ist das eindeutig? (Vielleicht stimmt deine Antwort, bitte ausführlicher)

Also und stimmen nicht.

Edit : Mein Edit beachten. Die Operation ist nicht kompliziert, sie ist sehr simple. Denke mengentheoretisch.
Dukkha Auf diesen Beitrag antworten »

Es ist ein klassisches Problem der old-school theoretischen Informatik, bitte nicht googlen. Ich gebe dafür nochmals einen Tipp. (und noch mehr, so viel ihr wollt, aber bitte nicht googlen!) Die Antwort ist nicht kompliziert, du kennst sie bestimmt mit ein bisschen Nachdenken! Hier der Tipp:



Was brauchen wir, Surjektion, Injektion oder Bijektion?
 
 
Dukkha Auf diesen Beitrag antworten »

Noch ein Tipp, dann sollte es klar sein.

@IfindU Es ist Analysis 1! Wink

@Clearly_wrong btw. die Aufgabe ist nur Analysis 1.
Clearly_wrong Auf diesen Beitrag antworten »

Vielleicht haben wir genau aus diesem Grund nicht geantwortet, Dukkha Augenzwinkern

Aber gut, das lasse ich nicht auf mir sitzen.

Möglichkeit 1: Seien beliebige Primzahlen. Wenn ich die Zahl speichere, weiß ich aufgrund der Eindeutigkeit der Primfaktorzerlegung genau, welche zwei Zahlen ich gespeichert habe.

Möglichkeit 2: Gerader und ungerader Anteil einer Zahl: Wir bilden ab. Dabei handelt es sich sogar um eine Bijektion, wenn wir die natürlichen Zahlen bei beginnen lassen, auch wenn eine Injektion wie in Möglichkeit 1 natürlich ausreicht.
Dopap Auf diesen Beitrag antworten »



immer diese Minimalgegenbeispiele unglücklich
Dukkha Auf diesen Beitrag antworten »

Zitat:
Original von Clearly_wrong
Vielleicht haben wir genau aus diesem Grund nicht geantwortet, Dukkha Augenzwinkern

Aber gut, das lasse ich nicht auf mir sitzen.

Möglichkeit 1: Seien beliebige Primzahlen. Wenn ich die Zahl speichere, weiß ich aufgrund der Eindeutigkeit der Primfaktorzerlegung genau, welche zwei Zahlen ich gespeichert habe.


Ich kenne keinen Beweis für Deine Aussage, aber ich denke, sie wäre richtig, wenn wir die nicht zu den natürlichen Zahlen hinzufügen würden. Ich habe kennengelernt. Aber natürlich, sehr gute Antwort!!

(PS: Das ist kein Analysis 1)

Edit: Deine zweite Antwort scheint auch korrekt zu sein. Hier funktioniert sogar der -Fall. Well done, ich ziehe meinen Hut!
Auch wenn es nicht meine schöne Analysis 1 Lösung ist Augenzwinkern Aber Lösung ist Lösung!

Findest du noch meine analytische Lösung raus?
Clearly_wrong Auf diesen Beitrag antworten »

Irgendwie haben wir ein unterschiedliches Verständnis dafür, was man in Analysis 1 macht, aber ist ja nicht so wichtig, welcher Vorlesung nun was zugeordnet wird smile

Schönes Wochenende dir.
Dukkha Auf diesen Beitrag antworten »

Zitat:
Original von Clearly_wrong
Schönes Wochenende dir.


Danke, dass wünsch ich Dir auch!

Ich möchte Dir aber noch meine Lösung nennen: "Das Cantorsche Diagonalverfahren". In diesem Fall nennt man das die Cantorsche Paarungsfunktion https://de.wikipedia.org/wiki/Cantorsche_Paarungsfunktion

Aber sehr schön, einen algebraischen Ansatz zu sehen Freude
Clearly_wrong Auf diesen Beitrag antworten »

Schau auf der von dir verlinkten Seite mal bei Alternativen.

Da stehen witzigerweise auch beide meiner Möglichkeiten. Das ist also weniger ein algebraischer Ansatz als mehr eine andere Formulierung deiner Version Augenzwinkern
Dopap Auf diesen Beitrag antworten »

verwirrt
1.) zwei Primzahlen kann ich als Produkt speichern. Die Rückzerlegung in 2 Faktoren ist zwar eindeutig aber kommutativ. Das ist aber nicht gestattet !
2.) und was ist mit den anderen Zahlenpaaren ??

Kann jemand bei mir für etwas Erleuchtung sorgen?

btw: in der Rätselecke sollte die Lösung des TS schon von Diesem irgendwann dargelegt werden.
Dukkha Auf diesen Beitrag antworten »

Ach dann kanntest du die Lösung schon von Anfang an. geschockt Ich finde schon noch ein Rätsel, dass du nicht kennst Augenzwinkern Hast du Informatik studiert oder bist du Algebraiker?
Clearly_wrong Auf diesen Beitrag antworten »

@Dopap:

Ich verstehe deinen Einwand mit der Kommutativität nicht. Mal ein Beispiel: Ich wähle die Primzahlen 2 und 3. Kannst du mir jetzt x,y nennen, für die ich aus 2^x*3^y nicht wieder herausfinden kann, was x,y waren?

@Dukkha: Meinst du mich oder Dopap? Falls du mich meinst:

Ich habe Mathematik studiert, habe aber mit Algebra überhaupt nichts am Hut, damit kannst du mich jagen Big Laugh Die Lösung kannte ich schon, nur nicht als Rätsel verpackt. Wir sollten in Analysis 1 (duck und weg Big Laugh ) mal eine Bijektion zwischen und explizit angeben und damals war mir das Diagonalverfahren zu umständlich, deswegen der gerade und ungerade Anteil.
Dopap Auf diesen Beitrag antworten »

Zitat:
Original von Clearly_wrong
@Dopap:

Ich verstehe deinen Einwand mit der Kommutativität nicht. Mal ein Beispiel: Ich wähle die Primzahlen 2 und 3. Kannst du mir jetzt x,y nennen, für die ich aus 2^x*3^y nicht wieder herausfinden kann, was x,y waren?


Ach sooo! . Irgendwie habe ich das nicht herauslesen können oder wollen. Schreibe das doch klar und deutlich und in Latex hin.
edit: mathjax kann ich nicht lesen, dann lag es daran, Sorry

Meine eigene Idee war so ein Versuch in die richtige Richtung, aber (*) ist natürlich überzeugend !

Zitat:

@Dukkha: Meinst du mich oder Dopap? Falls du mich meinst:

Ich habe Mathematik studiert, habe aber mit Algebra überhaupt nichts am Hut, damit kannst du mich jagen Big Laugh [...]


geht mir ähnlich ...

(*) könnte mich ärgern denn schon vor langer Zeit hatte ich folgende Verschlüsselungsidee:

Big Laugh
Dukkha Auf diesen Beitrag antworten »

Zitat:
Original von Dopap
verwirrt
1.) zwei Primzahlen kann ich als Produkt speichern. Die Rückzerlegung in 2 Faktoren ist zwar eindeutig aber kommutativ. Das ist aber nicht gestattet !
2.) und was ist mit den anderen Zahlenpaaren ??

Kann jemand bei mir für etwas Erleuchtung sorgen?

btw: in der Rätselecke sollte die Lösung des TS schon von Diesem irgendwann dargelegt werden.


Ich habe diesen Beitrag überlesen. Ich habe die Lösung vorher gepostet, über ein Diagonalverfahren. Meine Lösung war: die Cantorsche Paarungsfunktion. Clearly_wrong hat aber eine andere Lösung gefunden.
Tochrim Auf diesen Beitrag antworten »

Ich weiß zwar nicht ob man das als "mathematische Lösung" betrachten kann, aber warum zerlege ich meine Zahlen nicht in die kleinsten Teiler?
Beispiel:
ich will zahl 40 und 24 Speichern.

2*2*2*5 =40
2*2*2*3 =24

und für mein System speichere ich dann

222502223

die 0 ist das Trennzeichen, da die 0 bei der Zerlegung nicht als Faktor vorkommen kann.

Falls ich etwas mit 0 speichern will wäre es auch eindeutig, da dann als einziges zwei bzw drei 0 hintereinander wären.

000
00x
x00


Edit:
Ok, ich habe den zweiten Edit nicht gelesen... Das mit den binären und der 8...
und ohne trennungszeichen klappte es leider bei sowas wie 2 und 4 nicht weil dann in beiden fällen 222 raus käme

Edit 2:
Wobei, wenn ich das ganze als:
1222512223
aufschreibe geht es, da es dann eindeutig ist ohne das ich explizit mit der 0 trenne und die zerlegung beinhaltet wenn ich will ja auch ne 1
Tochrim Auf diesen Beitrag antworten »

Ok, das klapt auch nicht bei den zahlen zB:

1 und 11, da es
1*1 und 1*11 wären und ich das dann
11111
sind... und das könnte ich 1 zu eins vertauschen. Aber wenn ich die zahlen vorher mal 2 Multipliziere sollte es spätestens gehen.

dann wären die Zahlen
121211

Also 2x2y kann man bei der Faktorzerlegung ohne probleme als eine Zahl ohne Trennzeichen (da die 1 ja auch ein Faktor ist) aus meiner sicht speichern.
HAL 9000 Auf diesen Beitrag antworten »

Komplett unausgegorener Vorschlag: Bei Kodierung 2223 weiß man nicht, ob sie für

2*2*2*3 = 24
2*2*23 = 92
oder
2*223 = 446

steht. Von Eindeutigkeit also keine Spur. unglücklich
Tochrim Auf diesen Beitrag antworten »

Da hast du natürlich recht.
Da muss man es anderst angeben.
wenn ich die komplette reihe der primzahlen angebe und statt zB 2*2*2 die 2^3 nehme sollte es doch dann aber klappen, oder? Also bei 24
1^0*2^3*3^1 =102331
und bei 92
1^0*2^2*3^0*5^0*7^0*11^0*13^0*17^0*19^0*23^1=1022305070110130170190231.
Und 24,92 wäre dann
1023311022305070110130170190231?
Tochrim Auf diesen Beitrag antworten »

Ich meine, dadurch das ich immer das Schema:

1^0bzw1*2^a*3^b*5^c*7^d*11^e*13^f*17^g*19^h*23^i...
habe lässt sich doch ein Muster erkennen, wo ich sehr klar die Wiederholung ausmachen kann

Edit:
Okok, bei

2^3*3^333 bzw bei
2^33*3^33 läge das selbe problem vor -.- also bei ganz großen zahlen gehts nicht... außerich setze immer ne 0 dazwischen a la

2^03*3^0333 -> 20330333
2^033*3^033 -> 20333033
[email protected] Auf diesen Beitrag antworten »

Wie wäre es denn damit:

In beiden Zahlen werden alle "Nullen" durch die Kombination "01" ersetzt und beide Zahlen durch "00" miteinander verbunden! Durch die Ersetzung mittels "01" kann in den beiden Zahlen keine mehrfache Null mehr auftreten. Die einzige Stelle mit doppelter Null ist die Trennstelle. In den beiden wieder herausgelösten Ziffernfolgen werden alle "1"-en nach einer Null gestrichen und man hat die Ausgangszahl.

2 und 4 => 2004

binär: 10 und 100 => 1010010101

1001 und 4056 => 1010110040156

binär: 1111101001 und 111111011000 => 1111101101011001111110111010101

Da jedes (sinnvolles) Zahlensystem mit mindestens zwei Ziffern arbeitet und eine einstellige Zahl, die bzgl. der Addition neutrale Zahl ist, und eine andere einstellige Zahl, die bzgl. der Multiplikation neutrale Zahl ist, sind die beiden zu wählenden Ziffern in jedem Zahlensystem vorhanden.

Das Verfahren lässt sich beliebig modifizieren, z.B.: Man schiebt in jeder Zahl, nachdem n-Mal eine Null gestanden hat, eine beliebige, aber unbedingt von Null verschiedene Ziffer ein. Dann verbindet man beide Zahlen mit (n+1)-Mal einer Null. Die Dekodierung findet die größte Anzahl an aufeinanderfolgenden Nullen und nimmt diese als Trennzeichen für die beiden Zahlen. Von der maximalen Anzahl aufeinanderfolgender Nullen wird eine Stelle abgezogen und bei jedem Auftreten dieser Anzahl von aufeinanderfolgenden Nullen wird die folgende Ziffer gestrichen. Bei diesem Verfahren muss man nicht mitteilen, wie viele Nullen man als Trennzeichen verwendet und man muss auch nicht die "1" als Auffüller verwenden.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »