Die Mathe-Redaktion - 23.07.2018 13:52 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 541 Gäste und 21 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von viertel GrafZahl
Mathematik » Schulmathematik » Beweisübung Teil III (Legendre I)
Thema eröffnet 2018-02-22 09:34 von
Bekell
Druckversion
Druckversion
Antworten
Antworten
Seite 5   [1 2 3 4 5 6 7]   7 Seiten
Autor
Schule Beweisübung Teil III (Legendre I)
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4054
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.160, eingetragen 2018-03-13

\(\begingroup\)
2018-03-13 07:23 - Bekell in Beitrag No. 159 schreibt:
kann man in Maple die Ausgabe noch optimieren, zb. in 20-ger Reihen nummeriert, so daß man sofort die Standortnummern der 0-Stellen erkennt, zb. die Nullen schwärzen?

Ich werde mir ansehen, ob da ohne zu großen Aufwand eine besondere Kennzeichnung der Nullen möglich ist, farblich geht das aber glaube ich nicht so einfach.

In der Logik dieser Untersuchung liegt, daß es dann auch irgendwann Intervalle gibt, die mit weniger PZ als <n dann 0 Löcher produzieren, oder?

Naja, hast du dir den oben gerechneten Fall $n=73$ genauer angesehen? Das ist doch gleich ein Beispiel, wo man für eine "volle Belegung" dann nicht mehr alle Primzahlen bis $73$ braucht, sondern schon eine von den "hohen" weglassen kann.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 1627
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.161, eingetragen 2018-03-13


sehr gut weird,


laut OEIS soll man ja mit prim n<=73 sogar 94felder abdecken können

ich hab also das gebiet erweitert, in diesem falle nur nach rechts, und von deinem ersten pattern die 47;53;59;61;67 durch probieren, so plaziert dass sie rechts gut weitere löcher abdecken

plaziert man dann 71+73 beliebig auf die letzten felder erhalte ich immerhin 83 felder abgedeckt

94 hätten immer noch 1-loch, ich vermute zur vollabdeckung müssen dann auch nochmal kleinere primzahlen als die 47 neu plaziert werden

insbesondere wundere ich mich über die pos.58 die gleichzeitig von 3;5;7;11;13 abgedeckt ist

die beiden anderen angegebenen pattern für n=73 hab ich noch nicht genauer angeschaut,
worin unterscheiden sich die drei pattern?

auch mit der startzahlermittlung bin ich nicht viel weiter... obiges bild ist eher hingeschoben als berechnet


haribo

nachtrag: die 67 von pos 20 auf die pos 11 geschoben wären sogar 86 abgedeckte felder






  Profil  Quote  Link auf diesen Beitrag Link
Bekell
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.09.2008
Mitteilungen: 1242
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.162, vom Themenstarter, eingetragen 2018-03-13


2018-03-13 07:59 - weird in Beitrag No. 160 schreibt:
2018-03-13 07:23 - Bekell in Beitrag No. 159 schreibt:
kann man in Maple die Ausgabe noch optimieren, zb. in 20-ger Reihen nummeriert, so daß man sofort die Standortnummern der 0-Stellen erkennt, zb. die Nullen schwärzen?

Ich werde mir ansehen, ob da ohne zu großen Aufwand eine besondere Kennzeichnung der Nullen möglich ist, farblich geht das aber glaube ich nicht so einfach.

@Weird

ich bin grade am Noten austauschen mit dem Mapl-Vertreter, aber ich habe den Eindruck, das es mathematischer zwar schneller als C++ ist, aber was die Ausgabegestaltungsmöglichkeit für unsere Zwecke betrifft, ich da gegenüber C++ vom Regen in die Traufe komme. Der Preis für die Personal Edition ist 285,60€. Eine Probier-Version gibt es nicht.

Ich will nicht, daß der Programmieraufwand für die Gestaltung der Ausgabe den Aufwand zur Berechnung der Ergebnisse übertrifft. Oder ist das zuviel von mir verlangt...?

Bei Mathematika gibt es sowas, z. B.: www.mathe-online.at/Mathematica/
allerdings kann man da nur Umformen, was durchaus sehr nützlich ist, .... ich jedenfalls kann die Programmierbefehle nicht entdecken. Und was die Ausgabe betrifft, sollte das Zahlen einfärben nach bestimmten Eigenschaften eigentlich Standard sein.




-----------------
Das Schwierige ist nicht die Mathematik. Schwierig ist es zu formulieren, daß man selber versteht, was man sieht und die anderen auch!



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2774
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.163, eingetragen 2018-03-13


Wie gesagt: Es gibt nach der Bemerkung zu der zitierten OEIS-Folge eine unendliche Serie von Werten n, dass man Intervalle der Länge 2n finden kann, die mit nur den ersten <math>\frac{n}{\log n}</math> abdeckbar sind, in dem Sinne, dass jede Zahl in diesem Intervall durch mindestens eine der ersten <math>\frac{n}{\log n}</math> Primzahlen teilbar ist. Insbesondere reichen dafür auch die Primzahlen <math>\leq n</math>.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 1627
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.164, eingetragen 2018-03-13


@cyrix, aber selbst wenn man weiss (oder glaubt) das es ne lösung gibt um 94 felder mit n<=73 abzudecken, ist doch die frage ob man die lösung findet bzw hier wie geschickt weird´s algorithmus funktioniert, er dachte ja vor kurzem noch das es mit seinem rechner nicht möglich wäre,über n<=23 hinauszukommen

in der umgebung von weird´s lösungen finde ich keine derartige abdeckung, das könnte dafür sprechen dass es, neben den drei angegebenen, noch weitere basis-pattern geben könnte für die kleinen zahlen welche mehrere positionen abdecken???

haribo



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4054
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.165, eingetragen 2018-03-13

\(\begingroup\)
2018-03-13 11:56 - haribo in Beitrag No. 161 schreibt:
laut OEIS soll man ja mit prim n<=73 sogar 94felder abdecken können

Bislang bin ich noch nicht auf so eine Belegung mit 94 Feldern gekommen, allerdings hab ich noch noch nicht alle Möglichkeiten ausgeschöpft.


die beiden anderen angegebenen pattern für n=73 hab ich noch nicht genauer angeschaut,
worin unterscheiden sich die drei pattern?

Schaut man sich nur jeweils die genau $7$ Positionen an, wo es Unterschiede in diesen drei patterns gibt, so würden die $3$ Listen zu je $73$ Elementen schrumpfen auf

$[0,0,31,37,0,0,31,37]$
$[31,0,0,37,31,0,37]$
$[31,37,0,0,31,37,0]$

Offensichtlich sind also hier $31$ und $37$ in gewisser Weise miteinander vertauschbar, was also dann eine weitere Symmetrie ins Spiel bringt, die ich aber unmöglich auch noch "herausfiltern" kann.

Bin dzt. wie gesagt noch am überlegen, welche Änderungen am Programm noch sinnvoll wären, von einer besseren Kennzeichnung der 0-Positionen mal abgesehen. Vor allem die Frage, ob mir da bei meinem "Greedy-Algorithmus" auch wirklich Lösungen durch den Lappen gehen, würde mich jetzt schon noch interessieren.

@Bekell

Was dir ein gutes CAS wert ist, musst du natürlich schon selbst entscheiden. Deinem Vergleich von Maple mit C++ kann ich jedenfalls in keiner Weise zustimmen, eigentlich "hinkt" er von vornherein, da man m.E. ein CAS jetzt nur mit einem anderen CAS vergleichen kann.

[Die Antwort wurde nach Beitrag No.163 begonnen.]
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 1627
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.166, eingetragen 2018-03-13


2018-03-13 19:42 - weird in Beitrag No. 165 schreibt:
Vor allem die Frage, ob mir da bei meinem "Greedy-Algorithmus" auch wirklich Lösungen durch den Lappen gehen, würde mich jetzt schon noch interessieren.


es scheinen lokale minima zu sein die man damit findet, ich hab eine 94 breite n<=73 4-loch abdeckung bei der jeder einzelne wechsel die abdeckung verschlechtert, also bräuchte es wohl ringtauschaktionen oder eben zufällige sprungfunktionen um aus diesem lokalen minimum zu entkommen

hergestellt hab ich diese abdeckung aus ner zufalsabdeckung und dann schrittweise verbesserungen in einer zufälligen reihenfolge für einzelne prims gesucht... alles mehr oder weniger händisch aber es waren nicht so sehr viele schritte ~50

haribo



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 693
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.167, eingetragen 2018-03-13

\(\begingroup\)
Hallo,

ich habe weird's optimierte Legendre-Funktion aus Beitrag #158 in Mathematica-Syntax übersetzt und diese Funktion LegendreWeirdOpt[n] genannt. Hier ist sie:
Mathematica
f[x_List] := Module[{z}, Return[Sum[Sign[x[[z]]], {z, 1, Length[x]}]]]
LegendreWeirdOpt[n_] := 
  Module[{c, i, j, h, m, M=0, M0, p=2, s, ss, S = {Table[0, {k, 1, n}]}, T, U, V={}},
    While[True,
      T={}; M0 = M;
      p = NextPrime[p];
      If[p > n, Goto["EndWhile"]];
      For[a = 1, a <= Length[S], a++, 
        s = S[[a]];
        m = 0;
        For[i = 1, i <= p, i++, 
          ss = s;
          For[j = i, j <= n, j = j + p,
            If[s[[j]] == 0, ss[[j]] = p];
          ];
          c = f[ss];
          If[c > m, U = {}];
          If[c >= m, m = c; U = Append[U, ss]]
        ];
        M = Max[M, m];
        T = FlattenAt[Append[T, U], Length[T] + 1];
      ];
      ToExpression[StringJoin["CountQ[l_List]:=Module[{},If[Length[l]-Count[l,0]==", 
        ToString[M], ",True,False]]"]];
      T = Select[T, CountQ];
      If[M == M0 + 1, M = M0; V = Append[V, p], S = T]
    ];
    Label["EndWhile"];
    h = Max[n-M-Length[V], 0];
    S = Sort[S];
    T = {};
    Print["The subsequent patterns have got only ", ToString[h], " hole(s) actually, ",
      "as you could replace 0-locations by any prime in ", ToString[V], ".\n"];
    For[a = 1, a <= Length[S], a++, 
      s = S[[a]];
      If[MemberQ[T, s] || MemberQ[T, Table[s[[-k]], {k, 1, Length[s]}]], Continue[]];
      Print[s, "\n"];
      T = Append[T, s]
    ];
    Return[]
  ]

