Palindrom und 81 Rätsel ist gelöst

Rätsel, die zum Lösen einen größeren Zeitaufwand erfordern, wie z. B. schwierige Physik- und Matherätsel.

Palindrom und 81

Beitragvon Otmar » Dienstag 6. Februar 2018, 22:44

Gesucht ist das kleinste durch 81 teilbare Zahlenpalindrom, dessen Dezimalziffern zur Hälfte Primzahlen sind.
:spass:
Bemerkung:
  • Das Rätsel kann ohne Taschenrechner, Computer, etc. gelöst werden.
  • Ein Zahlenpalindrom ist eine positive ganze Zahl, die vorwärts und rückwärts gelesen, die gleiche Ziffernfolge hat. Z.B.:
    55214041255
    Dieses Palindrom hat 11 Ziffern, wobei etwas mehr als die Hälfte, nämlich die 6 grünen, Primzahlen sind.
Spoilersperre ist festgelegt - Spoiler sind geöffnet
Start: Dienstag 6. Februar 2018, 22:44
Ende: Freitag 9. Februar 2018, 22:44
Aktuell: Samstag 18. August 2018, 16:56
Liebe Grüße, Otmar.
Benutzeravatar
Otmar
Schlaumeier
Schlaumeier
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 1605
Themen: 118
Registriert: Dienstag 10. Mai 2011, 22:10
Wohnort: München
Geschlecht: männlich

Re: Palindrom und 81

Beitragvon Neuling » Mittwoch 7. Februar 2018, 16:23

Mehr ->
Da das Zahlenpalindrom aus 2 "gespiegelten" Hälften besteht, müssen in jeder "Hälfte" die Hälfte der Ziffern Primzahlen sein.
Die Anzahl der Stellen der gesuchten Zahl muss also ein Vielfaches von 4 sein, also 4, 8, 12, 16, ...

Die Vielfachen von 81 sind:
81, 162, 243, 324, 405, 486, 567, 648, 729, 810, 891, 972, 1053, 1134, 1215, 1296, 1377, 1458, 1539, 1620, ...

Habe mir die 1377 gewählt, da sie 3 Primzahlen enthält. Zusammen mit der 81 habe ich einen "Baustein" (137781), bei dem die Hälfte Primzahlen sind.

Damit habe ich viel probiert und dabei auch den Taschenrechner benutzt. (Taschenrechner nur, weil ich so die Divisionen und Multiplikationen schneller durchführen konnte, hätte dies auch mit Zettel und Bleistift geschafft.)

Mit 6 von diesen "Bausteinen", aber anders sortiert, habe ich ein Zahlenpalindrom gefunden, allerdings ein sehr großes.

111111333777777888888777777333111111
: 81 = 1371744861454048010972565152260631

@Otmar
Mehr ->
Harte Nüsse kann ich ja meist nicht knacken. Deshalb bin ich schon froh, überhaupt ein Ergebnis gefunden zu haben.
Falls ich in den nächsten Tagen noch die Zeit finde, werde ich mich noch weiter mit dieser Problematik befassen. Ansonsten warte ich auf die Ergebnisse der Anderen bzw. auf deine Lösung.
Neuling
Superhirn
Superhirn
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 14820
Themen: 513
Registriert: Sonntag 30. Dezember 2012, 23:46
Geschlecht: weiblich

Re: Palindrom und 81

Beitragvon Neuling » Mittwoch 7. Februar 2018, 23:10

Mehr ->
Langsam taste ich mich heran. Nach 36stellig, hatte ich eine Lösung mit 28 Stellen.

Dann mal einen neuen Ansatz über 999999999 probiert.
Drei Neunen habe ich durch je zwei Primzahlen mit Summe 9 ersetzt.
222777999999999999777222 : 81 = 275034567912345676262
Damit ist meine beste Lösung jetzt 24stellig.
Neuling
Superhirn
Superhirn
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 14820
Themen: 513
Registriert: Sonntag 30. Dezember 2012, 23:46
Geschlecht: weiblich

Re: Palindrom und 81

Beitragvon Otmar » Sonntag 11. Februar 2018, 21:53

@Neuling,
:super: hatte gar nicht gedacht, dass es so schnell erste Lösungen gibt und bin heimlich ein paar Tage zum Skifahren verschwunden.

Mehr ->
Du bist auf dem richtigen Weg und mit etwas Glück, kannst du in den von dir genannten Zahlen eine gemeinsame Eigenschaft finden, die auch die Lösungszahl, die noch etwas kleiner ist, hat bzw. haben muss.
Liebe Grüße, Otmar.
Benutzeravatar
Otmar
Schlaumeier
Schlaumeier
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 1605
Themen: 118
Registriert: Dienstag 10. Mai 2011, 22:10
Wohnort: München
Geschlecht: männlich

