Multi Pascal Solver🐞

A sphenic number is a positive integer that is the product of three distinct prime numbers. More technically it’s a square-free 3-almost prime (see Related tasks below).

For the purposes of this task, a sphenic triplet is a group of three sphenic numbers which are consecutive.

I want to show the solution from rosettacode in five language variants:

Pascal
Python
Free Pascal
Free Pascal TIO Web
Delphi

Note that sphenic quadruplets are not possible because every fourth consecutive positive integer is divisible by 4 (= 2 x 2) and its prime factors would not therefore be distinct. Example

30 (= 2 x 3 x 5) is a sphenic number and is also clearly the first one. Lets start with Object Pascal in maXbox5 Editor:

procedure CreateSphenics(const pr: TInt64Array{tarrElements});
var
  i1,i2,i3,
  idx1,idx2,
  p1,p2,pp,cnt : Uint32;
begin
  cnt:= 0;
  pp:= trunc(exp(1/3*ln(LLimit)));
  idx1:= binary_search(pp,Pr)-1;
  i1:= 0;
  writeln('last prime: '+itoa(pr[high(pr)])+' of primes: '+itoa(high(pr)));
  repeat
    p1 := pr[i1];
    pp:= trunc(sqrt(LLimit DIV p1));
    idx2:= binary_search(pp,Pr)+1;
    For i2:= i1+1 to idx2 do begin
      p2:= pr[i2]*p1;
      For i3:= i2+1 to High(pr) do begin
        pp:= Pr[i3]*p2;
        if pp > LLimit then
          break;
        //mark as sphenic number
        PrimeSieve[pp]:= true;    //todo -done
        //primes[pp]:= 1;
        inc(cnt);
      end;
    end;
    inc(i1);
  until i1>idx1;
  //insert
  setlength(sphenics,cnt);
  pp:= 0;
  For i1:= 0 to LLimit do begin
    if primeSieve[i1] then begin
      sphenics[pp]:= i1;
      inc(pp);
    end; 
  end;
  //primeSieve.Free;
end;

Most of the time, ~ 75% in this case, is spent with sort. So i put in maXbox processmessagesOFF; and processmessagesON; between binary search to speed up and Now changed to use sieve of erathostenes and insert sphenic numbers in that array, as you can see dynamic arrays are the main storage:

const
  LLimit= 1000*1000;  // *1000;
   
type
  tPrimesSieve = array of boolean;
  ttElement = Uint32;
  tarrElements = array of ttElement;
   
var
  PrimeSieve : tPrimesSieve;
  primes : TInt64Array; // object prefilled //tarrElements;
  sphenics : tarrElements; 

We also use a class TPrimes for the primes array sieve, so its also Object Pascal:

try
  ClearAll;
  Sieve:=TPrimes.Create;
  primes:= sieve.prime;
  setlength(primes,78500);
  setlength(PrimeSieve,LLimit+1);// inits with #0
  CreateSphenics(Primes);   //must be the filled primes
finally
  Sieve.Free;
end; 

Next will be the Python one as Python4Delphi in maXbox5:

""" rosettacode.org task Sphenic_numbers """
//https://rosettacode.org/wiki/Sphenic_numbers#Python
 
from sympy import factorint
 
sphenics1m, sphenic_triplets1m = [], []
 
for i in range(3, 1_000_000):
    d = factorint(i)
    if len(d) == 3 and sum(d.values()) == 3:
        sphenics1m.append(i)
        if len(sphenics1m) > 2 and i - sphenics1m[-3] == 2 and i - sphenics1m[-2] == 1:
            sphenic_triplets1m.append(i)
 
print('Sphenic numbers less than 1000:')
for i, n in enumerate(sphenics1m):
    if n < 1000:
        print(f'{n : 5}', end='\n' if (i + 1) % 15 == 0 else '')
    else:
        break
 
print('\n\nSphenic triplets less than 10_000:')
for i, n in enumerate(sphenic_triplets1m):
    if n < 10_000:
        print(f'({n - 2} {n - 1} {n})', end='\n' if (i + 1) % 3 == 0 else '  ')
    else:
        break
 
print('\nThere are', len(sphenics1m), 'sphenic numbers and', len(sphenic_triplets1m),
      'sphenic triplets less than 1 million.')
 
S2HK = sphenics1m[200_000 - 1]
T5K = sphenic_triplets1m[5000 - 1]
print(f'The 200_000th sphenic number is {S2HK}, with prime factors {list(factorint(S2HK).keys())}.')
print(f'The 5000th sphenic triplet is ({T5K - 2} {T5K - 1} {T5K}).')

