Quadrate – diesmal Zahlen, keine Figuren

[Matthias Apsel]

Hallo alle,

zunächst ein einfacher Einstieg:
Was ist das besondere an dieser Folge von Zahlen?

81 – 100 – 121 – 144 – 169 – 196 – 225

Dann wird es schwieriger:
Ermittle die nächste Folge der Länge 7 von Zahlen dieser Eigenschaft.
Gibt es auch Folgen der Länge 8 von Zahlen dieser Eigenschaft?

Bis demnächst
Matthias

[Tabellenkalk]

Hallo,

zunächst ein einfacher Einstieg:
Was ist das besondere an dieser Folge von Zahlen?

81 – 100 – 121 – 144 – 169 – 196 – 225

Es sind Quadratzahlen.

Dann wird es schwieriger:
Ermittle die nächste Folge der Länge 7 von Zahlen dieser Eigenschaft.

Schwierig. Ist das die, die mit 100 beginnt oder die, die mit 256 beginnt?

Gibt es auch Folgen der Länge 8 von Zahlen dieser Eigenschaft?

Klar, einfach 256 anhängen.

Gruß
Kalk

[Matthias]

zunächst ein einfacher Einstieg:
Was ist das besondere an dieser Folge von Zahlen?

81 – 100 – 121 – 144 – 169 – 196 – 225

Es sind Quadratzahlen.

Das ist nicht besonders genug.

[Der Martin]

Moin,

Was ist das besondere an dieser Folge von Zahlen?

81 – 100 – 121 – 144 – 169 – 196 – 225

es sind die Quadrate aufeinander folgender Zahlen, und die Differenz von einer zur nächsten wächst immer um 2. Aber das ist dir anscheinend noch nicht genug, denn das gilt für jede Zahlenfolge, denn

(n+1)² - n² = 2n+1

gilt für alle n≥0 - die Differenz zweier aufeinanderfolgenden n² wächst also immer um 2.

Ermittle die nächste Folge der Länge 7 von Zahlen dieser Eigenschaft.
Gibt es auch Folgen der Länge 8 von Zahlen dieser Eigenschaft?

Hmm. Welche Eigenschaft denn noch?

Live long and pros healthy,
 Martin

[Henry]

Hallo Matthias,

Hallo alle,

zunächst ein einfacher Einstieg:
Was ist das besondere an dieser Folge von Zahlen?

81 – 100 – 121 – 144 – 169 – 196 – 225

9x9, 10x10, usw...

Oder eben auch

+19,+21,+23,+25,+27,+29, usw...

Dann wird es schwieriger:
Ermittle die nächste Folge der Länge 7 von Zahlen dieser Eigenschaft.
Gibt es auch Folgen der Länge 8 von Zahlen dieser Eigenschaft?

Verstehe nicht genau was gesucht wird? Beide Eigenschaften lassen sich auf zig Zahlenreihen anwenden, daher was genau soll erzeugt werden?

Gruss
Henry

[MudGuard]

Hi,

Was ist das besondere an dieser Folge von Zahlen?

81 – 100 – 121 – 144 – 169 – 196 – 225

Die Besonderheit hab ich gefunden.

Aber ob's noch weitere Folgen gibt, könnte man damit programmatisch ermitteln, aber dazu hab ich grad keine Zeit.

cu,
Andreas a/k/a MudGuard

[Rolf B]

Hallo MudGuard,

Die Besonderheit hab ich gefunden.

ich auch. Aber nur mit Hilfe 😟. Ich war nahe dran, habe aber dann - wie es mir so oft passiert - nicht weit genug gedacht.

Dass die Kette aus Quadraten aufeinanderfolgener Zahlen besteht, ist ja offensichtlich. Die erste quadrierte Zahl nenne ich mal die Kettenbasis (in Matthias Muster wäre das also die 9).

Und wenn für eine bestimmte Kettenbasis k gilt, dass k+x (x<7) ebenfalls eine Kettenbasis ist, dann nenne ich das einen Kettenstrang mit Abstand x. Es gibt einen Strang aus 5 Ketten, die jeweils einen Abstand von 3 haben!

