Primes whose sum of digits is 25: Difference between revisions

Content added Content deleted
(Realize in F#)
(→‎{{header|Pascal}}: reduced count of generated numbers for testing,move 1,3,7,9 and permute digits in front)
Line 1,055: Line 1,055:


=={{header|Pascal}}==
=={{header|Pascal}}==
added only strechted goal.Generating the combination of the digits for the numbers and afterwards generating the [[Permutations with some identical elements]]
added only strechted goal.Generating the combination of the digits for the numbers and afterwards generating the [[Permutations with some identical elements]]<BR>
Now seting one digit out of 1,3,7,9 to the end and permute the rest of the digits in front.<BR>So much less numbers have to be tested.10.5e6 instead of 16.4e6.Generating of the numbers is reduced in the same ratio.
<BR>Same count of generated numbers as in [[go]] .Runtime for only generating the numbers reduced from 5.8s to 0.4s<BR>
I don't know why the gmp test is so much faster and why there is one more probably prime<BR>
Added sum to n*9 => no primes ;-)
<lang pascal>program Perm5aus8;
<lang pascal>program Perm5aus8;
//formerly roborally take 5 cards out of 8
//formerly roborally take 5 cards out of 8
Line 1,071: Line 1,069:
gmp;
gmp;
const
const
cTotalSum = 63;
cTotalSum = 31;


cMaxCardsOnDeck = cTotalSum;//8
cMaxCardsOnDeck = cTotalSum;//8
Line 1,083: Line 1,081:


tSetElem = record
tSetElem = record
Elem : tDiffCardCount;
Elemcount : tDeckIndex;
Elemcount : tDeckIndex;
Elem : tDiffCardCount;
end;
end;


tSet = record
tSet = record
RemSet : array [low(tDiffCardCount)..High(tDiffCardCount)] of tSetElem;
RemSet : array [low(tDiffCardCount)..High(tDiffCardCount)] of tSetElem;
MaxUsedIdx,
MaxUsedIdx,
TotElemCnt : word;
TotElemCnt : byte;
end;
end;


tRemainSet = array [low(tSequenceIndex)..High(tSequenceIndex)+1] of tSet;
tRemainSet = array [low(tSequenceIndex)..High(tSequenceIndex)+1] of tSet;


tCardSequence = array [low(tSequenceIndex)..High(tSequenceIndex)] of tDiffCardCount;
tCardSequence = array [low(tSequenceIndex)..High(tSequenceIndex)] of tDiffCardCount;
tPermRec = packed record
permTiefe : byte;// Stelle der Änderung gegenüber Vorgängerpermutation
permCardSequence :tCardSequence ;
end;


var
var
ManifoldOfDigit : array[tDiffCardCount] of Byte;
TotalUsedDigits : array[tDeckIndex] of Byte;
RemainSets : tRemainSet;
RemainSets : tRemainSet;

TotalUsedDigits : array[tDeckIndex] of Int32;
ManifoldOfDigit : array[tDiffCardCount] of Int32;
CardSequence : tCardSequence;
CardString : AnsiString;
CardString : AnsiString;


PrimeCount : integer;
Count: NativeInt;
PermCount : integer;
PermCount : integer;
mindepth : integer;


//*****************************************************************************
//*****************************************************************************
var
procedure SetInit(var ioMenge:tSet);
CS : pchar;
z : mpz_t;

procedure SetInit(var ioSet:tSet);
var
var
i : integer;
i : integer;
begin
begin
with ioMenge do
with ioSet do
begin
begin
MaxUsedIdx := 0;
MaxUsedIdx := 0;
Line 1,129: Line 1,126:
end;
end;


procedure CheckPrime(LastDigit:NativeInt);
procedure CheckPrime;inline;
var
z : mpz_t;
begin
begin
mpz_set_str(z,CS,10);
if Lastdigit in [1,3,7,9] then
inc(PrimeCount,ORD(mpz_probab_prime_p(z,3)>0));
Begin
mpz_init_set_str(z,pChar(@CardString[1]),10);
if mpz_probab_prime_p(z,1)>0 then
inc(count);
mpz_clear(z);
end;
end;
end;


procedure Permute(depth,MaxCardsUsed:NativeInt);
procedure Permute(depth,MaxCardsUsed:NativeInt);
var
var
pMengeElem : ^tSetElem;
pSetElem : ^tSetElem;
i : NativeInt;
i : NativeInt;
begin
begin
i := 0;
i := 0;
pMengeElem := @RemainSets[depth].RemSet[i];
pSetElem := @RemainSets[depth].RemSet[i];
repeat
repeat
if pMengeElem^.Elemcount <> 0 then begin
if pSetElem^.Elemcount <> 0 then begin
//take one of the same elements of the stack
//take one of the same elements of the stack
//insert in result here string
dec(pMengeElem^.ElemCount);
CS[depth] := chr(pSetElem^.Elem+Ord('0'));
//insert in result here string too
CardSequence[depth] := pMengeElem^.Elem;
CardString[depth+1] := chr(pMengeElem^.Elem+Ord('0'));

