| Autor |
  * Diophants bunte Quadrate |
|
querin
Aktiv 
Dabei seit: 12.01.2018
Mitteilungen: 746
 |  Beitrag No.80, vom Themenstarter, eingetragen 2023-02-26 21:47
|
\quoteon(2023-02-26 19:14 - hyperG in Beitrag No. 79)
OK, (N-k)*4*k habe ich als "Formel 4" eingebaut.
Bei k=43 stimmt sie mit meiner Formel 3 überein und darüber wächst die Anzahl der zu betrachtenden Glieder für die Partialsummen um je 1 (da n ja als Funktion von k angesehen werden kann).
Das hört sich wenig an, aber schon bei k=66 sind das 23 Glieder mehr,
was aus wenigen 100000 Partialsummen fast 1 Mrd. Partialsummen macht & bei 4 Threads meinen RAM überlastet! Bis k=65 wurde keine kleinere Fundstelle ermittelt. Ein Beweis für "Formel 3 ist immer ausreichend" ist das natürlich nicht!
\quoteoff
Ok, mir war nur aufgefallen, dass die Abschätzung besser als 3 (N^2 - (N-k-43)^2) sein müsste.
Für k=128 habe ich 33239 + [269714537] + 6476624 = 16620^2
|
 Profil
|
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben! |
hyperG
Senior 
Dabei seit: 03.02.2017
Mitteilungen: 1994
 | Beitrag No.81, eingetragen 2023-02-27 00:12
