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

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).

using System.Collections.Generic;

using System.Linq;

a.Count, sw.Elapsed.TotalMilliseconds);

}

{{out|Output @Tio.run}}

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

===Alternate Version===

A little quicker, seeks between squares.

using System.Collections.Generic;

using System.Linq;

Console.Write(sf, s.Last()-y.Last(),y.Last());

}

{{out|Output @Tio.run}}

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

{{libheader|Go-rcu}}

The quicker version and hence (indirectly) a translation of C#.

import (

}

{{out}}

Since the implementation is based on generic concepts (such as runs), the

helper functions are potentially independently useful.

# sums of distinct squares (sods)

| [range(2; $ix+2|sq)] - $sods;

{{out}}

<pre>

=={{header|Julia}}==

A true proof of the sketch below would require formal mathematical induction.

Here we show all the 128 < numbers < 400 can be expressed as a sum of distinct squares. Now

11 * 11 < 128 < 12 * 12. It is also true that we need no square less than 144 (12 * 12) to

println(possibles)

<pre>

[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]

=={{header|Mathematica}}/{{header|Wolfram Language}}==

SumOfSquareable[n_Integer] := MemberQ[Total /@ Subsets[Range[1, Floor[Sqrt[n]]]^2, {1, \[Infinity]}], n]

notsummable = {};

{\[Infinity]}

]

{{out}}

<pre>{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}</pre>

are not reachably nor<br>

SumOfSquare-2, SumOfSquare-3,SumOfSquare-6,...SumOfSquare-108,SumOfSquare-112,SumOfSquare-128<br>

{$IFDEF Windows} {$APPTYPE CONSOLE} {$ENDIF}

var

{$IFNDEF UNIX} readln; {$ENDIF}

end.

{{out}}

<pre>

Strictly speaking the termination test should probably be <code>if r and sq>r then</code>, not that shaving off two pointless iterations makes any difference at all.

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #004080;">sequence</span> <span style="color: #000000;">summable</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #004600;">true</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- (1 can be expressed as 1*1)</span>

<span style="color: #008080;">constant</span> <span style="color: #000000;">nwansods</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"numbers which are not the sum of distinct squares"</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">find_all</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">summable</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">),</span><span style="color: #000000;">nwansods</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">))})</span>

{{out}}

<pre>

'''Spoiler:''' ''(highlight to read)''<br>

<span style="foreground-color:black;background-color:black;">Once the longest run of consecutive generated sums is longer the the next square, every number after can be generated by adding the next square to every number in the run. Find the ''new'' longest run, add the ''next'' square, etc.<span>

for 1..∞ -> $sq { # for every combination of all squares

}

put grep * ∉ @sums, 1..@run.tail and last if @run.elems > @squares[$sq];

{{out}}

<pre>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</pre>

===Brute force===

This uses a brute force approach to generate the relevant numbers, similar to Julia, except using the same figures as the above proof. Still slow in Wren, around 20 seconds.

var combs = []

var results = []

System.print("Numbers which are not the sum of distinct squares:")

{{out}}

{{libheader|Wren-fmt}}

Hugely quicker in fact - only 24 ms, the same as C# itself.

import "./fmt" for Fmt

System.print(a.join(", "))

Fmt.print(sf, i - g, g)

{{out}}