Anonymous user
Pan base non-primes: Difference between revisions
→{{header|J}}: append Free Pascal Version
m (→{{header|Phix}}: reverted to the slightly clearer and simpler if/else of Wren) |
(→{{header|J}}: append Free Pascal Version) |
||
Line 66:
100*(+/%#)2|1+I.pbnp 1+i.1e3 NB. percent odd pan based non primes up to 1000
16.9761</lang>
=={{header|Pascal}}==
==={{header|Free Pascal}}===
<lang pascal>
program PanBaseNonPrime;
// Check Pan-Base Non-Prime
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$ENDIF}
{$IFDEF WINDOWS}{$APPTYPE CONSOLE}{$ENDIF}
// MAXLIMIT beyond 10000 gets really slow 5 digits, depends on isPrime
//10004 checked til base 10003 -> 10003⁴+3 = 1.0012e16, takes >1 s longer
//real 0m1,307s
// 9999 checked til base 9998 -> 8,99555E12 much smaller
//real 0m0,260s
type
tDgts = 0..31;// Int32 is faster than 0..9 -> word
tUsedDgts = set of tDgts;
tDecDigits = packed record
decdgts :array[0..20] of byte;
decmaxIdx :byte;
decmaxDgt :byte;
decUsedDgt :tUsedDgts;
end;
const
MAXLIMIT = 2500;
WithGCDNotOne : array[0..24] of tUsedDgts =
//all the same digits
([0],[2],[3],[4],[5],[6],[7],[8],[9],
//all even
[2,4],[2,6],[2,8],
[2,4,6],[2,4,8],[2,6,8],
[2,4,6,8],
[4,6],[4,8],
[4,6,8],[2,4,6,8],
[6,8],
//all divible 3
[3,6],[3,9],
[3,6,9],
[6,9]);
var
gblCnt,
gblOddCnt :NativeINt;
procedure OutDecDigits(var Dgts:tDecDigits);
var
idx : nativeInt;
begin
with Dgts do
begin
idx := decMaxIDx;
repeat
dec(idx);
write(decdgts[idx]);
until idx <= 0;
write(decmaxdgt:3);
writeln;
end;
end;
procedure CountOne(n:NativeInt);inline;
Begin
inc(gblCnt);
If odd(n) then
inc(gblOddCnt);
end;
procedure OutCountOne(n:NativeInt);
begin
CountOne(n);
write(n:5);
if gblCnt mod 10 = 0 then
writeln;
end;
function CheckGCD(var Dgts:tDecDigits):boolean;
var
idx: NativeInt;
UsedDgts:tUsedDgts;
begin
UsedDgts := Dgts.decUsedDgt;
For idx := Low(WithGCDNotOne) to High(WithGCDNotOne) do
if UsedDgts = WithGCDNotOne[idx] then
Exit(true);
Exit(false);
end;
procedure ConvToDecDgt(n : NativeUint;out Dgts:tDecDigits);//inline;
var
dgt,maxdgt,idx,q :NativeInt;
UsedDgts : tUsedDgts;
begin
UsedDgts := [];
maxdgt := 0;
idx := 0;
repeat
q := n div 10;
dgt := n-q*10;
Dgts.decdgts[idx]:= dgt;
include(UsedDgts,dgt);
IF maxdgt<dgt then
maxdgt := dgt;
inc(idx);
n := q;
until n = 0;
with Dgts do
Begin
decMaxIDx := idx;
decMaxdgt := maxDgt;
decUsedDgt := UsedDgts;
end;
end;
function ConvDgtToBase(var Dgts:tDecDigits;base:NativeInt):NativeUInt;
var
idx :NativeInt;
begin
result := 0;
if base<= Dgts.decMaxdgt then
EXIT;
with Dgts do
Begin
idx := decMaxIDx;
repeat
dec(idx);
result := result*base+decdgts[idx];
until idx <= 0;
end;
end;
function isPrime(n: NativeInt):boolean;
//simple trial division
var
j : nativeInt;
begin
if n in [2,3,5,7,11,13,17,19,23,29,31] then
EXIT(true);
if n<32 then
EXIT(false);
if not(odd(n)) then
EXIT(false);
if n mod 3 = 0 then
EXIT(false);
if n mod 5 = 0 then
EXIT(false);
j := 7;
while j*j<=n do
begin
if n mod j = 0 then
EXIT(false);
inc(j,4);
if n mod j = 0 then
EXIT(false);
inc(j,2);
end;
EXIT(true);
end;
function CheckPanBaseNonPrime(n: NativeUint):boolean;
var
myDecDgts:tDecDigits;
b,num : NativeInt;
Begin
result := true;
ConvToDecDgt(n,myDecDgts);
if (n>10) then
Begin
if (myDecDgts.decdgts[0] = 0) then
Exit;
if CheckGCD(myDecDgts) then
Exit;
end;
b := myDecDgts.decmaxdgt+1;
if b >= n then
Begin
if isPrime(n) then
Exit(false);
end
else
begin
while b < n do
begin
num := ConvDgtToBase(myDecDgts,b);
if isPrime(num) then
EXIT(false);
inc(b);
end;
end;
end;
var
i : NativeInt;
BEGIN
writeln('First 50 pan-base non-prime numbers ');
gblCnt := 0;
gblOddCnt := 0;
For i := 3 to MAXLIMIT do
Begin
if CheckPanBaseNonPrime(i) then
OutCountOne(i);
if gblCnt = 50 then
break;
end;
writeln;
writeln('First 20 pan-base non-prime odd numbers ');
gblCnt := 0;
gblOddCnt := 0;
For i := 3 to MAXLIMIT do
Begin
if ODD(i) then
Begin
if CheckPanBaseNonPrime(i) then
OutCountOne(i);
if gblOddCnt = 20 then
break;
end;
end;
writeln;
gblCnt := 0;
gblOddCnt := 0;
For i := 3 to MAXLIMIT do
if CheckPanBaseNonPrime(i) then
CountOne(i);
writeln('Count of pan-base composites up to and including ',MAXLIMIT,' : ',gblCnt);
writeln('odd up to and including ',MAXLIMIT,' = ',gblOddCnt:4,' equals ',gblOddCnt/gblCnt*100:10:6,'%');
writeln('even up to and including ',MAXLIMIT,' = ',gblCnt-gblOddCnt:4,' equals ',(gblCnt-gblOddCnt)/gblCnt*100:10:6,'%');
END.
</lang>
{{out}}
<pre>
First 50 pan-base non-prime numbers
4 6 8 9 20 22 24 26 28 30
33 36 39 40 42 44 46 48 50 55
60 62 63 64 66 68 69 70 77 80
82 84 86 88 90 93 96 99 100 110
112 114 116 118 120 121 130 132 134 136
First 20 pan-base non-prime odd numbers
9 33 39 55 63 69 77 93 99 121
143 165 169 187 231 253 273 275 297 299
Count of pan-base composites up to and including 2500 : 953
odd up to and including 2500 = 161 equals 16.894019%
even up to and including 2500 = 792 equals 83.105981%
</pre>
=={{header|Phix}}==
| |||