Forbidden numbers: Difference between revisions

Content added Content deleted

Inline

@@ Line 32: / Line 32: @@
 ;* [[oeis:A004215|OEIS A004215 - Numbers that are the sum of 4 but no fewer nonzero squares]]
+=={{header|Go}}==
+{{libheader|Go-rcu}}
+A translation of the Python code in the OEIS link. Runtime around 7 seconds.
+<syntaxhighlight lang="go">package main
+import (
+    "fmt"
+    "math"
+    "rcu"
+)
+func isForbidden(n int) bool {
+    m := n
+    v := 0
+    for m > 1 && m%4 == 0 {
+        m /= 4
+        v++
+    }
+    pow := int(math.Pow(4, float64(v)))
+    return n/pow%8 == 7
+}
+func main() {
+    forbidden := make([]int, 50)
+    for i, count := 0, 0; count < 50; i++ {
+        if isForbidden(i) {
+            forbidden[count] = i
+            count++
+        }
+    }
+    fmt.Println("The first 50 forbidden numbers are:")
+    rcu.PrintTable(forbidden, 10, 3, false)
+    fmt.Println()
+    limit := 500
+    count := 0
+    for i := 1; ; i++ {
+        if isForbidden(i) {
+            count++
+        }
+        if i == limit {
+            slimit := rcu.Commatize(limit)
+            scount := rcu.Commatize(count)
+            fmt.Printf("Forbidden number count <= %11s: %10s\n", slimit, scount)
+            if limit == 500_000_000 {
+                return
+            }
+            limit *= 10
+        }
+    }
+}</syntaxhighlight>
+{{out}}
+<pre>
+The first 50 forbidden numbers are:
+15  23  28  31  39  47  55  60  63
+79  87  92  95 103 111 112 119 124
+135 143 151 156 159 167 175 183 188
+199 207 215 220 223 231 239 240 247
+255 263 271 279 284 287 295 303 311
+Forbidden number count <=         500:         82
+Forbidden number count <=       5,000:        831
+Forbidden number count <=      50,000:      8,330
+Forbidden number count <=     500,000:     83,331
+Forbidden number count <=   5,000,000:    833,329
+Forbidden number count <=  50,000,000:  8,333,330
+Forbidden number count <= 500,000,000: 83,333,328
+</pre>
 =={{header|jq}}==
@@ Line 87: / Line 156: @@
 Forbidden number count up to 500000: 83331
 </pre>
 =={{header|Pascal}}==