Numbers which are not the sum of distinct squares: Difference between revisions
Numbers which are not the sum of distinct squares (view source)
Revision as of 21:49, 26 November 2021
, 2 years ago→{{header|C#|CSharp}}: added Alternative version
(→{{header|Wren}}: Added a quicker version, C# translation.) |
(→{{header|C#|CSharp}}: added Alternative version) |
||
Line 77:
stopped checking after finding 130 sequential non-gaps after the final gap of 128
found 31 total in 24.7904 ms</pre>
===Alternate Version===
A little quicker, seeks between squares.
<lang csharp>using System;
using System.Collections.Generic;
using System.Linq;
class Program {
static List<int> y = new List<int>();
// checks permutations of squares in a binary fashion
static void soms(ref List<int> f, int d) { f.Add(f.Last() + d);
int l = 1 << f.Count, max = f.Last(), min = max - d;
var x = new List<int>();
for (int i = 1; i < l; i++) {
int j = i, k = 0, r = 0; while (j > 0) {
if ((j & 1) == 1 && (r += f[k]) >= max) break;
j >>= 1; k++; } if (r > min && r < max) x.Add(r); }
for ( ; ++min < max; ) if (!x.Contains(min)) y.Add(min); }
static void Main() {
var sw = System.Diagnostics.Stopwatch.StartNew();
var s = new List<int>{ 1 };
var sf = "stopped checking after finding {0} sequential non-gaps after the final gap of {1}";
for (int d = 1; d <= 29; ) soms(ref s, d += 2);
sw.Stop();
Console.WriteLine("Numbers which are not the sum of distinct squares:");
Console.WriteLine(string.Join (", ", y));
Console.WriteLine("found {0} total in {1} ms",
y.Count, sw.Elapsed.TotalMilliseconds);
Console.Write(sf, s.Last()-y.Last(),y.Last());
}
}</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
found 31 total in 9.9693 ms
stopped checking after finding 128 sequential non-gaps after the final gap of 128</pre>
=={{header|Julia}}==
| |||