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