Jedenfalls gibt's noch genug andere 7er. Für die Frage, nach welchen Gesetzmäßigkeiten so eine 7er Kette findbar ist, habe ich keine Antwort. Die Abstände zwischen den Grundzahlen der 7er Ketten sind sehr unregelmäßig; spannend ist vor allem ein Strang aus fünf Ketten mit Abstand 3 ab der Grundzahl 33. Dafür gibt's dann zwischen den Kettenbasen 498 und 1002 einen Abstand von 504, und gleich darauf von 1002 bis 2823 einen Abstand 1821. Und bei 3108 beginnt ist wieder ein Strang aus 2 Ketten mit Abstand 3.

Was ich noch fand: alle Abstände der Kettenbasen sind durch 3 teilbar. Eine Voraussetzung für eine Grundzahl, dass sie der Anfang einer 7er Kette ist, scheint die Teilbarkeit durch 3 zu sein. Keine Ahnung, wieso das so ist.

Eine 8er-Kette scheint es nicht zu geben, ich habe aber bei einer Grundzahl von 3600 aufgehört zu suchen.

Rolf

[Gunnar Bittersmann]

@@Rolf B

Jedenfalls gibt's noch genug andere 7er.

Huch? Da hast du wohl eine andere Gesetzmäßigkeit gefunden als ich? (Oder mein Script ist fehlerhaft.)

Eine 8er-Kette scheint es nicht zu geben, ich habe aber bei einer Grundzahl von 3600 aufgehört zu suchen.

Bei meiner Gesetzmäßigkeit auch nicht; ich hab bei 10⁶ aufgehört zu suchen.

😷 LLAP

[MudGuard]

Hi,

Huch? Da hast du wohl eine andere Gesetzmäßigkeit gefunden als ich? (Oder mein Script ist fehlerhaft.)

Für die Gemeinsamkeit, die ich gefunden habe, muß man ein wenig quer denken.

cu,
Andreas a/k/a MudGuard

[Rolf B]

Hallo MudGuard,

ja, sehe ich auch so.

(Spoiler): Chain Explorer

Update: Ich habe aber anders quer gedacht als Matthias…

Rolf

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Jedenfalls gibt's noch genug andere 7er.

Huch? Da hast du wohl eine andere Gesetzmäßigkeit gefunden als ich?

Hattest du. Ich hatte die von Matthias angedachte.

Aber auch da gibt es genug andere 7er (was zu beweisen wäre).

ich hab bei 10⁶ aufgehört zu suchen.

Um genug andere zu finden, muss man schon etwas weiter suchen …

😷 LLAP

[Matthias Apsel]

Hallo Matthias Apsel,

Was ist das besondere an dieser Folge von Zahlen?

81 – 100 – 121 – 144 – 169 – 196 – 225

Es handelt sich um aufeinanderfolgende Quadratzahlen, deren Quersummen ebenfalls Quadratzahlen sind.

Bis demnächst
Matthias

[Rolf B]

Hallo Matthias,

interessant. Ich hatte die Folge gegoogelt, und fand da als Bedingung, dass die Summe der Quersummen eine Quadratzahl ist.

Solche Ketten gibt's eine ganze Menge, mit Basiszahlen 3 (9-16-25-36-49-64-81), die von dir gezeigte 9, dann 27, und dann der Kettenstrang ab 33, 36, 39, 42 und 45.

Deine Anforderung ist wesentlich strenger.

Aber es gibt mutmaßlich unendlich viele deiner Siebenerketten. Ich kann eine Bildungsregel für die erste Zahl dieser Ketten angeben, auch wenn ich die nur bis zum ersten Gogool getestet habe. Ob die 10 Stück, die ich auf diese Weise finde, alle sind, kann ich nicht sagen.

Was ich noch gefunden habe, ist eine Achterkette im mittleren Millionenbereich. Also - die Kettenbasis liegt da. Die Kette selbst beginnt mit dem Quadrat der Grundzahl. Da habe ich allerdings überhaupt keine Ahnung für eine Systematik. Die Systematik der 7er Ketten hat nicht funktioniert.

Eine Neunerkette habe ich nicht entdeckt. Wenn es sie gibt, liegt ihre Kettenbasis jenseits einer halben Milliarde.

Chain Explorer 2

Rolf

[Gunnar Bittersmann]

@@Rolf B

Aber es gibt mutmaßlich unendlich viele deiner Siebenerketten.

Zusatzaufgabe: Beweise diese Mutmaßung.

😷 LLAP

[Rolf B]

Hallo Gunnar,

ok, done.

Dass es keine anderen Siebenerketten als diese gibt, zeige ich damit allerdings nicht.

Rolf