//done one permutation
//done one permutation
IF depth = MaxCardsUsed then
IF depth = MaxCardsUsed then
begin
begin
inc(permCount);
inc(permCount);
//writeln(CardString);
CheckPrime;
// ###########
CheckPrime(CardSequence[depth]);
// ###########
mindepth := depth;
end
end
else
else
begin
begin
dec(pSetElem^.ElemCount);
RemainSets[depth+1]:= RemainSets[depth];
RemainSets[depth+1]:= RemainSets[depth];
Permute(depth+1,MaxCardsUsed);
Permute(depth+1,MaxCardsUsed);
//re-insert that element
//re-insert that element
inc(pMengeElem^.ElemCount);
inc(pSetElem^.ElemCount);
dec(minDepth);
end;
end;
end;
end;
//move on to the next digit
//move on to the next digit
inc(pMengeElem);
inc(pSetElem);
inc(i);
inc(i);
until i >=RemainSets[depth].MaxUsedIdx;
until i >=RemainSets[depth].MaxUsedIdx;
Line 1,208: Line 1,191:
TotElemCnt := dgtCnt;
TotElemCnt := dgtCnt;
MaxUsedIdx := dgtIdx;
MaxUsedIdx := dgtIdx;

CS := @CardString[1];
//Check only useful end-digits
For i := 0 to dgtIdx-1 do
Begin
if RemSet[i].Elem in[1,3,7,9]then
Begin
CS[dgtCnt-1] := chr(RemSet[i].Elem+Ord('0'));
CS[dgtCnt] := #00;

dec(RemSet[i].ElemCount);
permute(0,dgtCnt-2);
inc(RemSet[i].ElemCount);
end;
end;
end;
end;
setlength(CardString,dgtCnt);
permute(0,dgtCnt-1);
end;
end;


Line 1,226: Line 1,222:
Begin
Begin
Check(n);
Check(n);
//n is 0 based count combinations of length n
//n is 0 based PrimeCount combinations of length n
inc(TotalUsedDigits[n+1]);
inc(TotalUsedDigits[n+1]);
end;
end;
Line 1,237: Line 1,233:
i :NativeInt;
i :NativeInt;
begin
begin
setlength(CardString,SumGoal);
IF sumGoal>cTotalSum then
IF sumGoal>cTotalSum then
EXIT;
EXIT;
permcount:=0;
fillchar(ManifoldOfDigit[0],SizeOf(ManifoldOfDigit),#0);
fillchar(ManifoldOfDigit[0],SizeOf(ManifoldOfDigit),#0);
count := 0;
permcount:=0;
PrimeCount := 0;

For i := 1 to 9 do
For i := 1 to 9 do
AppendToSum(0,i,SumGoal-i);
AppendToSum(0,i,SumGoal-i);

writeln('Count of generated numbers with digits sum of ',SumGoal,' are ',permcount);
writeln('PrimeCount of generated numbers with digits sum of ',SumGoal,' are ',permcount);
writeln('Propably primes ',count);
writeln('Propably primes ',PrimeCount);
writeln;
writeln;
end;
end;
var
var
GoalSum: 0..cTotalSum;
T1,T0 : Int64;
SumGoal: NativeInt;
BEGIN
BEGIN
writeln('GMP-Version ',gmp.version);
CheckAll(25);
CheckAll(1*9);
mpz_init_set_ui(z,0);
T0 := GetTickCount64;
CheckAll(2*9);
For SumGoal := 25 to 25 do
CheckAll(3*9);
Begin
END.</lang>
CheckAll(SumGoal);
T1 := GetTickCount64;Writeln((T1-T0)/1000:7:3,' s');
T0 := T1;
end;
mpz_clear(z);
END.
</lang>
{{out}}
{{out}}
<pre>
<pre>
//Runnning on TIO.RUN
Count of generated numbers with digits sum of 25 are 16499120
GMP-Version 6.1.2
Propably primes 1525142 //only this real 0m6,880s
PrimeCount of generated numbers with digits sum of 25 are 10488498

Propably primes 1525141
Count of generated numbers with digits sum of 9 are 256
Propably primes 0

Count of generated numbers with digits sum of 18 are 129792
Propably primes 0

Count of generated numbers with digits sum of 27 are 65866496
Propably primes 0


9.932 s
real 0m13,137s
....
Free Pascal Compiler version 3.0.4 [2018/07/13] for x86_64
Copyright (c) 1993-2017 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling .code.tio.pp
Linking .bin.tio
/usr/bin/ld: warning: link.res contains output sections; did you forget -T?
204 lines compiled, 0.2 sec


Real time: 10.135 s
// without testing for prime real 0m2,590s </pre>
User time: 10.027 s
Sys. time: 0.052 s
CPU share: 99.45 %
Exit code: 0
</pre>


=={{header|Perl}}==
=={{header|Perl}}==
Retrieved from "https://rosettacode.org/wiki/Primes_whose_sum_of_digits_is_25"