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
#Jq

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