How to resolve the algorithm Numbers which are not the sum of distinct squares step by step in the jq 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 jq 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 jq programming language
Source code in the jq programming language
#def squares: range(1; infinite) | . * .;
# sums of distinct squares (sods)
# Output: a stream of [$n, $sums] where $sums is the array of sods based on $n
def sods:
# input: [$n, $sums]
def next:
. as [$n, $sums]
| (($n+1)*($n+1)) as $next
| reduce $sums[] as $s ($sums + [$next];
if index($s + $next) then . else . + [$s + $next] end)
| [$n + 1, unique];
[1, [1]]
| recurse(next);
# Input: an array
# Output: the length of the run beginning at $n
def length_of_run($n):
label $out
| (range($n+1; length),null) as $i
| if $i == null then (length-$n)
elif .[$i] == .[$i-1] + 1 then empty
else $i-$n, break $out
end;
# Input: an array
def length_of_longest_run:
. as $in
| first(
foreach (range(0; length),null) as $i (0;
if $i == null then .
else ($in|length_of_run($i)) as $n
| if $n > . then $n else . end
end;
if $i == null or (($in|length) - $i) < . then . else empty end) );
def sq: .*.;
# Output: [$ix, $length]
def relevant_sods:
first(
sods
| . as [$n, $s]
| ($s|length_of_longest_run) as $length
| if $length > ($n+1|sq) then . else empty end );
def not_sum_of_distinct_squares:
relevant_sods
| . as [$ix, $sods]
| [range(2; $ix+2|sq)] - $sods;
not_sum_of_distinct_squares
You may also check:How to resolve the algorithm 100 prisoners step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm FASTA format step by step in the C++ programming language
You may also check:How to resolve the algorithm SHA-1 step by step in the S-lang programming language
You may also check:How to resolve the algorithm Pell's equation step by step in the Perl programming language
You may also check:How to resolve the algorithm Count the coins step by step in the jq programming language