Re: Palindrom und 81

Beitragvon Neuling » Sonntag 11. Februar 2018, 22:54

Die Gemeinsamkeit hatte ich schon entdeckt und glaubte aber, damit schon am Ende zu sein.
Neuer Versuch:

Mehr ->

125777799999999997777521
Neuling
Superhirn
Superhirn
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 14820
Themen: 513
Registriert: Sonntag 30. Dezember 2012, 23:46
Geschlecht: weiblich

Re: Palindrom und 81

Beitragvon Otmar » Montag 12. Februar 2018, 10:47

@Neuling :daumen: Das passt so. Ich warte mit dem Haken noch ein wenig, denn vielleicht gibt es ja noch eine Begründung dafür, dass das wirklich nicht kleiner geht...
Liebe Grüße, Otmar.
Benutzeravatar
Otmar
Schlaumeier
Schlaumeier
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 1605
Themen: 118
Registriert: Dienstag 10. Mai 2011, 22:10
Wohnort: München
Geschlecht: männlich

Re: Palindrom und 81

Beitragvon MadMac » Donnerstag 15. Februar 2018, 10:33

Hallo,

ich fange bei sowas gerne mit einer ...

Mehr ->
Restwertebetrachtung für eine Teilbarkeitsregel (bewertete Quersumme) an:


1 durch 81 rest 1
10 durch 81 rest 10
100 durch 81 rest 19
1000 durch 81 rest 28

hat immer die Differenz 9.

Darum haben z.B. durch Einfügen von je zwei Nullen und Verschiebung um eine Stelle

110000 druch 81 rest 2
1001000 druch 81 rest 2
10000100 druch 81 rest 2

etc.
alle den gleichen Rest. Für alle Verschiebungen lässt sich zeigen, dass keiner dieser Reste einen gemeinsamen Teiler mit 81 hat. Da die Hälfte der Dezimalziffern Primzahlen sein sollen, muss die Zahl eine gerade Anzahl Stellen haben (und ich kann mir eine äquivalente Betrachtung für 1000, 101000, 1000100, ... sparen).

Darum muss schlichtweg die Quersumme der Hälfte der Ziffern meiner Zahl den Wert 81 haben, so dass die Bewertete Quersumme der Zahl 81 * (Rest von 11000.... = Rest von 1001000... = Rest von 10000...1). Jetzt muss ich nur noch sparsam mit der Anzahl stellen umgehen.

Mit 20 Stellen komme ich gerade nicht hin, denn
77777999999999977777 hat die Quersumme 160
Bei 24 Ziffern stelle ich mal eine 1 vorne an (keine Primzahl) und versuche, die übrigen Ziffern so klein wie möglich zu halten, und komme auf

125777799999999997777521


Gruß,
MadMac
MadMac
Denksportler
Denksportler
 
MitgliedsjahreMitgliedsjahre
 
Beiträge: 159
Themen: 6
Registriert: Freitag 8. Juli 2016, 14:09
Geschlecht: männlich

Re: Palindrom und 81

Beitragvon Neuling » Donnerstag 15. Februar 2018, 14:55

Was ich nicht verstehe:
Mehr ->
Alle meine gefundenen Palindromzahlen hatten die Quersumme 162. Also habe ich vermutet, dass alle diese Zahlen mit der Quersumme 162 durch 81 teilbar sind und versucht, die kleinste zu finden. So weit, so gut.

Aber, es ist doch nicht zwingend notwendig, dass eine Zahl die Quersumme 81 haben muss, um durch 81 teilbar zu sein. 1215, 1539, 1782, ... haben die Quersummen 9 bzw. 18, enthalten die Hälfte Primziffern und sind durch 81 teilbar.
Könnte es daher nicht sein, dass man unter den "Spiegelbildern" solcher Zahlen (also 5121, 9351, 2871, ... ) mal eine findet, die auch durch 81 teilbar ist und man so eine kleinere Palindromzahl bilden könnte?
Neuling
Superhirn
Superhirn
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 14820
Themen: 513
Registriert: Sonntag 30. Dezember 2012, 23:46
Geschlecht: weiblich

Re: Palindrom und 81

Beitragvon Otmar » Donnerstag 15. Februar 2018, 18:50

Dann geht auch ein :glueckwunsch: an MadMac. Gut gemacht, obwohl du dem geneigten Leser noch ein paar kleine Beweise deiner Ideen und Vermutungen übrig gelassen hast.

