Discussion:
Ganzzahlenreihe, deren Elemente keine Summen und Differenzen von 3 anderen Elementen der Reihe sind
(zu alt für eine Antwort)
Marcel Mueller
2018-03-03 17:24:42 UTC
Permalink
Raw Message
Hallo,

ich bin auf der Suche nach einer Reihe möglichst dichter ganzer Zahlen,
deren Elemente sich /nicht/ als Summen oder Differenzen von maximal
/drei/ anderen Elementen der Reihe darstellen lassen.

Für Summen und Differenzen aus maximal /zwei/ anderen Elementen ist das
trivial: alle ungeraden Zahlen.
Aber was macht man bei /drei/ Summanden?
Mit Modulo-N wie bei 2 Zahlen komme ich da nicht weiter. Spätestens die
Terme der Art A+B-C haben liefern bei egal welchem N immer denselben
Modulo-N wie die Komponenten des Terms.


Hintergund: die Frage kommt eigentlich aus der Messtechnik. Ich versuche
eine nichtlineares Übertragungsfunktion mit einem Frequenzspektrum zu
auf einen Schlag Charakterisieren. Nichtlinearitäten erzeugen
Intermodulation, die sich in Summen oder Differenzen enthaltener
Frequenzen manifestiert. Dabei können an sich beliebig viele Terme
auftreten, aber in der Praxis sind die höheren Ordnungen bei moderaten
Nichtlinearitäten vernachlässigbar klein.

Irgendwelche Ideen?
Ich weiß ehrlich gesagt überhaupt nicht, wie man da ansetzen sollte.


Marcel
Rainer Rosenthal
2018-03-04 00:01:27 UTC
Permalink
Raw Message
Post by Marcel Mueller
Hallo,
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer Zahlen,
deren Elemente sich /nicht/ als Summen oder Differenzen von maximal
/drei/ anderen Elementen der Reihe darstellen lassen.
Hintergund: die Frage kommt eigentlich aus der Messtechnik. ...
Irgendwelche Ideen?
Ich weiß ehrlich gesagt überhaupt nicht, wie man da ansetzen sollte.
Es ist eine hübsche Fragestellung, an die man beispielsweise
experimentell mit der greedy-Methode herangehen kann.
Du suchst Zahlenmengen, die in der von Dir beschriebenen Weise
"sperrig" sind.
Du startest mit einer kleinen sperrigen Menge M_0 und erweiterst sie
um die kleinste mögliche Zahl zu einer sperrigen Menge M_1.
Das ist wilde Probiererei, die ein Programm Deiner Wahl liebend gerne
für Dich erledigt, aber es ist immerhin ein Anfang.

Mit etwas Glück sammelst Du dabei Datenmaterial in Form von Zahlen-
folgen, die Du dann in der Online Enzyklopädie der Ganzzahl-Folgen
(OEIS, https://oeis.org) wiederfindest - zusammen mit spannenden
Querverweisen.

Ich will mir das mal näher anschauen, aber nur zum Spaß, und wenn der
Sonntag Zeit dazu lässt.

Alles Gute,
Gruß,
Rainer Rosenthal
Valentin Schmidt
2018-03-04 01:45:24 UTC
Permalink
Raw Message
Post by Marcel Mueller
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer Zahlen,
deren Elemente sich /nicht/ als Summen oder Differenzen von maximal
/drei/ anderen Elementen der Reihe darstellen lassen.
Hallo Marcel,

ich bin mir bewusst, dass es dir um eigentlich um eine mathematische
Definition so einer Reihe geht. Aber falls es doch irgendwie
weiterhelfen könnte, hier der numerische (=mit Computer generierte)
Output einer Reihe von Zahlen zw. 1 und 1000, für die diese Bedingung
erfüllt ist, ausgehend von der Start-Reihe 1,2,3:

[1, 2, 3, 10, 20, 34, 49, 75, 91, 136, 161, 227, 265, 340, 396, 445,
553, 617, 740, 803, 917]

Valentin
Valentin Schmidt
2018-03-04 01:53:50 UTC
Permalink
Raw Message
Post by Valentin Schmidt
Post by Marcel Mueller
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer Zahlen,
deren Elemente sich /nicht/ als Summen oder Differenzen von maximal
/drei/ anderen Elementen der Reihe darstellen lassen.
Hallo Marcel,
ich bin mir bewusst, dass es dir um eigentlich um eine mathematische
Definition so einer Reihe geht. Aber falls es doch irgendwie
weiterhelfen könnte, hier der numerische (=mit Computer generierte)
Output einer Reihe von Zahlen zw. 1 und 1000, für die diese Bedingung
[1, 2, 3, 10, 20, 34, 49, 75, 91, 136, 161, 227, 265, 340, 396, 445,
553, 617, 740, 803, 917]
ps: sorry, ich hatte das *maximal* drei in deiner Frage überlesen. Bei
dieser Reihe handelt es sich stattdessen um Zahlen, die sich nicht durch
Summen oder Diffrenzen von *genau* drei voherigen Elementen darstellen
lassen.
Valentin Schmidt
2018-03-04 11:38:18 UTC
Permalink
Raw Message
Post by Valentin Schmidt
Post by Marcel Mueller
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer Zahlen,
deren Elemente sich /nicht/ als Summen oder Differenzen von maximal
/drei/ anderen Elementen der Reihe darstellen lassen.
Hallo Marcel,
ich bin mir bewusst, dass es dir um eigentlich um eine mathematische
Definition so einer Reihe geht. Aber falls es doch irgendwie
weiterhelfen könnte, hier der numerische (=mit Computer generierte)
Output einer Reihe von Zahlen zw. 1 und 1000, für die diese Bedingung
Gestern abend war es doch schon bisschen zu spät für bug-freien Code ;)

Aber ich habe das grade nochmal korrekt durchgerechnet:


a) Wenn mit "anderen Elementen der Reihe" gemeint ist, dass diese NICHT
unterschiedlich sein müssen - also auch das selbe vorherige Element
mehrfach in Summe/Differenz einbezogen werden kann - ist ein Ergebnis
folgende Reihe:

1, 4, 10, 17, 29, 52, 67, 89, 132, 164, 205, 259, 303, 350, 405, 505,
529, 588, 680, 903, ...

Diese Reihe ist bei OESIS bereits als "A096077" registriert:
https://oeis.org/A096077

Hier der Wolfram-Plot dazu:
http://bit.ly/2FkVed7


b) Wenn gemeint ist, dass die Element unterschiedlich sein müssen, also
jedes Element nur einmal in Summe/Differenz eingehen kann, ist ein
Ergebnis stattdessen diese Reihe:

1, 2, 3, 7, 13, 24, 41, 59, 77, 106, 151, 200, 219, 249, 335, 386, 437,
549, 616, 671, 704, 793, ...

Diese Reihe ist bei OESIS anscheinend nicht bekannt.

Wolfram-Plot dazu:
http://bit.ly/2tgmTHm


Valentin
Rainer Rosenthal
2018-03-04 11:59:38 UTC
Permalink
Raw Message
Post by Valentin Schmidt
Post by Marcel Mueller
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer Zahlen,
deren Elemente sich /nicht/ als Summen oder Differenzen von maximal
/drei/ anderen Elementen der Reihe darstellen lassen.
b) Wenn gemeint ist, dass die Element unterschiedlich sein müssen, also
jedes Element nur einmal in Summe/Differenz eingehen kann, ist ein
1, 2, 3, 7, 13, 24, 41, 59, 77, 106, 151, 200, 219, 249, 335, 386, 437,
549, 616, 671, 704, 793, ...
Diese Reihe ist bei OESIS anscheinend nicht bekannt.
Was macht die 3 hier?
Ich nehme die anderen Elemente 1 und 2 und stelle die 3 dar als 3 = 1+2.
Das zeigt, dass die 3 hier fehl am Platz ist.
Valentin Schmidt
2018-03-04 12:28:45 UTC
Permalink
Raw Message
Post by Rainer Rosenthal
Post by Valentin Schmidt
b) Wenn gemeint ist, dass die Element unterschiedlich sein müssen, also
jedes Element nur einmal in Summe/Differenz eingehen kann, ist ein
1, 2, 3, 7, 13, 24, 41, 59, 77, 106, 151, 200, 219, 249, 335, 386, 437,
549, 616, 671, 704, 793, ...
Diese Reihe ist bei OESIS anscheinend nicht bekannt.
Was macht die 3 hier?
Ich nehme die anderen Elemente 1 und 2 und stelle die 3 dar als 3 = 1+2.
Das zeigt, dass die 3 hier fehl am Platz ist.
Uups, danke für den Hinweis! Während Lösung für Fall a) stimmte, war für
b) leider doch noch ein Bug im Code.

