How to resolve the algorithm Numbers which are not the sum of distinct squares step by step in the Wren 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 Wren 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 Wren programming language
Source code in the wren programming language
var squares = (1..18).map { |i| i * i }.toList
var combs = []
var results = []
// generate combinations of the numbers 0 to n-1 taken m at a time
var combGen = Fn.new { |n, m|
var s = List.filled(m, 0)
var last = m - 1
var rc // recursive closure
rc = Fn.new { |i, next|
var j = next
while (j < n) {
s[i] = j
if (i == last) {
combs.add(s.toList)
} else {
rc.call(i+1, j+1)
}
j = j + 1
}
}
rc.call(0, 0)
}
for (n in 1..324) {
var all = true
for (m in 1..18) {
combGen.call(18, m)
for (comb in combs) {
var tot = (0...m).reduce(0) { |acc, i| acc + squares[comb[i]] }
if (tot == n) {
all = false
break
}
}
if (!all) break
combs.clear()
}
if (all) results.add(n)
}
System.print("Numbers which are not the sum of distinct squares:")
System.print(results)
import "./math" for Nums
import "./fmt" for Fmt
// recursively permutates the list of squares to seek a matching sum
var soms
soms = Fn.new { |n, f|
if (n <= 0) return false
if (f.contains(n)) return true
var sum = Nums.sum(f)
if (n > sum) return false
if (n == sum) return true
var rf = f[-1..0].skip(1).toList
return soms.call(n - f[-1], rf) || soms.call(n, rf)
}
var start = System.clock
var s = []
var a = []
var sf = "\nStopped checking after finding $d sequential non-gaps after the final gap of $d"
var i = 1
var g = 1
var r
while (g >= (i >> 1)) {
if ((r = i.sqrt.floor) * r == i) s.add(i)
if (!soms.call(i, s)) a.add(g = i)
i = i + 1
}
System.print("Numbers which are not the sum of distinct squares:")
System.print(a.join(", "))
Fmt.print(sf, i - g, g)
Fmt.print("Found $d total in $d ms.", a.count, ((System.clock - start)*1000).round)
You may also check:How to resolve the algorithm Call a function step by step in the Raku programming language
You may also check:How to resolve the algorithm Discordian date step by step in the Raku programming language
You may also check:How to resolve the algorithm Heronian triangles step by step in the ALGOL W programming language
You may also check:How to resolve the algorithm Stack step by step in the Mercury programming language
You may also check:How to resolve the algorithm Tonelli-Shanks algorithm step by step in the C# programming language