[Gunnar Bittersmann]

@@Rolf B

Dass es keine anderen Siebenerketten als diese gibt, zeige ich damit allerdings nicht.

Natürlich nicht; das ist ja auch nicht notwendig.

Und auch nicht möglich; es gibt ja andere: mit dem Anfang und dem Ende der Achterkette hast du schon zwei solche.

😷 LLAP

[Rolf B]

Hallo Gunnar,

das ist ja auch nicht notwendig.

Aber natürlich ist das notwendig. Die Aufgabe besagt (fett von mir):

Ermittle die nächste Folge der Länge 7 von Zahlen dieser Eigenschaft.

Habe ich also ein t > 9, für das die Quadratzahlenkette ab t² die Bedingung erfüllt, dann ist das eine weitere Folge. Aber nicht die nächste. Dafür müsste ich zeigen, dass es kein u mit 9 < u < t gibt, das die Bedingung auch erfüllt. Für t < 1.000.000.000 kann man das noch in erträglicher Zeit mit dem Computer nachweisen (mein JavaScript-Scanner würde da ca 5 Stunden laufen). Aber da gibt's nur zwei Werte t. Das nächste ist schon so groß, dass das Script bis dahin 15.000 Jahre bräuchte. Mit Assembler und Multicore-Einsatz kann man das vermutlich auf 15 Jahre drücken, aber für das Nachrechnen bis zum vierten t müsste ich schon auf ein Raumschiff ausweichen, weil mir vorher die Sonne unter den Füßen wegbrennt. Und ggf. das Universum implodiert.

Rolf

[Gunnar Bittersmann]

@@Rolf B

Aber natürlich ist das notwendig. Die Aufgabe besagt (fett von mir):

Ermittle die nächste Folge der Länge 7 von Zahlen dieser Eigenschaft.

Nicht in diesem Subthread (der Zusatzaufgabe).

Hier besagt die Aufgabe: Zeige die Existenz unendlich vieler 7er-Ketten.

Wenn du von einer Sorte 7er-Ketten unendlich viele hast, ist es Wurst, ob es noch eine andere Sorte gibt.

😷 LLAP

[Rolf B]

Hallo Gunnar,

okay. Aber für die Aufgabe an sich müsste ich es schon beweisen. Und ich habe keine Ahnung, wie.

Genau genommen habe ich mich schon widerlegt. Es gibt eine Achterkette bei t≈46.000.000, die liegt zwischen dem 2. und 3. Wert für t. Fasst man eine Achterkette als zwei Siebenerketten auf, wäre schon widerlegt, dass meine Folge vollständig ist.

Und ein Update zum JavaScript-Scanner: Mit ein paar Optimierungen bin ich in 17s bei t=10.000.000. Das ist nicht linear, weil ich BigInt verwende, ich würde also nicht in 1700s bei der Milliarde sein.

Rolf

[Gunnar Bittersmann]

@@Rolf B

okay. Aber für die Aufgabe an sich müsste ich es schon beweisen. Und ich habe keine Ahnung, wie.

Beweisen, dass das Script das tut, was es soll, also dass es alle 7er-Ketten findet, die es gibt.

Wenn das gemacht ist, reicht „zwischen 9 und ████ hat das Script keine Kette gefunden“.

Und ein Update zum JavaScript-Scanner: Mit ein paar Optimierungen bin ich in 17s bei t=10.000.000. Das ist nicht linear, weil ich BigInt verwende, ich würde also nicht in 1700s bei der Milliarde sein.

Das muss ich mir glatt mal ansehen. Meiner (Spoiler!) läuft gefühlt viel langsamer. Und dabei bin ich noch nicht mal bei BigInt.

Liegt das an der CodePen-Umgebung? Oder dass ich Array.map() und Array.reduce() verwende?

😷 LLAP

[Rolf B]

Hallo Gunnar,

Beweisen, dass das Script das tut, was es soll, also dass es alle 7er-Ketten findet, die es gibt.

Nein, darum geht's nicht. Dass das Script tut, was es soll, könnte ich beweisen, wenn ich mich noch an Theoretische Informatik A erinnern würde. Tu ich aber nicht, also glaube ich meinen Tests. Das Script beweist aber nicht, dass meine Folge vollständig ist. Das kann es nicht, weil die Folge nicht endlich ist.

