Magnanimous numbers: Difference between revisions

Content added Content deleted
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>
Eliminating all numbers, which would sum to 5 in the last digit.<br>
On TIO.RUN found all til 569 84448000009 0.773 s
On TIO.RUN found all til 569 84448000009 0.715 s
<lang pascal>program Magnanimous;
<lang pascal>program Magnanimous;
//Magnanimous Numbers
//Magnanimous Numbers
Line 1,088: Line 1,089:
{$MODE DELPHI}
{$MODE DELPHI}
{$Optimization ON}
{$Optimization ON}
{$CODEALIGN proc=16,loop=4}
{$CODEALIGN proc=16}
{$ELSE}
{$ELSE}
{$APPTYPE CONSOLE}
{$APPTYPE CONSOLE}
Line 1,102: Line 1,103:
type
type
tprimes = array of byte;
tprimes = array of byte;
tBaseType = byte;
tBaseType = Byte;
tpBaseType = pByte;
tpBaseType = pByte;
tBase =array[0..15] of tBaseType;
tBase =array[0..15] of tBaseType;

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..1023] of Uint64;
var
var
{$ALIGN 32}
{$ALIGN 32}
MagList : tMagList;

dgtBase5, // count in Base 5
dgtBase5, // count in Base 5
dgtORMask, //Mark of used digit (or (1 shl Digit ))
dgtORMask, //Mark of used digit (or (1 shl Digit ))
dgtEvenBase10,
dgtEvenBase10,
dgtOddBase10: tbase;
dgtOddBase10: tbase;

MagList : tMagList;
primes : tprimes;
primes : tprimes;
{$IFDEF USE_GMP} z : mpz_t;gmp_count :NativeUint;{$ENDIF}
{$IFDEF USE_GMP} z : mpz_t;gmp_count :NativeUint;{$ENDIF}
pPrimes0 : pByte;
pPrimes0 : pByte;
T0: int64;
T0: int64;
HighIdx, cnt,num,MagIdx,count: NativeUint;
HighIdx,num,MagIdx,count,cnt: NativeUint;


procedure InitPrimes;
procedure InitPrimes;
Line 1,207: Line 1,209:
pMag[j+1]:= pivot;
pMag[j+1]:= pivot;
end;
end;
end;

function Base10toNum(var dgtBase10: tBase):NativeUint;
var
i : NativeInt;
begin
Result := 0;
for i := HighIdx downto 0 do
Result := Result * 10 + dgtBase10[i];
end;
end;


Line 1,231: Line 1,224:
for i := HighIdx downto 0 do
for i := HighIdx downto 0 do
write(pb[i]:3);
write(pb[i]:3);
end;

function Base10toNum(var dgtBase10: tBase):NativeUint;
var
i : NativeInt;
begin
Result := 0;
for i := HighIdx downto 0 do
Result := Result * 10 + dgtBase10[i];
end;

procedure OutSol(cnt:Uint64);
begin
writeln(MagIdx:4,cnt:13,Base10toNum(dgtOddBase10):20,
(Gettickcount64-T0) / 1000: 10: 3, ' s');
end;
end;


Line 1,239: Line 1,247:
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,259: Line 1,265:
end;
end;


procedure IncDgtBase5;
function IncDgtBase5:NativeUint;
// increment n base 5 until resulting sum of split number
// increment n base 5 until resulting sum of split number
// can't end in 5
// can't end in 5
Line 1,266: Line 1,272:
n,i: nativeint;
n,i: nativeint;
begin
begin
result := 0;
repeat
repeat
repeat
repeat
//increment Base5
pb:= @dgtBase5[0];
pb:= @dgtBase5[0];
i := 0;
i := 0;
Line 1,280: Line 1,288:
Inc(i);
Inc(i);
until False;
until False;

if HighIdx < i then
if HighIdx < i then
begin
begin
Line 1,285: Line 1,294:
pb[i] := 0;
pb[i] := 0;
end;
end;

if result < i then
result := i;


n := dgtORMask[i+1];
n := dgtORMask[i+1];
Line 1,295: Line 1,307:
dec(i);
dec(i);
end;
end;

if HighIdx<4 then
break;


if (n <> 31) OR (i=0) then
if (n <> 31) OR (i=0) then
break;
break;
//Now there are all digits are used at digit i
//Now there are all digits are used at digit i ( not in last pos)
//this will always lead to a number ending in 5-> not prime
//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
//so going on with a number that will change the used below i to highest digit
Line 1,308: Line 1,323:
dec(i);
dec(i);
until i < 0;
until i < 0;
until false;


