Forbidden numbers: Difference between revisions
Added Sidef
(Added AppleScript.) |
(Added Sidef) |
||
| (5 intermediate revisions by 4 users not shown) | |||
Line 442:
Forbidden number count up to 500000: 83331
</pre>
=={{header|Julia}}==
{{trans|Python}}
<syntaxhighlight lang ="python">""" true if num is a forbidden number """
function isforbidden(num)
fours, pow4 = num, 0
while fours > 1 && fours % 4 == 0
fours ÷= 4
pow4 += 1
end
return (num ÷ 4^pow4) % 8 == 7
end
const f500M = filter(isforbidden, 1:500_000_000)
for (idx, fbd) in enumerate(f500M[begin:begin+49])
print(lpad(fbd, 4), idx % 10 == 0 ? '\n' : "")
end
for fbmax in [500, 5000, 50_000, 500_000, 500_000_000]
println("\nThere are $(sum(x <= fbmax for x in f500M)) forbidden numbers <= $fbmax.")
end
</syntaxhighlight>{{out}}
<pre>
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
There are 82 forbidden numbers <= 500.
There are 831 forbidden numbers <= 5000.
There are 8330 forbidden numbers <= 50000.
There are 83331 forbidden numbers <= 500000.
There are 83333328 forbidden numbers <= 500000000.
</pre>
=={{header|Nim}}==
Uses the algorithm from the OEIS page.
<syntaxhighlight lang="Nim">import std/[math, strformat, strutils]
const Max = 500_000
func isForbidden(num: Positive): bool =
## Return "true" is "n" is a forbidden number.
var fours = num
var pow4 = 0
while fours > 1 and (fours and 3) == 0:
fours = fours shr 2
inc pow4
result = (num div 4^pow4 and 7) == 7
iterator forbiddenNumbers(): int =
var n = 1
while true:
if n.isForbidden:
yield n
inc n
var count = 0
var lim = 500
for n in forbiddenNumbers():
inc count
if count <= 50:
stdout.write &"{n:>3}"
stdout.write if count mod 10 == 0: '\n' else: ' '
if count == 50: echo()
elif n > lim:
echo &"Numbers of forbidden numbers up to {insertSep($lim)}: {insertSep($(count - 1))}"
lim *= 10
if lim > Max:
break
</syntaxhighlight>
{{out}}
<pre> 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
Numbers of forbidden numbers up to 500: 82
Numbers of forbidden numbers up to 5_000: 831
Numbers of forbidden numbers up to 50_000: 8_330
Numbers of forbidden numbers up to 500_000: 83_331
</pre>
Line 580 ⟶ 670:
printf "First %s forbidden numbers:\n", num2en 50;
print "\n\n";
Line 755 ⟶ 845:
2: 831
1: 8330
</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">say ("First 50 terms: ", 50.by { .squares_r(3) == 0 })
for n in (500, 5_000, 50_000, 500_000) {
var v = (1..n -> count {|n|
idiv(n, ipow(4, n.valuation(4))).is_congruent(7, 8)
})
say "There are #{v} forbidden numbers up to #{n.commify}."
}</syntaxhighlight>
{{out}}
<pre>
First 50 terms: [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]
There are 82 forbidden numbers up to 500.
There are 831 forbidden numbers up to 5,000.
There are 8330 forbidden numbers up to 50,000.
There are 83331 forbidden numbers up to 500,000.
</pre>
Line 761 ⟶ 869:
{{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="
var forbidden = Fn.new { |limit, countOnly|
Line 816 ⟶ 924:
===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="
var isForbidden = Fn.new { |n|
| |||