Meine Folge liefert eine hinreichende Bedingung für eine Siebenerkette. Dass diese Bedingung auch notwendig ist, müsste ich zeigen - aber sie ist es nicht. Ich lasse gerade mein Script laufen, bis t=1000.000.000, und soeben haut es mir für t=608.362.161 (und 1300s Laufzeit) eine Kettenbasis um die Ohren, die von meiner Folge nicht erfasst wird, bei dessen Quadrat 370.104.518.936.589.921 es aber eine 7er Kette gefunden hat. Ob das stimmt, oder ob mein Script einen Bug hat, muss ich noch nachrechnen.

Update:

     t                    t²             q(t²)    
608.362.161    370.104.518.936.589.921    81
608.362.162    370.104.520.153.314.244    49
608.362.163    370.104.521.370.038.569    64
608.362.164    370.104.522.586.762.896    81
608.362.165    370.104.523.803.487.225    64
608.362.166    370.104.525.020.211.556    49
608.362.167    370.104.526.236.935.889    81

Liegt das an der CodePen-Umgebung? Oder dass ich Array.map() und Array.reduce() verwende?

Am Codepen wohl eher nicht. Meins läuft unter jsFiddle. Aber wenn Du die Quersumme mit Arrays bildest, dann bist Du definitiv zu lahm. Mein Prozessor ist übrigens ziemlich alt (Core i5 3470)

Update. So, bin bis zur Milliarde gekommen. Angefangen habe ich mit 17ns pro Zahl, gegen Ende ging es hoch bis 20ns. Laufzeit war 2000 Sekunden. Das Script in der letzten Fassung habe ich verloren, weil ich in JSFiddle kein Autosave verwende und im falschen Browserfenster F5 gedrückt habe 🙄. Gut, dass ich die Basiszahl für die Widerlegung der Notwendigkeit meiner Folge hierhin kopiert hatte.

Rolf

[Rolf B]

Hallo Gunnar,

Das muss ich mir glatt mal ansehen

Deins ist schön sauber und objektorientiert. Und mit 2,1µs pro getestetem Wert auch gar nicht mal so langsam unterwegs. Ich bin in dieser Zahlenkategorie bei 1,4µs pro getestetem Wert.

Wenn ich deine digitSum durch meine Quersumme ersetze, komme ich auf 0,6µs pro Wert. Aber wenn ich auf BigInt umstelle, geht es hoch auf 4. Ugh!

Rolf

[Gunnar Bittersmann]

@@Gunnar Bittersmann

Aber es gibt mutmaßlich unendlich viele deiner Siebenerketten.

Zusatzaufgabe: Beweise diese Mutmaßung.

Ehe es Wochenende wird und Matthias schon wieder mit der nächsten Aufgabe kommt, hier noch der Beweis:

Wir betrachten aufeinanderfolgende Quadratzahlen, beginnend beim Quadrat einer Zehnerpotenz 10ⁿ mit n ∈ ℕ⁺:

Qudratzahl	Darstellung[1]	Quersumme
(10ⁿ)² = 10²ⁿ	10*	1
(10ⁿ + 1)² = 10²ⁿ + 2 · 10ⁿ + 1	10*20*1	4
(10ⁿ + 2)² = 10²ⁿ + 4 · 10ⁿ + 4	10*40*4	9
(10ⁿ + 3)² = 10²ⁿ + 6 · 10ⁿ + 9	10*60*9	16
(10ⁿ + 4)² = 10²ⁿ + 8 · 10ⁿ + 16	10*80*16 | 196	16
(10ⁿ + 5)² = 10²ⁿ + 10 · 10ⁿ + 25	10*10*25 | 225	9
(10ⁿ + 6)² = 10²ⁿ + 12 · 10ⁿ + 36	10*120*36 | 256	13

Die Zahlen (10ⁿ)² bis (10ⁿ + 5)² bilden eine 6er-Kette; nach oben lässt sich diese nicht zu einer 7er-Kette erweitern.

Aber vielleicht nach unten?

Qudratzahl	Darstellung[2]	Quersumme
(10ⁿ − 1)² = 10²ⁿ − 2 · 10ⁿ + 1 = (10ⁿ − 2) · 10ⁿ + 1	9{n−1}80*1	9n
(10ⁿ − 2)² = 10²ⁿ − 4 · 10ⁿ + 4 = (10ⁿ − 4) · 10ⁿ + 4	9{n−1}60*4	9n + 1