Ich glaube aber, dass diese Lösung für b) jetzt hinhaut:

0, 1, 3, 8, 18, 30, 43, 67, 90, 122, 161, 202, 260, 305, 388, 416, 450,
555, 624, 730, 750, 983

Falls ja: auch diese Reihe kennt OEIS nicht
Valentin Schmidt
2018-03-04 12:36:55 UTC
Permalink
Raw Message
Post by Valentin Schmidt
0, 1, 3, 8, 18, 30, 43, 67, 90, 122, 161, 202, 260, 305, 388, 416, 450,
555, 624, 730, 750, 983
Verdammt! Jetzt aber wirklich! ;-)

0, 1, 2, 4, 8, 15, 26, 44, 64, 84, 115, 162, 209, 259, 296, 333, 428,
482, 537, 604, 710, 843, 946
Rainer Rosenthal
2018-03-04 12:54:23 UTC
Permalink
Raw Message
Post by Valentin Schmidt
Post by Valentin Schmidt
0, 1, 3, 8, 18, 30, 43, 67, 90, 122, 161, 202, 260, 305, 388, 416, 450,
555, 624, 730, 750, 983
Verdammt! Jetzt aber wirklich! ;-)
0, 1, 2, 4, 8, 15, 26, 44, 64, 84, 115, 162, 209, 259, 296, 333, 428,
482, 537, 604, 710, 843, 946
Gratuliere!
Ich habe zu lange gelabert. Hatte meine Folge fertig und sah, dass
Deine anders aussah. Aber mein Veröffentlichungsdatum liegt nun mal
jetzt leider 5 Minuten nach Deinem *schluchz*.
Und ich wollte doch endlich mal wieder eine schöne Folge einreichen
können. Die Idee geht ohnehin auf Marcel Mueller zurück, dem ich hiermit
nochmals zu der schönen Aufgabenstellung gratuliere.

Anmerkung:
Mein Programm (Maple) startet mit der leeren Menge. Das finde ich nett:
S := {}:
for i to 20 do
H := huelle(S);
m := mex(S union H);
S := S union {m};
od:
print(S);
{1, 2, 4, 8, 15, 26, 44, 64, 84, 115, 162, 209, 259, 296, 333, 428, 482,
537, 604, 710}

Ich lasse meine lahme Implementierung nudeln, und bei 60 Zahlen fängt
es an, zäh zu werden.

Gruß,
Rainer Rosenthal
***@web.de
Valentin Schmidt
2018-03-04 19:45:07 UTC
Permalink
Raw Message
Post by Rainer Rosenthal
Post by Valentin Schmidt
Verdammt! Jetzt aber wirklich! ;-)
0, 1, 2, 4, 8, 15, 26, 44, 64, 84, 115, 162, 209, 259, 296, 333, 428,
482, 537, 604, 710, 843, 946
Gratuliere!
Ich habe zu lange gelabert. Hatte meine Folge fertig und sah, dass
Deine anders aussah. Aber mein Veröffentlichungsdatum liegt nun mal
jetzt leider 5 Minuten nach Deinem *schluchz*.
Ach, ist doch egal. Die Fields-Medaille überlasse ich gerne dir ;)
Das schöne an solchen Online-Geschichten wie z.B. Newsgroups ist doch,
gemeinsam zu einer Lösung zu kommen.

Hier zum Abschluss noch ein Plot mit beiden Varianten a) und b) der
"Marcel-Müller-Reihen", übereinander gelegt:

Loading Image...

Sie entwickeln sich ähnlich, aber interessanterweise "schneiden" (wenn
sie als kontinuierlich gedacht und Punkte verbunden werden) sie sich
immer wieder.

Gruß
Valentin
Valentin Schmidt
2018-03-04 20:50:13 UTC
Permalink
Raw Message
Post by Valentin Schmidt
Hier zum Abschluss noch ein Plot mit beiden Varianten a) und b) der
http://valentin.dasdeck.com/tmp/mmreihen.png
Sie entwickeln sich ähnlich, aber interessanterweise "schneiden" (wenn
sie als kontinuierlich gedacht und Punkte verbunden werden) sie sich
immer wieder.
"Schmidtsche Vermutung:
Für die beiden Marcel-Müller-Reihen Ma(n) (=OEIS A096077) und Mb(n)
(=keine Wiederholungen erlaubt) gilt: mit steigendem n wechselt
Ma(n)-Mb(n) unendlich oft das Vorzeichen."

Bisher ausgelobtes Preisgeld für Bestätigung oder Widerlegung der
Vermutung: 1 Flasche Bier ;-)
Rainer Rosenthal
2018-03-04 21:21:34 UTC
Permalink
Raw Message
Post by Valentin Schmidt
Post by Valentin Schmidt
Hier zum Abschluss noch ein Plot mit beiden Varianten a) und b) der
http://valentin.dasdeck.com/tmp/mmreihen.png
Sie entwickeln sich ähnlich, aber interessanterweise "schneiden" (wenn
sie als kontinuierlich gedacht und Punkte verbunden werden) sie sich
immer wieder.
Für die beiden Marcel-Müller-Reihen Ma(n) (=OEIS A096077) und Mb(n)
(=keine Wiederholungen erlaubt) gilt: mit steigendem n wechselt
Ma(n)-Mb(n) unendlich oft das Vorzeichen."
Bisher ausgelobtes Preisgeld für Bestätigung oder Widerlegung der
Vermutung: 1 Flasche Bier ;-)
Im Moment brauche ich eher Thymian- oder Kamillentee.

Du könntest Dich unsterblich ums OEIS verdient machen, wenn Du die
Folge Mb(n) einreichen würdest, dabei die Querverbindung zu A096077
notieren und die Schmidtsche Vermutung formulierend.

Ist mit ein paar formalen Hürden verbunden, aber wenn Du es mal
gemacht hast, wirst Du Dich sicher schon darauf freuen, bei Gelegenheit
eine andere hübsche Entdeckung - als Folge verpackt - ins OEIS
stellen zu können.

Viel Glück!
Von solchem Einsatz lebt das OEIS. Das Allerschönste, was Dir dabei
passieren kann, ist, dass Du was zum Thema X einreichst und nach ein
paar Jahren feststellst, dass irgendwelche Leute sich mit anderen
Themen Y und Z befasst hatten und bei genau der gleichen Folge gelandet
waren. Solche Glücksfälle hatte ich zwei- oder dreimal. Macht Freude,
na gönnst sich ja sonst nix.

Gruß,
Rainer
Valentin Schmidt
2018-03-04 12:07:41 UTC
Permalink
Raw Message
Post by Valentin Schmidt
a) Wenn mit "anderen Elementen der Reihe" gemeint ist, dass diese NICHT
unterschiedlich sein müssen - also auch das selbe vorherige Element
mehrfach in Summe/Differenz einbezogen werden kann - ist ein Ergebnis
1, 4, 10, 17, 29, 52, 67, 89, 132, 164, 205, 259, 303, 350, 405, 505,
529, 588, 680, 903, ...
https://oeis.org/A096077
Noch eine kleine Randbemerkung zu OESIS A096077:

wenn du mit 0 oder 1 startest, erhälst du in beiden Fällen A096077 (halt
nur entweder mit oder ohne einer 0 am Anfang).

Und aufgrund des Distributivgesetzes wäre eine gültige Lösung für
Startwert 2 natürlich einfach die Verdopplung aller Elemente von
A096077, also

2, 8, 20, 34, 58, ...

Aber interessanterweise gibt es "dichtere Lösungen" als obige, für
Startwert 2 zB diese hier:

2, 3, 10, 19, 33, 44, 59, 83, 131, 158, 213, 266, 284, 385, 455, 492,
559, 643, 722, 787, 819, ...
Marcel Mueller
2018-03-08 22:17:52 UTC
Permalink
Raw Message
Hallo!
Post by Valentin Schmidt
a) Wenn mit "anderen Elementen der Reihe" gemeint ist, dass diese NICHT
unterschiedlich sein müssen - also auch das selbe vorherige Element
mehrfach in Summe/Differenz einbezogen werden kann - ist ein Ergebnis
1, 4, 10, 17, 29, 52, 67, 89, 132, 164, 205, 259, 303, 350, 405, 505,
529, 588, 680, 903, ...
Tatsächlich war meine Spezifikation in diesem Punkt unvollständig. Die
Zahlen dürfen mehrfach vorkommen. Also, die 1 schließt aus dem Stand
gleich die 2 und 3 aus, die 4 entsprechend die 8 und die 12, und im
Kombination mit der 1 gehen dann noch die 5, 6, 7 und 9 nach Hause.
Post by Valentin Schmidt
https://oeis.org/A096077
Ja, passt.

