Forbidden numbers: Difference between revisions
→{{header|Free Pascal}}: inserted iterative counting with optimized isForbidden. 500,000,000 in 1,4 s @TIO.RUN
Drkameleon (talk | contribs) (added Arturo) |
(→{{header|Free Pascal}}: inserted iterative counting with optimized isForbidden. 500,000,000 in 1,4 s @TIO.RUN) |
||
Line 346:
uses
sysutils,strutils;
function isForbidden(n:NativeUint):boolean;inline;
// no need for power or div Only shr & AND when using Uint
// n > 7 => if n <= 7 -> only 4/0 would div 4 -> no forbidden number
Begin
while (n > 7) AND (n MOD 4 = 0) do
n := n DIV 4;
result := n MOD 8 = 7;
end;
function CntForbiddenTilLimit(lmt:NativeUint):NativeUint;
//
//forNmb = Power4 * 8*j + Power4 * 7
//forNmb = delta* j + n
var
Power4,
begin
result := 0;
power4 := 1;
repeat
delta := Power4*8;// j = 1
n := Power4*7;
if n > lmt then
Break;
//max j to reach limit
inc(result,(lmt-n) DIV delta+1);
Power4 *= 4;
until false;
end;
var
lmt,n,cnt: NativeUint;
BEGIN
writeln('First fifty forbidden numbers:');
n := 1;
lmt :=
repeat;
if isForbidden(n) then
Begin
inc(lmt);
if LMT MOD 20 = 0 THEN
end;
n +=1;
until lmt >= 50;
writeln;
writeln('count of forbidden numbers below iterative');
n := 1;
cnt := 0;
lmt := 5;
repeat
repeat;
//if isForbidden(n) then cnt+=1 takes to long 100% -> 65% of time
▲ inc(n);
inc(cnt,ORD(isForbidden(n)));
writeln(Numb2USA(IntToStr(lmt)):30,Numb2USA(IntToStr(Cnt)):25);
▲ writeln;
lmt
until lmt >
writeln;
▲ writeln;
writeln('count of forbidden numbers below ');
lmt := 5;
repeat
writeln(Numb2USA(IntToStr(lmt)):30,Numb2USA(IntToStr(CntForbiddenTilLimit(lmt))):25);
lmt *= 10;
Line 390 ⟶ 419:
{{out|@TIO.RUN}}
<pre>
First fifty forbidden numbers:
7 15 23 28 31 39 47 55 60 63 71 79 87 92 95 103 111 112 119 124
Line 395 ⟶ 425:
252 255 263 271 279 284 287 295 303 311
count of forbidden numbers below iterative
5 0
50 7
500 82
5,000 831
50,000 8,330
500,000 83,331
5,000,000 833,329
50,000,000 8,333,330
500,000,000 83,333,328
count of forbidden numbers below
5 0
50 7
Line 414 ⟶ 455:
50,000,000,000,000,000 8,333,333,333,333,325
500,000,000,000,000,000 83,333,333,333,333,323
Real time:
=={{header|Python}}==
| |||