Die Funktion läuft soweit ganz gut und bestätigt die drei Tests, die weird damit gemacht hat (für $n=19$, $n=43$, $n=73$). Die Zeitmessungen ergeben wiederum sehr rasante Berechnungszeiten:
0.015625 Sekunden für $n=19$
0.078125 Sekunden für $n=43$
1.3125 Sekunden für $n=73$

Ich habe u. a. auch noch $n=41$ untersucht. Hierbei gibt es 1-löchrige Maximalbelegungen, aber interessanterweise sind es nicht die drei höchsten Primzahlen $\leq$ 41, die hier flexibel zu verteilen sind, sondern die höchste, zweithöchste und vierthöchste (29, 37, 41). War mir gar nicht klar, dass auch ein solcher Fall auftreten kann.

Des Weiteren möchte ich aber auch noch auf zwei grundsätzliche Problemfälle hinweisen, die auftreten können.

1. Der Fall $n=18$:

Hier gibt es bei vollständiger Suche inklusive Symmetrien 13 Lösungen, ohne Symmetrien dagegen 7. Die Funktion LegendreWeirdOpt[18] liefert aber nur 6 Lösungen davon. Folgende Lösung wird NICHT durch den Algorithmus erfasst:
17, 3, 13, 11, 3, 7, 5, 3, 0, 0, 3, 5, 7, 3, 11, 13, 3, 17


2. Der Fall $n=7$:

Hier gibt es bei vollständiger Suche inklusive Symmetrien 18 Lösungen, ohne Symmetrien dagegen nur 9. Die Funktion LegendreWeirdOpt[7] liefert jedoch 12 Lösungen, da trotz des Versuchs Symmetrien zu vermeiden, durch die Lösungsangaben doch nochmal 3 Symmetriefälle entstehen. Die tatsächlichen Lösungen hier sind:
0, 5, 3, 0, 7, 3, 5
0, 5, 3, 7, 0, 3, 5
7, 5, 3, 0, 0, 3, 5
3, 0, 0, 3, 5, 7, 3
3, 0, 0, 3, 7, 5, 3
3, 0, 5, 3, 0, 7, 3
3, 0, 5, 3, 7, 0, 3
3, 0, 7, 3, 0, 5, 3
3, 5, 0, 3, 0, 7, 3

Die Funktion LegendreWeirdOpt[7] gibt hier jedoch vor, man könne um alle Lösungen zu finden, die Maximalbelegungen sind, die Anordnung
3,0,0,3,0,0,3
zugrundelegen und die Primzahlen 5 und 7 auf die vier 0-Positionen verteilen, was fälschlicherweise zu 12 Lösungen nach diesen Schemata führt:
5700, 7500, 5070, 7050, 5007, 7005, 0570, 0750, 0507, 0705, 0057, 0075

Dies führt jedoch dreimal zu Dopplungen (man denke auch daran, dass Lösungen, die rückwärts gelesen eine schon bekannte Vorwärts-Lösung ergeben, auszusortieren sind), so dass es am Ende nur 9 verschiedene Lösungen anstatt 12 sind.


Fazit:
Es scheint also gar nicht so einfach zu sein, Symmetriefälle wirksam auszuschließen und gleichzeitig keine Lösungen zu übersehen, wie z. B. die eben beschriebenen Fälle $n=7$ und $n=18$ zeigen. In weiteren Fällen, die ich untersucht habe, stimmte die von LegendreWeirdOpt[n] ermittelte Anzahl verschiedener Lösungen jedoch mit der tatsächlichen Anzahl Lösungen ohne Symmetrien überein.

In nachfolgender Tabelle habe ich nochmal die Ergebnisse meiner vollständigen Suche inklusive Symmetrien den Ergebnissen der Funktionen LegendreWeird[n] aus Beitrag #133 und LegendreWeirdOpt[n] gegenübergestellt. Insbesondere habe ich in der Tabelle unter der Angabe der tatsächlichen Anzahl Lösungen ohne Symmetrien die Fälle $n=7$ und $n=18$ nochmals festgehalten, bei denen es Diskrepanzen gibt, aber auch einige weitere Fälle, in denen die Zahlen der beiden letzten Tabellenspalten übereinstimmen. Alle Fälle von $n=3$ bis $n=22$ hab ich jedoch nicht untersucht, da dies teilweise sehr aufwendig ist (Edit: mittlerweile alle genannten Fälle untersucht). Mir geht es vor allem darum, auf die Fälle $n=7$ und $n=18$ hinzuweisen.
Tabelle
  n | Anzahl Lösungen     | Anzahl Lösungen   | Anzahl Lösungen     | Anzahl Lösungen
    | Maximalbelegungen   | Maximalbelegungen | Maximalbelegungen   | Maximalbelegungen
    | vollständige Suche  | LegendreWeird[n]  | LegendreWeirdOpt[n] | OHNE Symmetrie
    | inklusive Symmetrie |                   | mit teilweise       |
    |                     |                   | ungewollten Symme-  | 
    |                     |                   | trien (a) oder feh- | 
    |                     |                   | lenden Lösungen (b) | 
    |                     |                   | oder falschen       |
    |                     |                   | Lösungen (c)        |
----+---------------------+-------------------+---------------------+-------------------
  3 |                   3 |                 3 |                   3 | 2*                    
  4 |                   1 |                 1 |                   1 | 1*
  5 |                   6 |                 6 |                   3 | 3*
  6 |                   1 |                 1 |                   1 | 1*
  7 |                  18 |                12 |             (a)  12 | 9 
  8 |                   7 |                 6 |             (b)   3 | 4*
  9 |                   2 |                 2 |                   1 | 1
 10 |                   1 |                 1 |                   1 | 1
 11 |                  12 |                12 |                   6 | 6*
 12 |                   1 |                 1 |                   1 | 1
 13 |                  60 |                48 |             (b)  24 | 30*
 14 |                  13 |                12 |             (b)   6 | 7*
 15 |                   2 |                 2 |                   1 | 1
 16 |                   1 |                 1 |                   1 | 1
 17 |                  48 |                24 |             (b)  12 | 24*
 18 |                  13 |                12 |             (b)   6 | 7 
 19 |                  12 |                12 |                   6 | 6
 20 |                 151 |               120 |             (b)  60 | 76*
 21 |                   8 |               480 |             (c) 240 | 4*
 22 |                   1 |               440 |             (c) 220 | 1*
 
Legende:
* nachträglich ergänzt    

LG Primentus

[Die Antwort wurde nach Beitrag No.165 begonnen.]
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2774
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.168, eingetragen 2018-03-13


2018-03-13 22:02 - haribo in Beitrag No. 166 schreibt:

es scheinen lokale minima zu sein die man damit findet, ich hab eine 94 breite n<=73 4-loch abdeckung bei der jeder einzelne wechsel die abdeckung verschlechtert, also bräuchte es wohl ringtauschaktionen oder eben zufällige sprungfunktionen um aus diesem lokalen minimum zu entkommen

Das klingt für mich danach, als ob Simulated Annealing hier ganz gut funktionieren könnte.

Jedenfalls sind wir hier bei einer Optimierungsaufgabe mit einer komplexen (i.S. von "nicht einfachen") Zielfunktion. Ich würde auch mal stark vermuten, dass der Spaß - für ein n ein Intervall maximaler Länge zu finden, in dem jede Zahl durch mindestens eine der ersten n Primzahlen teilbar ist - NP-schwer ist. Ich sehe nämlich keinen sinnvollen Ansatz, der deutlich über Ausprobieren sämtlicher Restklassen-Kombinationen hinaus geht...


Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 1627
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.169, eingetragen 2018-03-13


@primentus

kannst du leicht n=83 eingeben aber dabei die primzahlen auf <73 beschränken
also versuchen ob du meine abdeckung gemäss #161 reproduzieren kannst?
(wenn man das bild anklickt/anzeigt werden die zahlen etwas besser lesbar)

please, nur wenns kein aufwand is...

lg haribo



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 693
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.170, eingetragen 2018-03-13

\(\begingroup\)
Hallo haribo,

genau Deine Abdeckung konnte ich jetzt auf die Schnelle nicht reproduzieren, aber dafür einen ähnlich gelagerten Fall. Die LegendreWeirdOpt-Funktion gibt für $n=83$ nur einen Abdeckungstyp aus und zwar
3,7,5,3,19,13,3,5,7,3,43,47,3,11,41,3,29,5,3,37,53,3,5,19,3,17,23,3,0,7,3, 13,5,3,31,11,3,5,0,3,0,0,3,7,13,3,11,5,3,23,7,3,5,43,3,41,37,3,47,17,3,19, 5,3,7,31,3,5,11,3,13,7,3,53,29,3,17,5,3,11,19,3,5

Hiermit können 0-löchrige Abdeckungen produziert werden, indem man auf die verbliebenen vier Nullen noch die Primzahlen 59, 61, 67 und 71 verteilt, welche allesamt $\leq$ 73 sind. Es gibt also $n=83$ lange 0-löchrige Abdeckungen, die sogar ohne die Primzahlen 73, 79 und 83 auskommen.

Wie in meinem letzten Beitrag geschrieben, könnte es aber durchaus sein, dass die verwendete Funktion weitere gültige Lösungen übersieht.

LG Primentus

Edit:
Und hier ist noch eine 0-löchrige Abdeckung für $n=94$, die mit den Primzahlen $\leq$ 79 auskommt:
3,5,17,3,73,0,3,41,7,3,13,5,3,23,11,3,5,19,3,17,53,3,7,13,3,11,5,3,37,7, 3,5,47,3,0,0,3,31,29,3,43,5,3,7,0,3,5,11,3,13,7,3,0,17,3,19,5,3,11,23,3, 5,13,3,7,37,3,29,31,3,17,5,3,53,19,3,5,73,3,47,11,3,23,43,3,7,5,3,13,41, 3,5,7,3
... wenn man auf die fünf Nullen noch die Primzahlen 59, 61, 67, 71, 79 verteilt. Mit den Primzahlen $\leq$ 73 reicht es immerhin noch für eine 1-löchrige Abdeckung.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Bekell
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.09.2008
Mitteilungen: 1242
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.171, vom Themenstarter, eingetragen 2018-03-14


2018-03-13 22:25 - cyrix in Beitrag No. 168 schreibt:
 - NP-schwer ist.

@Cyrix
de.wikipedia.org/wiki/NP-Schwere