until false;
if HighIdx<4 then
if HighIdx<4 then
break;
break;

n := dgtORMask[1];
n := dgtORMask[1];
//ending in 5. base10(base5) for odd 1+4(0,2),3+2(1,1),5+0(2,0)
//ending in 5. base10(base5) for odd 1+4(0,2),3+2(1,1),5+0(2,0)
Line 1,370: Line 1,386:
if n >MAXLIMIT then
if n >MAXLIMIT then
Begin
Begin
// IF NOT((n mod 30) in [1,7,11,13,17,19,23,29]) then EXIT;
mpz_set_ui(z,n);
mpz_set_ui(z,n);
gmp_count +=1;
gmp_count +=1;
Line 1,377: Line 1,394:
end;
end;
end;
end;

{$ENDIF}
{$ENDIF}
//insert magnanimous numbers
//insert magnanimous numbers
Line 1,383: Line 1,401:
inc(MagIdx);
inc(MagIdx);
end;
end;

function Run(StartDgtCount:byte):Uint64;
var
var
LastNum : NativeUint;
lastIdx: NativeInt;
begin
result := 0;
HighIdx := StartDgtCount;// 7 start with 7 digits
LastIdx := HighIdx;
repeat
if dgtBase5[HighIdx] <> 0 then
Begin
CnvEvenBase10(LastIdx);
CheckMagn(dgtEvenBase10);
end;
CnvOddBase10(LastIdx);
CheckMagn(dgtOddBase10);
inc(result);
//output for still running every 16.22 Mio
IF result AND (1 shl 22-1) = 0 then
OutSol(result);

lastIdx := IncDgtBase5;
until HighIdx > MAXHIGHIDX;

end;

BEGIN
BEGIN
{$IFDEF USE_GMP}mpz_init_set_ui(z,0);{$ENDIF}
{$IFDEF USE_GMP}mpz_init_set_ui(z,0);{$ENDIF}
Line 1,406: Line 1,448:
{$IFDEF USE_GMP} mpz_init_set_ui(z,0);{$ENDIF}
{$IFDEF USE_GMP} mpz_init_set_ui(z,0);{$ENDIF}


count := Run(0);
HighIdx := 0;// 7 start with 7 digits
LastNum := 0;
repeat
if dgtBase5[highIdx] <> 0 then
Begin
CnvEvenBase10(highIdx);
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(dgtOddBase10):22,
(Gettickcount64-T0) / 1000: 10: 3, ' s');
end;


CnvOddBase10(highIdx);
CheckMagn(dgtOddBase10);

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

until HighIdx > MAXHIGHIDX;
writeln;
writeln;
CnvOddBase10(highIdx);
writeln(MagIdx:5,count:12,Base10toNum(dgtOddBase10):18,
(Gettickcount64-T0) / 1000: 10: 3, ' s');
InsertSort(@MagList[0],0,MagIdx-1);
InsertSort(@MagList[0],0,MagIdx-1);


Line 1,436: Line 1,459:
For cnt := 0 to MagIdx-1 do
For cnt := 0 to MagIdx-1 do
writeln(cnt+1:3,' ',MagList[cnt]);
writeln(cnt+1:3,' ',MagList[cnt]);

T0 -= Gettickcount64;
writeln(-T0 / 1000: 0: 3, ' s');
{$IFDEF WINDOWS}
{$IFDEF WINDOWS}
readln;
readln;
{$ENDIF}
{$ENDIF}
end.
end.</lang>
</lang>
{{out}}
{{out}}
<pre style="height:180px">
<pre style="height:180px">
TIO.RUN
TIO.RUN
Real time: 0.924 s User time: 0.864 s Sys. time: 0.053 s CPU share: 99.29 %
getting primes 0.022 s

0 0.000 s
getting primes 0.023 s
567 4194304 53771777176 0.400 s


569 6990860 111111111110 0.715 s
Count of gmp tests 45755
Count of gmp tests 45755
1 0
1 0
Line 2,020: Line 2,042:
568 46884486265
568 46884486265
569 84448000009
569 84448000009
0.773 s
//Real time: 0.964 s User time: 0.914 s Sys. time: 0.045 s CPU share: 99.45 %
</pre>
</pre>


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