Magnanimous numbers: Difference between revisions

m
→‎{{header|Pascal}}: check for ending in 5 improved.At home AMD 2200G finds 571 in 49s instead 78s before.
(→‎{{header|Pascal}}: Inc in base 5 so long, until no sum of splitted number ends in 5 (10x speedup ))
m (→‎{{header|Pascal}}: check for ending in 5 improved.At home AMD 2200G finds 571 in 49s instead 78s before.)
Line 1,078:
{{works with|Free Pascal}}
Version nearly like on Talk.<br>
On TIO.RUN found all til 569 84448000009 10.191773 s
<lang pascal>program Magnanimous;
//Magnanimous Numbers
Line 1,085:
//so 1,11,20,101,1001 will not be found
//starting at 100001 "1>"+x"0"+"1" is not prime because of 1001 not prime
//To keep it simple and fast insert special case 40001,
//which would be thrown out in IncBase5 because 4+1 sum to 5 not ending in 5.
{$IFDEF FPC}
{$MODE DELPHI}
{$Optimization ON}
{$CODEALIGN proc=16,loop=4}
{$ELSE}
{$APPTYPE CONSOLE}
Line 1,097 ⟶ 1,095:
uses
//strUtils, // commatize Numb2USA
{$IFDEF USE_GMP} gmp,{$ENDIF}
SysUtils;
const
Line 1,109 ⟶ 1,107:
 
tNumType = NativeUint;
tSplitNum = array[0..15] of tNumType;
tMagList = array[0..1000] of Uint64;
var
{$ALIGN 32}
dgtBase5, // count in Base 5
dgtORMask, //Mark of used digit (or (1 shl Digit ))
dgtEvenBase10,
dgtOddBase10: tbase;
Line 1,121 ⟶ 1,120:
pPrimes0 : pByte;
T0: int64;
HighIdx, cnt,num,MagIdx,count: NativeUint;
 
procedure InitPrimes;
Line 1,210 ⟶ 1,209:
end;
 
function Base10toNum(var dgtBase10: tBase):NativeUint;
procedure OutBase5;
var
pbi : tpBaseTypeNativeInt;
i : NativeUint;
begin
write(numResult :15)= 0;
pb:= @dgtBase5[0];
for i := HighIdx downto 0 do
write(pBResult := Result * 10 + dgtBase10[i]:2);
write(#13);
end;
 
procedure OutBase5;
function Base10toNum(var dgtBase10: tBase):NativeUint;
var
i pb: NativeInttpBaseType;
i : NativeUint;
begin
Resultwrite(count := 010);
pb:= @dgtBase5[0];
for i := HighIdx downto 0 do
Result := Result * 10 + dgtBase10write(pb[i]:3);
write(#13' : ' );
pb:= @dgtBase5dgtORMask[0];
for i := HighIdx downto 0 do
write(pb[i] := 03);
end;
 
Line 1,237 ⟶ 1,239:
begin
pDgt := @dgtEvenBase10[0];
//make all even
for idx := lastIdx downto 1 do
pDgt[idx] := 2 * dgtBase5[idx];
//but the lowest odd;
pDgt[0] := 2 * dgtBase5[0]+1;
end;
Line 1,248 ⟶ 1,252:
begin
pDgt := @dgtOddBase10[0];
//make all odd
for idx := lastIdx downto 1 do
pDgt[idx] := 2 * dgtBase5[idx] + 1;
//but the lowest even
pDgt[0] := 2 * dgtBase5[0];
end;
Line 1,261 ⟶ 1,267:
begin
repeat
pb:= @dgtBase5[0];
i := 0;
repeat
n pb:= pb@dgtBase5[i0] + 1;
if ni <:= 5 then0;
Inc(i);repeat
n := pb[0i] + 1;
if n < 5 then
begin
pb[i] := n;
break;
end;
pb[i] := 0;
Inc(i);
until False;
if HighIdx < i then
begin
pb[i]HighIdx := ni;
breakpb[i] := 0;
end;
pb[i] := 0;
Inc(i);
until False;
 
if HighIdx <n i:= thendgtORMask[i+1];
begin while i >= 0 do
HighIdx := i;begin
pb[i] n := 0n OR (1 shl pb[i]);
end dgtORMask[i]:= n;
if n = 31 then
break;
dec(i);
end;
 
if (n <> 31) OR (i=0) then
break;
//Now there are all digits are used at digit i
//this will always lead to a number ending in 5-> not prime
//so going on with a number that will change the used below i to highest digit
//to create an overflow of the next number, to change the digits
dec(i);
repeat
pb[i] := 4;
dgtORMask[i]:= 31;
dec(i);
until i < 0;
until false;
 
if HighIdx<4 then
break;
n := dgtORMask[1];
 
//ending in 5. base10(base5) //for odd 1+4(0,2),3+2(1,1),5+0(2,0),7+8(3,4),9+6(4,3)
n := pb[0];
For i := HighIdx downto 1 dopb[0];
if i //sum<= ending2 in 5 -> no primethen
begin
//for odd 1+4(0,2),3+2(1,1),5+0(2,0),7+8(3,4),9+6(4,3)
if n+pb[i] in:= [2,7]1 thenshl (2-i);
beginend
n := -1;else
BREAK;Begin
end;//ending in 5 7+8(3,4),9+6(4,3)
if n >i := 01 shl then(4-i);
breakn := n shr 3;
end;
if (i AND n) = 0 then
BREAK;
until false;
end;
Line 1,302 ⟶ 1,335:
//1234 -> 1+234,12+34 ;123+4
var
LowSplitNum : tSplitNum;
i,fac,n: NativeInt;
isMagn : boolean;
Begin
//writeln(Base10toNum(dgtBase10));
n := 0;
fac := 1;
Line 1,350 ⟶ 1,382:
MagList[MagIdx] := num;
inc(MagIdx);
//OutBase5;//Not for TIO.RUN
end;
var
 
LastNum : NativeUint;
BEGIN
{$IFDEF USE_GMP}mpz_init_set_ui(z,0);{$ENDIF}
Line 1,375 ⟶ 1,407:
 
HighIdx := 0;// 7 start with 7 digits
LastNum := 0;
repeat
if dgtBase5[highIdx] <> 0 then
Line 1,381 ⟶ 1,414:
CheckMagn(dgtEvenBase10);
end;
//output for still running every 16.22 Mio
IF count AND (1 shl 24-1) = 0 then
begin
CnvOddBase10(highIdx);
// writeln(Base10toNum(dgtBase10dgtOddBase10));:22,
(Gettickcount64-T0) / 1000: 10: 3, ' s');
end;
 
CnvOddBase10(highIdx);
CheckMagn(dgtOddBase10);
 
inc(count);
IncDgtBase5;
CnvEvenBase10(highIdx);
 
until HighIdx > MAXHIGHIDX;
writeln;
InsertSort(@MagList[0],0,MagIdx-1);
 
{$IFDEF USE_GMP} mpz_clear(z);writeln('Count of gmp tests ',gmp_count);{$ENDIF}
For cnt := 0 to MagIdx-1 do
Line 1,401 ⟶ 1,447:
<pre style="height:180px">
TIO.RUN
getting primes 0.024022 s
0 0.000 s
 
Count of gmp tests 45755
Line 1,973 ⟶ 2,020:
568 46884486265
569 84448000009
10.191773 s
//Real time: 10.411964 s User time: 10.341914 s Sys. time: 0.061045 s CPU share: 99.4045 %
 
Real time: 1.411 s User time: 1.341 s Sys. time: 0.061 s CPU share: 99.40 %
</pre>
 
Anonymous user