Rosetta Code

Magnanimous numbers: Difference between revisions

Page Discussion

Magnanimous numbers (view source)

Revision as of 15:17, 4 October 2021

224 bytes added ,  2 years ago
→‎{{header|Pascal}}: Inc in base 5 so long, until no sum of splitted number ends in 5 (10x speedup )
(→‎{{header|Pascal}}: using gmp for numbers >MAXLIMIT improves speed enormous)
(→‎{{header|Pascal}}: Inc in base 5 so long, until no sum of splitted number ends in 5 (10x speedup ))
Line 1,077:
=={{header|Pascal}}==
{{works with|Free Pascal}}
Version nearly like on Talk. Generating the sieve for primes takes most of the time.<br>
On TIO.RUN found all til 569 84448000009 in 191.171191 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}
Line 1,098 ⟶ 1,100:
SysUtils;
const
MaxLimit = 10010*1000*1000 +10;// 1e8 == MAXHIGHIDX = 7
MAXHIGHIDX = 1110;
type
tprimes = array of byte;
tBaseType = wordbyte;
tpBaseType = pWordpByte;
tBase =array[0..3115] of tBaseType;
 
tNumType = NativeUint;
Line 1,119 ⟶ 1,121:
pPrimes0 : pByte;
T0: int64;
HighIdx,lstIdx, cnt,num,MagIdx: NativeUint;
 
procedure InsertSort(pMag:pUint64; Left, Right : NativeInt );
var
I, J: NativeInt;
Pivot : Uint64;
begin
for i:= 1 + Left to Right do
begin
Pivot:= pMag[i];
j:= i - 1;
while (j >= Left) and (pMag[j] > Pivot) do
begin
pMag[j+1]:=pMag[j];
Dec(j);
end;
pMag[j+1]:= pivot;
end;
end;
 
function isprime(n: NativeUint):boolean;
var
k,flipflop: NativeUint;
Begin
if Not(odd(n)) then
EXIT(false);
if n mod 3 = 0 then
EXIT(false);
k := 5;
flipflop := 2;
while k*k<=n do
Begin
if n mod k = 0 then
EXIT(false);
inc(k,flipflop);
flipflop := 6-flipflop;
end;
EXIT(true);
end;
 
procedure InitPrimes;
Line 1,226 ⟶ 1,190:
 
pPrimes0 := pPrimes;
end;
 
procedure InsertSort(pMag:pUint64; Left, Right : NativeInt );
var
I, J: NativeInt;
Pivot : Uint64;
begin
for i:= 1 + Left to Right do
begin
Pivot:= pMag[i];
j:= i - 1;
while (j >= Left) and (pMag[j] > Pivot) do
begin
pMag[j+1]:=pMag[j];
Dec(j);
end;
pMag[j+1]:= pivot;
end;
end;
 
Line 1,233 ⟶ 1,215:
i : NativeUint;
begin
pb:= @dgtBase5[0];
write(num:15);
pb:= @dgtBase5[0];
for i := HighIdx downto 0 do
write(pB[i]:2);
Line 1,240 ⟶ 1,222:
end;
 
function IncDgtBase5Base10toNum(var dgtBase10:nativeUint tBase):NativeUint;
var
pbi : tpBaseTypeNativeInt;
num: nativeint;
begin
pbResult := @dgtBase5[0];
resultfor i := HighIdx downto 0; do
Result := Result * 10 + dgtBase10[i];
repeat
num := pb[result] + 1;
if num < 5 then
begin
pb[result] := num;
break;
end;
pb[result] := 0;
Inc(result);
until False;
if HighIdx < result then
begin
HighIdx := result;
pb[result] := 0;
end;
end;
 
Line 1,286 ⟶ 1,253:
end;
 
procedure IncDgtBase5;
function Base10toNum(var dgtBase10: tBase):NativeUint;
// increment n base 5 until resulting sum of split number
// can't end in 5
var
i pb: NativeInttpBaseType;
n,i: nativeint;
begin
Result := 0;repeat
for i pb:= HighIdx downto @dgtBase5[0 do];
Resulti := Result * 10 + dgtBase10[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
HighIdx := i;
pb[i] := 0;
end;
 
if HighIdx<4 then
break;
 
n := pb[0];
For i := HighIdx downto 1 do
//sum ending in 5 -> no prime
//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
begin
n := -1;
BREAK;
end;
if n >= 0 then
break;
until false;
end;
 
Line 1,304 ⟶ 1,306:
isMagn : boolean;
Begin
//writeln(Base10toNum(dgtBase10));
n := 0;
fac := 1;
Line 1,322 ⟶ 1,325:
n := n*10+dgtBase10[fac-i];
LowSplitNum[i] += n;
//test if not isMagn as soon as possible
if LowSplitNum[i]<=MAXLIMIT then
begin
Line 1,348 ⟶ 1,350:
MagList[MagIdx] := num;
inc(MagIdx);
//OutBase5;//Not for TIO.RUN
end;
 
Line 1,368 ⟶ 1,370:
MagList[MagIdx] := 101;inc(MagIdx);
MagList[MagIdx] := 1001;inc(MagIdx);
//cant be checked easy for ending in 5
 
MagList[MagIdx] := 40001;inc(MagIdx);
{$IFDEF USE_GMP} mpz_init_set_ui(z,0);{$ENDIF}
 
HighIdx := 0;// 7 start with 7 digits
lstIdx := 0;
repeat
if dgtBase5[highIdx] <> 0 then
beginBegin
CnvEvenBase10(lstIdxhighIdx);
CheckMagn(dgtEvenBase10);
end;
CnvOddBase10(lstIdxhighIdx);
CheckMagn(dgtOddBase10);
lstIdx := IncDgtBase5;
until HighIdx > MAXHIGHIDX;
writeln;
Line 1,399 ⟶ 1,401:
<pre style="height:180px">
TIO.RUN
getting primes 0.311024 s
 
Count of gmp tests 10206145755
1 0
2 1
Line 1,971 ⟶ 1,973:
568 46884486265
569 84448000009
191.171191 s
 
Real time: 191.793411 s User time: 191.520341 s Sys. time: 0.095061 s CPU share: 99.0940 %</pre>
</pre>
 
=={{header|Perl}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/299268"