Du meinst also, es ist damit nicht möglich, ein Programm zu schreiben, daß für alle n kleiner einer Grenze die Anzahl der möglichen Lösungen ausspuckt. Und es wird auch keine Formel geben, mit der man die Anzahl der Lösungen, ähnlich, wie bei der Teileranzahlfunktion, wird berechnen können.


-----------------
Das Schwierige ist nicht die Mathematik. Schwierig ist es zu formulieren, daß man selber versteht, was man sieht und die anderen auch!



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4054
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.172, eingetragen 2018-03-14

\(\begingroup\)
@Primentus

Wieder einmal vielen herzlichen Dank für deine wertvolle Hilfe bei der Untersuchung der Ausgaben des Programms in der Mathematica-Version!  wink

Die von dir zitierten Fälle $n=7$ und $n=18$ zeigen schon mal, dass das Programm nicht mehr alle optimalen Lösungen findet, wenngleich die Mindesanzahl der Löcher in diesen Fällen noch stimmt.

Man sieht übrigens gerade am Fall $n=7$ sehr schön, dass man hier auf die optimale Verlegung der $3$-Leiter verzichten kann, da man diesen "Rückstand" mit der $5$-Leiter dann wieder aufholt. Allerdings stimmt es nicht, dass hier auch nicht symmetrische Lösungen mit ausgegeben werden, das traf nur für das alte Programm zu. Das Programm sagt ja nur, dass man zwei der vier 0-Stellen in $[3,0,0,3,0,0,3]$ durch die Primzahlen $5$ und $7$ ersetzen soll, aber nicht wie. Wenn du also Wert darauf legst, dass symmetrische Lösungen nicht mitangeführt werden, dann musst du sozusagen auch bei deiner Belegung der vier 0-Stellen selbst darauf achten. Dies hängt hier auch damit zusammen, dass diese vier $0$-Stellen symmetrisch zur Mitte liegen, was normalerweise nicht der Fall ist.

Ansonsten muss ich mir das Ganze selber noch genauer ansehen, ev. baue ich ja noch eine Relaxation der greediness des Programms mit ein. Auch eine Anzeige von potenziellen Fortsetzungen von Lösungen über den linken oder rechten Rand hinaus wäre denkbar. Im Moment bin ich aber gerade sehr "busy" und muss warten, bis ich wieder etwas mehr Zeit "in einem Stück" habe.  frown
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 1627
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.173, eingetragen 2018-03-14

\(\begingroup\)
2018-03-13 23:27 - Primentus in Beitrag No. 170 schreibt:
Hallo haribo,

genau Deine Abdeckung konnte ich jetzt auf die Schnelle nicht reproduzieren, aber dafür einen ähnlich gelagerten Fall. Die LegendreWeirdOpt-Funktion gibt für $n=83$ nur einen Abdeckungstyp aus und zwar
3,7,5,3,19,13,3,5,7,3,43,47,3,11,41,3,29,5,3,37,53,3,5,19,3,17,23,3,0,7,3, 13,5,3,31,11,3,5,0,3,0,0,3,7,13,3,11,5,3,23,7,3,5,43,3,41,37,3,47,17,3,19, 5,3,7,31,3,5,11,3,13,7,3,53,29,3,17,5,3,11,19,3,5

Hiermit können 0-löchrige Abdeckungen produziert werden, indem man auf die verbliebenen vier Nullen noch die Primzahlen 59, 61, 67 und 71 verteilt, welche allesamt $\leq$ 73 sind. Es gibt also $n=83$ lange 0-löchrige

nimmt man noch die 73 dazu wie ich es ja auch gemacht hatte, dann ist es sogar ne 88er abdeckung, also immerhin besser als ich es händisch herstellen konnte!!! obwohl es ne sehr ähnliche grundstruktur hat (gleich bis 19 z.B.)

jetzt kommt ne interessante variante: die 23 oder 47 oder 53 kann man nun tauschen auf je einen anderen platz ohne das ergebnis zu verschlechtern.... und irgendwann kann man es mit solchen aktionen dann meist weiter verbessern.... ick hab aber auch leider heute keine zeit für diesen spass, der entgeht uns aber nicht (der spass!)

liebe grüsse
haribo

\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 693
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.174, eingetragen 2018-03-14

\(\begingroup\)
2018-03-14 12:09 - weird in Beitrag No. 172 schreibt:
@Primentus

Wieder einmal vielen herzlichen Dank für deine wertvolle Hilfe bei der Untersuchung der Ausgaben des Programms in der Mathematica-Version!  wink

Gern geschehen! smile

2018-03-14 12:09 - weird in Beitrag No. 172 schreibt:
Die von dir zitierten Fälle $n=7$ und $n=18$ zeigen schon mal, dass das Programm nicht mehr alle optimalen Lösungen findet, wenngleich die Mindesanzahl der Löcher in diesen Fällen noch stimmt.

Ja, also die von LegendreWeirdOpt[n] gefundenen Lösungen weisen zwischen $n=3$ und $n=22$ auf alle Fälle eine Mindestabdeckung auf, welche der Maximalabdeckung entspricht, d. h. die Anzahl Löcher ist auf jeden Fall korrekt (Edit: für $n=21$ und $n=22$ stimmt dies leider doch nicht). Nur werden nicht mehr zwangsläufig alle Lösungen gefunden, die dieser Maximalabdeckung entsprechen. Für $n>22$ kann ich wie gesagt keine Aussagen mehr diesbezüglich machen, da ich ab dann keine vollständigen Lösungen mehr vorliegen habe.

Ich werde mal noch schauen, dass ich zu weiteren $n$ bis 22 die Anzahl Lösungen aller Maximalabdeckungen ohne Symmetrien ermitteln kann, damit wir verlässliche Zahlen bezüglich aller Lösungen ohne Symmetriefälle haben.

2018-03-14 12:09 - weird in Beitrag No. 172 schreibt:
Das Programm sagt ja nur, dass man zwei der vier 0-Stellen in $[3,0,0,3,0,0,3]$ durch die Primzahlen $5$ und $7$ ersetzen soll, aber nicht wie. Wenn du also Wert darauf legst, dass symmetrische Lösungen nicht mitangeführt werden, dann musst du sozusagen auch bei deiner Belegung der vier 0-Stellen selbst darauf achten. Dies hängt hier auch damit zusammen, dass diese vier $0$-Stellen symmetrisch zur Mitte liegen, was normalerweise nicht der Fall ist.

Ja, $n=7$ ist hier möglicherweise ein Sonderfall, der aber dennoch des öfteren auftreten könnte. Das interessante ist jetzt, dass man denken könnte, dass von den 12 möglichen Verteilungen
5700, 7500, 5070, 7050, 5007, 7005, 0570, 0750, 0507, 0705, 0057, 0075
auf die vier Nullen der Konfiguration 3,0,0,3,0,0,3 letztlich 6 von 12 Fälle symmetriebedingt wegfallen würden. Tatsächlich ist das auch so, allerdings habe ich festgestellt, dass ich sogar noch etwas übersehen habe. Die Funktion LegendreWeirdOpt[7] enthält weder bei Betrachtung aller 12 Lösungen alle tatsächlichen 9 Lösungen, noch tut sie es bei der Betrachtung der lediglich 6 Lösungen (also ohne die Symmetriefälle):
3,5,7,3,0,0,3
3,7,5,3,0,0,3
3,5,0,3,7,0,3
3,7,0,3,5,0,3
3,5,0,3,0,7,3
3,7,0,3,0,5,3 entfällt
3,0,5,3,7,0,3
3,0,7,3,5,0,3 entfällt
3,0,5,3,0,7,3 entfällt
3,0,7,3,0,5,3 entfällt
3,0,0,3,5,7,3 entfällt
3,0,0,3,7,5,3 entfällt

Zusätzlich zu den 6 nicht entfallenden Lösungen gibt es nämlich folgende weitere Lösungen, die sogar von der Funktion übersehen werden:
0, 5, 3, 0, 7, 3, 5
0, 5, 3, 7, 0, 3, 5
7, 5, 3, 0, 0, 3, 5
Damit ist gezeigt, dass es auch Lösungen gibt, die nicht die anfängliche 3 besitzen. Das deckt sich mit dem Fall $n=18$, dessen nicht gefundene Lösung ebenfalls keine 3, sondern eine 17 zu Beginn hatte.

Aber mach dir keinen Stress, weird, im Endeffekt ist schon allein das Finden der richtigen Anzahl Löcher der tatsächlichen Maximalabdeckungen mit Ausgabe einiger Lösungsbeispiele dazu sehr viel wert. Wenn dabei ein paar Lösungen fehlen, ist das nicht allzu dramatisch. Selbst eine einzige 0-löchrige oder 1-löchrige Belegung, welche eine tatsächliche Maximalabdeckung für das gegebene $n$ zeigt, würde ja schon genügen.

2018-03-14 18:04 - haribo in Beitrag No. 173 schreibt:
nimmt man noch die 73 dazu wie ich es ja auch gemacht hatte, dann ist es sogar ne 88er abdeckung, also immerhin besser als ich es händisch herstellen konnte!!!

Ja, ich habe jetzt auch mal die von der Funktion vorgeschlagene Abdeckung händisch weitergesponnen, und ich komme dann auch auf eine n=88 lange 0-löchrige Abdeckung mit Primzahlen $\leq$ 73, indem man hinten noch 5 Positionen weiter macht:

3,7,5,3,19,13,3,5,7,3,43,47,3,11,41,3,29,5,3,37,53,3,5,19,3,17,23,3,0,7,3, 13,5,3,31,11,3,5,0,3,0,0,3,7,13,3,11,5,3,23,7,3,5,43,3,41,37,3,47,17,3,19, 5,3,7,31,3,5,11,3,13,7,3,53,29,3,17,5,3,11,19,3,5,13,3,7,0,3

Auf die fünf Nullen sind dann die Primzahlen 59, 61, 67, 71 und 73 zu verteilen.

2018-03-14 18:04 - haribo in Beitrag No. 173 schreibt:
jetzt kommt ne interessante variante: die 23 oder 47 oder 53 kann man nun tauschen auf je einen anderen platz ohne das ergebnis zu verschlechtern.... und irgendwann kann man es mit solchen aktionen dann meist weiter verbessern....

Das hab ich jetzt nicht ausprobiert, aber wie ich bei der n=88 langen Abdeckung gesehen habe, kann man da tatsächlich händisch auch ein bisschen weiterkommen. Ja, so bleibt der Spaß dann auch weiterhin erhalten. wink

