Numbers which are not the sum of distinct squares: Difference between revisions

=={{header|C#|CSharp}}==

Following in the example set by the '''Free Pascal''' entry for this task, this C# code is re-purposed from [[Practical_numbers#C#]].<br>

It seems that finding as many (or more) contiguous numbers-that-''are''-the-sum-of-distinct-squares as the highest found gap demonstrates that there is no higher gap, since there is enough overlap among the permutations of the sums of possible squares (once the numbers are large enough).

<lang csharp>using System;

using System.Collections.Generic;

using System.Linq;

class Program {

// recursively permutates the list of squares to seek a matching sum

static bool soms(int n, IEnumerable<int> f) {

if (n <= 0) return false;

if (f.Contains(n)) return true;

switch(n.CompareTo(f.Sum())) {

case 1: return false;

case 0: return true;

case -1:

var rf = f.Reverse().Skip(1).ToList();

return soms(n - f.Last(), rf) || soms(n, rf);

}

return false;

}

static void Main() {

var sw = System.Diagnostics.Stopwatch.StartNew();

int c = 0, r, i, g; var s = new List<int>(); var a = new List<int>();

var sf = "stopped checking after finding {0} sequential non-gaps after the final gap of {1}";

for (i = 1, g = 1; g >= (i >> 1); i++) {

if ((r = (int)Math.Sqrt(i)) * r == i) s.Add(i);

if (!soms(i, s)) a.Add(g = i);

}

sw.Stop();

Console.WriteLine("Numbers which are not the sum of distinct squares:");

Console.WriteLine(string.Join(", ", a));

Console.WriteLine(sf, i - g, g);

Console.Write("found {0} total in {1} ms",

a.Count, sw.Elapsed.TotalMilliseconds);

}

}</lang>

{{out|Output @Tio.run}}

<pre>Numbers which are not the sum of distinct squares:

2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128

stopped checking after finding 130 sequential non-gaps after the final gap of 128

found 31 total in 24.7904 ms</pre>