Es scheint auch mit vernünftiger Komplexität möglich zu sein, die Sache
zu berechnen. Leider ist die Zahlenreihen weniger dicht, als ich mir
erhofft hatte - im Besonderen verglichen mit den ungeraden Zahlen für
maximal 2-er Terme. Da muss ich mal sehen, was ich daraus mache.


Marcel
Hans-Peter Diettrich
2018-03-09 00:53:05 UTC
Permalink
Raw Message
Post by Marcel Mueller
Hallo!
Post by Valentin Schmidt
a) Wenn mit "anderen Elementen der Reihe" gemeint ist, dass diese NICHT
unterschiedlich sein müssen - also auch das selbe vorherige Element
mehrfach in Summe/Differenz einbezogen werden kann - ist ein Ergebnis
1, 4, 10, 17, 29, 52, 67, 89, 132, 164, 205, 259, 303, 350, 405, 505,
529, 588, 680, 903, ...
Tatsächlich war meine Spezifikation in diesem Punkt unvollständig. Die
Zahlen dürfen mehrfach vorkommen.
Wie soll das zu Deinem physikalischen Problem passen?

Zudem ergibt sich dann eine Unstimmigkeit: Wenn x und y Elemente der
Reihe sind, dann ergibt x+y-y wieder x, das in der Reihe bereits
enthalten ist.

DoDi
Valentin Schmidt
2018-03-09 09:51:34 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Post by Marcel Mueller
Hallo!
Post by Valentin Schmidt
a) Wenn mit "anderen Elementen der Reihe" gemeint ist, dass diese NICHT
unterschiedlich sein müssen - also auch das selbe vorherige Element
mehrfach in Summe/Differenz einbezogen werden kann - ist ein Ergebnis
1, 4, 10, 17, 29, 52, 67, 89, 132, 164, 205, 259, 303, 350, 405, 505,
529, 588, 680, 903, ...
Tatsächlich war meine Spezifikation in diesem Punkt unvollständig. Die
Zahlen dürfen mehrfach vorkommen.
Wie soll das zu Deinem physikalischen Problem passen?
Zudem ergibt sich dann eine Unstimmigkeit: Wenn x und y Elemente der
Reihe sind, dann ergibt x+y-y wieder x, das in der Reihe bereits
enthalten ist.
Nee, das ergibt keine Unstimmigkeit, da es ja nicht um eine
Mengendefinition, sondern eine "quasi-rekursive" Definition einer Folge
geht. x+y-y = x bedeutet nur, dass in dieser Folge kein Element jemals
doppelt vorkommen kann. Wie gesagt, die so definierte Folge gibts auch
hier beit OEIS:
https://oeis.org/A096077

Valentin
Hans-Peter Diettrich
2018-03-09 15:41:57 UTC
Permalink
Raw Message
Post by Valentin Schmidt
Post by Hans-Peter Diettrich
Post by Marcel Mueller
Hallo!
Post by Valentin Schmidt
a) Wenn mit "anderen Elementen der Reihe" gemeint ist, dass diese NICHT
unterschiedlich sein müssen - also auch das selbe vorherige Element
mehrfach in Summe/Differenz einbezogen werden kann - ist ein Ergebnis
1, 4, 10, 17, 29, 52, 67, 89, 132, 164, 205, 259, 303, 350, 405, 505,
529, 588, 680, 903, ...
Tatsächlich war meine Spezifikation in diesem Punkt unvollständig. Die
Zahlen dürfen mehrfach vorkommen.
Wie soll das zu Deinem physikalischen Problem passen?
Diese Frage hast Du immer noch nicht beantwortet. Da jede Frequenz im
Spektrum nur einmal vorkommt, kann sie nicht mehrfach im Mischprodukt
auftreten.
Post by Valentin Schmidt
Post by Hans-Peter Diettrich
Zudem ergibt sich dann eine Unstimmigkeit: Wenn x und y Elemente der
Reihe sind, dann ergibt x+y-y wieder x, das in der Reihe bereits
enthalten ist.
Nee, das ergibt keine Unstimmigkeit, da es ja nicht um eine
Mengendefinition, sondern eine "quasi-rekursive" Definition einer Folge
geht. x+y-y = x bedeutet nur, dass in dieser Folge kein Element jemals
doppelt vorkommen kann.
Wegen "nicht als Summe ... von ... *anderen* Elementen" ist sowieso
alles in Ordnung.

DoDi
Marcel Mueller
2018-03-04 09:25:31 UTC
Permalink
Raw Message
Post by Valentin Schmidt
ich bin mir bewusst, dass es dir um eigentlich um eine mathematische
Definition so einer Reihe geht.
Das wäre zumindest eine Lösung, die nicht bei jedem Start einer Messung
erst einmal 15 Minuten rechnen muss. ;-)
Post by Valentin Schmidt
Aber falls es doch irgendwie
weiterhelfen könnte, hier der numerische (=mit Computer generierte)
Output einer Reihe von Zahlen zw. 1 und 1000, für die diese Bedingung
1,2,3 funktioniert schon nicht, aber das war ja schon erkannt. 1,2,4,9
scheint auf den ersten Blick zu gehen.

Wie auch immer. Das war jetzt trial and error mit Computer.
Vielleicht ist das tatsächlich der Weg. Ein Computer wäre schon immer dabei.
Allerdings brauche ich schon größere Zahlen. Bis zu 1 Mio. würde ich
sagen - also nicht die Anzahl, sondern das Maximum.
Wenn ich es richtig abschätze ist die Komplexität O(N³). Also jede neue
Zahl gegen alle Kombinationen aus je zwei anderen Zahlen verproben. Das
dürfte bei bis zu 1 Mio. auch moderne Computer hoffnungslos plätten.
Selbst, wenn man das mit einer Lookup-Tabelle auf O(N²) eindampfen
könnte - Komplexität im Speicher und in CPU Zeit ist ja oft irgendwie
austauschbar -, wäre das immer noch grenzwertig.

Theoretisch könnten es (in Grenzen) auch rationale Zahlen sein, solange
das kgV der Nenner nicht zu groß wird. Das ist aber letztlich äquivalent
mit einer Zahlenfolge bei der die 1 und vielleicht auch noch ein paar
weitere, kleine Zahlen fehlen. Technisch gesehen brauche ich keine
Zahlen kleiner als ca. 0,1% des jeweiligen Maximums. Ich weiß aber
nicht, wie sich das signifikant positiv auswirken würde.


Marcel
Hans-Peter Diettrich
2018-03-05 14:11:33 UTC
Permalink
Raw Message
Post by Marcel Mueller
Allerdings brauche ich schon größere Zahlen. Bis zu 1 Mio. würde ich
sagen - also nicht die Anzahl, sondern das Maximum.
Wenn ich es richtig abschätze ist die Komplexität O(N³). Also jede neue
Zahl gegen alle Kombinationen aus je zwei anderen Zahlen verproben. Das
dürfte bei bis zu 1 Mio. auch moderne Computer hoffnungslos plätten.
Wie kommst Du zu dieser Einschätzung? Von der Rechenleistung her würde
ein kleiner Arduino ausreichen, nur mit dem Speicher wird es dort etwas
knapp. Aber was ist heute schon 1MB Speicher für eine Hilfstabelle?

Leider bin ich heute erst zum Programmieren gekommen, kann also keinen
Blumentopf mehr gewinnen. Mein Notebook liefert die ersten 315 Elemente
der Reihe (bis 1001840) im Bruchteil einer Sekunde. Für die Startwerte
1,4,10 sind es 317 Elemente bis 1015058, für 2,3,10 sogar nur 312 bis
1003239, was etwas erstaunlich ist. Obwohl die Liste am Anfang dichter
aussieht, werden es längerfristig nicht signifikant mehr Elemente.

Oder enthält mein Algorithmus noch einen Fehler?

BTW meine erste Einschätzung lag bei 1000 Elementen bis 1 Mio., also
durchaus nicht zu niedrig. Also keine Angst vor großen Exponenten ;-)
Post by Marcel Mueller
Selbst, wenn man das mit einer Lookup-Tabelle auf O(N²) eindampfen
könnte - Komplexität im Speicher und in CPU Zeit ist ja oft irgendwie
austauschbar -, wäre das immer noch grenzwertig.
Nun ja, brute force könnte tatsächlich etwas länger dauern, aber das ist
ja sowas von uncool ;-)

