Forbidden numbers: Difference between revisions
Added Wren
(Added Wren) |
|||
Line 159:
Forbidden number count up to five million: 833,329</pre>
=={{header|Wren}}==
===Version 1===
{{libheader|Wren-fmt}}
This uses a sieve to filter out those numbers which are the sums of one, two or three squares. Works but very slow (c. 52 seconds).
<syntaxhighlight lang="ecmascript">import "./fmt" for Fmt
var forbidden = Fn.new { |limit, countOnly|
var sieve = List.filled(limit+1, false)
var ones
var twos
var threes
var i = 0
while((ones = i*i) <= limit) {
sieve[ones] = true
var j = i
while ((twos = ones + j*j) <= limit) {
sieve[twos] = true
var k = j
while ((threes = twos + k*k) <= limit) {
sieve[threes] = true
k = k + 1
}
j = j + 1
}
i = i + 1
}
if (countOnly) return sieve.count { |b| !b }
var forbidden = []
for (i in 1..limit) {
if (!sieve[i]) forbidden.add(i)
}
return forbidden
}
System.print("The first 50 forbidden numbers are:")
Fmt.tprint("$3d", forbidden.call(400, false).take(50), 10)
System.print()
for (limit in [500, 5000, 50000, 500000, 5000000]) {
var count = forbidden.call(limit, true)
Fmt.print("Forbidden number count <= $,9d: $,7d", limit, count)
} </syntaxhighlight>
{{out}}
<pre>
The first 50 forbidden numbers are:
7 15 23 28 31 39 47 55 60 63
71 79 87 92 95 103 111 112 119 124
127 135 143 151 156 159 167 175 183 188
191 199 207 215 220 223 231 239 240 247
252 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
</pre>
===Version 2===
This is a translation of the formula-based Python code in the OEIS link which at around 1.1 seconds is almost 50 times faster than Version 1 and is also about 3 times faster than the PARI code in that link.
<syntaxhighlight lang="ecmascript">import "./fmt" for Fmt
var isForbidden = Fn.new { |n|
var m = n
var v = 0
while (m > 1 && m % 4 == 0) {
m = (m/4).floor
v = v + 1
}
return (n/4.pow(v)).floor % 8 == 7
}
var f400 = (1..400).where { |i| isForbidden.call(i) }
System.print("The first 50 forbidden numbers are:")
Fmt.tprint("$3d", f400.take(50), 10)
System.print()
for (limit in [500, 5000, 50000, 500000, 5000000]) {
var count = (1..limit).count { |i| isForbidden.call(i) }
Fmt.print("Forbidden number count <= $,9d: $,7d", limit, count)
}</syntaxhighlight>
{{out}}
<pre>
Same as Version 1
</pre>
| |||