@Neuling, ich hoffe, dass mit einer der beiden Varianten in unten stehender Lösung deine Vermutung zur Sicherheit wird. ;)

Und so sieht meine Lösung aus:
Mehr ->
Die Anzahl der Ziffern des Palindroms x sei n. Die Zahl n ist gerade, da n/2, die Anzahl der Primzahlziffern, ja auch eine ganze Zahl ist. D.h. x kann in der Mitte gespiegelt werden und damit kommt jede Primzahlziffer in gerader Anzahl vor. Also ist n/2 auch gerade und n durch 4 teilbar.

Das erste Zwischenergebnis ist, dass die Quersumme von x ein Vielfaches von 2*81 = 162 ist.
Das kann man auf verschiedene Weise zeigen. Ich hab zwei Möglichkeiten:

Erste Möglichkeit:

Mehr ->
Es sei
A = 100..001
B = 10..010
Hier habe B zwischen den beiden Einsen k Nullen (k = 0, 1, 2, ...). A hat zwischen den beiden Einsen k+2 Nullen. Offenbar gilt:
A-1=10*(B-10) ---> A=10*B-99
Betrachtet man die Differenz D=A-B:
D=10*B-99-B=9*B-99=9*(B-11)
Dann sieht man das D ein Vielfaches von 9 ist. Weiterhin ist B-11=99... (k+2 Neunen) was man sich leicht klar macht:
.
99 999 9999 99999
+11 + 11 + 11 + 11
--- ---- ----- ------
110 1010 10010 100010
Da auch B-11 durch 9 teilbar ist, ist D ein Vielfaches von 9²=81, was auch bedeutet, dass A und B bei Division durch 81 den gleichen Rest R lassen. Vielfache l * A und l * B lassen bei Division durch 81 den gleichen Rest übrig und zwar den, den auch l*R übrig lässt.

Wenn man für l Zehnerpotenzen einsetzt, kann man sich klarmachen, dass alle Zahlen:
B1 =         110000
A1 = 1001000 = B2
B3 = 10000100 = A2
A3 = 100000010 = B4
B5 = 1000000001 = A4

bei Division durch 81 den gleichen Rest lassen, wobei man das Schema beliebig nach unten und rechts erweitern kann. A1, B1, A2, B2, ... sind die mit Zehnerpotenzen multiplizierten Zahlen A und B von oben.

Für das Palindrom x
x = ... Z5 Z4 Z3 Z2 Z1 Z1 Z2 Z3 Z4 Z5 ... = Z1 * B1 + Z2 * B2 + Z3 * B3 + Z4 * B4 + Z5 * B5 +...
sei dieser Rest Q und
x = Z1 * Q + Z2 * Q + Z3 * Q + Z4 * Q + Z5 * Q + ... + 81 * p = Q * (Z1 + Z2 + Z3 + Z4 + Z5 +...) + 81 * p. Dabei sind in 81 * p alle schon bekannten Vielfachen von 81 in den Summanden von
Z1 * B1 + Z2 * B2 + Z3 * B3 + Z4 * B4 + Z5 * B5 +... zusammengefasst.

Nach Voraussetzung ist x ein Vielfaches von 81, also x = 81 * q, dann ist:

81 * q = Q * (Z1 + Z2 + Z3 + Z4 + Z5 +...) + 81 * p oder
81 * (q-p) = 3^4 * (q-p) = Q * (Z1 + Z2 + Z3 + Z4 + Z5 +...).
Q ist offenbar nicht durch 3 teilbar, da z.B. die Quersumme von B1 nicht durch 3 teilbar ist. Deshalb muss
Z1 + Z2 + Z3 + Z4 + Z5 +... ein Vielfaches von 81=3^4 sein.

Zweite Möglichkeit:

Mehr ->
Das Palindrom x sei x = z(0) z(1) z(2) ... z(n/2-1) z(n/2-1) ... z(2) z(1) z(0)

x = z(0) * 1000.......0001 + 
z(1) * 100.......0010 +
z(2) * 10.......0100 +
.
.
.
z(n/2-1) * 1100..000


x = z(0) * (10^(n-1) + 1 ) +
z(1) * (10^(n-2) + 10 ) +
z(2) * (10^(n-3) + 10² ) +
.
.
.
z(n/2-1) * (10^(n/2) + 10^(n/2-1))

10^k = (1+9)^k = (1+9) * (1+9) * ... * (1+9) (Produkt mit k Faktoren (1+9))
= 1 + 9*k + 9² * q(k)