Etwas anspruchsvoller wäre dann die Suche nach der längsten Reihe (bis 1
Mio.).

DoDi
Marcel Mueller
2018-03-06 22:12:16 UTC
Permalink
Raw Message
Post by Hans-Peter Diettrich
Post by Marcel Mueller
Allerdings brauche ich schon größere Zahlen. Bis zu 1 Mio. würde ich
sagen - also nicht die Anzahl, sondern das Maximum.
Wenn ich es richtig abschätze ist die Komplexität O(N³). Also jede
neue Zahl gegen alle Kombinationen aus je zwei anderen Zahlen
verproben. Das dürfte bei bis zu 1 Mio. auch moderne Computer
hoffnungslos plätten.
Wie kommst Du zu dieser Einschätzung? Von der Rechenleistung her würde
ein kleiner Arduino ausreichen,
Für eine Trilliarde Iterationen? - Also, in diesem Universum wird das
nichts.
Post by Hans-Peter Diettrich
nur mit dem Speicher wird es dort etwas
knapp. Aber was ist heute schon 1MB Speicher für eine Hilfstabelle?
Wenn man Bitvektoren nutzt, sollten 125kB pro Lookup-Tabelle reichen.
Post by Hans-Peter Diettrich
Leider bin ich heute erst zum Programmieren gekommen, kann also keinen
Blumentopf mehr gewinnen. Mein Notebook liefert die ersten 315 Elemente
der Reihe (bis 1001840) im Bruchteil einer Sekunde.
Wie war denn der Algorithmus?
Post by Hans-Peter Diettrich
1,4,10 sind es 317 Elemente bis 1015058, für 2,3,10 sogar nur 312 bis
1003239, was etwas erstaunlich ist. Obwohl die Liste am Anfang dichter
aussieht, werden es längerfristig nicht signifikant mehr Elemente.
Oder enthält mein Algorithmus noch einen Fehler?
Wer weiß das schon.
Post by Hans-Peter Diettrich
Post by Marcel Mueller
Selbst, wenn man das mit einer Lookup-Tabelle auf O(N²) eindampfen
könnte - Komplexität im Speicher und in CPU Zeit ist ja oft irgendwie
austauschbar -, wäre das immer noch grenzwertig.
Nun ja, brute force könnte tatsächlich etwas länger dauern, aber das ist
ja sowas von uncool ;-)
Ich für meinen Teil habe bisher keine bessere Lösung.
Und bei n Zahlen gibt es n²+n Kombinationen, gegen die wiederum alle
Zahlen geprüft werden müssen.
Die Sache lässt sich signifikant beschleunigen, wenn man sich die
Zahlenkombinationen nebst der daraus resultierenden Summen und
Differenzen merkt. Dann muss man nur noch gegen die verproben und landet
bei O(n²).
Wenn man da noch ein bisschen herumoptimiert, sollte es tatsächlich eine
Sache von Sekunden sein, zumindest, wenn man nicht gerade eine Raspberry
Pi zum messen nimmt - der sich im Übrigen dank flotter GPU tatsächlich
eignet.
Post by Hans-Peter Diettrich
Etwas anspruchsvoller wäre dann die Suche nach der längsten Reihe (bis 1
Mio.).
In der tat.


Marcel
Hans-Peter Diettrich
2018-03-07 10:54:15 UTC
Permalink
Raw Message
Post by Marcel Mueller
Post by Hans-Peter Diettrich
Post by Marcel Mueller
Allerdings brauche ich schon größere Zahlen. Bis zu 1 Mio. würde ich
sagen - also nicht die Anzahl, sondern das Maximum.
Wenn ich es richtig abschätze ist die Komplexität O(N³). Also jede
neue Zahl gegen alle Kombinationen aus je zwei anderen Zahlen
verproben. Das dürfte bei bis zu 1 Mio. auch moderne Computer
hoffnungslos plätten.
Wie kommst Du zu dieser Einschätzung? Von der Rechenleistung her würde
ein kleiner Arduino ausreichen,
Für eine Trilliarde Iterationen? - Also, in diesem Universum wird das
nichts.
Mit brute force wird das natürlich nichts. Wenn sich aber die Reihe bis
1 Mio. auf gut 300 Werte beschränkt, dann sind das nur noch etwa 27 Mio.
Operationen. Das wußte ich zwar vorher nicht, aber mit mehr als 1000
Elementen habe ich sowieso nicht gerechnet.
Post by Marcel Mueller
Post by Hans-Peter Diettrich
knapp. Aber was ist heute schon 1MB Speicher für eine Hilfstabelle?
Wenn man Bitvektoren nutzt, sollten 125kB pro Lookup-Tabelle reichen.
Wenn man die längere Laufzeit in Kauf nimmt. Angesichts der kleinen
Tabelle habe ich mir das erst mal gespart.
Post by Marcel Mueller
Post by Hans-Peter Diettrich
Leider bin ich heute erst zum Programmieren gekommen, kann also keinen
Blumentopf mehr gewinnen. Mein Notebook liefert die ersten 315 Elemente
der Reihe (bis 1001840) im Bruchteil einer Sekunde.
Wie war denn der Algorithmus?
Ich lasse alle erreichbaren Zahlen markieren, und suche dann nach der
nächsten Lücke in diesem Hilfsfeld.

Das Feld mußte ich zuletzt auf 3 Mio. dimensionieren, weil das etwa die
höchste erreichbare Zahl aus 3 Elementen ist. Dann habe ich die Grenzen
verdoppelt, um ganz sicher alle Elemente bis 1 Mio. zu bekommen. Alle
Versuche, die Rechnung vorzeitig systematisch zu beenden, hatten
irgendwelche Fehler (Lücken oder zu viele Elemente) zur Folge. Auf eine
Einzelprüfung aller Summen wollte ich verzichten, weil das nur die
Laufzeit erhöht.

Alles in allem hat es 2 Stunden gedauert, bis das Programm lief - ich
bin halt etwas aus der Übung ;-)
Post by Marcel Mueller
Post by Hans-Peter Diettrich
1,4,10 sind es 317 Elemente bis 1015058, für 2,3,10 sogar nur 312 bis
1003239, was etwas erstaunlich ist. Obwohl die Liste am Anfang dichter
aussieht, werden es längerfristig nicht signifikant mehr Elemente.
Oder enthält mein Algorithmus noch einen Fehler?
Wer weiß das schon.
Nachprüfen?

DoDi
Christian Gollwitzer
2018-03-04 08:37:49 UTC
Permalink
Raw Message
Post by Marcel Mueller
Hallo,
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer Zahlen,
deren Elemente sich /nicht/ als Summen oder Differenzen von maximal
/drei/ anderen Elementen der Reihe darstellen lassen.
Für Summen und Differenzen aus maximal /zwei/ anderen Elementen ist das
trivial: alle ungeraden Zahlen.
Aber was macht man bei /drei/ Summanden?
Mit Modulo-N wie bei 2 Zahlen komme ich da nicht weiter. Spätestens die
Terme der Art A+B-C haben liefern bei egal welchem N immer denselben
Modulo-N wie die Komponenten des Terms.
Ich weiß jetzt nicht genau, ob das hilft, aber die Fragestellung
erinnert mich an Golomb-Lineale:

https://de.wikipedia.org/wiki/Golomb-Lineal

Christian
Rainer Rosenthal
2018-03-04 10:11:48 UTC
Permalink
Raw Message
Post by Christian Gollwitzer
Post by Marcel Mueller
Hallo,
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer
Zahlen, deren Elemente sich /nicht/ als Summen oder Differenzen von
maximal /drei/ anderen Elementen der Reihe darstellen lassen.
Ich weiß jetzt nicht genau, ob das hilft, aber die Fragestellung
https://de.wikipedia.org/wiki/Golomb-Lineal
War auch mein erster Gedanke, wobei auch die Wichmann-Lineale
(Luschny/OEIS) interessant sind und der dort benutzte Ausdruck "Perfect
Difference Sets".
Gemeinsam ist allen, dass es nix formelmäßig fix-und-fertiges gibt.
(Abgesehen davon, wenn Peter Luschnys Vermutung stimmt, dass "große"
Wichmann-Lineale optimal sind, wenn sie nach der Wichmann-Formel
zusammengebaut werden.)

Auf jeden Fall führt auch die Suche nach Golomb-Lineal über OEIS.org
zu vielleicht hilfreichen Referenzen.