Edit:
Aussagen bezüglich Anzahl Löcher von LegendreWeirdOpt für $n=21$ und $n=22$ korrigiert
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 693
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.175, eingetragen 2018-03-14

\(\begingroup\)
Hallo,

mittlerweile habe ich in der Tabelle des Beitrags #167 die noch fehlenden Werte in der letzten Spalte ergänzt (mit * gekennzeichnet).

Dabei haben sich die Fälle mit Diskrepanzen (dort mit (a) und (b) gekennzeichnet) noch weiter erhöht.

Insbesondere ist mir auch nochmals der hohe Unterschied der Werte der letzten beiden Tabellenspalten für $n=21$ und $n=22$ aufgefallen. Für zumindest diese beiden n-Werte muss ich nochmal zurückrudern, weird - dort stimmt die Anzahl Löcher, die durch LegendreWeirdOpt ermittelt wird, leider doch nicht mit der Anzahl Löcher der tatsächlichen Maximalbelegungen überein. Die Funktion ermittelt 3 Löcher, obwohl die Maximalbelegungen nur 2 Löcher haben. So kommt es zu einer falschen Anzahl von Lösungen, als auch die ermittelten Lösungen selbst sind keine Maximalbelegungen.
Das habe ich eben noch festgestellt.

LG Primentus
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4054
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.176, eingetragen 2018-03-14

\(\begingroup\)
2018-03-14 21:47 - Primentus in Beitrag No. 175 schreibt:
Insbesondere ist mir auch nochmals der hohe Unterschied der Werte der letzten beiden Tabellenspalten für $n=21$ und $n=22$ aufgefallen. Für zumindest diese beiden n-Werte muss ich nochmal zurückrudern, weird - dort stimmt die Anzahl Löcher, die durch LegendreWeirdOpt ermittelt wird, leider doch nicht mit der Anzahl Löcher der tatsächlichen Maximalbelegungen überein.

Ja, das ist natürlich sehr betrüblich.  frown

Diesen Fehler gab es allerdings auch schon in dem alten Programm, nur hatte ich da diese Werte nicht getestet. Ganz offensichtlich hat das Programm ein Problem damit, die von Bekell so propagierte "Zentralanordnung" zu finden, welche diese Fälle ja lösen würde. Werde mir also dann als Nächstes ansehen, ob man das irgendwie leicht reparieren kann.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 693
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.177, eingetragen 2018-03-14

\(\begingroup\)
2018-03-14 22:41 - weird in Beitrag No. 176 schreibt:
Ja, das ist natürlich sehr betrüblich.  frown

Diesen Fehler gab es allerdings auch schon in dem alten Programm, nur hatte ich da diese Werte nicht getestet. Ganz offensichtlich hat das Programm ein Problem damit, die von Bekell so propagierte "Zentralanordnung" zu finden, welche diese Fälle ja lösen würde. Werde mir also dann als Nächstes ansehen, ob man das irgendwie leicht reparieren kann.