Die letzte Formel erhält man durch Ausmultiplizieren von (1+9)^k. Genau ein Summand ist das Produkt aus k Einsen, k weitere Summanden haben den Faktor 9 genau ein Mal und k-1 Einsen und alle anderen Summanden haben mindestens zwei Faktoren mit Wert 9.

Dann schreibt sich x

x = z(0)     * (1 + 9*(n-1) + 1           ) + 
z(1) * (1 + 9*(n-2) + 1 + 9 ) +
z(2) * (1 + 9*(n-3) + 1 + 9*2 ) +
.
.
.
z(n/2-1) * (1 + 9*(n/2) + 1+ 9*(n/2-1)) +
9² * Q.

In 9² * Q sind alle oben weggelassenen Terme der Form z(i) * 9² * q(j) enthalten. Schön ist, dass die Faktoren in der rechten Spalte alle gleich sind und zwar 2+9*(n-1). Also kann man 2 + 9*(n-1) ausklammern und erhält:

x = (z(0)+z(1)+z(2)+...+z(n/2-1)) * (2+9*(n-1)) + 81 * Q oder
3^4 * (x/81-Q) = (z(0)+z(1)+z(2)+...+z(n/2-1)) * (2+9*(n-1))
Und weil x/81 nach Voraussetzung ganzzahlig ist und 2+9*(n-1) nicht durch 3 teilbar ist, muss (z(0)+z(1)+z(2)+...+z(n/2-1)) ein Vielfaches von 3^4 sein.

Beide Möglichkeiten zeigen,
Mehr ->
dass die Summe der Ziffern der rechten bzw. linken Palindromhälfte ein Vielfaches von 81 ist und die Suche wird leichter. In so einer Hälfte sind n/4 Primzahlziffern und n/4 andere Ziffern. Würde man im gesuchten Palindrom x die Primzahlziffern durch 7 und die anderen durch 9 ersetzen, wäre die Summe der Ziffern nicht kleiner geworden. Gedanklich kann man das ja mal machen:

n/4 * (7+9) >= m * 81
n/4 >= m * 81 / 16 = m * (5 + 1/16)

Das kleinste n/4 und damit die kleinste mögliche Stellenzahl erhält man für m = 1 und n/4 = 6. Man kann es mit n=4*6=24 Ziffern versuchen und macht gedankliche die Ersetzung der Ziffern rückgängig, also aus Siebenen werden Primzahlziffern und aus Neunen werden andere Ziffern. Man startet in der linken Palindromhälfte mit 6 Primzahlziffern vom Wert 7 und sechs anderern vom Wert 9 (Reihenfolge noch beliebig) und verringert die Ziffernwerte so, dass ihre Summe 81 wird und x so klein wie möglich:

6 * (7 + 9) = 96 = 81 + 15. Man kann also insgesamt 15 von einzelnen Ziffern wegnehmen:

Die erste Ziffer ist mindestens 1. Keine Primzahl also 1=9-8. Es bleiben noch 15-8=7 zum Wegnehmen.
Zweite Ziffer:
0 oder 1 geht nicht, da beides keine Primzahlen und 9-7 > 1 > 0 ist.
2 ist Primzahl, da geht 2=7-5 und die aktuelle halbe Quersumme ist 1+2+ 5*7 + 5*9 = 83, d.h. man kann für die dritte Ziffer aus einer 7 noch eine 5 machen.
Eine kleinere dritte Ziffer geht nicht. Damit ist das gesuchte Palindrom:

x = 125777799999999997777521

und das x ist ganz sicher durch 81 teilbar, ohne nachzurechnen.
Liebe Grüße, Otmar.
Benutzeravatar
Otmar
Schlaumeier
Schlaumeier
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 1605
Themen: 118
Registriert: Dienstag 10. Mai 2011, 22:10
Wohnort: München
Geschlecht: männlich

Re: Palindrom und 81

Beitragvon MadMac » Mittwoch 21. Februar 2018, 14:50

@Neuling:

Zur Erläuterung meiner Betrachtungen:

Mehr ->
Wir alle wissen, dass man durch Berechnen der einfachen Quersumme ermitteln kann, ob eine Zahl durch 3 teilbar ist. Dieses Prinzip kann man vom Grundsatz her auf alle Zahlen anwenden, wenn man die einzelnen Stellen zusätzlich bewertet. Wie ich in meiner Lösung begonnen habe, hat

1 / 81 den Rest 1
10 / 81 den Rest 10
100 / 81 den Rest 19
... die Reste 28, 37, 46, 55, 64, 73
und 1000000000 / 81 wieder den Rest 1
und so weiter (ab hier wiederholen sich die Reste periodisch).