Schönen Sonntag,
Rainer
Ralf Goertz
2018-03-06 08:24:12 UTC
Permalink
Raw Message
Am Sun, 4 Mar 2018 11:11:48 +0100
Post by Rainer Rosenthal
Post by Christian Gollwitzer
Post by Marcel Mueller
Hallo,
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer
Zahlen, deren Elemente sich /nicht/ als Summen oder Differenzen
von maximal /drei/ anderen Elementen der Reihe darstellen lassen.
Ich weiß jetzt nicht genau, ob das hilft, aber die Fragestellung
https://de.wikipedia.org/wiki/Golomb-Lineal
War auch mein erster Gedanke, wobei auch die Wichmann-Lineale
(Luschny/OEIS) interessant sind und der dort benutzte Ausdruck
"Perfect Difference Sets".
Gemeinsam ist allen, dass es nix formelmäßig fix-und-fertiges gibt.
(Abgesehen davon, wenn Peter Luschnys Vermutung stimmt, dass "große"
Wichmann-Lineale optimal sind, wenn sie nach der Wichmann-Formel
zusammengebaut werden.)
Ich kann leider nur die erste Seite des Artikels lesen und weiß daher
nicht, ob [vermute aber stark, dass] die perfect difference sets die
sind, die man mithilfe projektiver Ebenen über endlichen Körpern erhält.
Wenn das so ist, dann gibt es zwar nichts einfaches formelmäßiges, aber
immerhin einen konstruktiven Beweis von Singer¹, der sich in PARI/GP zum
Beispiel so schreiben lässt:

diffset=m-> {
if (type(m)!="t_INT" || m<2 ,error(concat(m," is not an integer≥2")));
if (omega(m)>1,error(concat(m," is not a prime power")));
my(fc=factorint(m));
my(p=fc[1,1]);
my(n=fc[1,2]);
my(lambda=ffprimroot(ffgen(ffinit(p,3*n)))); \\ Generator for field F_{p^{3n}}
my(v=p^(2*n)+p^n+1);
my(lambda_sf=lambda^v); \\ Generator for subfield F_{p^n}
my(s=Set([]));
my(elem=lambda);
for(i=0,fforder(lambda_sf),
for(j=0,fforder(lambda_sf),
if (i+j==0,next);
elem=if(i==0,0,(lambda_sf^i)*lambda)+if(j==0,0,lambda_sf^j);
\\elem=(lambda_sf^i)*lambda+lambda_sf^j;
s=setunion(s,Set([fflog(elem,lambda)]%v));
if(length(s)==m+1,break);
)
);
return(s);
}

Damit lässt sich sehr schnell zur Ordnung m=p^n (p prim) eine
Differenzmenge D mit m+1 Elementen erzeugen, also eine Menge, so dass
jeder nichtverschwindende Rest modulo m^2+m+1 auf genau eine Art als
Differenz zweier Elemente von D darstellen lässt:

? diffset(4)
%4 = [0, 1, 6, 8, 18]

hier ist der Modul 21, also jede der 20 möglichen Differenzen ungleich 0
kommt genau einmal vor.

¹SINGER, JAMES: A theorem in finite projective geometry and some
applications to number theory. Transactions of the American Mathematical
Society, 43(3):377–385, 1938.
H. Schreiber
2018-03-04 11:39:10 UTC
Permalink
Raw Message
Post by Marcel Mueller
Hallo,
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer Zahlen,
deren Elemente sich /nicht/ als Summen oder Differenzen von maximal
/drei/ anderen Elementen der Reihe darstellen lassen.
Für Summen und Differenzen aus maximal /zwei/ anderen Elementen ist das
trivial: alle ungeraden Zahlen.
Aber was macht man bei /drei/ Summanden?
Mit Modulo-N wie bei 2 Zahlen komme ich da nicht weiter. Spätestens die
Terme der Art A+B-C haben liefern bei egal welchem N immer denselben
Modulo-N wie die Komponenten des Terms.
Hintergund: die Frage kommt eigentlich aus der Messtechnik. Ich versuche
eine nichtlineares Übertragungsfunktion mit einem Frequenzspektrum zu
auf einen Schlag Charakterisieren. Nichtlinearitäten erzeugen
Intermodulation, die sich in Summen oder Differenzen enthaltener
Frequenzen manifestiert. Dabei können an sich beliebig viele Terme
auftreten, aber in der Praxis sind die höheren Ordnungen bei moderaten
Nichtlinearitäten vernachlässigbar klein.
Irgendwelche Ideen?
Ich weiß ehrlich gesagt überhaupt nicht, wie man da ansetzen sollte.
Marcel
Maximal drei oder maximal drei paarweise unterschiedliche?

Harald
Rainer Rosenthal
2018-03-04 12:41:07 UTC
Permalink
Raw Message
Post by Marcel Mueller
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer Zahlen,
deren Elemente sich /nicht/ als Summen oder Differenzen von maximal
/drei/ anderen Elementen der Reihe darstellen lassen.
Um beim Prioritätenstreit die Nase vorn haben zu können, gebe ich
folgenden OEIS-Kandidaten zu Protokoll:
1, 2, 4, 8, 15, 26, 44, 64, 84, 115, 162, 209, 259, 296, 333, 428, 482,
537, 604, 710

Ähnlich wie Valentin Schmidt habe ich mich bemüht, einen bug-freien
Code zu basteln, um nach dem greedy-Prinzip eine Zahlenreihe zu
bilden, die Deiner Bedingung genügt.

Da mein Vorschlag von seinem etwas abweicht, werde ich mir jetzt
anschauen, woher die Abweichung kommt, und was nun richtig ist.

Gruß,
Rainer Rosenthal
***@web.de
Rainer Rosenthal
2018-03-04 12:58:41 UTC
Permalink
Raw Message
Post by Rainer Rosenthal
Post by Marcel Mueller
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer
Zahlen, deren Elemente sich /nicht/ als Summen oder Differenzen von
maximal /drei/ anderen Elementen der Reihe darstellen lassen.
Um beim Prioritätenstreit die Nase vorn haben zu können, gebe ich
1, 2, 4, 8, 15, 26, 44, 64, 84, 115, 162, 209, 259, 296, 333, 428, 482,
537, 604, 710
Priorität war zwar nix, aber hier habe ich die ersten 72 Zahlen:

1, 2, 4, 8, 15, 26, 44, 64, 84, 115, 162, 209, 259, 296, 333, 428, 482,
537, 604, 710, 843, 946, 1073, 1208, 1229, 1304, 1520, 1704, 1806, 2096,
2189, 2426, 2660, 2817, 3190, 3544, 3747, 3940, 4403, 4556, 4806, 4907,
5191, 5439, 5801, 6241, 6437, 6816, 7166, 7752, 7809, 8246, 8392, 8547,
9221, 9666, 10512, 10850, 11615, 11941, 12747, 13093, 13664, 14287,
14965, 15384, 15737, 16996, 17310, 17889, 18672

Gruß,
Rainer Rosenthal
***@web.de
Rainer Rosenthal
2018-03-04 13:18:10 UTC
Permalink
Raw Message
Post by Rainer Rosenthal
Post by Marcel Mueller
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer
Zahlen, deren Elemente sich /nicht/ als Summen oder Differenzen von
maximal /drei/ anderen Elementen der Reihe darstellen lassen.
1, 2, 4, 8, 15, 26, 44, 64, 84, 115, 162, 209, 259, 296, 333, 428, 482,
537, 604, 710, 843, 946, 1073, 1208, 1229, 1304, 1520, 1704, 1806, 2096,
2189, 2426, 2660, 2817, 3190, 3544, 3747, 3940, 4403, 4556, 4806, 4907,
5191, 5439, 5801, 6241, 6437, 6816, 7166, 7752, 7809, 8246, 8392, 8547,
9221, 9666, 10512, 10850, 11615, 11941, 12747, 13093, 13664, 14287,
14965, 15384, 15737, 16996, 17310, 17889, 18672
Das waren gerade genug, um den Plot der Differenzen mit Vergnügen
anschauen zu können und den Sprung von 15737 auf 16996 zu bemerken.

Hier die Liste der Differenzen der obigen 72 Zahlen:
1, 2, 4, 7, 11, 18, 20, 20, 31, 47, 47, 50, 37, 37, 95, 54, 55, 67, 106,
133, 103, 127, 135, 21, 75, 216, 184, 102, 290, 93, 237, 234, 157, 373,
354, 203, 193, 463, 153, 250, 101, 284, 248, 362, 440, 196, 379, 350,
586, 57, 437, 146, 155, 674, 445, 846, 338, 765, 326, 806, 346, 571,
623, 678, 419, 353, 1259, 314, 579, 783

Man sieht, wie die Differenz 1259 heraussticht.
Bis zum nächsten Herausstechen werde ich mit meinem lahmen Ansatz nicht
rechnen können.

