| Autor |
Beitrag |
    
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Mittwoch, den 14. August, 2002 - 16:27: | 
|
Beim Zahlenbasteln ist mir aufgefallen, dass viele zusammengesetzte Zahlen durch Ersetzen einer einzigen Ziffer in Primzahlen verwandelt werden können. So gibt es zum Beispiel bei 121 mehrere Möglichkeiten, u.a. 421, 151 oder 127. Aber man findet auch Zahlen bei denen das nicht funktioniert. Daher meine Frage:
Wer findet die kleinste Zahl m mit folgender Eigenschaft:
Unter m aufeinanderfolgenden natürlichen Zahlen ist immer eine Zahl, die sich nicht durch Ersetzen einer einzigen Ziffer in eine Primzahl verwandeln lässt.
|
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1308
Registriert: 07-2000
| | Veröffentlicht am Mittwoch, den 14. August, 2002 - 22:15: |
|
Fürwahr - sehr verwirrend!
m > 10, denn sonst gäbe es ja unter 10, 11, ..., 19 eine Zahl 1x, die sich nicht durch Ersetzen einer Ziffer in eine Primzahl verwandeln lässt. Aber 1x lässt sich ja immer in z. B. 13 verwandeln.
Habe ich das richtig verstanden?
|
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 85
Registriert: 03-2001
| | Veröffentlicht am Mittwoch, den 14. August, 2002 - 22:37: |
|
hi sol@ti, hi zaph.
ja, so habe ich es auch verstanden.
und ich würde mal vermuten, daß m=200 gilt, da 200 die kleinste zahl ist, die man durch ersetzten einer ziffer nicht in eine primzahl umwandeln kann. und da die primzahldichte nach oben hin abnimmt, wird man es mit größeren zahlen einfacher haben, die kriterien zu erfüllen. oder mache ich es mir da zu einfach??
gruß
markus |
SpockGeiger (spockgeiger)
Senior Mitglied
Benutzername: spockgeiger
Nummer des Beitrags: 566
Registriert: 05-2000
| | Veröffentlicht am Donnerstag, den 15. August, 2002 - 02:05: |
|
Hi sol@ti
Ist es denn erlaubt, die führende Ziffer durch eine Null zu ersetzen?
viele Grüße
SpockGeiger |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Donnerstag, den 15. August, 2002 - 11:17: |
|
Hallo,
und ja zu allen bisherigen Beiträgen. Genau so ist's gemeint und auch SpockGeigers "Trick" ist zulässig: aus 1000002 wir die Primzahl 0000002.
@Markus: Da alle Zahlen von 1 bis 199 durch Ersetzen einer Ziffer in eine Primzahl verwandelt werden können, gilt m >= 200. Der strenge Beweis für m = 200 wäre optimal. Ich muss bisher aber mit einer deutlich größeren oberen Schranke für m vorlieb nehmen.
Viele Grüße
sol@ti
|
clara
Unregistrierter Gast
| | Veröffentlicht am Donnerstag, den 15. August, 2002 - 18:00: |
|
Hi,
soll man denn auch die Primzahlen noch mal in einer andere Primzahl verwandeln können, durch Änderung einer Ziffer?
m=200 geht nicht, da alle Zahlen zwischen 629 und 839 durch Änderung einer Ziffer in eine Primzahl verwandelt werden können (auch die Primzahlen).
Erst 840 geht wieder nicht.
Ich vermute auch eher, dass es so eine Zahl nicht gibt, aber kann es nicht beweisen (noch nicht). Ist eben nur eine Vermutung.
gruß clara |
Onkel Murray (murray)
Erfahrenes Mitglied
Benutzername: murray
Nummer des Beitrags: 134
Registriert: 10-2001
| | Veröffentlicht am Donnerstag, den 15. August, 2002 - 18:27: |
|
Hi,
es ist vielleicht auch mal wieder eine Frage wie man diese Aufgabe versteht.
Wenn es darum geht wirklich nur EINE Ziffer auszutauschen, dann dürften bei m=200 folgende Zahlen keine Primzahlen sein:
1. wenn man nur Hunderter austauscht, das ist klar (eg. 300, 000).
2. wenn man nur Zehner austauscht, das ist klar (eg. 220).
3. wenn man nur Einer tauscht, dann darf 201, 203, 207 und 209 nicht Primzahl sein.
Und das ist der Fall.
Also würde, nach meiner Interpretation der Aufgabe, 200 die kleinste Zahl sein für die das gilt.
Murray |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Freitag, den 16. August, 2002 - 11:19: |
|
Hallo,
@clara: Es ging mir ursprünglich um die "Herstellung" von Primzahlen aus Nicht-Primzahlen. Wenn schon eine Primzahl vorliegt, könnte man rein formal eine Ziffer durch dieselbe Ziffer "ersetzen" und so die Primzahl gleich lassen. Du kannst sie aber gern durch eine andere Primzahl ersetzen, wenn das Vorteile für deinen Beweis bringt.
Markus' Vermutung m = 200 hast du widerlegt, wir wissen jetzt m >= 211 (wenn es so ein m überhaupt gibt!)
@Murray: Erinnerst du dich an Raphaels Frage wegen der Primzwillinge? Die Lösung war: Unter 3 aufeinanderfolgenden Zahlen ist immer eine durch 3 teilbar. Genau so ist's hier gemeint: Unter m aufeinanderfolgenden Zahlen ist immer (mindestens) eine nicht prim-verwandelbar. Egal wie die erste der m Zahlen gewählt wird. Wenn m = 300 wäre, müsste z.B. zwischen 17,384.855 und 17,385.154 garantiert eine nicht prim-verwandelbare Zahl liegen. Diese Allgemeingültigkeit macht die Sache natürlich nicht gerade einfacher ;-)
Viele Grüße
sol@ti
|
clara
Unregistrierter Gast
| | Veröffentlicht am Freitag, den 16. August, 2002 - 12:58: |
|
Hi,
wenn ich mich nicht täusche ist m>211 auch nicht richtig. Zwischen 2591 und 2819 dürfte auch keine Zahl liegen die man derart verwandeln kann. Damit wären wir schon bei m>228.
gruß clara |
ende (ende)
Neues Mitglied
Benutzername: ende
Nummer des Beitrags: 4
Registriert: 05-2002
| | Veröffentlicht am Freitag, den 16. August, 2002 - 13:05: |
|
Hallo!
Ich moechte es nur mal hinschreiben, damit ich besser denken kann.
claras Vermutung lautet also:
Fuer alle natuerlichen Zahlen m gilt:
Es gibt m aufeinanderfolgende Zahlen, von denen jede einzige sich durch Ersetzen einer einzigen Ziffer in eine Primzahl verwandeln laesst.
Richtig?
Gruss, E. |
Onkel Murray (murray)
Erfahrenes Mitglied
Benutzername: murray
Nummer des Beitrags: 135
Registriert: 10-2001
| | Veröffentlicht am Freitag, den 16. August, 2002 - 13:07: |
|
Achso, mit beliebigem Anfang, ich dachte immer für m=200 gilt m=[1,2,...,199,200].
Ok, das macht die Sache bedeutend schwieriger.
Aber fassen wir doch mal zusammen welche Eigenschaften diese Zahl haben müßte - damit kann man die Suche deutlich vereinfachen.
1. die Zahl ist >= 200 und damit gilt
2. die Einerstelle muß 0,2,4,5,6 oder 8 sein
(da alle gleichgut sind kann man auch 0 verwenden)
3. wenn man die Einerstelle durch 1,3,7 oder 9 austauscht, dann dürfen das keine Primzahlen sein
4. die Stellen über der Einerstelle spielen eigentlich nur eine untergeordnete Rolle, weil jede beliebige Zahl die nach 2. endet keine Primzahl sein kann.
Damit dienen diese Stellen nur der Findung von Zahlen für "10'er-Löchern" (nach 3.)
Gesucht sind am Ende also 'nur' jene Zahlen, bei denen 10 aufeinanderfolgende keine Primzahlen sind.
Bsp. 200-209, 320,329 u.s.w.
Wir suchen also das kleinste m in dem garantiert solch eine Folge auftritt und zwar egal von wo auch immer der Zahlenraum beginnt.
Man könnte auch einwenden, das die Zahl gleich mit 1,3,7 oder 9 enden kann (siehe 2.). Das darf dann aber trotzdem keine Primzahl sein und damit ist wieder nach einem "10'er-Loch" gesucht - also machen wir es uns nur leichter wenn wir gleich die 0 nehmen.
Aber wie nun weiter?
Kann man eine Regel definieren mit der man solche "10'er-Löcher" findet?
Murray
(Beitrag nachträglich am 16., August. 2002 von murray editiert) |
clara
Unregistrierter Gast
| | Veröffentlicht am Freitag, den 16. August, 2002 - 17:17: |
|
@ende,
das ist richtig. So habe ich vermutet, aber mittlerweile kann ich mir das nicht mehr vorstellen. Ich denke, dass m=229 richtig ist, aber kann es nicht beweisen.
clara |
ende (ende)
Neues Mitglied
Benutzername: ende
Nummer des Beitrags: 5
Registriert: 05-2002
| | Veröffentlicht am Freitag, den 16. August, 2002 - 18:48: |
|
@clara,
also waere jetzt zu zeigen, dass zwischen zwei verschiedenen Zahlen, die sich nicht zu Primzahlen verwandeln lassen, mindestens 228 Zahlen liegen?
Gruss, E. |
Onkel Murray (murray)
Erfahrenes Mitglied
Benutzername: murray
Nummer des Beitrags: 136
Registriert: 10-2001
| | Veröffentlicht am Freitag, den 16. August, 2002 - 19:04: |
|
@ende: Nicht ganz, das mindestens ist schon klar - oder auch nicht .
Es gilt jetzt zu beweisen, das das für alle Zahlen der kleinste Bereich ist.
Murray |
ende (ende)
Junior Mitglied
Benutzername: ende
Nummer des Beitrags: 6
Registriert: 05-2002
| | Veröffentlicht am Freitag, den 16. August, 2002 - 19:19: |
|
Hm, ich glaube, ich habe falsch gedacht. Es ist zu zeigen, dass die groesste Differenz zweier aufeinanderfolgender nichtverwandelbarer Zahlen 229 betraegt.
So richtig?
Gruss, E.
(Beitrag nachträglich am 16., August. 2002 von ende editiert) |
fahrstuhl
Unregistrierter Gast
| | Veröffentlicht am Freitag, den 16. August, 2002 - 19:32: |
|
ende, nein höchstens 228. |
fahrstuhl
Unregistrierter Gast
| | Veröffentlicht am Freitag, den 16. August, 2002 - 19:36: |
|
ende, so is richtig. |
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 86
Registriert: 03-2001
| | Veröffentlicht am Samstag, den 17. August, 2002 - 04:27: |
|
hi.
kleine korrektur der zahlen von clara:
die zahl 2588 läßt sich nicht in eine primzahl umwandeln,
die zahlen von 2589 bis 2819 kann man zu primzahlen machen,
die zahl 2820 wiederum nicht.
d.h. m>=232
gruß
markus |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Samstag, den 17. August, 2002 - 10:39: |
|
Hallo,
alle Zahlen von 15209 bis einschließlich 15479 kann man durch Ersetzen einer Ziffer in Primzahlen verwandeln. Hat jemand eine obere Schranke für m (oder Ideen dazu)?
@Murray: Sehr interessante Analyse. Ich glaube du hältst den Schlüssel zur Lösung in der Hand!
Viele Grüße
sol@ti
|
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 87
Registriert: 03-2001
| | Veröffentlicht am Samstag, den 17. August, 2002 - 21:34: |
|
nein, noch keine idee. aber ich kann vermelden, daß die von die gefundene stelle mit in primzahlen umwandelbaren zahlen (15209-15479, d.h. m>=272) die größte bis 2'500'000 ist (und wohl auch darüber hinaus). tja, jetzt wäre es zeit für mathematik...
gruß
markus |
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1312
Registriert: 07-2000
| | Veröffentlicht am Sonntag, den 18. August, 2002 - 15:13: |
|
Konnte bestätigen, dass es unterhalb von 100.000.000 keinen Run größerer Länge als 271 gibt.
@Sol@ti: Am 15. Agust sagtest du "Ich muss bisher aber mit einer deutlich größeren oberen Schranke für m vorlieb nehmen." Heißt das, du hast eine obere Grenze? Wie lautet die? Brauchst ja noch nicht zu verraten, wie du drauf gekommen bist. |
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 88
Registriert: 03-2001
| | Veröffentlicht am Sonntag, den 18. August, 2002 - 15:51: |
|
hmm, da hat wohl jemand nen besseren pc bzw. bessere programmierkenntnisse wie ich... wahrscheinlich beides...  |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Sonntag, den 18. August, 2002 - 16:02: |
|
m <= 2311
|
clara
Unregistrierter Gast
| | Veröffentlicht am Sonntag, den 18. August, 2002 - 17:10: |
|
Hi,
wenn ihr bis 31610054640417607788145206291543662493274686990 = 2*3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97*101*103*107*109*113
kein größeres m gefunden habt, müsste der Beweis erbracht sein.
Ich habe mir folgendes überlegt:
Man gehe nach dem Sieb des Erathostenes vor:
Schreibe die Zahlen 0 - 9 nebeneinander und die nächsten 10 Zahlen jeweils darunter, dann beginnt man alle Nicht-Primzahlen zu streichen. Die erste ganz gestrichene Reihe findet sich bei 200-209, d.h. die erste Zahl die sich nicht umwandeln läßt ist 200. Das "Streichungsmuster" bis hier hat sich durch die Primzahlen 2,3,5,7,11 und 13 ergeben. Bei 2*3*5*7*11*13=30030 "wiederholt" sich dieses Muster, es werden höchstens noch mehr Zahlen gestrichen. Hätte sich allerdings bis dahin kein größeres m ergeben, könnte es auch kein größeres geben (ganz gestrichene Reihen ergeben sich eher früher).
Da wir mittlerweile aber schon bei 15479 angekommen sind ergibt sich mit gleicher Überlegung die obige Grenze.
gruß clara |
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1316
Registriert: 07-2000
| | Veröffentlicht am Sonntag, den 18. August, 2002 - 22:44: |
|
Noch ne merkwürdige Beobachtung.
Wenn x + 1, ... , x + n ein maximaler Run ist, d. h. x + 1, ..., x + n sind alles "Beinahe-Primzahlen", und weder x noch x + n + 1 ist eine Beinahe-Primzahl, dann ist fast immer n = 1 mod 10.
Wenige Ausnahmen scheint es zu geben. Wenn ich den Schub der 199 Beinahe-Primzahlen am Anfang mal außer acht lasse, nur
n = 3, 10, 20, 30, 40, 50.
Bei x = 3.073.868 kommt noch mal n = 201 vor. Danach maximal nur noch n = 181. Das aber immer wieder - das letzte Mal in meinen Beobachtungen für x = 77.126.188.
@clara: Habe es leider nicht ganz gerafft :-/ |
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 89
Registriert: 03-2001
| | Veröffentlicht am Montag, den 19. August, 2002 - 05:24: |
|
hi.
gute idee, clara. du schaust dir die erste gestrichene reihe, also die zahlen von 200 bis 209 an. dann nimmst du von jeder dieser zahlen den kleinsten primfaktor und bildest deren produkt, wobei es ausreicht, wenn jeder faktor einmal vorkommt. dieses produkt ist aber 2*3*5*7*11=2310, der faktor 13 tritt zwar bei 208 auf, die zahl wird jedoch schon durch die 2 abgedeckt.
da also alle der zahlen 200 bis 209 mindestens einen der faktoren 2, 3, 5, 7 oder 11 enthalten, verhält sich dies bei den zahlen 200+k*2310 bis 209+k*2310 ebenso. d.h. zwischen zwei 10er-löchern liegt maximal der abstand 2310 (kann natürlich auch geringer sein).
die letzte zahl vor einem längstmölichen 'run' ist also 209+k*2310. bei einer zahl dieser form ist es allerdings unter umständen möglich, sie in eine primzahl umzuwandeln, indem man eine andere ziffer als die einerstelle ändert (z.b. 209 -> 229). d.h. die letzte zahl vor einem run, die sicher nicht zur primzahl gemacht werden kann, ist 208+k*2310. die zahl nach einem run, auf die dies zutrifft, ist 200+(k+1)*2310. zwischen diesen beiden werten liegen 2301 zahlen, so daß unter 2302 aufeinanderfolgenden zahlen auf jeden fall eine nicht zur primzahl gemacht werden kann.
d.h. m<=2302
@clara: deine letzten zwei sätze sowie die bedeutung der zahl (produkt der primzahlen bis 113) habe ich leider nicht verstanden.
gruß
markus |
clara
Unregistrierter Gast
| | Veröffentlicht am Montag, den 19. August, 2002 - 12:39: |
|
Hi,
o.k. Versuche mal mich verständlicher auszudrücken.
Stellt Euch die natürlichen Zahlen untereinander geschrieben vor, wie ich es oben schon beschrieben habe. Dann beginnt man die Nichtprimzahlen zu streichen. Dabei ergibt sich bis 209 ein ganz spezielles Streichungsmuster. Macht man jetzt von diesem Muster eine Schablone (von den Zahlen 0-209), dann kann man diese Schablone auf die Zahlen 30030-30209 legen. Alle gestrichenen Zahlen sind dann sicherlich Nichtprimzahlen. Man muss höchstens noch mehr Zahlen streichen, aber damit kann man m nicht mehr vergrößern. Hätten wir jetzt bis 30030 kein größeres m gefunden, dann wäre m = 200 gewesen. Haben wir aber ja.
Das Streichungsmuster von 0 - 15479 wird verursacht durch die Primzahlen von 2 - 113. Dies wieder als Schablone gedacht, kann man wieder beim Produkt dieser Primzahlen anlegen und erhält wieder dieses Muster plus noch mehr gestrichenen Zahlen.
Das Problem ist nur, dass von 15480 bis zu diesem Produkt ein größeres m auftreten kann, wenn es dies aber nicht tut, dann kann es danach sicherlich kein größeres geben.
Ich hoffe, dass man dies jetzt verstehen kann.
gruß clara |
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 90
Registriert: 03-2001
| | Veröffentlicht am Montag, den 19. August, 2002 - 15:18: |
|
hi.
ok, alles klar. aber wie bereits oben gesagt, wiederholt sich die 'kleine schablone', die die zalen 200-209 streicht, bereits nach 2*3*5*7*11=2310.
es wird vermutlich schwierig, alle zahlen bis 'produkt-aller-primzahlen-bis-113' zu testen.
aber mit deiner methode habe ich festgestellt, daß 510-519, 1790-1799 und 2100-2109 ebenfalls durch die primzahlen 2, 3, 5, 7 und 11 gestrichen werden und sich diese schablonen also ebenfalls 2310 zahlen weiter wiederholen. der größte run findet sich nun zwischen 518+k*2310 und 1790+k*2310.
d.h. m<=1272
(übrigens genau 1000 mehr als die untere schranke, m>=272)
gruß
markus
(Beitrag nachträglich am 19., August. 2002 von boothby81 editiert) |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Montag, den 19. August, 2002 - 16:17: |
|
Bravo Markus und Clara!
Claras Idee mit der wiederholten "Schablone" war die Initialzündung, Markus hat sie perfektioniert. Die Folge 200+k*2310 und damit m <= 2310 war übrigens auch meine Lösung (die Primzahl 2311 diente nur zur Verschleierung der auffälligen Faktorisierung ;-). Markus' Idee, die 2310-Periode mit verschiedenen Startwerten zu betrachten, ist echt super! Es gilt sogar m <= 1271, da der längste Run nur die Zahlen von 520+k*2310 bis 1789+k*2310, also 1270 Zahlen umfassen kann.
Kann man die Lücke zwischen m >= 272 und m <= 1271 noch verkleinern?
@Zaph: Deine Beobachtung ist interessant. Klar ist: Wenn eine gerade Zahl nicht in eine Primzahl verwandelt werden kann, dann gilt das für alle geraden Zahlen im selben Zehnerblock. Also kommt für die Länge n eines Runs nur 0,1,3,7,9 (mod 10) in Frage. 1 ist der Normalfall (ganze Zehnerblöcke und die vorhergehende Zahl mit Endziffer 9); 0 (ganze Zehnerblöcke) und 3 sind selten. Dass aber 7 nie und 9 nur am Anfang auftritt ist bemerkenswert. Hast du konkrete Beispiele für n=3 ?
Viele Grüße
sol@ti
|
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1317
Registriert: 07-2000
| | Veröffentlicht am Montag, den 19. August, 2002 - 18:14: |
|
Alle 18 Beispiele für 3 unter 100.000.000. Nach meiner obigen Notation x =
200
20000
30000
50000
60000
80000
600000
800000
3000000
4000000
5000000
6000000
9000000
50000000
60000000
70000000
80000000
90000000
|
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Montag, den 19. August, 2002 - 18:50: |
|
Danke Zaph, aber wie ist n = 3 z.B. bei x = 200 zu verstehen?
|
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1318
Registriert: 07-2000
| | Veröffentlicht am Montag, den 19. August, 2002 - 20:26: |
|
Soll heißen:
x + 1, x + 2, x + 3
ist ein maximaler Run.
Das sind natürlich genau die Zahlen r * 10^k (0 < r < 10), für die
r * 10^k + 1
keine Primzahl ist, aber es m und s gibt (0 < m < k, 0 < s < 10), sodass
r * 10^k + s * 10^m + 1
eine Primzahl ist.
Gruß
Z.
P.S.: Vielleicht solltest du das Rätsel mal im American Mathematical Monthly veröffentlichen. Die haben dort eine spezielle Rubrik für sowas. |
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1321
Registriert: 07-2000
| | Veröffentlicht am Montag, den 19. August, 2002 - 22:01: |
|
Hatte ich fast vergessen:
@Markus: Mein Aldi-PC wird demnächst drei. Aufgerüstet auf 256 MB RAM. |
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 91
Registriert: 03-2001
| | Veröffentlicht am Dienstag, den 20. August, 2002 - 03:06: |
|
hi.
@sol@ti: analog zu bereits oben erwähntem kann der längste run schon mit 519+k*2310 beginnen. 519 kann z.b. in 509 umgewandelt werden, 519+2310=2829 in 2819,... im selben beitrag deiner korrektur hast du es im kommentar an zaph übrigens selbst erwähnt: ganze Zehnerblöcke und die vorhergehende Zahl mit Endziffer 9. also 272<=m<=1272.
@zaph: so wie ich deine definition verstanden habe, soll x=200, n=3 bedeuten, daß 201, 202 und 203 in primzahlen umgewandelt werden können, 200 und 204 jedoch nicht. das ist aber nicht der fall, auch zu den anderen werten paßt diese deutung nicht...?!?
trotz des relativ hohen alters deines pc's hat meiner noch mal zwei jahre mehr auf dem buckel. bin aber schon am prospekte blättern ;)
gruß
markus
(Beitrag nachträglich am 20., August. 2002 von boothby81 editiert) |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Dienstag, den 20. August, 2002 - 16:27: |
|
Hallo Markus,
du hast natürlich vollkommen recht, ich hatte die fixe Idee im Hinterkopf, dass der ganze Zehnerblock 510-519 nicht verwandelbar ist. Aber 511 >> 521, 513 >> 503, 517 >> 547 und eben 519 >> 509, alle sind verwandelbar!
@Zaph: Ich kann mich Markus nur anschließen. Es passt nicht zu deiner Definition eines "maximalen Run" vom 18. August, 23:44. Außerdem hab ich jetzt bemerkt, dass ja viele Runs der Länge n = 1 auftreten müssen (z.B. die isolierten 511, 513 und 517).
Bezüglich American Mathematical Monthly: Das wär aus meiner Sicht nur der halbe Spaß. Mir gefällt es, selbst interaktiv mitzumachen, eigene Ideen und auch eigene Fehler zu diskutieren. Ich sehe das nicht ausschließlich ergebnisorientiert, der Weg ist das Ziel!
Viele Grüße
sol@ti
|
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1323
Registriert: 07-2000
| | Veröffentlicht am Dienstag, den 20. August, 2002 - 16:46: |
|
Hm, habe ich jetzt ein Brett vorm Kopf?
201 -> 211 prim
202 -> 002 prim
203 -> 003 prim
200 und 204 können nicht verwandelt werden, da für keine Ziffer X eine der Zahlen X00, X04, 2X0, 2X4, 20X prim ist.
Wo ist mein Fehler?
Und: Runs der Länge n = 1 stehen nicht mit n = 1 mod 10 im Widerspruch.
(Beitrag nachträglich am 20., August. 2002 von zaph editiert) |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Dienstag, den 20. August, 2002 - 17:04: |
|
Natürlich! SpockGeigers führende Null - die hatte ich völlig vergessen. Und n = 1 war nicht als Widerspruch gedacht, sondern als mein eigenes Aha-Erlebnis.
Nochmal danke für deine geduldige Erklärung
sol@ti
|
Onkel Murray (murray)
Erfahrenes Mitglied
Benutzername: murray
Nummer des Beitrags: 137
Registriert: 10-2001
| | Veröffentlicht am Dienstag, den 20. August, 2002 - 19:58: |
|
Ahh, die Verwirrung habe wohl ich angestiftet
Natürlich ist z.B. 201 in eine Primzahl überführbar, aber die Zahl 200 ist es nicht, wenn man nur ihre Einerstelle durch 1,3,7 oder 9 ersetzt.
201 ist im Bezug auf eine Änderung an der Einerstelle genauso gut wie 200 oder 204. Im Bezug zu Änderungen an anderen Stellen aber nicht mehr. Weswegen wir nur Zahlen suchen müssen, die bei einer Änderung der Einerstelle nicht zu einer Primzahl gemacht werden können - besagte 10'er-Löcher (siehe oben) und welche EINDEUTIG durch Änderung einer anderen Stelle auch nicht in eine Primzahl überführbar ist. Womit diese Zahl nur auf 0 enden kann.
Klar, 204 endet auf 4. Aber beim ersetzen der Einerstelle gibt es dort nur 200,201,202,203, ... , 209. Die erste Zahl in diesem 10'er-Loch ist also die 200 oder auch die Zahl die auf 0 endet.
Und das ist immer so
Das heißt aber auch, das der Abstand zwischen 10'er-Löchern immer durch 10 teilbar ist (also m | 10).
Man kann also alle bisher gefundene Zahl auf 10 normieren.
IMHO ist 280<=m<=1270 (wobei ich das mit der 1272 irgendwie nicht nachvollziehen kann).
Murray
|
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 92
Registriert: 03-2001
| | Veröffentlicht am Dienstag, den 20. August, 2002 - 21:37: |
|
hi murray.
ich konnte deiner argumentation zwar nicht ganz folgen, aber dein ergebnis ist nicht richtig.
klar ist: grob gesehen befindet sich der längste run aus verwandelbaren zahlen immer zwischen zwei 10er-löchern. als beispiel verwende ich unsere bis jetzt größte stelle (dort sind die 10er-löcher 15200-15209 und 15480-15489) sowie die notation von zaph (x läßt sich nicht umwandeln, x+1, ..., x+n lassen sich umwandeln, x+n+1 nicht).
nun betrachten wir x, die letzte zahl vor dem run. x stammt aus dem ersten 10er-loch und hat die einerstelle 8 oder (unwahrscheinlich) 9. im beispiel ist dies 15208. 15209 läßt sich z.b. in die primzahl 15259 verwandeln. es ist theoretisch möglich, daß die zahl mit endung 9 nicht umgewandelt werden kann, dies ist aber sehr unwahrscheinlich, da dann alle zahlen, die durch ersetzung einer anderen ziffer als der einerstelle aus der 'endung-9'-zahl hervorgehen können, nicht prim sein dürfen.
x+n+1, die erste zahl nach einem run, die sich also wiederum nicht in eine primzahl umwandeln läßt, ist die zahl mit der einerstelle 0 aus dem zweiten 10er-loch.
d.h.
x mod 10 = 8 (oder 9)
x+n+1 mod 10 = 0
=> n mod 10 = 1 (oder 0)
n = m-1
=> m mod 10 = 2 (oder 1)
gruß
markus |
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1324
Registriert: 07-2000
| | Veröffentlicht am Mittwoch, den 21. August, 2002 - 00:21: |
|
@sol@ti: Danke für deinen Dank für meine "geduldige Erklärung" ;-))
Noch mal zum Monthly. Ich meinte natürlich nicht, dass du deine Fragen STATTDESSEN dort veröffentlichen solltest. Dann wäre ich wirklich beleidigt ;-)
Finde es total klasse, über solche neuen Ideen nachzudenken!
Nur in diesem Falle (so wie auch in einigen anderen früheren Fällen), wo wir uns gemeinsam langsam an eine Lösung herantasten und eine endgültige Lösung nicht in unserem Vermögen scheint, wäre es doch interessant zu wissen, ob wir alleine so "doof" sind, oder ob irgendwo auf der Welt jemand ist, der uns auf die Sprünge helfen kann.
Schönen Gruß
Zaph |
clara
Unregistrierter Gast
| | Veröffentlicht am Mittwoch, den 21. August, 2002 - 12:31: |
|
Hi,
ich komme wohl nicht mehr so ganz mit. Suchst ihr jetzt nur nach einer einfachen bzw. eleganten Lösung?
Wenn ihr alle Zahlen bis zum Produkt der Primzahlen von 2-113 durchprobiert und kein größeres m findet, ist der Beweis doch erbracht.
Oder habe ich da einen Denkfehler drin?
gruß clara |
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 93
Registriert: 03-2001
| | Veröffentlicht am Mittwoch, den 21. August, 2002 - 15:26: |
|
hi clara.
es stimmt schon, was du sagst. aber es stellt eben kein kleines problem dar, alle zahlen bis 3,16*10^46 auf 10er-löcher durchzutesten. so zumindest meine sicht der dinge. da würde auch zaph's pc nicht mehr mitmachen ;).
gruß
markus |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Mittwoch, den 21. August, 2002 - 16:22: |
|
Hallo,
melde eine verbesserte Abschätzung nach Markus' Methode: 530-539, 1260-1269, 1460-1469, 2190-2199 und dann wieder 3260-3269 werden durch die Primzahlen 2, 3, 5, 7 und 13 "gestrichen". Die Schablonenlänge beträgt 2*3*5*7*13 = 2730. Der längst Run liegt zwischen 2198+k*2730 und 3260+k*2730.
272 <= m <= 1062
@Zaph: Ich überlasse es dir gern, dieses Problem bei Monthly einzureichen :-)
@clara: Es ist einfach praktisch nicht möglich den Bereich bis 3,16*10^46 zu überprüfen. Selbst wenn man 10^12 Zahlen pro Sekunde prüfen könnte (wird in einigen Jahren vielleicht möglich sein) bräuchte man 10^27 Jahre.
Viele Grüße
sol@ti
|
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 94
Registriert: 03-2001
| | Veröffentlicht am Mittwoch, den 21. August, 2002 - 22:42: |
|
hi.
die obergrenze 1062 ist auch die kleinste, die mit dieser methode zu finden ist, da alle primzahlkombinationen, die für 10er-löcher unterhalb von 1070 verantwortlich sind, jeweils größere runs als 1070 erzeugen.
um die obergrenze also noch weiter zu reduzieren, ist nun ein neus verfahren notwendig. andernfalls war's das...
gruß
markus |
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1326
Registriert: 07-2000
| | Veröffentlicht am Samstag, den 24. August, 2002 - 18:58: |
|
Ein bisschen geht noch :-)
Die Markus-Sol@ti-Methode lässt sich auf die Primzahlen 2, 3, 5, 7, 11, 13 (Produkt 30030 - die Zahl, die auch schon von clara vorgeschlagen wurde) ausweiten.
Gesucht sind Zahlen z, die auf 0 enden, sodass z, z+1, ... z+9 je mindestens einen Primfaktor <= 13 Enthalten.
Bis 30030 sind das z = 200, 510, 530, 1260, 1460, 1790, 2100, 2190, 2510, 2820, 3260, 3750, 3990, 4100, 4190, 4410, 4820, 4920, 5130, 5750, 5990, 6410, 6720, 6920, 7110, 7130, 7440, 7650, 8040, 8720, 9030, 9110, 9440, 9450, 9650, 9750, 10040, 10380, 11030, 11340, 11400, 11450, 11750, 12060, 12180, 12330, 12380, 13110, 13340, 13400, 13650, 14060, 14180, 14330, 14370, 14910, 15110, 15650, 15690, 15840, 15960, 16370, 16620, 16680, 16910, 17640, 17690, 17840, 17960, 18270, 18570, 18620, 18680, 18990, 19640, 19980, 20270, 20370, 20570, 20580, 20910, 20990, 21300, 21980, 22370, 22580, 22890, 22910, 23100, 23300, 23610, 24030, 24270, 24890, 25100, 25200, 25610, 25830, 25920, 26030, 26270, 26760, 27200, 27510, 27830, 27920, 28230, 28560, 28760, 29490, 29510, 29820
und dann wieder z = 30230.
Die größte auftretende Differenz ist 730. (Vier Mal: 730 = 1260 - 530 = 13110 - 12380 = 17640 - 16910 = 29490 - 28760)
Ein Run bis 30230 darf keine der Zahlen z, z+1, ..., z+8 enthalten, kann also maximal die Länge 721 haben.
Somit hat JEDER Run die Länge <= 721.
Somit m <= 722.
(Übrigens ein Zahlendreher von 272 ;-) |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Sonntag, den 25. August, 2002 - 11:19: |
|
Super Zaph,
und die (richtigerweise so genannte) Markus-Clara-Methode müsste mit deinem Programm theoretisch sogar bis 2*3*5*7*11*13*17*19*23 ~ 223 Mio. anwendbar sein.
Viele Grüße
sol@ti
|
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1328
Registriert: 07-2000
| | Veröffentlicht am Sonntag, den 25. August, 2002 - 11:39: |
|
Das hatte ich sogar ausprobiert - bringt aber nichts neues.
Um die 271-er Lücke einzuengen, müssen auf jeden Fall diejenigen Primzahlen hinzugenommen werden, die dafür verantwortlich sind, dass die Lücke nicht größer ist.
Das sind 23 (wegen 15203), 67 (15209), 113 815480) und 17 (15487).
2, 3 und 5 natürlich sowieso.
Aber es ist schon 2 * 3 * 5 * 17 * 23 * 67 * 113 = 88.807.830 - und damit sind meine Kapazitäten fast erschöpft.
Ich fürchte, auf die 7, 11 oder 13 wird man nicht verzichten können - und damit sind wir über 100.000.000.
Mal sehen, ob das noch geschickter zu programmieren ist ... |
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 98
Registriert: 03-2001
| | Veröffentlicht am Freitag, den 20. September, 2002 - 01:30: |
|
hallo nochmal.
zaph, hast du die aufgabe eigentlich an das american mathematical monthly geschickt? gab's/gibt's da irgendeine antwort/reaktion? ich hoffe, du hältst uns up-to-date.
hab mir die aufgabe die letzten tage nochmal vorgenommen, mit neuem pc und neuem algorithmus bin ich zwar auch an die 100 mio herangekommen, habe aber nichts neues mehr rausgekriegt.
nur der vollständigkeit halber wollte ich aber noch folgendes anmerken (ich weiß nicht, ob du das bereits ausgenutzt hast, erwähnt wurde es nirgends): innerhalb ihrer periode (p1*p2*..*pn) sind die zehnerlöcher 'symmetrisch' zur mitte der periode, d.h. man muß die größte differenz nur bis dorthin suchen. halbiert zwar den rechenaufwand, aber da dieser für hinzukommende primzahlen um das 23- oder 67-fache o.ä. ansteigt, bringt uns das auch nicht wirklich weiter.
gruß
markus |
|
