Magnanimous numbers: Difference between revisions

Content added Content deleted
(→‎{{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: Line 1,078:
{{works with|Free Pascal}}
{{works with|Free Pascal}}
Version nearly like on Talk.<br>
Version nearly like on Talk.<br>
On TIO.RUN found all til 569 84448000009 1.191 s
On TIO.RUN found all til 569 84448000009 0.773 s
<lang pascal>program Magnanimous;
<lang pascal>program Magnanimous;
//Magnanimous Numbers
//Magnanimous Numbers
Line 1,085: Line 1,085:
//so 1,11,20,101,1001 will not be found
//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
//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}
{$IFDEF FPC}
{$MODE DELPHI}
{$MODE DELPHI}
{$Optimization ON}
{$Optimization ON}
{$CODEALIGN proc=16}
{$CODEALIGN proc=16,loop=4}
{$ELSE}
{$ELSE}
{$APPTYPE CONSOLE}
{$APPTYPE CONSOLE}
Line 1,097: Line 1,095:
uses
uses
//strUtils, // commatize Numb2USA
//strUtils, // commatize Numb2USA
{$IFDEF USE_GMP} gmp,{$ENDIF}
{$IFDEF USE_GMP}gmp,{$ENDIF}
SysUtils;
SysUtils;
const
const
Line 1,109: Line 1,107:


tNumType = NativeUint;
tNumType = NativeUint;
tSplitNum =array[0..15] of tNumType;
tSplitNum = array[0..15] of tNumType;
tMagList = array[0..1000] of Uint64;
tMagList = array[0..1000] of Uint64;
var
var
{$ALIGN 32}
{$ALIGN 32}
dgtBase5,
dgtBase5, // count in Base 5
dgtORMask, //Mark of used digit (or (1 shl Digit ))
dgtEvenBase10,
dgtEvenBase10,
dgtOddBase10: tbase;
dgtOddBase10: tbase;
Line 1,121: Line 1,120:
pPrimes0 : pByte;
pPrimes0 : pByte;
T0: int64;
T0: int64;
HighIdx, cnt,num,MagIdx: NativeUint;
HighIdx, cnt,num,MagIdx,count: NativeUint;


procedure InitPrimes;
procedure InitPrimes;
Line 1,210: Line 1,209:
end;
end;


⚫
function Base10toNum(var dgtBase10: tBase):NativeUint;
⚫
procedure OutBase5;
var
var
pb: tpBaseType;
i : NativeInt;
⚫
i : NativeUint;
begin
begin
write(num:15);
Result := 0;
⚫
pb:= @dgtBase5[0];
for i := HighIdx downto 0 do
for i := HighIdx downto 0 do
write(pB[i]:2);
Result := Result * 10 + dgtBase10[i];
⚫
write(#13);
end;
end;


⚫
procedure OutBase5;
⚫
function Base10toNum(var dgtBase10: tBase):NativeUint;
var
var
i : NativeInt;
pb: tpBaseType;
⚫
i : NativeUint;
begin
begin
Result := 0;
write(count :10);
⚫
pb:= @dgtBase5[0];
for i := HighIdx downto 0 do
for i := HighIdx downto 0 do
Result := Result * 10 + dgtBase10[i];
write(pb[i]:3);
⚫
write(' : ' );
⚫
pb:= @dgtORMask[0];
for i := HighIdx downto 0 do
⚫
write(pb[i]:3);
end;
end;


Line 1,237: Line 1,239:
begin
begin
pDgt := @dgtEvenBase10[0];
pDgt := @dgtEvenBase10[0];
//make all even
for idx := lastIdx downto 1 do
for idx := lastIdx downto 1 do
pDgt[idx] := 2 * dgtBase5[idx];
pDgt[idx] := 2 * dgtBase5[idx];
//but the lowest odd;
pDgt[0] := 2 * dgtBase5[0]+1;
pDgt[0] := 2 * dgtBase5[0]+1;
end;
end;
Line 1,248: Line 1,252:
begin
begin
pDgt := @dgtOddBase10[0];
pDgt := @dgtOddBase10[0];
//make all odd
for idx := lastIdx downto 1 do
for idx := lastIdx downto 1 do
pDgt[idx] := 2 * dgtBase5[idx] + 1;
pDgt[idx] := 2 * dgtBase5[idx] + 1;
//but the lowest even
pDgt[0] := 2 * dgtBase5[0];
pDgt[0] := 2 * dgtBase5[0];
end;
end;
Line 1,261: Line 1,267:
begin
begin
repeat
repeat
⚫
pb:= @dgtBase5[0];
⚫
i := 0;
repeat
repeat
n := pb[i] + 1;
pb:= @dgtBase5[0];
if n < 5 then
i := 0;
⚫
repeat
⚫
n := pb[i] + 1;
if n < 5 then
begin
pb[i] := n;
break;
end;
⚫
pb[i] := 0;
Inc(i);
⚫
until False;
if HighIdx < i then
begin
begin
pb[i] := n;
HighIdx := i;
break;
pb[i] := 0;
end;
end;
⚫
pb[i] := 0;
⚫
Inc(i);
⚫
until False;


if HighIdx < i then
n := dgtORMask[i+1];
begin
while i >= 0 do
HighIdx := i;
begin
pb[i] := 0;
n := n 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
if HighIdx<4 then
break;
break;
n := dgtORMask[1];

⚫
//ending in 5. base10(base5) for odd 1+4(0,2),3+2(1,1),5+0(2,0)
⚫
n := pb[0];
For i := HighIdx downto 1 do
i := pb[0];
//sum ending in 5 -> no prime
if i <= 2 then
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] then
i := 1 shl (2-i);
begin
end
n := -1;
else
BREAK;
Begin
end;
//ending in 5 7+8(3,4),9+6(4,3)
if n >= 0 then
i := 1 shl (4-i);
break;
n := n shr 3;
end;
if (i AND n) = 0 then
BREAK;
until false;
until false;
end;
end;
Line 1,302: Line 1,335:
//1234 -> 1+234,12+34 ;123+4
//1234 -> 1+234,12+34 ;123+4
var
var
LowSplitNum :tSplitNum;
LowSplitNum : tSplitNum;
i,fac,n: NativeInt;
i,fac,n: NativeInt;
isMagn : boolean;
isMagn : boolean;
Begin
Begin
⚫
//writeln(Base10toNum(dgtBase10));
n := 0;
n := 0;
fac := 1;
fac := 1;
Line 1,350: Line 1,382:
MagList[MagIdx] := num;
MagList[MagIdx] := num;
inc(MagIdx);
inc(MagIdx);
//OutBase5;//Not for TIO.RUN
end;
end;
var

LastNum : NativeUint;
BEGIN
BEGIN
{$IFDEF USE_GMP}mpz_init_set_ui(z,0);{$ENDIF}
{$IFDEF USE_GMP}mpz_init_set_ui(z,0);{$ENDIF}
Line 1,375: Line 1,407:


HighIdx := 0;// 7 start with 7 digits
HighIdx := 0;// 7 start with 7 digits
LastNum := 0;
repeat
repeat
if dgtBase5[highIdx] <> 0 then
if dgtBase5[highIdx] <> 0 then
Line 1,381: Line 1,414:
CheckMagn(dgtEvenBase10);
CheckMagn(dgtEvenBase10);
end;
end;
//output for still running every 16.22 Mio
IF count AND (1 shl 24-1) = 0 then
begin
CnvOddBase10(highIdx);
⚫
writeln(Base10toNum(dgtOddBase10):22,
(Gettickcount64-T0) / 1000: 10: 3, ' s');
end;

CnvOddBase10(highIdx);
CnvOddBase10(highIdx);
CheckMagn(dgtOddBase10);
CheckMagn(dgtOddBase10);

inc(count);
IncDgtBase5;
IncDgtBase5;
CnvEvenBase10(highIdx);

until HighIdx > MAXHIGHIDX;
until HighIdx > MAXHIGHIDX;
writeln;
writeln;
InsertSort(@MagList[0],0,MagIdx-1);
InsertSort(@MagList[0],0,MagIdx-1);

{$IFDEF USE_GMP} mpz_clear(z);writeln('Count of gmp tests ',gmp_count);{$ENDIF}
{$IFDEF USE_GMP} mpz_clear(z);writeln('Count of gmp tests ',gmp_count);{$ENDIF}
For cnt := 0 to MagIdx-1 do
For cnt := 0 to MagIdx-1 do
Line 1,401: Line 1,447:
<pre style="height:180px">
<pre style="height:180px">
TIO.RUN
TIO.RUN
getting primes 0.024 s
getting primes 0.022 s
0 0.000 s


Count of gmp tests 45755
Count of gmp tests 45755
Line 1,973: Line 2,020:
568 46884486265
568 46884486265
569 84448000009
569 84448000009
1.191 s
0.773 s
⚫
//Real time: 0.964 s User time: 0.914 s Sys. time: 0.045 s CPU share: 99.45 %

⚫
Real time: 1.411 s User time: 1.341 s Sys. time: 0.061 s CPU share: 99.40 %
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Magnanimous_numbers"