Anonymous user
Magnanimous numbers: Difference between revisions
m
→{{header|Pascal}}: reordered
m (→{{header|Pascal}}: check for ending in 5 improved.At home AMD 2200G finds 571 in 49s instead 78s before.) |
m (→{{header|Pascal}}: reordered) |
||
Line 1,078:
{{works with|Free Pascal}}
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.715 s
<lang pascal>program Magnanimous;
//Magnanimous Numbers
Line 1,088 ⟶ 1,089:
{$MODE DELPHI}
{$Optimization ON}
{$CODEALIGN proc=16
{$ELSE}
{$APPTYPE CONSOLE}
Line 1,102 ⟶ 1,103:
type
tprimes = array of byte;
tBaseType =
tpBaseType = pByte;
tBase =array[0..15] of tBaseType;
tNumType = NativeUint;
tSplitNum = array[0..15] of tNumType;
tMagList = array[0..
var
{$ALIGN 32}
MagList : tMagList;
dgtBase5, // count in Base 5
dgtORMask, //Mark of used digit (or (1 shl Digit ))
dgtEvenBase10,
dgtOddBase10: tbase;
primes : tprimes;
{$IFDEF USE_GMP} z : mpz_t;gmp_count :NativeUint;{$ENDIF}
pPrimes0 : pByte;
T0: int64;
HighIdx
procedure InitPrimes;
Line 1,207 ⟶ 1,209:
pMag[j+1]:= pivot;
end;
end;
Line 1,231 ⟶ 1,224:
for i := HighIdx downto 0 do
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;
Line 1,239 ⟶ 1,247:
begin
pDgt := @dgtEvenBase10[0];
for idx := lastIdx downto 1 do
pDgt[idx] := 2 * dgtBase5[idx];
pDgt[0] := 2 * dgtBase5[0]+1;
end;
Line 1,259 ⟶ 1,265:
end;
// increment n base 5 until resulting sum of split number
// can't end in 5
Line 1,266 ⟶ 1,272:
n,i: nativeint;
begin
result := 0;
repeat
repeat
//increment Base5
pb:= @dgtBase5[0];
i := 0;
Line 1,280 ⟶ 1,288:
Inc(i);
until False;
if HighIdx < i then
begin
Line 1,285 ⟶ 1,294:
pb[i] := 0;
end;
if result < i then
result := i;
n := dgtORMask[i+1];
Line 1,295 ⟶ 1,307:
dec(i);
end;
if HighIdx<4 then
break;
if (n <> 31) OR (i=0) then
break;
//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
//so going on with a number that will change the used below i to highest digit
Line 1,308 ⟶ 1,323:
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)
Line 1,370 ⟶ 1,386:
if n >MAXLIMIT then
Begin
// IF NOT((n mod 30) in [1,7,11,13,17,19,23,29]) then EXIT;
mpz_set_ui(z,n);
gmp_count +=1;
Line 1,377 ⟶ 1,394:
end;
end;
{$ENDIF}
//insert magnanimous numbers
Line 1,383 ⟶ 1,401:
inc(MagIdx);
end;
function Run(StartDgtCount:byte):Uint64;
var
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
{$IFDEF USE_GMP}mpz_init_set_ui(z,0);{$ENDIF}
Line 1,406 ⟶ 1,448:
{$IFDEF USE_GMP} mpz_init_set_ui(z,0);{$ENDIF}
count := Run(0);
writeln;
CnvOddBase10(highIdx);
writeln(MagIdx:5,count:12,Base10toNum(dgtOddBase10):18,
(Gettickcount64-T0) / 1000: 10: 3, ' s');
InsertSort(@MagList[0],0,MagIdx-1);
Line 1,436 ⟶ 1,459:
For cnt := 0 to MagIdx-1 do
writeln(cnt+1:3,' ',MagList[cnt]);
{$IFDEF WINDOWS}
readln;
{$ENDIF}
end.</lang>
{{out}}
<pre style="height:180px">
TIO.RUN
Real time: 0.924 s User time: 0.864 s Sys. time: 0.053 s CPU share: 99.29 %
getting primes 0.023 s
567 4194304 53771777176 0.400 s
569 6990860 111111111110 0.715 s
Count of gmp tests 45755
1 0
Line 2,020 ⟶ 2,042:
568 46884486265
569 84448000009
</pre>
|