Um zu ermitteln, ob eine große Zahl durch 81 teilbar ist, berechne ich eine "bewertete" Quersumme, indem ich jede Ziffer mit dem dem Stellenwert entsprechenden Divisionsrest multipliziere:

abcdefghiabcdefghiabcdefghi (Buchstaben zur Hilfestellung)
123456789333334444455555555
/ 81 hat den gleichen Rest wie
(
(a) (1 + 3 + 4 ) * 73 +
(b) (2 + 3 + 5 ) * 64 +
(c) (3 + 3 + 5 ) * 55 +
(d) (4 + 3 + 5 ) * 46 +
(e) (5 + 3 + 5 ) * 37 +
(f) (6 + 4 + 5 ) * 28 +
(g) (7 + 4 + 5 ) * 19 +
(h) (8 + 4 + 5 ) * 10 +
(i) (9 + 4 + 5 ) * 1
) / 81

Ist also diese "bewertete" Quersumme durch 81 teilbar, so ist auch die große Zahl durch 81 teilbar.


Der zweite Schritt war meine Feststellung, dass die Berwertungsfaktoren für zwei Benachbarte stellen sich stets um 9 unterscheiden. Dadurch kam ich auf die Überlegung (dass ich eine gerade bzw. durch 4 teilbare Anzahl Stellen brauche, setze ich, weil schon begründet, voraus):

Ein Palindrom mit gerader Stellenzahl kann ich ausdrücken durch
x = a0*1000000....1 + a1*100000...10 + a2*10000...100 + a3*1000...1000 + a4*100...10000 + ... Daher die Betrachtung von Zahlen mit je 2 1en und ihren Verschiebungen:

Wenn ich eine Zahl 11000...0 habe, hat die irgendenen Rest bei Division durch 81.
Verschiebe ich nun eine 1 nach rechts und eine 1 nach links, ändert sich meine bewertete Quersumme für die eine Ziffer um ein Delta von + 9, für die andere Ziffer um eine Delta von -9. Das heißt, diese bleibt identisch. Beispiel:
11000 / 81 hat den gleichen Rest wie ( 37 + 28 ) / 81, nämlich 65
Verschiebung:
100100 / 81 hat den gleichen Rest wie ( 46 + 19 ) / 81, nämlich 65
Das kann ich so lange wiederholen, bis eine 1 ganz rechts steht, und immer muss der Rest identisch bleiben (da ich ihn mit einer 1 durch Verschiebung um eine Stelle um 9 erhöhe und mit der anderen um 9 erniedrige).

Nun kenne ich noch nicht die Länge meines Palindroms, muss meine Zahlen mit den Einserpärchen noch einmal genauer betrachten.

11 / 81 hat den Rest 10 + 1 = 11
110 / 81 hat den Rest 19 + 10 = 29
1100 / 81 hat den Rest 28 + 19 = 47
... (Reste 65, 2, 20, 38, 56, 74)
Wie ganz oben setzt bei 9 Nullen wieder eine Periode ein.
11000000000 / 81 hat den Rest 11

DANN kommt meine Feststellung: Alle diese Reste haben keinen Faktor 3 (also keinen mit 81 gemeinsamen Faktor). ERST JETZT kommt meine Schlussfolgerung, dass bei Konstruktion des Palindrums nach dem Schema
x = a0*1000000....1 + a1*100000...10 + a2*10000...100 + a3*1000...1000 + a4*100...10000 + ...
diese Zahl bei divisision durch 81 den Rest
Rest(x/81) = Rest( ( a0*Rest(1000000....1/81) + a1*Rest(100000...10) + a2*Rest(10000...100) + a3*Rest(1000...1000) + a4*Rest(100...10000) + ... )/81 )
= Rest( (a0 + a1 + a2 + a3 + a4 + ...) * Rest (1000000....1/81) )/81 )
haben muss.
Rest (1000000....1/81) hat, wie festgestellt, keinen gemeinsamen Faktor mit 81, darum muss
(a0 + a1 + a2 + a3 + a4 + ...)
für mein konstruiertes Palindrom durch 81 teilbar sein.

Der Rest wie in meiner Lösung ;-)



Gruß,
MadMac
MadMac
Denksportler
Denksportler
 
MitgliedsjahreMitgliedsjahre
 
Beiträge: 159
Themen: 6
Registriert: Freitag 8. Juli 2016, 14:09
Geschlecht: männlich

Nächste

  • Ähnliche Themen
    Antworten
    Zugriffe
    Autor

Zurück zu Harte Nüsse

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast