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 15:06, 21 April 2022
, 2 years agoAdded Go
m (→Quicker: Removed an unused variable.) |
(Added Go) |
||
Line 116:
found 31 total in 9.9693 ms
stopped checking after finding 128 sequential non-gaps after the final gap of 128</pre>
=={{header|Go}}==
{{trans|Wren}}
{{libheader|Go-rcu}}
The quicker version and hence (indirectly) a translation of C#.
<lang go>package main
import (
"fmt"
"math"
"rcu"
)
func contains(a []int, n int) bool {
for _, e := range a {
if e == n {
return true
}
}
return false
}
// recursively permutates the list of squares to seek a matching sum
func soms(n int, f []int) bool {
if n <= 0 {
return false
}
if contains(f, n) {
return true
}
sum := rcu.SumInts(f)
if n > sum {
return false
}
if n == sum {
return true
}
rf := make([]int, len(f))
copy(rf, f)
for i, j := 0, len(rf)-1; i < j; i, j = i+1, j-1 {
rf[i], rf[j] = rf[j], rf[i]
}
rf = rf[1:]
return soms(n-f[len(f)-1], rf) || soms(n, rf)
}
func main() {
var s, a []int
sf := "\nStopped checking after finding %d sequential non-gaps after the final gap of %d\n"
i, g := 1, 1
for g >= (i >> 1) {
r := int(math.Sqrt(float64(i)))
if r*r == i {
s = append(s, i)
}
if !soms(i, s) {
g = i
a = append(a, g)
}
i++
}
fmt.Println("Numbers which are not the sum of distinct squares:")
fmt.Println(a)
fmt.Printf(sf, i-g, g)
fmt.Printf("Found %d in total\n", len(a))
}
var r int</lang>
{{out}}
<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 in total
</pre>
=={{header|jq}}==
| |||