How to resolve the algorithm Numbers which are not the sum of distinct squares step by step in the Nim programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Numbers which are not the sum of distinct squares step by step in the Nim programming language

Table of Contents

Problem Statement

Integer squares are the set of integers multiplied by themselves: 1 x 1 = 1, 2 × 2 = 4, 3 × 3 = 9, etc. ( 1, 4, 9, 16 ... ) Most positive integers can be generated as the sum of 1 or more distinct integer squares. Many can be generated in multiple ways: The number of positive integers that cannot be generated by any combination of distinct squares is in fact finite:

Find and show here, on this page, every positive integer than cannot be generated as the sum of distinct squares. Do not use magic numbers or pre-determined limits. Justify your answer mathematically.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Numbers which are not the sum of distinct squares step by step in the Nim programming language

Source code in the nim programming language

import std/[algorithm, math, monotimes, strformat, strutils, times]

proc soms(n: int; f: seq[int]): bool =
  ## Recursively permutates the list of squares to seek a matching sum.
  if n <= 0: return false
  if n in f: return true
  case cmp(n, sum(f))
  of 1:
    result = false
  of 0:
    result = true
  else:
    let rf = reversed(f.toOpenArray(0, f.len - 2))
    result = soms(n - f[^1], rf) or soms(n, rf)

let start = getMonoTime()
var s, a: seq[int]
var i, g = 1
while g >= i shr 1:
  let r = sqrt(i.toFloat).int
  if r * r == i: s.add i
  if not soms(i, s):
    g = i
    a.add g
  inc i

echo "Numbers which are not the sum of distinct squares:"
echo a.join(" ")
echo &"\nStopped checking after finding {i - g} sequential non-gaps after the final gap of {g}."
echo &"Found {a.len} total in {(getMonotime() - start).inMicroseconds} µs."


  

You may also check:How to resolve the algorithm Loops/Break step by step in the VBA programming language
You may also check:How to resolve the algorithm Pathological floating point problems step by step in the Crystal programming language
You may also check:How to resolve the algorithm N'th step by step in the AWK programming language
You may also check:How to resolve the algorithm Cramer's rule step by step in the Maple programming language
You may also check:How to resolve the algorithm Color of a screen pixel step by step in the Logo programming language