Quadrate – diesmal Zahlen, keine Figuren – Lösung der Zusatzaufgabe

[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.