Find largest left truncatable prime in a given base: Difference between revisions
Find largest left truncatable prime in a given base (view source)
Revision as of 17:43, 29 May 2023
, 1 year ago→{{header|PARI/GP}}: append =={{header|Pascal}}==
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(→{{header|PARI/GP}}: append =={{header|Pascal}}==) |
||
Line 1,380:
Takes half a second to find the terms up to 10, with proofs of primality. The time can be halved without proofs (use <code>ispseudoprime</code> in place of <code>isprime</code>).
<syntaxhighlight lang="parigp">a(n)=my(v=primes(primepi(n-1)),u,t,b=1,best); while(#v, best=vecmax(v); b*=n; u=List(); for(i=1,#v,for(k=1,n-1,if(isprime(t=v[i]+k*b), listput(u,t)))); v=Vec(u)); best</syntaxhighlight>
=={{header|Pascal}}==
==={{header|Free Pascal}}===
Using gmp and depth first search, like by [[Find_largest_left_truncatable_prime_in_a_given_base#Phix|Phix]].<br>Use preset numbers and powers of base to max values expecting that no memory-reallocations during runtime are needed.<br>
HTOP shows no variance in used memory.
<syntaxhighlight lang="pascal">
program TruncatablePrimes;
//https://rosettacode.org/wiki/Find_largest_left_truncatable_prime_in_a_given_base
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$ENDIF}
{$IFDEF Windows}{$APPTYPE CONSOLE}{$ENDIF}
uses
sysutils,gmp;// http://rosettacode.org/wiki/Extensible_prime_generator#Pascal
const
DgtToChar : array[0..10+26+26-1] of char =
'0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
MaxDgtCnt = 50;
var
pot_Base : array[0..MaxDgtCnt] of mpz_t;
Numbers : array[0..MaxDgtCnt] of mpz_t;
MAX_Found : mpz_t;
Digits,
Digits_Found: array[0..MaxDgtCnt] of byte;
gbl_Count,
Max_Pot : Uint32;
procedure InitAll;
var
pot : mpz_t;
MaxBase,
i : integer;
begin
MaxBase := MaxDgtCnt;
mpz_init_set_ui(pot,1);
For i := 0 to High(pot_Base) do
begin
mpz_mul_ui(pot,pot,MaxBase);
mpz_init_set(pot_Base[i],Pot);
mpz_init_set(Numbers[i],Pot);
end;
mpz_init_set(MAX_Found,pot);
mpz_set_ui(MAX_Found,0);
mpz_clear(pot);
end;
procedure ClearAll;
var
i : integer;
begin
For i := High(pot_Base) downto 0 do
begin
mpz_clear(pot_Base[i]);
mpz_clear(Numbers[i]);
end;
mpz_clear(MAX_Found);
end;
procedure InitPot(Base : byte);
var
pot : mpz_t;
i : integer;
begin
mpz_init_set_ui(pot,1);
For i := 0 to High(pot_Base) do
begin
mpz_set(pot_Base[i],Pot);
mpz_mul_ui(pot,pot,base);
end;
mpz_clear(pot);
mpz_set_ui(MAX_Found,0);
Fillchar(Digits,SizeOf(Digits),#0);
end;
procedure Next_Number(Base,pot : byte);
var
i : integer;
begin
inc(gbl_Count);
if pot = 0 then
mpz_set_ui(Numbers[pot],0)
else
mpz_set(Numbers[pot],Numbers[pot-1]);
For i := 1 to Base-1 do
begin
Digits[pot] := i;
mpz_add(Numbers[pot],Numbers[pot],pot_Base[pot]);
if mpz_probab_prime_p(Numbers[pot],5)>0 then
Begin
IF mpz_cmp(MAX_Found,Numbers[pot])<0 then
Begin
mpz_set(Max_Found,Numbers[pot]);
Max_pot := pot;
Digits_Found := Digits;
end;
Next_Number(Base,pot+1);
end;
end;
end;
var
base,i : NativeUint;
sol : pChar;
Begin
GetMem(sol,10000);
InitAll;
try
For base := 3 to 31 do
begin
IF (Base>17) AND Not(Odd(Base)) then
continue;
InitPot(base);
gbl_Count := 0;
write('Base ',base:2,' digits ');
Next_Number(base,0);
write(Max_Pot+1:4,' checks ',gbl_Count:8,' ');
if mpz_fits_ulong_p(Max_Found)<> 0 then
write(mpz_get_ui(Max_Found),' ')
else
Begin
mpz_get_str(Sol,10,Max_Found);
write(Sol,' ');
end;
For i := Max_Pot downto 0 do
write(DgtToChar[Digits_Found[i]]);
writeln;
end;
except
ClearAll;
end;
ClearAll;
FreeMem(sol);
end.
</syntaxhighlight>
{{out|@TIO.RUN}}
<pre>
Base 3 digits 3 checks 4 23 212
Base 4 digits 6 checks 17 4091 333323
Base 5 digits 6 checks 16 7817 222232
Base 6 digits 17 checks 455 4836525320399 14141511414451435
Base 7 digits 7 checks 23 817337 6642623
Base 8 digits 15 checks 447 14005650767869 313636165537775
Base 9 digits 10 checks 109 1676456897 4284484465
Base 10 digits 24 checks 4261 357686312646216567629137 357686312646216567629137
Base 11 digits 9 checks 76 2276005673 A68822827
Base 12 digits 32 checks 170054 13092430647736190817303130065827539 471A34A164259BA16B324AB8A32B7817
Base 13 digits 8 checks 101 812751503 CC4C8C65
Base 14 digits 26 checks 34394 615419590422100474355767356763 D967CCD63388522619883A7D23
Base 15 digits 22 checks 9358 34068645705927662447286191 6C6C2CE2CEEEA4826E642B
Base 16 digits 25 checks 27983 1088303707153521644968345559987 DBC7FBA24FE6AEC462ABF63B3
Base 17 digits 11 checks 363 13563641583101 6C66CC4CC83
Base 19 digits 14 checks 686 546207129080421139 CIEG86GCEA2C6H
Base 21 digits 27 checks 59132 391461911766647707547123429659688417 G8AGG2GCA8CAK4K68GEA4G2K22H
Base 23 digits 17 checks 1373 116516557991412919458949 IMMGM6C6IMCI66A4H
Base 25 digits 20 checks 10485 8211352191239976819943978913 ME6OM6OECGCC24C6EG6D
Base 27 digits 28 checks 98337 10681632250257028944950166363832301357693 O2AKK6EKG844KAIA4MACK6C2ECAB
Base 29 digits 19 checks 3927 4300289072819254369986567661 KCG66AGSCKEIASMCKKJ
Base 31 digits 22 checks 11315 645157007060845985903112107793191 UUAUIKUC4UI6OCECI642SD
Real time: 4.274 s User time: 4.155 s Sys. time: 0.047 s CPU share: 98.32 %</pre>
=={{header|Perl}}==
| |||