Jetzt wäre die Frage, ob der greedy-Ansatz überhaupt hilfreich ist für
die ursprüngliche Fragestellung.

Gruß,
Rainer
Detlef Müller
2018-08-17 14:06:56 UTC
Permalink
Raw Message
Hallo, allerseits,

man könnte sich fragen, wie gut die "greedy"-Folge an einer wirklich
längsten Folge von Zahlen <= n liegt, die der gestellten Bedingung
genügt.

Solche Folgen habe ich mit "sage" über ein Backtracking ermittelt,
wie zu erwarten war, ging der Rechner schon ab n=20 in die Knie :)

Da bin ich auf C umgestiegen (ja, ich habe gerade Zeit :) ), was
um einen Faktor >100 schneller ist.
Daß ich die Sache erst in sage (d.h. im wesentlichen Python um
bequeme Mengen-Operationen erweitert)implementiert habe, war dabei
Gold wert - vermutlich wäre ich ohne die Möglichkeit, die Ausgaben
zu vergleichen, beim Testen verzweifelt.
Post by Rainer Rosenthal
Post by Rainer Rosenthal
Post by Marcel Mueller
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer
Zahlen, deren Elemente sich /nicht/ als Summen oder Differenzen von
maximal /drei/ anderen Elementen der Reihe darstellen lassen.
1, 2, 4, 8, 15, 26, 44, 64, 84, 115, 162, 209, 259, 296, 333, 428, 482,
537, 604, 710, 843, 946, 1073, 1208, 1229, 1304, 1520, 1704, 1806, 2096,
2189, 2426, 2660, 2817, 3190, 3544, 3747, 3940, 4403, 4556, 4806, 4907,
5191, 5439, 5801, 6241, 6437, 6816, 7166, 7752, 7809, 8246, 8392, 8547,
9221, 9666, 10512, 10850, 11615, 11941, 12747, 13093, 13664, 14287,
14965, 15384, 15737, 16996, 17310, 17889, 18672
Das waren gerade genug, um den Plot der Differenzen mit Vergnügen
anschauen zu können und den Sprung von 15737 auf 16996 zu bemerken.
[...]
Post by Rainer Rosenthal
Jetzt wäre die Frage, ob der greedy-Ansatz überhaupt hilfreich ist für
die ursprüngliche Fragestellung.
Hier (nachdem mein Programm einen Tag lang gelaufen ist) die (modulo
Denk- und Programmierfehler) für gewisse Obergrenzen n (hier "lae"
genannt) längsten Folgen - aufgrund des Algorithmus wird die
lexikografisch kleinste Folge ausgegeben.
Hier schlägt das Kombinatorische Wachstum so ab n=70 zu, spätestens
ab da will man nicht mehr live zuschauen :)
Im berechneten Bereich scheint sich die "greedy"-Folge ganz gut zu
machen. Ab 44 geht es anscheinend um 1 länger, für 115 dauerte die
Rechnung 2.5 Stunden ...

Im Folgenden die Resultate, jeweils mit Obergrenze für n, der
maximalen Länge für eine "sperrige" Liste mit Zahlen <= n
und einer Beispiel-Liste.

lae: 1, max: 2, |0,1|
lae: 2, max: 2, |0,1|
lae: 3, max: 3, |0,2,3|
lae: 4, max: 3, |0,1,4|
lae: 5, max: 3, |0,1,4|
lae: 6, max: 3, |0,1,4|
lae: 7, max: 4, |0,4,5,7|
lae: 8, max: 4, |0,1,5,8|
lae: 9, max: 4, |0,1,5,8|
lae: 10, max: 4, |0,1,4,10|
lae: 11, max: 4, |0,1,4,10|
lae: 12, max: 5, |0,5,9,11,12|
lae: 13, max: 5, |0,4,10,11,13|
lae: 14, max: 5, |0,2,5,13,14|
lae: 15, max: 5, |0,2,5,13,14|
lae: 16, max: 5, |0,1,5,13,16|
lae: 17, max: 5, |0,1,4,10,17|
lae: 18, max: 5, |0,1,4,10,17|
lae: 19, max: 6, |0,7,11,16,17,19|
lae: 20, max: 6, |0,5,13,14,16,20|
lae: 21, max: 6, |0,2,12,13,18,21|
lae: 22, max: 6, |0,1,10,14,17,22|
lae: 23, max: 6, |0,1,8,13,19,23|
lae: 24, max: 6, |0,1,8,13,19,23|
lae: 25, max: 6, |0,1,5,14,17,25|
lae: 26, max: 6, |0,1,5,14,17,25|
lae: 27, max: 6, |0,1,5,14,17,25|
lae: 28, max: 6, |0,1,4,15,21,28|
lae: 29, max: 7, |0,4,10,17,26,28,29|
lae: 30, max: 7, |0,3,16,18,25,26,30|
lae: 31, max: 7, |0,3,16,18,25,26,30|
lae: 32, max: 7, |0,1,11,18,24,27,32|
lae: 33, max: 7, |0,1,9,14,26,30,33|
lae: 34, max: 7, |0,1,7,18,22,31,34|
lae: 35, max: 7, |0,1,7,18,22,31,34|
lae: 36, max: 7, |0,1,7,18,22,31,34|
lae: 37, max: 7, |0,1,5,14,26,34,37|
lae: 38, max: 7, |0,1,4,15,25,32,38|
lae: 39, max: 7, |0,1,4,15,25,32,38|
lae: 40, max: 8, |0,7,8,18,31,35,37,40|
lae: 41, max: 8, |0,1,10,16,29,34,37,41|
lae: 42, max: 8, |0,1,10,16,29,34,37,41|
lae: 43, max: 8, |0,1,10,16,29,34,37,41|
lae: 44, max: 8, |0,1,10,16,29,34,37,41|
lae: 45, max: 8, |0,1,10,16,29,34,37,41|
lae: 46, max: 8, |0,1,7,24,27,37,42,46|
lae: 47, max: 8, |0,1,7,24,27,37,42,46|
lae: 48, max: 8, |0,1,7,24,27,37,42,46|
lae: 49, max: 8, |0,1,6,22,31,35,46,49|
lae: 50, max: 8, |0,1,4,16,26,37,44,50|
lae: 51, max: 8, |0,1,4,16,26,37,44,50|
lae: 52, max: 8, |0,1,4,16,26,37,44,50|
lae: 53, max: 9, |0,8,18,25,38,47,49,52,53|
lae: 54, max: 9, |0,5,12,16,31,45,51,53,54|
lae: 55, max: 9, |0,2,14,29,36,46,49,54,55|
lae: 56, max: 9, |0,1,22,29,38,42,48,53,56|
lae: 57, max: 9, |0,1,22,29,38,42,48,53,56|
lae: 58, max: 9, |0,1,22,29,38,42,48,53,56|
lae: 59, max: 9, |0,1,15,27,34,38,51,56,59|
lae: 60, max: 9, |0,1,15,27,34,38,51,56,59|
lae: 61, max: 9, |0,1,10,26,40,43,48,55,61|
lae: 62, max: 9, |0,1,7,24,35,40,50,53,62|
lae: 63, max: 9, |0,1,6,26,35,45,48,59,63|
lae: 64, max: 9, |0,1,4,19,31,40,47,53,64|
lae: 65, max: 9, |0,1,4,17,28,40,50,59,65|
lae: 66, max: 9, |0,1,4,15,32,41,53,59,66|
lae: 67, max: 10, |0,9,15,23,34,50,60,62,63,67|
lae: 68, max: 10, |0,9,15,23,34,50,60,62,63,67|
lae: 69, max: 10, |0,4,24,37,43,54,59,66,68,69|
lae: 70, max: 10, |0,4,24,37,43,54,59,66,68,69|
lae: 71, max: 10, |0,1,21,27,38,52,56,61,68,71|
lae: 72, max: 10, |0,1,19,33,41,45,56,62,69,72|
lae: 73, max: 10, |0,1,19,33,41,45,56,62,69,72|
lae: 74, max: 10, |0,1,19,33,41,45,56,62,69,72|
lae: 75, max: 10, |0,1,19,33,41,45,56,62,69,72|
lae: 76, max: 10, |0,1,19,33,41,45,56,62,69,72|
lae: 77, max: 10, |0,1,8,28,40,53,59,63,74,77|
lae: 78, max: 10, |0,1,8,28,40,53,59,63,74,77|
lae: 79, max: 10, |0,1,7,31,42,54,57,70,75,79|
lae: 80, max: 10, |0,1,7,31,42,54,57,70,75,79|
lae: 81, max: 10, |0,1,4,15,37,46,58,64,71,81|
lae: 82, max: 10, |0,1,4,15,37,46,58,64,71,81|
lae: 83, max: 10, |0,1,4,15,37,46,58,64,71,81|
lae: 84, max: 11, |0,8,14,29,48,53,71,73,80,83,84|
lae: 85, max: 11, |0,7,20,29,32,62,66,67,77,83,85|
lae: 86, max: 11, |0,7,20,29,32,62,66,67,77,83,85|
lae: 87, max: 11, |0,4,13,28,42,48,64,75,82,85,87|
lae: 88, max: 11, |0,2,24,27,39,60,69,70,77,83,88|
lae: 89, max: 11, |0,1,11,29,34,48,65,73,80,86,89|
lae: 90, max: 11, |0,1,11,29,34,48,65,73,80,86,89|
lae: 91, max: 11, |0,1,11,29,34,48,65,73,80,86,89|
lae: 92, max: 11, |0,1,11,29,34,48,65,73,80,86,89|
lae: 93, max: 11, |0,1,9,23,48,53,59,74,86,90,93|
lae: 94, max: 11, |0,1,9,23,48,53,59,74,86,90,93|
lae: 95, max: 11, |0,1,9,23,48,53,59,74,86,90,93|
lae: 96, max: 11, |0,1,7,33,44,54,57,69,74,92,96|
lae: 97, max: 11, |0,1,7,33,44,54,57,69,74,92,96|
lae: 98, max: 11, |0,1,7,33,44,54,57,69,74,92,96|
lae: 99, max: 11, |0,1,6,22,47,56,67,82,86,96,99|
lae: 100, max: 11, |0,1,6,22,47,56,67,82,86,96,99|
lae: 101, max: 11, |0,1,6,22,47,56,67,82,86,96,99|
lae: 102, max: 11, |0,1,5,19,46,62,69,77,90,99,102|
lae: 103, max: 11, |0,1,5,19,46,62,69,77,90,99,102|
lae: 104, max: 11, |0,1,4,13,28,51,61,67,86,97,104|
lae: 105, max: 11, |0,1,4,13,28,51,61,67,86,97,104|
lae: 106, max: 11, |0,1,4,13,28,51,61,67,86,97,104|
lae: 107, max: 11, |0,1,4,13,28,51,61,67,86,97,104|
lae: 108, max: 12, |0,8,11,34,43,55,70,83,101,103,107,108|
lae: 109, max: 12, |0,7,32,52,65,74,82,93,103,105,108,109|
lae: 110, max: 12, |0,2,15,39,44,67,75,89,100,101,107,110|
lae: 111, max: 12, |0,2,15,39,44,67,75,89,100,101,107,110|
lae: 112, max: 12, |0,2,15,39,44,67,75,89,100,101,107,110|
lae: 113, max: 12, |0,2,15,39,44,67,75,89,100,101,107,110|
lae: 114, max: 12, |0,1,19,43,47,74,82,88,99,104,111,114|
lae: 115, max: 12, |0,1,19,43,47,74,82,88,99,104,111,114|
...