9n, die Quersumme von (10ⁿ − 1)², ist genau dann eine Quadratzahl, wenn n eine Quadratzahl ist; n = k². In dem Fall ist 9n + 1 keine Quadratzahl.

Das heißt: Für alle k ∈ ℕ⁺ bildet die Folge $$(10^{k^2}-1)^2, (10^{k^2})^2, (10^{k^2}+1)^2, …, (10^{k^2}+5)^2$$ eine 7er-Kette. Folglich gibt es unendlich viele 7er-Ketten. (Dass es auch 7er-Ketten mit anderen Startzahlen als $$(10^{k^2}-1)^2$$ geben könnte, muss für diesen Beweis nicht betrachtet werden.)

Außerdem sieht man: Es gibt kein k, für das sich die derart gebildete 7er-Kette zu einer 8er-Kette erweitern ließe. Das schließt aber nicht aus, dass es 8er-Ketten mit anderen Startzahlen als $$(10^{k^2}-2)^2$$ geben könnte.

😷 LLAP

---

1. angeleht an die RegExp-Notation: 0* heißt: beliebig viele Nullen ↩︎

2. 9{n−1} heißt: genau n − 1 Neunen ↩︎

[Rolf B]

Hallo Gunnar,

jo, den "Beweis" für die Quersummen habe ich genauso geführt, nur umständlicher aufgeschrieben.

Dass diese Folge aus Startzahlen nicht alle 7er Ketten liefert, konnte ich ja mehr oder weniger zufällig nachweisen; bei 608.362.161² beginnt ebenfalls eine. Weiter als bis eine Milliarde habe ich mein Script nicht laufen lassen.

Eine Achterkette startet bei 46.045.846², andere habe ich nicht gefunden.

Rolf

[Matthias Apsel]

Hallo Rolf B,

Dass diese Folge aus Startzahlen nicht alle 7er Ketten liefert, konnte ich ja mehr oder weniger zufällig nachweisen; bei 608.362.161² beginnt ebenfalls eine. Weiter als bis eine Milliarde habe ich mein Script nicht laufen lassen.

Eine Achterkette startet bei 46.045.846², andere habe ich nicht gefunden.

Damit startet auch eine Siebenerkette bei dieser Zahl.

Bis demnächst
Matthias

[Rolf B]

Hallo Matthias,

ja. Schrub ich weiter oben auch mal.

Ich habe den Chain Explorer nach C# portiert, weil ich hoffte, dann schneller zu sein. Bei den ersten Versuchen bin ich fast ausgeflippt; JavaScript prüft eine Zahl in 1,5µs (steigend auf 2µs wenn man in den Milliardenbereich kommt), und mein C# Programm schien schon bei kleinen Zahlen 3µs und mehr zu brauchen. Aber ich muss mich da bei der Umrechnung von Ticks in µs vertan haben, nachdem ich etwas hin und her gebastelt habe sind es 0,4µs pro Zahl wenn ich die BigInteger Implementierung von .net verwende und 0,08µs pro Zahl, wenn ich ulong benutze (das ist aber bei 2^32-1 am Ende).

Dabei lernt man dann was über Tradeoffs Laufzeit gegen Speicher.

Zum Beispiel: Ist eine Quersumme quadratisch? Pro Quersumme die Wurzel ziehen? Hui, das ist langsam. Aber bei einer 100-stelligen Zahl ist die Quersumme maximal 900, also warum nicht ein Array bilden, in dem für jede Zahl von 1-1000 ein Flag steht, ob sie eine Quadratzahl ist.

Gesagt getan, statt

double sq = Math.Sqrt(checksum);
if (Math.Floor(sq) == sq) {
   // Quadratzahl
}

schrieb ich also

if (squares[checksum] == 1) {
   // Quadratzahl
}

Effekt: ca 20ns pro Zahl. 5% der Zeit pro Zahl (bei BigInt, bei ulong ist es natürlich signifikanter). Aber da hätte ich viel mehr Effekt erwartet.

Zweites Beispiel: Bilden der Quersumme.

Naiver Ansatz:

   BigInteger value = k*k;
   while (value > 0)
   {
      int digit = (int)(value % 10);
      value = (value - digit) / 10;
      checksum += digit;
   } 

Hui, das kostet. 2µs pro Zahl sind es so. Besser die DivRem Methode verwenden, die liefert den Rest als Abfallprodukt des Quotienten

   BigInteger value = k*k;
   while (value > 0)
   {
      value = BigInteger.DivRem(value, 10, out BigInteger digit);
      checksum += (int)digit;
   }