And it will be of course the same result and interesting almost the same performance (~12 seconds):

There are 206964 sphenic numbers and 5457 sphenic triplets less than 1 million.
The 200_000th sphenic number is 966467, with prime factors [17, 139, 409].
The 5000th sphenic triplet is (918005 918006 918007).
mX5🐞 executed: 03/04/2025 10:04:44 Runtime: 0:0:13.64 Memload: 75% use

In Python4Delphi we import extra libaries with execstr:

procedure Delphi9_PySolution(loc: string);
var Data1, Data2 : array of Double; 
begin
  with TPythonEngine.Create(Nil) do begin
   //pythonhome:= PYHOME64;
   // -V:3.12 *   Python 3.12 (64-bit)
   loadDLL;
   autofinalize:= false;
   try
    execstr('import io, sys  # Added')
    execstr('output = io.StringIO()') 
    execstr('sys.stdout = output');  
    execstr('from sympy import factorint');
    execstr('sphenics1m, sphenic_triplets1m = [], []');

Next is a solution of the web therefore it runs in a browser:

Call of tio.run from maXbox5 generator to invoke the Free Pascal Compiler:

The web server of Try It Online and the arenas (where user code is executed) are currently run on three separate servers. TIO is getting more and more traffic, so additional arenas will be required. Also, server-side permalinks will eventually require a separate storage. With your help, I hope to ensure a smooth operation of all TIO services.

TIO is powered by DigitalOcean. Their virtual private servers are affordable, fast, scalable, and (most importantly) professionally managed. The TIO web app is free of charge, ad-free, and doesn’t use tracking cookies or third-party analytic scripts.

The last solution is the Delphi one, not finished yet with further tests and profiling. The TPrimes class introduced has been enhanced to include the GetPrevPrime and GetNthPrime function and moved into a MathsLib unit which is included here with the source code zip file and is also now included in our common library file DFFLIBV04. The array of int64 will be filled with 78499 primes up to the last one 1,000,003 as the range of one million. There are exactly 78,498 prime numbers between 1 and 1,000,000. This count has been determined using mathematical methods such as the Prime Number Theorem, which estimates the density of primes below a given number.

In maXbox the class and library is precompiled so you dont need to install or import it.

Sieve:= TPrimes.Create;
  prime:= sieve.prime;
  writeln(itoa(prime[78499])+'  '+itoa(high(prime)));
  for it:=1 to 50 {Sieve.MaxPrimeInTable-1} do
     //write(itoa(Sieve.GetNthPrime(It))+' ');
     write(itoa(prime[It])+' ');
  sieve.free;
  GetSphenicNumbers(Sphenic);
  Memo2.Lines.Add('Some Sphenic numbers less than 1,000:');
  S:='';
  for i:=0 to 1000-1 {High(Sphenic)} do begin
     if Sphenic[i]>993 then break;
     S:=S+Format('%4d',[Sphenic[i]]);
     if (i mod 15)=14 then S:=S+CRLF;
   end;
  writeln(S); 
  writeln('Total Sphenic Numbers found = '+
      FloatToStrF(Sphenic[Length(Sphenic)-1]-800,ffNumber,18,0));

In number theory, a sphenic number (from Greek: σφήνα, ‘wedge’) is a positive integer that is the product of three distinct prime numbers. Because there are infinitely many prime numbers, there are also infinitely many sphenic numbers. The cyclotomic polynomials Φn(x) $\Phi _{n}(x)$ , taken over all sphenic numbers n, may contain arbitrarily large coefficients[1] (for n a product of two primes the coefficients are ±1 $\pm 1$ or 0).

Any multiple of a sphenic number (except by 1) is not sphenic. This is easily provable by the multiplication process at a minimum adding another prime factor, or raising an existing factor to a higher power.

Solutions Overview of Math Solver

1 Internal Pascal code scripting in maXbox5
2 External call of Python for Delphi (P4D)
3 Internal Free Pascal Compiler & Lazarus API
4 External call of Free Pascal TIO Web
5 Internal script (precompiled Delphi VM)

Conclusion

When it comes to problem-solving, there are often multiple solutions that can be used to solve the same problem. The choice of solution depends on various factors such as performance, storage, correctness, implement-ation, accessibility, simplicity, and also scaleability and security in different environments. The code is more or less the same but the choice of the environment (script, executable, container, hosting, web or cloud API) could be a response of different requirements.

The Script you can find at: https://sourceforge.net/projects/maxbox5/files/examples/1390_Sphenic_Numbers2TIO_12_py_uc.txt/download

https://rosettacode.org/wiki/Sphenic_numbers#Delphi

Search This Blog

maXbox4