puh - leider etwas mageres Datenmaterial für Spekulationen,
vielleicht findet jemand noch einen pfiffigeren Algorithmus.

Z.B. wäre es interessant, inwiefern "sperrige" Listen zu n
existieren, die möglichst

Gruß,
Detlef

PS: Hier das Programm ... vermutlich nicht wirklich
durchschaubar.
In gcc kann man dankenswerterweise Arrays innerhalb einer
{...} Umgebung lokal mit einer Variablen als Dimension
deklarieren, das ist wohl kein Standard.

#include <stdio.h>
#include <stdlib.h>

// Gesucht wird eine möglichst lange Liste von ganzen, nicht
// negativen Zahlen aus {0, 1, ..., lae}, von denen sich keine
// als Summe oder Differenz von bis zu drei der übrigen Zahlen
// darstellen lässt.

// Globale Variablen (oh Grauß)

int lae=100;
// Konvention für Listen: Listenname groß, Länge klein geschrieben.
int *Lm; // bisher gefundene Liste maximaler Länge.
int lm; // deren Länge.
long found;

// Ausgabe einer Liste

void Lout(int *L, int l){
int i;
printf("|");
if(l>0) printf("%i",L[0]);
for(i=1; i<l; i++)
printf(",%i",L[i]);
printf("|\n");
fflush(stdout);
}

// comb1
// Liste der Summen und Differenzen von zwei Eingangslisten
// Eingabe: zwei sortierte Listen
// Ausgabe: sortierte Liste aller Elemente, sowie ihrer Summen
// und Differenzen im Bereich 0, ... , lae
// Hilfstabelle K1 global, um in dieser häufig aufgerufenen Routine
// nicht jedesmal neuen Speicher zu allozieren.

int *K1;
void comb1(int *L1, int l1, int *L2, int l2, int *R1, int *r1)
{
int i,j;
for(i=0; i<lae+1; i++) K1[i]=0;
for(i=0; i<l1; i++){
K1[L1[i]]=1;
for(j=0; j<l2 && L1[i]+L2[j]<=lae; j++){
K1[L1[i]+L2[j]]=1;
}
}
for(j=0; j<l2; j++){
K1[L2[j]]=1;
for(i=0; i<l1 && L1[i]<L2[j]; i++){
K1[L2[j]-L1[i]]=1;
}
for( ; i<l1; i++){
K1[L1[i]-L2[j]]=1;
}
}
j=0;
for(i=0;i<lae+1;i++){
if(K1[i]){
R1[j++]=i;
}
}
*r1=j;
}

// comb2
// Liste der Summen und Differenzen von je drei Elementen im
// betrachteten Bereich.
// Eingabe: sortierte Liste
// Ausgabe: sortierte Liste aller Elemente, sowie der Summen
// und Differenzen im Bereich 0, ... , lae

int *K2;
void comb2(int *L, int l, int *R, int *r)
{
// int *K=(int *)malloc((lae+1)*sizeof(int));
int Z[lae+1];
int z;
int i,j;
comb1(L, l,L,l,Z,&z);
for(i=0; i<lae+1; i++) K2[i]=0;
for(i=0; i<l; i++){
K2[L[i]]=1;
for(j=0; j<z && L[i]+Z[j]<=lae; j++){
K2[L[i]+Z[j]]=1;
}
}
for(i=0;i<z;i++){
for(j=0; j<l && Z[i]>L[j];j++){
K2[Z[i]-L[j]]=1;
}
for( ; j<l;j++){
K2[L[j]-Z[i]]=1;
}
}
j=0;
for(i=0;i<lae+1;i++){
if(K2[i]){
R[j++]=i;
}
}
*r = j;
}

// Test, ob die "Sperrigkeit" erfüllt ist. Wenn nicht, Gegenbeispiel
// ausgeben.
int checklist(int*L,int l)
{
int i,j,k,m;
for(i=0;i<l;i++)
for(j=0;j<l;j++)
for(k=0;k<l;k++)
for(m=0;m<l;m++)
if(m!=i && m!=j && m!=k){
if(L[i]+L[j]+L[k]==L[m]){
printf("%i+%i+%i=%i",L[i],L[j],L[k],L[m]); return(1);
}
if(L[i]+L[j]-L[k]==L[m]){
printf("%i+%i-%i=%i",L[i],L[j],L[k],L[m]); return(1);
}
if(L[i]-L[j]-L[k]==L[m]){
printf("%i-%i-%i=%i",L[i],L[j],L[k],L[m]); return(1);
}
}
return 0;
}

// Komplement der Listeneinträge zur Liste [0,...,lae] bestimmen.
void kompl(int*L,int l,int *Erg, int *erg){
int i, lauf, er;
lauf=0; er=0;
for(i=0; i<l; i++){
while(L[i]>lauf){Erg[er++]=lauf; lauf++;}
lauf++; // Vorhandenen Wert überspringen
}
// Ggf. Rest auffüllen:
while(lauf<lae+1) {Erg[er++]=lauf; lauf++;}
*erg=er;
}

// Backtrack: Sucht die längste Liste von Zahlen 0, ... , lae derart,
// daß sich keine der Zahlen als Summe oder Differenz von 1 bis 3
// der anderen Zahlen darstellen lässt.
void btr(int *L, int l)
{
int Ko[lae+1], ko; // Kombinationen
int Di[lae+1], di; // verbleibende Möglichkeiten
int i;
comb2(L,l,Ko,&ko);
if(ko==lae+1)
{ // nicht erweiterbare Liste erreicht!
found++;
if(l>lm){ // Neues Maximum gefunden!
lm=l;
for(i=0;i<l;i++) Lm[i]=L[i]; // Neue Bestliste merken.
}
}else{ // Weitere Möglichkeiten durchgehen.
kompl(Ko,ko,Di,&di); // Differenzmenge Di finden.
// Nun alle Möglichkeiten aus Di "backtracken"
// Dabei nur größere als den bisher größten Wert
// L[l] berücksichtigen!
for(i=0; Di[i]<L[l-1]; i++);
for(; i<di; i++){
L[l]=Di[i];
btr(L,l+1); // und eine Ebene tiefer gehen.
}
}
}