|
Sehr gut!
Damit kann ich die Formel 4 verfeinern:
(Formel3 * 2 + FormelQuerin)/3
\sourceon nameDerSprache
Naeherungsformel maxSummand (1=schnell; 2=sicher {k=71}; 3={k=83}; 4=(F3*2+F4)/3):4
Risikofaktor66 (in [] f³r k=8 61 ; k>8: kann 66):92
von Nmin-Offset(0;4;8;12):146
min=16615 k=128: 33231[1]+228826530[116] + 26803748[6] + 20427947[5] = 276091456 = (N=16616)^2 in 70.434 s PScount=677033491 21,6 GB
\sourceoff
Noch kleiner. Erstaunlich, dass RF=92% das schaffte!
Morgen nach der Arbeit werde ich natürlich ohne Offset 146 starten und die ganze Tabelle mit der neuen Formel4 durchrechnen...
Gute Nacht.
|
Profil
|
querin
Aktiv
Dabei seit: 12.01.2018
Mitteilungen: 746
| Beitrag No.82, vom Themenstarter, eingetragen 2023-02-27 22:59
|
Für $(k,N)$ treten nur Summanden der Form $a\cdot (2\,N-a)$ mit einem ganzzahligen $1\le a \le 2\,k$ auf.
Verwendest Du diese Eigenschaft bzw. könnte das eine Laufzeitverbesserung bringen?
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.83, eingetragen 2023-02-28 00:26
|
\quoteon(2023-02-27 22:59 - querin in Beitrag No. 82)
Für $(k,N)$ treten nur Summanden der Form $a\cdot (2\,N-a)$ mit einem ganzzahligen $1\le a \le 2\,k$ auf.
Verwendest Du diese Eigenschaft bzw. könnte das eine Laufzeitverbesserung bringen?
\quoteoff
Das ist die selbe obere Schranke wie Beitrag 78, da
\sourceon nameDerSprache
FullSimplify[Sqrt[n^2 - (n - k)*4*k]]
=FullSimplify[Sqrt[n^2 - (2*k*(2*n - 2*k))]]
= n-2*k für den Laufindex
\sourceoff
also die, die ich im Beitrag 81 als FormelQuerin bezeichnet hatte.
Also viel zu groß.
Und ja, wegen N^2 - (N - a)^2 = k*(2*N-a)
{siehe c++ Code }
haben alle Summanden bereits diese Form.
Ich hatte nur gerade viel Zeit in die Ausgabe ALLER Summanden gesteckt...
|
Profil
|
querin
Aktiv
Dabei seit: 12.01.2018
Mitteilungen: 746
| Beitrag No.84, vom Themenstarter, eingetragen 2023-02-28 12:20
|
\quoteon(2023-02-28 00:26 - hyperG in Beitrag No. 83)
Und ja, wegen N^2 - (N - a)^2 = k*(2*N-a)
{siehe c++ Code }
haben alle Summanden bereits diese Form.
\quoteoff
Sorry. Ich hatte übersehen, dass Du sowieso nur Quadratdifferenzen als Summanden verwendest.
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.85, eingetragen 2023-02-28 18:25
|
Hallo querin,
Du brauchst Dich nicht entschuldigen. Manchmal kommt man doch noch auf Ideen oder hat was übersehen.
Viele Verbesserungen & Optimierungen:
- nun doch Einzelzeiten und am Ende eine Gesamtzeit
- Auf Wunsch Ausgabe ALLER Summanden (nun 6 Parameter vor Start eingeben)
- Deine QuerinFormel als Formel 5 (bisher reichten alle Formel4 Fälle)
- Smaxmax ist der aus der Näherungsformel berechnete maximal betrachtete Summand
- ab k=8 gab es NIE einen Fall, wo der eine Teil der Partialsumme=0 war! Tests mit
\sourceon nameDerSprache
aktuelle Partialsumme <= Sollpartialsumme-kleinstesGliedderPartialsumme
\sourceoff
brachte manchmal eine Halbierung der AnzahlPartialsummenglieder, RAM & Zeit (alles Formel5):
https://matheplanet.com/matheplanet/nuke/html/uploads/c/47407_k61_ScountHalbiert.png
Wie man schön sieht, ist bei Formel 5 der Abstand zum größten Summanden oft etwa doppelt zu groß und kostet Unmengen an Rechenzeit & RAM.
Ich rechne gerade zur Sicherheit alle Werte noch einmal durch, da der größte Summand per Formel 3 {damaliges Max bei k=83} ja wegen k=128 nun mindestens Formel 4 sein muss.
Grüße
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.86, eingetragen 2023-02-28 19:39
|
Korrekturen durch Formel 4 (größerer maximal betrachteter Summand):
- k=92: im Beitrag 72 dort hinzugefügt
- k=101: im Beitrag 79
- k=104: Beitrag 79
- k=107: Beitrag 79
- k=110: Beitrag 79
- k=128: Beitrag 79
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.87, eingetragen 2023-03-01 18:16
|
Neue Berechnungen mit etwas mehr Sicherheit bei allen Parametern:
\sourceon Zusammenfassung k=92-130 mit Einzelzeiten, Formel 4, RF=89..91:
k=92: 17279[1]+ 55796041[79] + 12853200[8] + 5983080[4] = 74649600 = (N= 8640)^2 i 2422.450 s Scount=446106353|398275412 Smaxmax=3128751|3145664 F5 28,7GB
k=93: 17591[1]+ 59660820[81] + 11008633[7] + 6682572[4] = 77369616 = (N= 8796)^2 in 74.262 s Scount= 22972424| 18037307 Smaxmax=2668167|2650880 RF=89
k=94: 17903[1]+ 62201387[82] + 7874436[5] + 10044578[6] = 80138304 = (N= 8952)^2 in 44.051 s Scount= 19613322| 15435208 Smaxmax=2733500|2715903
k=95: 18191[1]+ 64726139[83] + 9775010[6] + 8217876[5] = 82737216 = (N= 9096)^2 in 9.109 s Scount= 15571241| 13948209 Smaxmax=2795735|2813616
k=96: 18737[1]+ 68260318[84] + 8391560[5] + 11107546[6] = 87778161 = (N= 9369)^2 in 90.286 s Scount= 25042204| 22879605 Smaxmax=2898792|2917217
k=97: 19049[1]+ 71031270[85] + 10464746[6] + 9210560[5] = 90725625 = (N= 9525)^2 in 50.622 s Scount= 20941674| 18743336 Smaxmax=2966201|2984936
k=98: 19353[1]+ 73844459[86] + 10747568[6] + 9032949[5] = 93644329 = (N= 9677)^2 in 10.754 s Scount= 19195613| 14966461 Smaxmax=3071040|3052005
k=99: 19907[1]+ 77708777[87] + 7292268[4] + 14061164[7] = 99082116 = (N= 9954)^2 in 105.146 s Scount= 30759544| 23856976 Smaxmax=3179267|3159680
k=100: 20243[1]+ 80818012[88] + 7496152[4] + 14120477[7] = 102454884 = (N=10122)^2 in 63.976 s Scount= 26344414| 20458830 Smaxmax=3253284|3233363
k=101: 20781[1]+ 82972164[88] + 17160096[8] + 7819840[4] = 107972881 = (N=10391)^2 in 515.145 s Scount=121798461| 93203716 Smaxmax=3381352|3360897
k=102: 21125[1]+ 86242780[89] + 17321304[8] + 7991760[4] = 111576969 = (N=10563)^2 in 377.029 s Scount=105791637| 81366759 Smaxmax=3458565|3437768
k=103: 21461[1]+ 89563125[90] + 10340688[5] + 15229087[7] = 115154361 = (N=10731)^2 in 202.325 s Scount= 90079349| 69531887 Smaxmax=3535136|3514005
k=104: 22015[1]+ 93898623[91] + 14105938[6] + 13149488[6] = 121176064 = (N=11008)^2 in 591.553 s Scount=128706131|116904490 Smaxmax=3648783|3670464
k=105: 22375[1]+ 97510662[92] + 16566896[7] + 11071411[5] = 125171344 = N=11188)^2 in 434.072 s Scount=114373901|103880497 Smaxmax=3730944|3752983
k=106: 22727[1]+ 101176498[93] + 11246355[5] + 16694916[7] = 129140496 = (N=11364)^2 in 252.064 s Scount= 97962593| 88811228 Smaxmax=3812471|3834860
k=107: 23305[1]+ 105961735[94] + 16752232[7] + 13055137[5] = 135792409 = (N=11653)^2 in 783.726 s Scount=169373754|130784690 Smaxmax=3979048|3956085
k=108: 23665[1]+ 109865695[95] + 12134745[5] + 17995784[7] = 140019889 = (N=11833)^2 in 535.937 s Scount=145386060|112203081 Smaxmax=4064289|4040968
k=109: 24025[1]+ 113862608[96] + 9760936[4] + 20664600[8] = 144312169 = (N=12013)^2 in 319.543 s Scount=122253462| 94575211 Smaxmax=4150248|4126569 29 GB
k=110: 24619[1]+ 121516031[98] + 12748280[5] + 17247170[6] = 151536100 = (N=12310)^2 in 298.836 s Scount= 63962169| 50809248 Smaxmax=4302144|4277875
k=111: 24987[1]+128339650[100] + 13435064[5] + 14300335[5] = 156100036 = (N=12494)^2 in 125.823 s Scount= 15064528| 13945552 Smaxmax=4366912|4391547
k=112: 25355[1]+130234850[100] + 16260048[6] + 14211431[5] = 160731684 = (N=12678)^2 in 228.322 s Scount= 45393086| 35716328 Smaxmax=4481684|4456683
k=113: 25957[1]+135972462[101] + 18239822[6] + 14216200[5] = 168454441 = (N=12979)^2 in 662.535 s Scount= 66734268| 60844410 Smaxmax=4614441|4640040
k=114: 26349[1]+140734687[102] + 17213784[6] + 15605805[5] = 173580625 = (N=13175)^2 in 484.601 s Scount= 58323982| 53069945 Smaxmax=4710600|4736589
k=115: 26725[1]+145516855[103] + 14559221[5] + 18466968[6] = 178569769 = (N=13363)^2 in 268.721 s Scount= 48136414| 44346317 Smaxmax=4804645|4831008
k=116: 27351[1]+151795124[104] + 11932180[4] + 23278321[7] = 187032976 = (N=13676)^2 in 818.782 s Scount= 83418812| 65863730 Smaxmax=4998912|4971927
k=117: 27743[1]+156905840[105] + 23119721[7] + 12379080[4] = 192432384 = (N=13872)^2 in 569.731 s Scount= 70748954| 56797925 Smaxmax=5098415|5071040
k=118: 28135[1]+162127583[106] + 15693400[5] + 20059506[6] = 197908624 = (N=14068)^2 in 330.944 s Scount= 59530908| 47944078 Smaxmax=5198700|5170935
k=119: 28769[1]+168885697[107] + 24718423[7] + 13295336[4] = 206928225 = (N=14385)^2 in 942.604 s Scount= 87342633| 80892444 Smaxmax=5345021|5373416
k=120: 29169[1]+174407346[108] + 16619744[5] + 21665966[6] = 212722225 = (N=14585)^2 in 644.451 s Scount= 74421137| 68896962 Smaxmax=5448616|5477409
k=121: 29561[1]+179996714[109] + 21373046[6] + 17078640[5] = 218477961 = (N=14781)^2 in 336.157 s Scount= 61583980| 55896337 Smaxmax=5551497|5580680
k=122: 30219[1]+187355245[110] + 26718560[7] + 14208076[4] = 228312100 = (N=15110)^2 i 1073.719 s Scount=105530143| 84642198 Smaxmax=5765376|5735539
k=123: 30651[1]+190040125[110] + 30403520[8] + 14411980[4] = 234886276 = (N=15326)^2 i 2580.705 s Scount=280635646|256251032 Smaxmax=5848320|5878587
k=124: 31051[1]+195991405[111] + 30371800[8] + 14662420[4] = 241056676 = (N=15526)^2 i 1400.113 s Scount=229836336|209905634 Smaxmax=5955787|5986452
k=125: 31717[1]+203776552[112] + 14915160[4] + 32784452[8] = 251507881 = (N=15859)^2 i 4100.009 s Scount=395296048|309803335 Smaxmax=6178312|6146985
k=126: 32149[1]+210210736[113] + 15119084[4] + 33043656[8] = 258405625 = (N=16075)^2 i 2985.141 s Scount=343087210|270041014 Smaxmax=6294741|6262984
k=127: 32565[1]+216669065[114] + 19532192[5] + 28902267[7] = 265136089 = (N=16283)^2 i 1660.089 s Scount=286404716|225677183 Smaxmax=6408864|6376693 14,4 GB
k=128: 33231[1]+224952075[115] + 24302402[6] + 26803748[6] = 276091456 = (N=16616)^2 in 398.176 s Scount=406134268|373435735 Smaxmax=6573567|6606400
k=129: 33679[1]+231918626[116] + 29326980[7] + 22306315[5] = 283585600 = (N=16840)^2 i 3300.398 s Scount=360035510|330316791 Smaxmax=6696000|6729279
k=130: 34103[1]+238855422[117] + 20898275[5] + 30982904[7] = 290770704 = (N=17052)^2 i 1765.252 s Scount=297038770|271316692 Smaxmax=6814503|6848204 14,8 GB
\sourceoff
Da die Eingabe des Risikofaktors je nach k zu sehr indirekten Einfluss auf
RAM & die hinteren Partialsummen hat (bei einer Sammelberechnung stieg der RAM-Bedarf pro k zu schnell an: k=8 benötigt 61%, dann eine weile 66%; k> 110 benötigt über 90%), überlege ich mir gerade eine neue Eingabe einer festen Anzahl an hinteren Summanden.
Testrechnung mit k=150 läuft noch, aber mit erweiterter Ausgabe...
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.88, eingetragen 2023-03-01 21:08
|
Nach 3 Anläufen endlich eine Ausgabe:
- zunächst mit RF=91% begonnen
https://matheplanet.com/matheplanet/nuke/html/uploads/c/47407_k_150_32GB.png
- dann bis Start-N=22707 bei 92% gerechnet -> Absturz wegen RAM-Überlauf
- dann ab 22707 mit 93% weiter (größere N -> bedeutet größeres Smax und mehr RAM)
bis endlich die Fundstelle nach insges. fast 1 Stunde kam:
https://matheplanet.com/matheplanet/nuke/html/uploads/c/47407_k_150.png
Die große Wartezeit resultiert aus dem großen Abstand zum Startwert: 140 Einheiten (bei nur 2 Rechenkernen)!
Natürlich hätte ich auch auf 1 Kern runter gehen können um beim RF=91% zu bleiben, aber das hätte dann auch die doppelte Zeit gekostet.
Grüße Gerd
|
Profil
|
querin
Aktiv
Dabei seit: 12.01.2018
Mitteilungen: 746
| Beitrag No.89, vom Themenstarter, eingetragen 2023-03-01 21:49
|
Bestenliste
$k=\text{Anzahl der Farben}$
$$\begin{array}{lcl}
\text{k=2 } & 5\times 5 & \text{StrgAltEntf } \#13 \\
\text{k=3 } & 21\times 21 & \#1 \\
\text{k=4 } & 31\times 31 & \#2 \\
\text{k=5 } & 40\times 40 & \text{StrgAltEntf } \#13 \\
\text{k=6 } & 56\times 56 & \text{StrgAltEntf } \#13 \\
\text{k=7 } & 77\times 77 & \text{StrgAltEntf } \#6 \\
\text{k=8 } & 84\times 84 & \text{StrgAltEntf } \#11 \\
\text{k=9 } & 96\times 96 & \text{DerEinfaeltige } \#17 \\
\text{k=10 } & 112\times 112 & \text{DerEinfaeltige } \#17 \\
\text{k=11 } & 145\times 145 & \text{DerEinfaeltige } \#17 \\
\text{k=12 } & 165\times 165 & \text{DerEinfaeltige } \#17 \\
\text{k=13 } & 202\times 202 & \text{DerEinfaeltige } \#17 \\
\text{k=14 } & 226\times 226 & \text{DerEinfaeltige } \#17 \\
\text{k=15 } & 254\times 254 & \text{DerEinfaeltige } \#17 \\
\text{k=16 } & 299\times 299 & \text{Kay_S } \#18 \\
\text{k=17 } & 327\times 327 & \text{Kay_S } \#18 \\
\text{k=18 } & 355\times 355 & \text{Kay_S } \#18 \\
\text{k=19 } & 412\times 412 & \text{DerEinfaeltige } \#22 \\
\text{k=20 } & 444\times 444 & \text{DerEinfaeltige } \#22 \\
\text{k=21 } & 476\times 476 & \text{DerEinfaeltige } \#22 \\
\text{k=22 } & 512\times 512 & \text{DerEinfaeltige } \#22 \\
\text{k=23 } & 577\times 577 & \text{DerEinfaeltige } \#22 \\
\text{k=24 } & 617\times 617 & \text{hyperG } \#24 \\
\text{k=25 } & 657\times 657 & \text{hyperG } \#24 \\
\text{k=26 } & 734\times 734 & \text{Kay_S } \#27 \\
\text{k=27 } & 774\times 774 & \text{Kay_S } \#27 \\
\text{k=28 } & 847\times 847 & \text{Kay_S } \#27 \\
\text{k=29 } & 899\times 899 & \text{hyperG } \#28 \\
\text{k=30 } & 951\times 951 & \text{hyperG } \#28 \\
\text{k=31 } & 999\times 999 & \text{hyperG } \#30 \\
\text{k=32 } & 1088\times 1088 & \text{hyperG } \#30 \\
\text{k=33 } & 1144\times 1144 & \text{hyperG } \#32 \\
\text{k=34 } & 1200\times 1200 & \text{hyperG } \#34 \\
\text{k=35 } & 1293\times 1293 & \text{hyperG } \#34 \\
\text{k=36 } & 1353\times 1353 & \text{hyperG } \#36 \\
\text{k=37 } & 1454\times 1454 & \text{hyperG } \#34 \\
\text{k=38 } & 1522\times 1522 & \text{hyperG } \#34 \\
\text{k=39 } & 1582\times 1582 & \text{hyperG } \#36 \\
\text{k=40 } & 1650\times 1650 & \text{hyperG } \#37 \\
\text{k=41 } & 1759\times 1759 & \text{hyperG } \#37 \\
\text{k=42 } & 1831\times 1831 & \text{hyperG } \#39 \\
\text{k=43 } & 1903\times 1903 & \text{hyperG } \#41 \\
\text{k=44 } & 2024\times 2024 & \text{hyperG } \#41 \\
\text{k=45 } & 2096\times 2096 & \text{hyperG } \#41 \\
\text{k=46 } & 2176\times 2176 & \text{hyperG } \#40 \\
\text{k=47 } & 2301\times 2301 & \text{hyperG } \#42 \\
\text{k=48 } & 2381\times 2381 & \text{hyperG } \#42 \\
\text{k=49 } & 2461\times 2461 & \text{hyperG } \#42 \\
\text{k=50 } & 2537\times 2537 & \text{hyperG } \#34 \\
\text{k=51 } & 2686\times 2686 & \text{hyperG } \#46 \\
\text{k=58 } & 3436\times 3436 & \text{hyperG } \#52 \\
\text{k=70 } & 4988\times 4988 & \text{hyperG } \#54 \\
\text{k=82 } & 6824\times 6824 & \text{hyperG } \#58 \\
\text{k=50 bis k=100} & & \text{hyperG } \#72 \\
\text{k=92 bis k=130} & & \text{hyperG } \#87 \\
\text{k=150 } & 22739\times 22739 & \text{hyperG } \#88 \\
\text{k=334 } & 111952\times 111952 & \text{hyperG } \#102 \\
\text{k=335 } & 112476\times 112476 & \text{hyperG } \#100 \\
\text{k=527 } & 278124\times 278124 & \text{hyperG } \#102 \\
\end{array}
$$
|
Profil
|
querin
Aktiv
Dabei seit: 12.01.2018
Mitteilungen: 746
| Beitrag No.90, vom Themenstarter, eingetragen 2023-03-01 21:54
|
Hallo Gerd 🙂
Deine Ausdauer ist wirklich bewundernswert 👍
Danke und viele Grüße
querin
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.91, eingetragen 2023-03-01 23:45
|
Wird es einen weiteren Einbruch bei der Differenz zum theoretischen Nmin geben?
https://matheplanet.com/matheplanet/nuke/html/uploads/c/47407_DifferenzenDiagrammUntergrenze130.PNG
Wenn nicht, dann könnte man viel Rechenzeit sparen...
Auffällig ist auch die Differenz von 4 bei Fundstellen mit gleichem k.
So könnte ich wieder parallel die "schnellste Fundstelle" suchen -> und dann entlang der STEP 4 Linie nach kleineren Fundstellen Ausschau halten...
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.92, eingetragen 2023-03-02 19:47
|
Und da ist er schon: "der nächste Einbruch"!
\sourceon nameDerSprache
theoretische Vorhersage von Querin:
('k=', 143, ' N=', 20544, '...', (20556, 20606), ' i=', 139, ' a=', 20411)
Nachgerechnet mit Formel 4:
min=20544 k=143: 41111[1]+354655275[130] + 33681380[6] + 34171370[6] = 422549136 = (N=20556)^2 in 601.985 s
Zugabe:
k=146: 42849[1]+386724366[133] + 35876330[6] + 36387080[6] = 459030625 = (N=21425)^2 in 679.853 s
\sourceoff
Stimmt überein! Differenz zum Nmin=12 Einheiten (Einbruch im Liniendiagramm)
Deshalb auch schnell zu finden :-)
Grüße
Nachtrag: k=146 auch Differenz 12
|
Profil
|
querin
Aktiv
Dabei seit: 12.01.2018
Mitteilungen: 746
| Beitrag No.93, vom Themenstarter, eingetragen 2023-03-02 21:12
|
\quoteon(2023-03-01 23:45 - hyperG in Beitrag No. 91)
Auffällig ist auch die Differenz von 4 bei Fundstellen mit gleichem k.
So könnte ich wieder parallel die "schnellste Fundstelle" suchen -> und dann entlang der STEP 4 Linie nach kleineren Fundstellen Ausschau halten...
\quoteoff
Der 4-Abstand ist mir auch aufgefallen. Ich hatte das für k=53 genauer untersucht.
Ausgehend von großen N ("schneller Fund") gibt es step-4-Ketten, die bei
N = 3042 = 2 mod 4,
N = 3005 = 1 mod 4,
N = 2948 = 0 mod 4,
N = 2915 (Minimum) = 3 mod 4
enden.
Von einem beliebigen "schnellen Fund" ausgehend wird es zwar step-4 Ketten mit kleineren N geben, aber das Minimum ist damit i.A. nicht zu finden.
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.94, eingetragen 2023-03-02 22:22
|
Ich hatte die selbe Idee mit k=53 (weil da der Einbruch fehlt) und habe sogar das Programm derart geändert, dass auch negative Offsets eingebbar sind. (also Nmin kleiner als Deine Nmin Formel!)
Start ab -13 bis hin zur bekannten Nullstelle und noch mehr Sicherheit beim RF=66 und Deiner zu großen Formel 5 für größten Summanden:
- hat richtig lange gedauert!
- volle 32 GB RAM nötig
- leider KEINE Fundstelle (für mich natürlich kein LEIDER, da ich alle Risikofaktoren hätte anpassen müssen)
Oder Struktur in den beiden Folgen:
\sourceon Folge der "Einbrüche"
k: 50| 95| 98| 143|146
Diff: 4| 8| 8| 12| 12
\sourceoff
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.95, eingetragen 2023-03-02 22:55
|
Hier die explizite Formel für die Einbrüche:
\sourceon Mathematica
Table[{n,97/2+48 Floor[n/2]-3/2*(-1)^n,Floor[n/2+1]*4},{n,0,11}]//Grid
n k Diff
0 47 4 ???
1 50 4
2 95 8
3 98 8
4 143 12
5 146 12
6 191 16
7 194 16
8 239 20
9 242 20
10 287 24
11 290 24
...
\sourceoff
Damit könnte ich auch die Suche für alle anderen weiter eingrenzen!
Gegenargumente?
Die 47 schaue ich mir genauer an...
Nix. Dann beginnt diese Folge (wie viele OEIS-Folgen) erst bei n=1.
k=191 läuft...
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.96, eingetragen 2023-03-02 23:26
|
Explizite Formel für die "Einbruchstellen" mit meinem Programm bis k=194
bestätigt!!
https://matheplanet.com/matheplanet/nuke/html/uploads/c/47407_k_191.PNG
https://matheplanet.com/matheplanet/nuke/html/uploads/c/47407_k_194.PNG
Hinweis: noch habe ich das Programm nicht geändert! Nur durch die Theorie bin ich mit Offset 15 (besser wäre 16, aber durch 2 Threads war das mit abgedeckt) genau an die richtige Stelle für das N gesprungen und die beiden Risikofaktoren RF=95% (vorn) und Formel 4 (hinten) haben ausgereicht für diese Fundstelle.
Ist das der Quantensprung für die "Einbruchstellen"? {was doch die richtige Motivation ausrichten kann...}
|
Profil
|
querin
Aktiv
Dabei seit: 12.01.2018
Mitteilungen: 746
| Beitrag No.97, vom Themenstarter, eingetragen 2023-03-03 12:36
|
Deine Formel für die minimalen Differenzen kann ich bestätigen, man könnte sie auch so schreiben $3\,n+42\,\lfloor n/2\rfloor+47$.
Daraus ergibt sich die Abschätzung für alle k: $\text{Diff}(k)\ge \lfloor (k+4)/12 \rfloor$
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.98, eingetragen 2023-03-03 23:38
|
Die Floor-Funktion habe ich noch durch cos-Funktion ersetzt und konnte sie mit
\sourceon Mathematica
InverseFunction[Function[n, (73 + 48 n + 21 Cos[n Pi])/2]][k]
\sourceoff
in eine Funktion N(k) wandeln, die mit einem Case-Verteiler:
a) Inverse= ganzzahlig {dann exakt}
b) k mod 3==0
c) k mod 3==1
d) k mod 3 ==2
in der Differenz-Ansicht (ab k=53) dann orange so aussieht:
https://matheplanet.com/matheplanet/nuke/html/uploads/c/47407_DifferenzenDiagrammUntergrenze130_NForange.PNG
Das zu durchsuchende Toleranzband verringert sich damit enorm,
wenn es nicht doch noch "Ausreißer" gibt, die das immer größer werdende Kartenhaus aus zig Annahmen zusammenbrechen lässt...
Grüße
|
Profil
|
querin
Aktiv
Dabei seit: 12.01.2018
Mitteilungen: 746
| Beitrag No.99, vom Themenstarter, eingetragen 2023-03-04 12:01
|
Die Darstellung mit cos ist klar, mit einer Fallunterscheidung könnte man auch einfach rechnen
$24\,n+47$ für gerade $n$
$24\,n+26$ für ungerade $n$
Aber was die InverseFunction macht und warum hier Fallunterscheidungen mod 3 auftreten verstehe ich nicht.
Nach der Formel ist $\text{Diff}(k=95)=8$.
Wie sollte man daraus mit Hilfe der Formel auf etwas Besseres als $\text{Diff}(k=96)\ge 8$ schließen können?
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.100, eingetragen 2023-03-04 16:41
|
Die im Beitrag 95 vorgestellte Formel bezieht sich doch nur auf Sonderfälle für Einbruchstellen mit der Hilf-Index-Variable n.
Bei universeller Eingabe gibt man aber beliebiges k vor!
Man benötigt also eine Inverse Funktion, um (intern) von k auf die Hilfsvariable n (hätte besser j oder h nehmen sollen) zu kommen, um daraus entscheiden zu können, ob denn eine Einbruchstelle vor liegt.
Nun bin ich schon weiter und erweitere die Berechnung auch für NICHT-Einbruchstellen. Dabei fand ich weitere 3 Regelmäßigkeiten, die ich mit Mod 3 in einem Case-Verteiler gesondert betrachte (eine Universallösung habe ich ja noch nicht).
Beispiel k=334..335:
https://matheplanet.com/matheplanet/nuke/html/uploads/c/47407_k_335Inverse.PNG
Im Fall 334 ergibt die Inverse keine ganze Zahl (Offset 27.9 ist unbrauchbar) und muss mit einer der 3 Mod-Näherungsformeln berechnet werden. (Offset 268 ist nur eine Näherung).
Nur die k=335 ergibt eine ganzzahlige Inverse, wo Offset 28 direkt genommen werden kann.
Natürlich bin ich immer noch Misstrauisch (ob nicht doch noch 4 weiter vorn eine kleinere Lösung) und gebe das kleinere Offset 23 ein. Nach 2 Runden mit je 2 Threads kam ich so auf die 28er Fundstelle (also stimmte Vorhersage exakt):
https://matheplanet.com/matheplanet/nuke/html/uploads/c/47407_k_335k.PNG
Wow! -> aber bei immer größeren k wird RF zu groß und ungenau, weshalb ich demnächst auf eine andere Eingabe absolute "Anzahl hintere Partialsummen" umsteigen werde.
Korrektur: nur im Bild letzte Zeile (3 Summanden) gab es einen internen Überlauf -> im Programm & im Bild korrigiert!
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.101, eingetragen 2023-03-05 13:03
|
\quoteon(2023-03-04 12:01 - querin in Beitrag No. 99)
... mit einer Fallunterscheidung könnte man auch einfach rechnen
$24\,n+47$ für gerade $n$
$24\,n+26$ für ungerade $n$
...
\quoteoff
Ja stimmt, rechentechnisch ist ein weiterer Case-Fall zig mal schneller & sicherer als eine ungenaue cos-Funktion oder sogar deren Inverse (acos...).
Zusammen umgestellt nach k wird aus der "gerade/ungerade" Abfrage eine Mod 48:
\sourceon Mathematica
HilfsInverseEinbruch[k_] :=
If[Mod[k, 48] == 2, (k - 26)/24,
If[Mod[k, 48] == 47, (k - 47)/24, 0]];
\sourceoff
Im Falle eines NICHT-Einbrachs-Falles ergibt das 0, der mit den anderen 3 Modulos noch verfeinert werden muss.
k=52 rechne ich gerade mit höchster Sicherheit nochmals nach, da N eigentlich (nach meiner Theorie) kleiner sein müsste...
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.102, eingetragen 2023-03-05 19:20
|
@querin: kannst Du bitte mal k=52 testen?
Ich habe trotz höchster Sicherheitseinstellung kein kleineres N als 2819 gefunden. 2 Möglichkeiten:
a) meine Näherungsformel für diesen Modulo-Fall ist erst oberhalb k>52 genau
(Sicherheitsabstand ist bei diesem Fall noch sehr groß, was nur die Wartezeit unnütz vergrößert)
b) es gibt doch noch eine kleinere Lösung, weil: größter Summand ist noch größer als Deine Formel5 und/oder RF nicht klein genug (selbst 19 Partialsummen und 32 GB RAM reichen nicht aus, um hier eine kleinere Lösung zu finden)
Dann habe ich weitere Verbesserungen eingebaut:
- Auswahl zwischen "Eingabe der festen Partialsummenanzahl" oder der alte "Risikofaktor in %"
- Berechnung und Anzeige des prognostizierten Offsets
Damit sind nicht nur große Einbruchstellen exakt vorhersehbar, sondern auch die anderen 3 Modulo-Fälle schneller berechenbar.
Wie bereits im Beitrag 100 angedeutet hier nun der Fall k=334:
https://matheplanet.com/matheplanet/nuke/html/uploads/c/47407_k_334.png
Nach nur 12 Runden (statt 179 bei Offset 0 nach alter Formel für nmin) kam die Fundstelle.
Wegen der exakten Vorgabe der Partialsummenanzahl kann man sich RAM-technisch exakt an die noch machbare Speichergrenze herantasten. Hier nun ohne Multitasking
k=527:
https://matheplanet.com/matheplanet/nuke/html/uploads/c/47407_k_527_13GBk.PNG
Schönen Restsonntag!
Nachtrag: ich suche noch nach ein besseres Wort für "Partialsummenanzahl".
In Wirklichkeit ist die Logik hinter der eingegebenen 8:
8 aus (107*2=214) -> also Binom(214,8)=95563144300338 theoretischen Partialsummen ;
Wegen Ausklammerung SollHi & nie eine Partialsumme==0 -> jedoch nur 1379856152 Partialsummen zu betrachten, wobei dann die letzten 8 Summanden eine exakte Summe ergeben müssen.
Es ist auch nicht die Merge-Size 214 (die daraus 2 107er Arrays macht), sondern es wird noch aus allen richtigen Soll-Partialsummen die herausgesucht, dessan Summandenanzahl exakt der Vorgabe entspricht.
Besser wäre z.B.: "hintere Summandenanzahl-Vorgabe für's Mergen".
|
Profil
|
querin
Aktiv
Dabei seit: 12.01.2018
Mitteilungen: 746
| Beitrag No.103, vom Themenstarter, eingetragen 2023-03-05 21:47
|
k=52 habe ich ausführlich getestet und auch keine kleinere Lösung gefunden.
Erstaunlich, dass Du immer noch weitere Optimierungen findest 👍
Deine Werte für k=334, k=335 und k=527 sind in die Bestenliste eingetragen.
Bist Du sicher, dass diese Lösungen minimal sind? Es sind ja (außer bei 334) genau die Nmax meiner einfachen Abschätzung.
Grüße
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 1994
| Beitrag No.104, eingetragen 2023-03-06 00:59
|
\quoteon(2023-03-05 21:47 - querin in Beitrag No. 103)
...
Bist Du sicher, dass diese Lösungen minimal sind? Es sind ja (außer bei 334) genau die Nmax meiner einfachen Abschätzung.
Grüße
\quoteoff
Wie im Beitrag 54 & 98 (und weiteren) bereits beschrieben, bin ich mir NICHT 100% sicher, da ich mehrere Annahmen treffen musste, von denen ich die meisten nicht beweisen kann:
- größter Summand mit Formel 4 hat bisher immer gereicht (Du hattest Formel5)
- RF bzw. AnzahlPartitionen (vordere Summanden immer ungerade/gerade)
- Einbruchstellen: ja, diese explizite Formel stimmt mit Deinen oft überein; da sie wesentlich kleiner als die anderen 3 Mod3 Fälle ist, schätze ich sie zu 99% sicher ein.
Deshalb sieht man auch bei den letzten Fundstellen immer die Screenshots mit allen Parametern.
|
Profil
|
Home / Seite ohne Frame
2023-03-26 20:19 U <
Wie unterstütze ich den Matheplaneten mit Geld?