Ja, das ist etwas schade, dass die Anzahl Löcher nicht immer korrekt ist.
Es sind meines Erachtens aber nicht nur die Zentralordnungen, die fehlen, sondern auch Fälle, in denen z. B. die 3 nicht am Anfang des Intervalls oder weder am Anfang noch am Ende steht, wie auch die drei Zusatzfälle bei $n=7$ zeigen (siehe Beitrag #174).

Falls Du für die Behebung des Problems vorab spicken magst, was die Maximalbelegungen für $n=21$ und $n=22$ sind, kannst Du hier im versteckten Bereich gucken (wobei ich hier jetzt extra darauf geachtet habe, statt der größten Primteiler $\leq n$ die kleinsten Primteiler $\leq n$ aufzulisten):

Maximalbelegungen für $n=21$:
mit Symmetrien (8 Lösungen):
11, 3, 5, 17, 3, 13, 0, 3, 7, 0, 3, 11, 5, 3, 19, 7, 3, 5, 13, 3, 17
17, 3, 13, 5, 3, 7, 0, 3, 5, 11, 3, 0, 7, 3, 19, 13, 3, 17, 5, 3, 11
17, 3, 13, 5, 3, 7, 0, 3, 5, 11, 3, 19, 7, 3, 0, 13, 3, 17, 5, 3, 11
19, 17, 3, 13, 11, 3, 7, 5, 3, 0, 0, 3, 5, 7, 3, 11, 13, 3, 17, 19, 3
3, 19, 17, 3, 13, 11, 3, 7, 5, 3, 0, 0, 3, 5, 7, 3, 11, 13, 3, 17, 19
11, 3, 5, 17, 3, 13, 0, 3, 7, 19, 3, 11, 5, 3, 0, 7, 3, 5, 13, 3, 17
11, 3, 5, 17, 3, 13, 19, 3, 7, 0, 3, 11, 5, 3, 0, 7, 3, 5, 13, 3, 17
17, 3, 13, 5, 3, 7, 19, 3, 5, 11, 3, 0, 7, 3, 0, 13, 3, 17, 5, 3, 11
ohne Symmetrien (4 Lösungen):
11, 3, 5, 17, 3, 13, 0, 3, 7, 0, 3, 11, 5, 3, 19, 7, 3, 5, 13, 3, 17
17, 3, 13, 5, 3, 7, 0, 3, 5, 11, 3, 0, 7, 3, 19, 13, 3, 17, 5, 3, 11
17, 3, 13, 5, 3, 7, 0, 3, 5, 11, 3, 19, 7, 3, 0, 13, 3, 17, 5, 3, 11
19, 17, 3, 13, 11, 3, 7, 5, 3, 0, 0, 3, 5, 7, 3, 11, 13, 3, 17, 19, 3

Maximalbelegungen für $n=22$:
(hier gibt es nur eine Lösung)
3, 19, 17, 3, 13, 11, 3, 7, 5, 3, 0, 0, 3, 5, 7, 3, 11, 13, 3, 17, 19, 3

LG Primentus
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 12.01.2018
Mitteilungen: 85
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.178, eingetragen 2018-03-15


Die Belegung

3,5,17,3,73,47,3,37,7,3,13,5,3,23,11,3,5,19,3,17,59,3,7,13,
3,11,5,3,61,7,3,5,41,3,31,67,3,71,29,3,43,5,3,7,37,3,5,11,
3,13,7,3,47,17,3,19,5,3,11,23,3,5,13,3,7,31,3,29,53,3,17,5,
3,41,19,3,5,73,3,59,11,3,23,43,3,7,5,3,13,61,3,5,7,3

liefert eine Folge von 94 aufeinander folgenden ungeraden Zahlen mit Primteilern ≤73. Eine mögliche Startzahl dafür ist 24476618228578834613364564423.



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 693
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.179, eingetragen 2018-03-15

\(\begingroup\)
@querin:

Sehr gut! Dann gibt es also tatsächlich eine $n=94$ lange 0-löchrige Abdeckung, die mit den Primzahlen $\leq$ 73 auskommt, d. h. die von den drei höchsten zulässigen Prim-Leitern 79, 83, 89 gar keinen Gebrauch macht. Das dürfte dann unsere bisher längste 0-löchrige Abdeckung sein.
Eine höchst interessante Maximalabdeckung!
Danke dafür!

LG Primentus
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4054
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.180, eingetragen 2018-03-15

\(\begingroup\)
@Primentus

Habe jetzt mal auf die Schnelle eine kleine Änderung in meinem Programm durchgeführt, womit dieses also dann nicht mehr ganz so "greedy" ist, aber dafür dann auch deutlich langsamer ist.

Man kann jetzt an der "Schraube" r (für Relaxation, Defaultwert 1) ein bißchen drehen, aber auch noch im Programm selber wird für p>13 der Wert von $r$ auf 0 zurückgesetzt, wo man ev. auch noch etwas drehen kann. Insgesamt habe ich nicht sehr viel noch ausprobiert, es scheint aber so zu sein, dass wenn das Programm jeweils die "Bekellsche Zentralanordnung" findet, dass dann die Ausgabe insgesamt in Ordnung ist. Jedenfalls muss man an der früheren Version nicht allzuviel ändern für den Fall, dass du es selbst wieder in Mathematica ausprobieren willst.  wink
Maple
legendre:=proc(n,r0:=1)    
   local b,c,c0,f,i,j,h,m,M:=0,p:=2,r:=r0,s,s_,S:=[[seq(0,k_=1..n)]],T,U,V:=[];
   f:=x->add(signum(x_),x_ in x);     
   do
      T:=[]; b:=true; 
      if p>19 then r:=min(r0,1) elif p>53 then r:=0 end if;
      p:=nextprime(p); if p>n then break end if;           
      for s in S do
         m:=0; U:=[];                
         for i to p do
            s_:=s; c0:=f(s_);
            for j from i to n by p do
               if s[j]=0 then s_[j]:=p end if
            end do;
            c:=f(s_); if c=c0 then next end if;
            if c>c0+1 then b:=false end if;            
            if c>=m-r then m:=max(c,m); U:=[op(U),s_] end if;                           
         end do;
         M:=max(M,m); T:=[op(T),op(U)]; 
      end do;      
      T:=select(x->is(f(x)>=M-r),T);        
      if b then M:=M-1; V:=[op(V),p] else S:=T end if       
   end do;   
   h:=max(n-M-nops(V),0); S:=sort(select(x->f(x)=M,S)); T:={}; c:=0;
   printf("The subsequent patterns have got only %d hole(s) actually,\\
   as you could replace 0-locations by any prime in %a.\n\n",h,V);   
   for s in S do
      if s in T or [seq(s[-k],k=1..nops(s))] in T then next end if; 
      c:=c+1; printf("%4d. %a\n",c,s); T:={op(T),s} 
   end do;
   return
end:      
 
 
legendre(7)
 
The subsequent patterns have got only 2 hole(s) actually, as you could
replace 0-locations by any prime in [7].
 
[0, 5, 3, 0, 0, 3, 5]
[3, 0, 0, 3, 0, 5, 3]
[3, 0, 0, 3, 5, 0, 3]
 
t:=time():legendre(21,2);(time()-t)*'s'
 
The subsequent patterns have got only 2 hole(s) actually, as you could
replace 0-locations by any prime in [].
 
[3, 19, 17, 3, 13, 11, 3, 7, 5, 3, 0, 0, 3, 5, 7, 3, 11, 13, 3, 17, 19]
[11, 3, 5, 17, 3, 13, 0, 3, 7, 0, 3, 11, 5, 3, 19, 7, 3, 5, 13, 3, 17]
[11, 3, 5, 17, 3, 13, 0, 3, 7, 19, 3, 11, 5, 3, 0, 7, 3, 5, 13, 3, 17]
[11, 3, 5, 17, 3, 13, 19, 3, 7, 0, 3, 11, 5, 3, 0, 7, 3, 5, 13, 3, 17]
 
                            25.265 s
 
t:=time():legendre(22);(time()-t)*'s'
 
The subsequent patterns have got only 2 hole(s) actually, as you could
replace 0-locations by any prime in [].
 
[3, 19, 17, 3, 13, 11, 3, 7, 5, 3, 0, 0, 3, 5, 7, 3, 11, 13, 3, 17, 19, 3]
 
                            8.297 s

@Querin

Ja, toll!  wink  

Mit der Hand gerechnet oder per Computer?

PS: Hab mir deine Lösung nun noch etwas genauer angesehen. Der "Trick" dabei ist, dass man auf die maximale 53-Leiter mit 2 Belegungen verzichtet und dafür die Primzahlen 59 und 61 zweimal legen kann. Daran scheitert mein Programm bislang leider noch.  frown
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 1627
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.181, eingetragen 2018-03-16


2018-03-15 21:43 - querin in Beitrag No. 178 schreibt:
Die Belegung

3,5,17,3,73,47,3,37,7,3,13,5,3,23,11,3,5,19,3,17,59,3,7,13,
3,11,5,3,61,7,3,5,41,3,31,67,3,71,29,3,43,5,3,7,37,3,5,11,
3,13,7,3,47,17,3,19,5,3,11,23,3,5,13,3,7,31,3,29,53,3,17,5,
3,41,19,3,5,73,3,59,11,3,23,43,3,7,5,3,13,61,3,5,7,3

liefert eine Folge von 94 aufeinander folgenden ungeraden Zahlen mit Primteilern ≤73. Eine mögliche Startzahl dafür ist 24476618228578834613364564423.

Gratulation , endlich mal die 73 doppelt belegt, mit den einfachen 53 67 71 gibt es 6 Lösungen bzw 12 mit Spiegelungen
Ist die schön lange Startzahl davon die kleinste?

Ich bin auch gespannt ob du es gar mit nem japanischen Soroban gefunden hast?

Kann ich irgendwie mit zwei 15 stelligen Zahlen 30 stellige  multiplizieren?
Haribo



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4054
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.182, eingetragen 2018-03-16

\(\begingroup\)
Habe inzwischen versucht, die Lösung von querin zu $n=94$ auch mit meinem Programm zu erhalten, indem ich es an einer Stelle zu Beginn etwas modifizierte und auch sonst die Ausgabe etwas übersichtlicher gestaltete. Auch wenn die Rechenzeit damit leider nochmals deutlich in die Höhe ging, ist es mir dann doch gelungen: Die Lösung von querin entspricht nun der dritten der insgesamt 6 Lösungen.

Maple
t:=time():legendre(94);(time()-t)*'s'
 
The subsequent patterns have got only 0 hole(s) actually, as you could
replace 0-locations by any prime in [67, 71, 79, 83, 89].
[..] 
 
   3. [3,5,17,3,73,47,3,37,7,3,13,5,3,23,11,3,5,19,3,17,59,3,7,13,3,11,
5,3,61,7,3,5,41,3,31,0,3,0,29,3,43,5,3,7,37,3,5,11,3,13,7,3,47,17,3,19,
5,3,11,23,3,5,13,3,7,31,3,29,53,3,17,5,3,41,19,3,5,73,3,59,11,3,23,43,
3,7,5,3,13,61,3,5,7,3]
 
[..]  
                           5531.812 s


\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 12.01.2018
Mitteilungen: 85
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.183, eingetragen 2018-03-16


Freut mich, wenn es euch gefällt smile

Meine Strategie ist ein einfacher hill climbing Algorithmus: Ausgehend von einer zufälligen Permutation der Primzahlen 3 bis 73 (die in dieser Reihenfolge das Feld der 94 Zahlen iterativ füllen), wird durch lokale Suche (alle möglichen Vertauschungen von zwei Primzahlen) rekursiv eine bessere Permutation mit weniger "Löchern" gesucht. Wird keine Verbesserung mehr erreicht, beginnt das Spiel mit einer anderen zufälligen Permutation von Neuem. Das klappt erstaunlich gut.

@haribo
Ich verwende Python, da sind beliebig große ganze Zahlen kein Problem. Die Startzahl ergibt sich aus dem Chinesischen Restsatz. Ich habe mehrere Lösungen und die Startzahlen liegen alle in der Größenordnung 10^28, also der Größenordung des Primorials 73#.




  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4054
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.184, eingetragen 2018-03-16


2018-03-16 20:01 - querin in Beitrag No. 183 schreibt:
Meine Strategie ist ein einfacher hill climbing Algorithmus: Ausgehend von einer zufälligen Permutation der Primzahlen 3 bis 73 (die in dieser Reihenfolge das Feld der 94 Zahlen iterativ füllen), wird durch lokale Suche (alle möglichen Vertauschungen von zwei Primzahlen) rekursiv eine bessere Permutation mit weniger "Löchern" gesucht. Wird keine Verbesserung mehr erreicht, beginnt das Spiel mit einer anderen zufälligen Permutation von Neuem. Das klappt erstaunlich gut.

Ja, das ist dann schon ein grundverschiedener Ansatz, der eher darauf ausgerichtet ist, überhaupt optimale Lösungen zu finden, während mein Programm versucht, alle optimalen Lösungen zu finden und die in einem gewissen Sinne "gleichwertigen" Lösungen auch nur einmal auszugeben. Bislang ist das mehr schlecht als recht gelungen, in der allerletzten Version (editiert in #180) klappt das aber schon deutlich besser, zumindestens sehe ich keine Fehler mehr nach der Liste von Primentus in #167, auch wenn sich die Verbesserungen dann natürlich auch in deutlich höheren Rechenzeiten niederschlagen. Alles im Leben hat halt auch seinen Preis!  wink



  Profil  Quote  Link auf diesen Beitrag Link
Bekell
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.09.2008
Mitteilungen: 1242
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.185, vom Themenstarter, eingetragen 2018-03-16


Gibt es denn jetzt schon Gedanken, ab "wann" diese 0-löchrigen Intervalle auftreten können? Ich meine jetzt nicht global, da sagte ja Primentus ab n=31, ich meine die Bedingungen des Auftretens, daß man sagen kann, ein 0-löchriges Intervall bei n=31 kann erst ab der und der Größe auftreten, darunter nicht, weil .....


-----------------
Das Schwierige ist nicht die Mathematik. Schwierig ist es zu formulieren, daß man selber versteht, was man sieht und die anderen auch!



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4054
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.186, eingetragen 2018-03-16

\(\begingroup\)
2018-03-16 21:35 - Bekell in Beitrag No. 185 schreibt:
Gibt es denn jetzt schon Gedanken, ab "wann" diese 0-löchrigen Intervalle auftreten können? Ich meine jetzt nicht global, da sagte ja Primentus ab n=31, ich meine die Bedingungen des Auftretens, daß man sagen kann, ein 0-löchriges Intervall bei n=31 kann erst ab der und der Größe auftreten, darunter nicht, weil .....

Hm, wie kommst du auf diesen Wert $n=31$ bzw. wo hat Primentus davon gesprochen, das es da 0-löchtige Lösungen gäbe. Ich selber habe die erste bei $n=43$ gefunden, aber sie sind danach sehr häufig bzw. gewissermaßen sogar der "Normalfall", wie dies ja auch aus den Abschätzungen, welche Cyrix hier irgendwo gegeben hat, hervorgeht. Es könnte als durchaus ein größtes $n$ geben, für welches die entsprechende Folge von $n$ aufeinanderfolgenden ungeraden Zahlen nicht 0-löchrig ist.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 1627
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.187, eingetragen 2018-03-16


also ist 2*94+1=189 die grösstmögliche prim>74 lücke die es überhaupts gibt in der ganzzahligen zahlenwelt

dat gefällt natürlich schon, hast du ne vorstelleung wie viele neue random-versuche es ungefähr erforderte? du findest ja jedesmal sowas wie lokale maximal abdeckungen (berg-gipfel), aber wie viele verschiedene hill´s mag es ungefähr geben

weiss nicht wie man das besser ausdrücken kann

haribo



  Profil  Quote  Link auf diesen Beitrag Link
Bekell
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.09.2008
Mitteilungen: 1242
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.188, vom Themenstarter, eingetragen 2018-03-17

\(\begingroup\)
2018-03-16 22:05 - weird in Beitrag No. 186 schreibt:
 Ich selber habe die erste bei $n=43$ gefunden, aber sie sind danach sehr häufig bzw. gewissermaßen sogar der "Normalfall", wie dies ja auch aus den Abschätzungen, welche Cyrix hier irgendwo gegeben hat, hervorgeht. Es könnte als durchaus ein größtes $n$ geben, für welches die entsprechende Folge von $n$ aufeinanderfolgenden ungeraden Zahlen nicht 0-löchrig ist.

Ja, ich versteh Dich, Weird, aber Du mich nicht ... auch ich habe eher den Eindruck, das diese 0-löchrigen Folgen der "Normalfall" werden, ja daß zunehmend für längere 0-löchrige Folgen tendenziell immer weniger PZ notwendig sein werden. Aber eventuell gibt es da einen Grenzwert, daß man sagen kann, die PZ bis zu 1/2 n oder so sind mindestens notwendig - Also, die PZ können nicht gegen Null gehen.

Und auch Deine 2. Vermutung:

Es könnte als durchaus ein größtes $n$ geben, für welches die entsprechende Folge von $n$ aufeinanderfolgenden ungeraden Zahlen nicht 0-löchrig ist.
finde ich plausibel....


Das ist aber nicht meine Frage. (ich rede über die gelbe Spalte) Mein Frage lautet, wenn ich sie umdrehe: Könnte so ein 0-löchriges Intervall theoretisch von n=43 schon bei sagen wir 5 beginnen. Wir wissen, daß dem nicht so ist, aber wir haben außer dem Quadrat keine Grenze, wo wir sagen können. Erst ab hier kann so ein 0-löchriges Intervall auftreten. Oder wir sagen, bis zum Primorial 43 treten mindestens so und so viele solche Intervalle auf. Was ihr da herausfiltert, sind ja nicht nur Positionierungsmöglichkeiten von kleinsten Primfaktoren, sondern dahinter stecken ja immer reale ganzzahlige Intervalle.

Ich hoffe, diesmal mich besser ausgedrückt zu haben.


-----------------
Das Schwierige ist nicht die Mathematik. Schwierig ist es zu formulieren, daß man selber versteht, was man sieht und die anderen auch!
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4054
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.189, eingetragen 2018-03-17

\(\begingroup\)
2018-03-17 10:08 - Bekell in Beitrag No. 188 schreibt:
Mein Frage lautet, wenn ich sie umdrehe: Könnte so ein 0-löchriges Intervall theoretisch von n=43 schon bei sagen wir 5 beginnen. Wir wissen, daß dem nicht so ist, aber wir haben außer dem Quadrat keine Grenze, wo wir sagen können. Erst ab hier kann so ein 0-löchriges Intervall auftreten. Oder wir sagen, bis zum Primorial 43 treten mindestens so und so viele solche Intervalle auf. Was ihr da herausfiltert, sind ja nicht nur Positionierungsmöglichkeiten von kleinsten Primfaktoren, sondern dahinter stecken ja immer reale ganzzahlige Intervalle.

Ich weiß schon, was dich umtreibt: Ein Gegenbeispiel zur Legendreschen Vermutung für ein gewisses $n$ würde dann für dieses $n$ dann eine 0-löchrige Folge von $n$ aufeinanderfolgenden Zahlen mit einem außerordentlich kleinen Startwert, nämlich $n^2+1+(n \mod 2)$, ergeben. Könnte man also zeigen, dass die Startwerte für eine solche 0-löchrige Folge aufeinanderfolgeder ungerader Zahlen der Länge $n$ immer größer als dieser Wert ist, wäre damit die Vermutung von Legendre automatisch bewiesen.  cool

Aber eben deshalb bin ich der Überzeugung, dass man das nicht kann. Heuristisch gesehen sollte dieser Startwert aber viel, viel größer, nämlich in der Größenordnung von n# (=Produkt aller Primzahlen $\le n$) sein, wie sich das bisher auch noch immer bestätigt hat, aber das beweist halt noch nicht, dass er im Einzelfall nicht doch einmal auch sehr klein sein kann. Zumindestens sehe ich jetzt ad hoc nichts, was dagegen sprechen würde.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 1627
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.190, eingetragen 2018-03-17


@querin, interessant ist die pos 37 (also startzahl+72) die zahl ist durch  3;5;7;11;13;17;19;23; teilbar
das kann kein zufall sein

und könnte letztlich einen hinweis geben ab welcher mindestzahl null-löchrigkeit auftritt???

oder auch nicht, weil 94 ja deutlich grösser n=73 ist

haribo

[Die Antwort wurde nach Beitrag No.187 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 12.01.2018
Mitteilungen: 85
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.191, eingetragen 2018-03-17


2018-03-16 22:26 - haribo in Beitrag No. 187 schreibt:
hast du ne vorstelleung wie viele neue random-versuche es ungefähr erforderte? du findest ja jedesmal sowas wie lokale maximal abdeckungen (berg-gipfel), aber wie viele verschiedene hill´s mag es ungefähr geben
Bei p=73 umfasst der gesamte Suchraum 20! ~ 2.4*10^18 Permutationen. Eine Belegung mit n=93 wird sehr schnell gefunden, dann braucht es meist einige 10^5 Berggipfel bis n=94 gefunden wird.

2018-03-17 12:36 - haribo in Beitrag No. 190 schreibt:
interessant ist die pos 37 (also startzahl+72) die zahl ist durch  3;5;7;11;13;17;19;23; teilbar
das kann kein zufall sein
Inzwischen habe für alle Primzahlen bis p=97 eine Maximalbelegung entsprechend der OEIS Folge gefunden. Dabei tritt bei allen Belegungen mit n>p eine auffällige Zahl mit Primorial/2 Teiler auf:
n=44, p=43: 13#/2
n=49, p=47: 13#/2
n=65, p=61: 11#/2
n=75, p=67: 23#/2
n=86, p=71: 13#/2
n=94, p=73: 23#/2
n=99, p=79: 29#/2
n=107, p=83: 29#/2
n=116, p=89: 23#/2
n=128, p=97: 13#/2
Aber aus diesen paar Zahlen irgendwelche Schlüsse zu ziehen wäre m.E. reine Spekulation.



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2774
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.192, eingetragen 2018-03-17


Naja, dass man mit dieser lokalen Suche häufig Intervalle finden wird, wo es eine Zahl gibt, die durch viele Primzahlen gleichzeitig teilbar ist, verwundert jetzt nicht so sehr:

Im Intervall [-n, n] der Länge 2n+1 ist z.B. jede Zahl bis auf +-1 durch mindestens eine der Primzahlen <math>\leq n</math> teilbar. Wenn man dies jetzt nur leicht variert und "in der Nähe" sucht, wird man sich wohl die Eigenschaft, dass das hier mittlere Element durch viele der Primzahlen teilbar ist, nicht so einfach zerstören.

Analog sind also z.B. Intervalle, die solche der Form [k * m# - m, k * m# + m] umfassen, gute Start-Kandidaten für das weitere Hill-Climbing, da sie von Haus aus wenige Löcher mitbringen. Das spricht auch dafür, dass man von zufälligen Lösungen in sie hineinläuft...

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 1627
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.193, eingetragen 2018-03-17


wenn man weiss das man nach 23#/2 suchen muss ist das schon ne hilfe um den faktor 2*10^6, dat schadet jedenfals nicht gegenüber unseren ersten ansätzen vor zwei wochen...(jede ungerade zahl erschien damals als startzahl möglich)
haribo



  Profil  Quote  Link auf diesen Beitrag Link
Bekell
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.09.2008
Mitteilungen: 1242
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.194, vom Themenstarter, eingetragen 2018-03-17


2018-03-17 21:07 - cyrix in Beitrag No. 192 schreibt:
zufälligen Lösungen

Es ist jetzt alles zwar interessant, aber etwas planlos, dieses Herumsuchen.

Mich stört insgesamt dieser probabilistische Ansatz, weil er dazu verleitet, zu denken, es ginge hier um Wahrscheinlichkeiten, Verteilungen und glückliche Funde. Als ob wir mit einem Netz durchs Meer zögen und einzelne Fische fingen. Das hat zumindest zur Widerlegung der Ausgangthese, daß es keine 0-Löchrigen Intervalle gäbe, seine Berechtigung gehabt.

Jetzt wäre es aber wichtig, System rein zu kriegen, denn die Zahlen sind nicht wegen eines Zufalls an ihrer Stelle. Ich bin überzeugt, .... äh, ich meine, ich vermute, daß man die Anzahl und den Ort der 0-Loch-Intervalle berechnen kann, obwohl ich momentan außer Dickicht nicht viel sehe.

Zu beantworten wären die Fragen:
1. Gibt es eine Mathematik, die beantwortet, bei welchem n es wieviele Intervalle gibt?
2. Wo liegen die tiefsten und wo die höchsten Intervalle für ein n?
3. Wie sieht es mit Intervallen in Intervallen aus?
4. Gibt es feste Pattern und Metapattern und darüber wieder Pattern?




[Die Antwort wurde nach Beitrag No.192 begonnen.]


-----------------
Das Schwierige ist nicht die Mathematik. Schwierig ist es zu formulieren, daß man selber versteht, was man sieht und die anderen auch!



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 693
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.195, eingetragen 2018-03-18

\(\begingroup\)
Hallo,

ich habe die Legendre-Funktion von weird in der Version von Beitrag #180 nach Mathematica portiert und bin bereits seit längerem am testen. Die in der Tabelle in Beitrag #167 aufgeführten Diskrepanzen (a), (b), (c) scheinen nun beseitigt zu sein. Dennoch mache ich erst noch weitere Tests, bevor ich dann den Mathematica-Code dazu poste.

Ich möchte zwischenzeitlich noch etwas anderes in die Runde werfen, was uns vielleicht auch noch weiterbringen könnte. Bei meiner vollständigen Suche bis $n=22$ lege ich systematisch alle denkbaren Kombinationen von Prim-Leitern aus, und ermittle anschließend alle Belegungen mit der kleinsten Anzahl von Löchern (= Maximalbelegungen). Ich möchte das mal kurz anhand des Beispieles $n=6$ darstellen (hier gibt es lediglich zwei Prim-Leitern, nämlich 3 und 5):
Tabelle
Fall 1:    Fall 2:    Fall 3:    Fall 4:    Fall 5:
XOOXOX     OXOOXO     OOXOOX     XOOXOO     OXOOXO
3  3        3  3        3  3     3  3        3  3
5    5      5           5           5           5
 
Fall 6:    Fall 7:    Fall 8:    Fall 9:    Fall 10:
XOXOOX     XXOXOO     OXXOXO     OOXXOX     XOOXXO
  3  3     3  3        3  3        3  3     3  3
5    5      5           5           5           5
 
Fall 11:   Fall 12:   Fall 13:   Fall 14:   Fall 15:
XXOOXX     OXXOOX     XOXXOO     OXOXXO     OOXOXX
 3  3        3  3     3  3        3  3        3  3
5    5      5           5           5           5
 
Legende:
X = belegte Position
O = Loch
3 = Prim-Leiter 3
5 = Prim-Leiter 5

Es gibt für ein $n$ stets so viele Gesamtfälle wie das Produkt der Prim-Leiter-Zahlen ergibt (hier $3\cdot 5=15$). Am Anfang beginnt jede Prim-Leiter an Position 1. Dann wird jede Prim-Leiter von Fall zu Fall um eine Position weiterverschoben. Auf diese Weise entstehen alle möglichen Kombinationen des Prim-Leiter-Auslegens. Und wie man sieht, führt hier der Fall 11 zur einzigen Maximalbelegung mit lediglich 2 Löchern.

Nun kann man sich natürlich fragen: Ist es Zufall, dass ausgerechnet der Fall 11 zu einer Maximalbelegung führt oder lässt sich das nicht algorithmisch bestimmen? Die erfreuliche Nachricht ist: das lässt sich tatsächlich algorithmisch bestimmen. Nachteil dabei ist jedoch, dass man dazu die Maximalbelegung bereits kennen muss, also hier 5,3,0,0,3,5. Mit deren Hilfe und dem chinesischen Restsatz allerdings kann man tatsächlich die Fallnummer ermitteln. In Mathematica-geht das so:
Mathematica
ChineseRemainder[{2, 1}, {3, 5}]
Erstes Argument sind die Prim-Leiter Positionen der Reihe nach von der kleinsten Prim-Leiter zur größten, und zweites Argument ist die Liste der verwendeten Prim-Leitern. Ergebnis:
Mathematica
11

Nun bin ich noch einen Schritt weitergegangen und habe mich gefragt, ob man nicht auch eine inverse Funktion zum chinesischen Rest basteln könnte. Also die Frage ist: Kann man zu einem gegebenen $n$ und der bekannten Fallnummer einer Maximalbelegung die zugehörige Prim-Leiter-Auslegung ermitteln? Die Antwort lautet auch hier: ja. In unserem Beispiel ist $n=6$ und die Fallnummer gleich 11. In Mathematica geht das dann wie folgt:
Mathematica
InverseChineseRemainder[nn_, rest_] := 
 Module[{rr = {}}, ii = 2; 
  While[Prime[ii] <= nn, rr = Append[rr, Mod[rest, Prime[ii]]]; ii++];
   Return[rr]]
 
InverseChineseRemainder[6, 11]
Ergebnis:
Mathematica
{2,1}
Das heißt also, lediglich durch Kenntnis der Fallnummer zu einem gegebenen $n$ ist es möglich, die Prim-Leiter-Auslegung zu ermitteln, und anhand dieser ist es natürlich ein leichtes, die zugehörige Maximalbelegung 5,3,0,0,3,5 zu ermitteln.

Nur jetzt hat man folgendes Problem: Wenn man die Maximalbelegung noch nicht kennt, die man ja gerade erst ermitteln will, kennt man die Fallnummer nicht ohne weiteres. Diese könnte man zwar mit dem chinesischen Restsatz ermitteln, aber eben leider nur, wenn man die Maximalbelegung schon kennt. Hier beißt sich die Katze also in den Schwanz. Was ich aber mal gemacht habe, ist, sämtliche Fallnummern für alle $n$ von 3 bis 22 zu ermitteln. Das sieht dann so aus:

n=3 (3 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:  
1, 2, 3

n=4 (3 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:  
1

n=5 (15 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:  
7, 8, 10, 11, 13, 14

n=6 (15 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:  
11

n=7 (105 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:  
10, 11, 12, 13, 16, 31, 52, 55, 56, 57, 58, 61, 82, 97, 100, 101, 102, 103

n=8 (105 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:  
11, 13, 56, 57, 58, 101, 103

n=9 (105 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:  
57, 58

n=10 (105 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:  
58

n=11 (1155 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:
16, 416, 478, 479, 521, 583, 584, 646, 688, 689, 751, 1151

n=12 (1155 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:  
584

n=13 (15015 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:  
16, 418, 419, 688, 691, 838, 1905, 1906, 1948, 2326, 2686, 2788, 2791, 2956, 3883, 3884, 4048, 4049, 4050, 4051, 4111, 4636, 5413, 5458, 6256, 6421, 6613, 7408, 7513, 7514, 7515, 7516, 7621, 8416, 8608, 8773, 9571, 9616, 10393, 10918, 10978, 10979, 10980, 10981, 11145, 11146, 12073, 12238, 12241, 12343, 12703, 13081, 13123, 13124, 14191, 14338, 14341, 14610, 14611, 15013

n=14 (15015 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:  
419, 1906, 3884, 4049, 4051, 7514, 7515, 7516, 10979, 10981, 11146, 13124, 14611

n=15 (15015 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:  
7515, 7516

n=16 (15015 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:
7516

n=17 (255255 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:
14614, 15434, 34147, 36455, 36456, 36457, 38636, 38637, 38638, 42101, 57116, 60479, 61736, 73417, 76751, 79192, 83681, 83682, 83683, 97606, 97607, 116021, 117176, 127636, 127637, 138097, 139252, 157666, 157667, 171590, 171591, 171592, 176081, 178522, 181856, 193537, 194794, 198157, 213172, 216635, 216636, 216637, 218816, 218817, 218818, 221126, 239839, 240659

n=18 (255255 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:
36456, 36457, 38637, 38638, 83682, 83683, 127637, 171591, 171592, 216636, 216637, 218817, 218818

n=19 (4849845 mögliche Belegungen) - Maximalbelegungen (1-löchrig) sind Fallnummern:
38638, 218818, 1059658, 1359958, 1958377, 2078497, 2771368, 2891488, 3489907, 3790207, 4631047, 4811227

n=20 (4849845 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:
29, 2332, 2333, 14617, 38638, 38639, 66488, 93979, 120149, 218818, 218819, 229739, 293893, 390382, 495094, 495097, 570562, 652072, 658348, 662993, 763453, 763454, 791302, 804404, 843173, 943633, 1059658, 1059659, 1111529, 1128458, 1192612, 1260862, 1359958, 1359959, 1370254, 1426417, 1428758, 1437572, 1441042, 1465063, 1471499, 1531522, 1546147, 1591582, 1592009, 1645244, 1666657, 1673092, 1703123, 1709398, 1726327, 1761269, 1771369, 1891919, 1958377, 1958378, 2005603, 2026624, 2026627, 2042069, 2078497, 2078498, 2169677, 2169679, 2189878, 2194523, 2206807, 2294983, 2294984, 2311912, 2333752, 2357774, 2363783, 2402429, 2424932, 2424933, 2424934, 2447437, 2486083, 2492092, 2516114, 2537954, 2554882, 2554883, 2643059, 2655343, 2659988, 2680187, 2680189, 2771368, 2771369, 2807797, 2823239, 2823242, 2844263, 2891488, 2891489, 2957947, 3078497, 3088597, 3123539, 3140468, 3146743, 3176774, 3183209, 3204622, 3257857, 3258284, 3303719, 3318344, 3378367, 3384803, 3408824, 3412294, 3421108, 3423449, 3479612, 3489907, 3489908, 3589004, 3657254, 3721408, 3738337, 3790207, 3790208, 3906233, 4006693, 4045462, 4058564, 4086412, 4086413, 4186873, 4191518, 4197794, 4279304, 4354769, 4354772, 4459484, 4555973, 4620127, 4631047, 4631048, 4729717, 4755887, 4783378, 4811227, 4811228, 4835249, 4847533, 4847534, 4849837

n=21 (4849845 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:
2333, 763454, 2294984, 2424933, 2424934, 2554883, 4086413, 4847534

n=22 (4849845 mögliche Belegungen) - Maximalbelegungen (2-löchrig) sind Fallnummern:
2424934

Und nun habe ich einen Algorithmus gebastelt, der nicht mehr erst alle möglichen Belegungen erstellt, um anschließend die Maximalbelegungen zu ermitteln (das war meine vollständige Suche), sondern einen Algorithmus, der ohne Kenntnis aller Belegungsmöglichkeiten darauf abzielt, möglichst die erste Fallnummer einer Maximalbelegung zu erwischen (z. B. Nr. 29 bei $n=20$) und anhand dieser dann die Maximalbelegung selbst zu erstellen (eben mit Hilfe der oben angeführten inversen Funktion zum chinesischen Restsatz). Und damit kennt man dann auch 100 % verlässlich die Anzahl Löcher der tatsächlichen Maximalbelegungen. Mein Algorithmus erkennt automatisch Fallnummern, die zu keiner Maximalbelegung führen und sortiert diese aus, so dass es letztlich nur zur Ausgabe der ersten gefundenen tatsächlichen Maximalbelegung führt. Der Algorithmus zielt also darauf ab, die erste auftretende Belegung gemäß chinesischem Restsatz zu finden, die dann zwangsweise eine Maximalbelegung ist (Edit: Die ermittelte Belegung ist genau dann eine tatsächliche Maximalbelegung, wenn im Funktionsaufruf die passende Anzahl maximaler Löcher vorgegeben ist.)

Nun hab ich folgendes beobachtet: Manchmal ist die erste Fallnummer recht klein (z. B. Nr. 29 von 4849845 bei $n=20$) und tritt quasi nicht allzu weit vom Anfang der natürlichen Zahlen auf und manchmal ist diese sehr weit in der Mitte (z. B. Nr. 7516 von 15015 möglichen Belegungen bei $n=16$). Das heißt, es kann mal günstiger sein, von Beginn an zu suchen und mal ist es besser, von der Mitte aus zu suchen. Hier zwei Aufrufbeispiele für $n=20$:
Mathematica
MaximalbelegungenChinese[n_, maxloecher_, anfang_] := 
 Module[{p = {}, prod = 1, k, pos, r = Table[0, {a, 1, n}]}, i = 2; 
  While[Prime[i] <= n, p = Append[p, Prime[i]]; prod = prod*Prime[i]; 
   i++];
  If[anfang, k = 1, k = Floor[prod/2]]; 
  While[Count[r, 0] > maxloecher, r = Table[0, {a, 1, n}]; 
   pos = InverseChineseRemainder[n, k];
   For[i = Length[p], i >= 1, i--, 
    For[j = pos[[i]], j <= n, j = j + p[[i]], 
     If[j > 0, r[[j]] = p[[i]]];]]; k++]; Return[{k - 1, prod, r}]]
 
Timing[MaximalbelegungenChinese[20, 2, True]]
Timing[MaximalbelegungenChinese[20, 2, False]]
Erstes Argument ist $n$, zweites Argument ist die maximale Anzahl von Löchern, die gefunden werden soll (Achtung: wenn zu klein angegeben, wird u. U. nichts gefunden, d. h. man muss eine ungefähre Vorstellung davon haben, welche Anzahl von Löchern es kleinstenfalls geben könnte) und das dritte Argument steuert, ob von Beginn an (entspricht True) oder von der Mitte aus (entspricht False) gesucht werden soll. Bei $n=20$ sind beide Berechnungszeiten sehr kurz, da Maximalbelegungsfallnummern sowohl nahe 1 als auch nahe der Mitte sehr schnell auftreten.
Ergebnis:
Mathematica
{0.015625, {29, 4849845, {7, 3, 13, 5, 3, 0, 11, 3, 5, 19, 3, 17, 0, 3, 7, 13, 3, 11, 5, 3}}}
{0., {2424932, 4849845, {17, 3, 13, 11, 3, 7, 5, 3, 0, 0, 3, 5, 7, 3, 11, 13, 3, 17, 19, 3}}}

Bei $n=19$ ist es dann etwas langsamer, aber immer noch im Sekundenbereich:
Mathematica
Timing[MaximalbelegungenChinese[19, 1, True]]
Timing[MaximalbelegungenChinese[19, 1, False]]
Ergebnis:
Mathematica
{5.01563, {38638, 4849845, {3, 13, 5, 3, 7, 11, 3, 5, 0, 3, 19, 7, 3, 17, 13, 3, 11, 5, 3}}}
{47.2813, {2771368, 4849845, {3, 13, 5, 3, 7, 11, 3, 5, 19, 3, 17, 7, 3, 0, 13, 3, 11, 5, 3}}}
Wie man hier nun sieht, schneidet die Zu-Beginn-Suche deutlich besser ab als die Ab-Mitte-Suche.

Nun hat dieser Algorithmus vielleicht noch einen Nachteil:
Man kennt die Fallnummern nicht bereits im Vorhinein bzw. sie sind eben nicht ermittelbar ohne bereits eine Maximalbelegung zu kennen, daher muss man algorithmisch erstmal nach einer ersten solchen Fallnummer suchen. Aber ich habe ja nun sämtliche Fallnummern für alle $n$ von 3 bis 22 oben aufgelistet. Daher nun meine Frage: Sieht jemand von Euch irgendein Bildungsgesetz, anhand dem man etwa in Abhängigkeit von $n$, dem chinesischen Rest oder dem Primzahlprodukt mit $p_{i}$ $\leq n$ (ohne 2) oder anderweitige Abhängigkeiten eine der Fallnummern (egal welche) ermitteln kann, ohne erst eine Maximalbelegung kennen zu müssen? Denn dann wäre keine Suche nach einer Fallnummer mehr nötig, sondern man könnte diese direkt in den Algorithmus einspeisen und sofort die Maximalbelegung berechnen.

Vielen Dank für das Lesen dieses langen Beitrages.

LG Primentus
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 885
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.196, eingetragen 2018-03-18


Kurze Frage...
Was verstehst du unter Fallnummer? Bzw. was sagt eine Fallnummer 4354772 aus?

Und in der gelb unterlegten Tabelle: Fall 3, 5, 6, 9, 10, 12, 15 sollte doch nicht möglich sein, wenn man von Intervallen mit möglichst wenig Löchern redet... denn dann würde der Intervall schon mindestens eine Stelle eher beginnen (wenn man das von links nach rechts liest). Hängt natürlich auch davon ab, von welcher Seite aus man die 3 und 5 sucht.



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 693
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.197, eingetragen 2018-03-18

\(\begingroup\)
Hallo MartinN,

also eine Fallnummer besagt folgendes (nehmen wir mal den Fall $n=7$ - hier gibt es schon drei Prim-Leitern):

Fall 1: alle Prim-Leitern beginnen ab der ersten Position, also:
Tabelle
XOOXOXX
3  3  3
5    5
7

Fall 2 ist dann - jede Prim-Leiter aus Fall 1 wird um eine Position nach rechts verschoben:
Tabelle
OXOOXOX
 3  3  
 5    5
 7

Fall 3 ist dann - jede Prim-Leiter aus Fall 2 wird um eine Position nach rechts verschoben:
Tabelle
OOXOOXO
  3  3
  5  
  7

usw. - und dieses um eine Position nach rechts verschieben macht man solange, bis man beim Fall $3\cdot 5\cdot 7=105$ angelangt ist (da entsteht jedes mal eine andere Belegung). Auf diese Weise erhält man alle Möglichkeiten der Belegung. Als Fallnummer werden dann aber lediglich solche Fall-Nummerierungen bezeichnet, die zu einer Maximalbelegung führen. (Vielleicht ist das etwas missverständlich von mir ausgedrückt, weil ich einmal von Fällen und einmal von Fallnummer spreche).

Mein Algorithmus arbeitet so, dass er bei Beginn-Suche bei der Zahl 1 startet, diese als potentielle Fallnummer ansieht und dann mit Hilfe der inversen Funktion zum chinesischen Restsatz prüft, ob eine solche Belegung vorliegt, die maximal so viele Löcher hat wie beim Funktionsaufruf vorgegeben. Wenn ja, bricht der Algorithmus an der Stelle ab und gibt die Lösung aus. Natürlich steht es hier ein bisschen in der Verantwortung des Funktionsaufrufers, wie viele Löcher er denn denkt, dass es maximal gibt. Aber man kann sich eben Stück für Stück vortasten und erst nach maximal 2 Löchern suchen lassen, dann nach maximal 1 Loch und dann evtl. nach maximal 0 Löchern. Wenn irgendwo zu lange nichts gefunden wird, könnte es ein Indiz sein, dass es diese Maximalzahl an Löchern für das gegebene $n$ nicht existiert.

Allerdings würde ich gerne die erste auftrende Fallnummer im Vorhinein berechnen, damit man sie nicht erst suchen muss, weil sonst der Algorithmus für größere $n$ schon zu lange rechnet.

LG Primentus

Edit:

Vielleicht noch etwas verständlicher ausgedrückt: Alle Fallnummern (d. h. alle Fall-Nummerierungen, die zu Maximalbelegungen führen) entsprechen dem chinesisichen Rest für die zugehörige Prim-Leiter-Auslegung.
Beispiel: zweite Fallnummer für $n=19$, also 218818 kann wie folgt ermittelt werden:
Ausgehend von Prim-Leiter-Auslegung: 1,3,5,6,2,11,14
Zu dieser dann den chinesischen Rest ermitteln:
Mathematica
ChineseRemainder[{1, 3, 5, 6, 2, 11, 14}, {3, 5, 7, 11, 13, 17, 19}]
Ergebnis:
Mathematica
218818
Und dieser chinesische Rest entspricht genau derjenigen Fallnummer, die zu dieser Prim-Leiter-Auslegung gehört.
Ich suche jetzt allerdings nach einer anderen Möglichkeit, die Fallnummer (die dem chinesischen Rest entspricht) zu ermitteln, weil man für die jetzige Methode die Prim-Leiter-Auslegung der Maximalbelegung schon kennen muss. Aber genau die will man ja erst ermitteln. Und wenn ich eine der Fallnummern direkt in den Algorithmus einspeisen könnte, würde dieser wesentlich schneller arbeiten.

Das heißt also, die Vorgehensweise ist:
1. Mit geschickter Zahl zwischen 1 bis Produkt der Prim-Leitern beginnen
2. Zur vorliegenden Zahl mit Hilfe der inversen Funktion zum chinesischen Restsatz prüfen, ob damit eine Belegung mit einer Anzahl Löcher, die der vorgegebenen Anzahl maximaler Löcher entspricht, konstruiert werden kann, wenn ja Abbruch und Lösung ausgeben, wenn nein gleiches Prozedere mit nächster Zahl (1 hochzählen) - schöner wäre es aber, eine der Fallnummern schon vorab zu kennen, um nicht erst welche durchprobieren zu müssen.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4054
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.198, eingetragen 2018-03-19

\(\begingroup\)
@Primentus

Ist es nicht so, dass deine "Fallnummer" vor allem dazu dient, jeder möglichen Auslegung eine positive ganze Zahl zuzuordnen, aus der man diese Auslegung der Primleitern wieder rekonstruieren kann, ohne dass diese Fallnummern eine darüber hinausgehende Bedeutung haben?

Falls ich damit richtig liege, dann stellt sich natürlich die Frage, warum da nicht gleich die kleinstmögliche Startzahl einer "Realisation" des Patterns nimmst, deren Berechnung ebenfalls mit Chin. Restsatz ich ja schon in #37 angegeben hatte. Sie charakterisiert die Auslegungen der Primleitern ebenso, aber ist eben keine "seelenlose Zahl", sondern wirklich der Anfang der "ersten" Folge von $n$ aufeinanderfolgenden ungeraden Zahlen, welche zu diesem pattern passt. Insbesondere kann man aus der Tatsache, dass diese Startzahl $>n^2+1+(n \mod 2)$ ist, mit Sicherheit dann darauf schließen, dass diese Folge nicht zwischen $n^2$ und $(n+1)^2$ liegen kann, d.h., für eine Gegenbeispiel zur Legendreschen Vermutung für dieses eine $n$ und auch nur für dieses eine pattern nicht in Frage kommt. Das ist zwar eine sehr schwache Aussage, aber immerhin etwas.

Der "Bekellsche Traum" jedoch, wenn ich ihn richtig verstanden habe, dass man so eine Abschätzung nach unten für die kleinste Startzahl gleich für jedes $n$, für welches es 0-löchrige Lösungen gibt (ab $n=67$ scheint das dann durchgängig der Fall zu sein), sowie auch für alle patterns dazu angeben könne, erscheint mir jedoch nach wie vor undurchführbar.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Bekell
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.09.2008
Mitteilungen: 1242
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.199, vom Themenstarter, eingetragen 2018-03-19

\(\begingroup\)
2018-03-18 16:22 - Primentus in Beitrag No. 197 schreibt:
also eine Fallnummer besagt folgendes (nehmen wir mal den Fall $n=7$ - hier gibt es schon drei Prim-Leitern):
Fall 1: alle Prim-Leitern beginnen ab der ersten Position, also:
Tabelle
XOOXOXX
3  3  3
5    5
7

@Primentus

1. Das heißt dann, Deine "Fälle" liegen alle rechts von dem Primorial, sind also größer als das.
Sehe ich das richtig? (ich glaubs eher nicht!)

Dazu auch Weird in 196 oben:


"Falls ich damit richtig liege, dann stellt sich natürlich die Frage, warum da nicht gleich die kleinstmögliche Startzahl einer "Realisation" des Patterns nimmst, deren Berechnung ebenfalls mit Chin. Restsatz ich ja schon in #37 angegeben hatte. "

2. Nachfragenswert erscheint mir auch, daß Du in Deiner Aufzählung so unheimlich verschieden große Anzahlen an Findungen hast. (bei 19, 20, 21 und 22 gibt es 4849845 mögliche Belegungen, davor 17 +18 = eine Größe und die 4 davor (13,14,15,16) wieder eine Größe. Müßte nicht jede Zahl ihre eigene Größe, d. h. ihre eigene Anzahl an Belegungen haben?



-----------------
Das Schwierige ist nicht die Mathematik. Schwierig ist es zu formulieren, daß man selber versteht, was man sieht und die anderen auch!
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
-->> Fortsetzung auf der nächsten Seite -->>
Seite 5Gehe zur Seite: 1 | 2 | 3 | 4 | 5 | 6 | 7  
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]