int main( int argc, char *argv[] ) {
// int L[lae+1], l;
lae=200;
K1=(int *)malloc((lae+1)*sizeof(int)); // für comb1
K2=(int *)malloc((lae+1)*sizeof(int)); // für comb2
Lm=(int*)malloc((lae+1)*sizeof(int));
for(lae=1; lae<116; ){
int L[lae+1], l;
l=1;
lm=0; // Maximum auf 0.
L[0]=0;

btr(L,l);
printf("lae: %2i, max: %i, ",lae, lm);
Lout(Lm,lm);
lae++;
}
free(K1); free(K2); free(Lm);
}
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Alfred Heiligenbrunner
2018-03-05 00:11:16 UTC
Permalink
Raw Message
Post by Marcel Mueller
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer Zahlen,
deren Elemente sich /nicht/ als Summen oder Differenzen von maximal
/drei/ anderen Elementen der Reihe darstellen lassen.
Marcel
Hallo Marcel,

um bei einer allgemeinen Folge a(n) auf der sicheren Seite zu sein, müsste man wohl fordern:
a(n) + a(n+1) + a(n+2) < a(n+3).
Dann ist sichergestellt, dass die Summe von drei unterschiedlichen(!) Folgenelementen kein anderes ergeben. Und auch die Differenzen sind in sicheren Abständen:
a(n+3)-a(n+2)-a(n+1) > a(n),
a(n+3)-a(n+2) > a(n+1)+a(n) > a(n+1)
a(n+3)-a(n+1)-a(n) > a(n+2).

Damit kann man rekursiv diese Folge definieren:
a(n+3) = a(n+2) + a(n+1) + a(n) + 1.

Die Folgenglieder wachsen leider um Vieles schneller als die von Rainer ermittelten. Sie sind aber leicht zu bestimmen:
{1, 2, 4, 8, 15, 28, 52, 96, 177, 326, 600, 1104, 2031, 3736, 6872, 12640, 23249, 42762, 78652, 144664, 266079, 489396, 900140, 1655616, 3045153, 5600910, 10301680, 18947744, 34850335, 64099760, ...}.

LG
Alfred
Rainer Rosenthal
2018-03-05 10:11:14 UTC
Permalink
Raw Message
Post by Alfred Heiligenbrunner
Post by Marcel Mueller
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer Zahlen,
deren Elemente sich /nicht/ als Summen oder Differenzen von maximal
/drei/ anderen Elementen der Reihe darstellen lassen.
a(n+3) = a(n+2) + a(n+1) + a(n) + 1.
{1, 2, 4, 8, 15, 28, 52, 96, 177, 326, 600, 1104, 2031, 3736, 6872, 12640, ...}.
Hallo Alfred,

ein sehr interessanter Ansatz, prima!
Ich habe in der Zwischenzeit etwas herumgespielt und gestaunt,
wie gut der greedy-Ansatz funktioniert. Hätte geglaubt, dass er
ebenfalls zu sehr schnell anwachsender Zahlenfolge führten würde,
aber die Zahlen bleiben erstaunlich lange dicht beieinander.

Aus Jux und Dollerei habe ich Deine Folge noch etwas auffüllen lassen:
# 74
# 114, 135
# 242
# 361, 470
# 625, 765, 799, 886
# 1194, 1311, 1419, 1580, 1739, 1886
# 2228, 2445, 2568, 2908, 3174, 3389
# 3813, 4046, 4444, 4596, 5023, 5102, 5673, 5951, 6229
# 7273, 7304, 7828, 8026, 8419, 8951, 9398, 9881, 10337, 10490, 10793,
11157, 11340

Hübsch, was da noch alles reinpasste.
Vielleicht sieht Dein Röntgenblick noch einen Trick, der für eine
automatische Nachverdichtung Deiner bestechend einfach zu rechnenden
Folge ergibt.

Salutoj,
Rainer
Alfred Heiligenbrunner
2018-03-05 13:34:25 UTC
Permalink
Raw Message
Post by Rainer Rosenthal
Post by Alfred Heiligenbrunner
Post by Marcel Mueller
ich bin auf der Suche nach einer Reihe möglichst dichter ganzer Zahlen,
deren Elemente sich /nicht/ als Summen oder Differenzen von maximal
/drei/ anderen Elementen der Reihe darstellen lassen.
a(n+3) = a(n+2) + a(n+1) + a(n) + 1.
{1, 2, 4, 8, 15, 28, 52, 96, 177, 326, 600, 1104, 2031, 3736, 6872, 12640, ...}.
Hallo Alfred,
# 74
# 114, 135
# 242
...
Post by Rainer Rosenthal
Salutoj,
Rainer
Hallo Rainer,

mir ist nur aufgefallen, dass deine und meine Folge anfangs gleich sind, sich dann um drei Zweierpotenzen unterscheiden (2^1, 2^3, 2^5), dann aber in keinem für mich erkennbaren Muster.
Alfred[i] - Rainer[i]:
{0, 0, 0, 0, 0, 2, 8, 32, 93, 211, 438, 895, 1772, 3440, ...}.
Leider gibt's diese Folge auch nicht im OEIS.

Kun koraj salutoj,
Alfred
Valentin Schmidt
2018-03-05 15:47:48 UTC
Permalink
Raw Message
Post by Alfred Heiligenbrunner
a(n+3) = a(n+2) + a(n+1) + a(n) + 1.
{1, 2, 4, 8, 15, 28, 52, 96, 177, 326, 600, 1104, 2031, 3736, 6872, 12640, 23249, 42762, 78652, 144664, 266079, 489396, 900140, 1655616, 3045153, 5600910, 10301680, 18947744, 34850335, 64099760, ...}.
Hallo Alfred,

deine Folge ist eine enge Verwandte der "Tribonacci-Folge", und damit
OEIS A000073:
https://oeis.org/A000073

Wenn noch 2 führende Nullen an den Anfang deiner a(n) gesetzt werden, also

0, 0, 1, 2, 4, 8, 15, 28, 52, 96, 177, 326, 600,

gilt bzgl. Tribonacci-Folge T(n):

T(n) = a(n) - a(n-3)

oder auch

T(n) = a(n-1) + a(n-2) + 1

Aus deiner Folge a(n) kann also jederzeit die Tribonacci-Folge berechnet
werden. Ich denke, dass das wohl auch umgekehrt gilt und sich a(n) aus
den Werten von T(n) berechnen lässt, hab das aber noch nicht durchgespielt.

Valentin
Valentin Schmidt
2018-03-05 16:00:27 UTC
Permalink
Raw Message
Post by Valentin Schmidt
Wenn noch 2 führende Nullen an den Anfang deiner a(n) gesetzt werden, also
0, 0, 1, 2, 4, 8, 15, 28, 52, 96, 177, 326, 600,
T(n) = a(n) - a(n-3)
oder auch
T(n) = a(n-1) + a(n-2) + 1
Aus deiner Folge a(n) kann also jederzeit die Tribonacci-Folge berechnet
werden. Ich denke, dass das wohl auch umgekehrt gilt und sich a(n) aus
den Werten von T(n) berechnen lässt, hab das aber noch nicht durchgespielt.
Yep, das geht, und zwar recht elegant:

a(n) = Summe von T(i) für alle i von 1 bis n-1

Deine a(n) ist also - abgesehen von Verschiebung um 1 - die
Reihenentwicklung der Tribonacci-Folge
Rainer Rosenthal
2018-03-05 19:52:20 UTC
Permalink
Raw Message
Post by Rainer Rosenthal
Hallo Alfred,
deine Folge ist eine enge Verwandte der "Tribonacci-Folge", und damit
https://oeis.org/A000073
Wow, und damit sind wir - schwuppdiwupp! - an der Front der Forschung,
wie im Literaturverzeichnis zu dieser Folge zu sehen ist:

Tim Evink, Paul Alexander Helminck, Tribonacci numbers and primes of the
form p=x^2+11y^2, arXiv:1801.04605 [math.NT], 2018.
Link: https://arxiv.org/abs/1801.04605

Gruß,
Rainer
Loading...