Immerhin, noch 1,4µs pro Zahl (im kleinen Millionenbereich). Im Milliardenbereich eher 2,3µs.

Also wie reduziert man die BigInteger Operationen? Ich muss ja nicht Ziffer für Ziffer vorgehen. Ich kann für die Zahlen von 0-X Quersummen vorberechnen, z.B. X=1000. Das drittelt die Anzahl der BigInteger Divisionen.

   BigInteger value = k*k;
   while (value > 0)
   {
      value = BigInteger.DivRem(value, bChecksumCount, out BigInteger digitGroup);
      checksum += Checksums[(int)digitGroup];
   } 

Bingo, 560ns pro Zahl im kleinen Bereich, 800ns pro Zahl im Milliardenbereich. Es wird. Warum bei X=1000 stehen bleiben? Die Quersumme von 999999 ist 54, also reicht ein Byte pro Zahl. Also: 1000000 vorberechnete Quersummen. Damit komme ich dann auf 420ns und 520ns im Milliardenbereich.

Und jetzt noch der Oberclou. Die Berechnung eines Quadrats ist doch bestimmt aufwändig. Warum nicht den Umstand berücksichtigen, dass zwischen zwei Quadratzahlen die Differenz um je 2 ansteigt und sich hochaddieren statt multiplizieren. Genial! Schnell eingebaut: 470ns pro Zahl im kleinen Bereich. WTF? Etwas Profiling ergab: k=k+1 ist 15ns langsamer als k=k+b1 (mit b1 als Variable, die den BigInteger-Wert 1 enthält). Die Konvertierung einer Int-Konstanten in ein BigInteger ist ein Zeitfresser! Aber eine Addition braucht trotzdem noch doppelt so viel Zeit wie eine Multiplikation. Weird! Diese Optimierung war keine.

Für C++ suche ich noch eine BigInt Library. Bin gespannt was dann passiert; ich will ja nicht selbst eine programmieren.

Rolf

[Matthias Apsel]

Hallo Rolf B,

Das klingt ja spannend. Ich freue mich, zu sehen, was ich so alles ausgelöst habe. 😇

Bis demnächst
Matthias

[1unitedpower]

Ich habe da auch mal ein Skript gebastelt:

function digitSum(n) {
  let sum = 0
  while (n > 0n) {
    sum += Number(n % 10n)
    n = n / 10n
  }
  return sum
}

function isSquare(n) {
  return Math.floor(Math.sqrt(n))**2 === n
}

function run(limit) {
  console.profile()
  const start = performance.now()
  let sequenceLength = 0
  for (let i = 0n; i <= limit; i++) {
	if (isSquare(digitSum(i**2n))) {
	  sequenceLength++
	  if (sequenceLength === 7) {
		console.log(`Result found. Sequence starts at ${i - 6n}`)
	  }
	} else {
	  sequenceLength = 0
	}
  }
  const end = performance.now()
  console.profileEnd()
  const delta = end - start
  console.log('Total Time (s):', delta / 1000)
  console.log('Average Time per Number (μs):', delta / limit * 1000)
}

Um die ersten 10 Millionen Zahlen zu testen, braucht das Programm bei mir ca. 37s, bzw. 3,7μs pro Zahl.

Der Engpass ist eindeutig die Brechenung der Quersumme, dort verbringt das Programm ca. 85% der Zeit. Das konnte ich dem Profiler entnehmen.

Wenn ich die Funktion durch diese hier ersetze:

function digitSum(n) {
  const digits = n.toString()
  let sum = 0
  for (let digit of digits) {
    sum += Number(digit)
  }
  return sum
}

braucht das Programm insgesamt nur noch 6.5s, bzw. 0,65μs pro Zahl. Es verbingt etwa 42% mit der Berechnung von Quersummen und 42% mit der Berechnung der Quadratzahlen. Das Wurzelziehen schlägt mit 0.2% kaum zu Buche. Das liegt in dem Fall auch daran, dass ich die Quersummen in gewöhnlichen Number-Datentypen speichere und damit weiter rechne.

[Der Martin]

Hallo,

was ist denn das für eine Sprache, in der 0n oder 10n ein syntaktisch korrekter Ausdruck ist?

function digitSum(n) {
  let sum = 0
  while (n > 0n) {
    sum += Number(n % 10n)
    n = n / 10n
  }
  return sum
}

Live long and pros healthy,
 Martin

[1unitedpower]

Hallo,

was ist denn das für eine Sprache, in der 0n oder 10n ein syntaktisch korrekter Ausdruck ist?

Das ist JavaScripts Schreibweise für ganze Zahlen mit beliebiger Genauigkeit.

[Gunnar Bittersmann]

@@1unitedpower

was ist denn das für eine Sprache, in der 0n oder 10n ein syntaktisch korrekter Ausdruck ist?

Das ist JavaScripts Schreibweise für ganze Zahlen mit beliebiger Genauigkeit.

Guckst du hier: BigInt.

„Mit beliebiger Genauigkeit“ ist wohl etwas übertrieben.

😷 LLAP

[1unitedpower]

„Mit beliebiger Genauigkeit“ ist wohl etwas übertrieben.

Inwiefern? Sind die BigInts doch beschränkt? Oder spielst du auf physikalische Grenzen an?

[Gunnar Bittersmann]

@@1unitedpower

„Mit beliebiger Genauigkeit“ ist wohl etwas übertrieben.

Inwiefern? Sind die BigInts doch beschränkt? Oder spielst du auf physikalische Grenzen an?

Ich hab heute nicht nur Probleme mit dem Schreiben, sondern auch mit dem Lesen. Die auf MDN genannte Beschränkung bezieht sich ja auf Number, nicht auf BigInt.

😷 LLAP

[Der Martin]

Hi,

was ist denn das für eine Sprache, in der 0n oder 10n ein syntaktisch korrekter Ausdruck ist?

Das ist JavaScripts Schreibweise für ganze Zahlen mit beliebiger Genauigkeit.

danke, kannte ich noch nicht.
Man lernt doch täglich dazu!

Live long and pros healthy,
 Martin

[Gunnar Bittersmann]

@@1unitedpower

function isSquare(n) {
  return Math.floor(Math.sqrt(n))**2 === n
}

Kommt die Funktion mit Rundungsfehlern klar? Nicht doch besser Math.round() nehmen?

😷 LLAP

[1unitedpower]

Kommt die Funktion mit Rundungsfehlern klar? Nicht doch besser Math.round() nehmen?

Keine Ahnung, kann gut sein. Ich hab Floating Point Arithmetik gefressen. Am liebsten hätte ich ja einen Datentypen für konstruktive reelle Zahlen. Oder eine Wurzelfunktion von den ganzen Zahlen in die ganzen Zahlen.

[Rolf B]

Hallo 1unitedpower,

es ist schon faszinierend, dass toString die ideale Ausgangsbasis für eine Quersumme ist. Die toString-Methode von BigInt dürfte hoch optimiert sein und deutlich effizienter als Divisionen durch 10 oder 1000000 (für meine Block-Quersummen) auf JS-Level.

Wenn ich toString einsetze, kommt mein JS-Script auch auf 0,6µs pro Zahl.

Und mit dieser Methode komme ich unter 0,4µs:

function quersumme(n) {
   let digits = n.toString(),
       i = digits.length,
       q = 0;
   while (i > 0) q += digits.charCodeAt(--n)-48;
   return q;
}

Interessant ist auch, dass inlining von Funktionen kaum etwas bringt. Entweder macht der JIT-Compiler der JS-Engine das von allein, oder Funktionsaufrufe in JavaScript sind rasend schnell.

Und was mich nun komplett schockiert hat, ist, dass Firefox 80 das gleiche Script in 60% der Zeit absolviert, die Chrome 85 braucht. WTF? Ich dachte, V8 wäre der Maßstab in JS Performance - aber offenbar ist dieser Code Energiefutter für den Spinnenaffen.

Rolf

[Matthias Apsel]

Hallo Gunnar Bittersmann,

9n, die Quersumme von (10ⁿ − 1)², ist genau dann eine Quadratzahl, wenn n eine Quadratzahl ist; n = k². In dem Fall ist 9n + 1 keine Quadratzahl.

Für n > 0 ist höchstens eine der beiden Zahlen 9n und 9n + 1 eine Quadratzahl.

🤪

Bis demnächst
Matthias

[Der Martin]

Hallo Matthias,

was heißt denn hier "diesmal Zahlen, keine Figuren"?
Zahlen sind doch figures!

*scnr*
 Martin