“Natura abhorret vacuum” 1 — Spinoza.
Source: 1390_Sphenic_Numbers2TIO_12_py_uc.txt
Sometimes life is like playing with us: You write some useful code that solves a problem, and then someone comes along and makes the problem much harder. Here’s how to continuously integrate new solutions without having to rewrite your old solutions (as much). Means you don’t have to change the language, you change the environment.
Let’s start with a simple problem: For a new kind of two-factor authentication security you have to find the first 1000 sphenic numbers. 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:
Result in maXbox Console
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;Sphenic Numbers
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.
https://tio.run/#
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){\displaystyle \Phi _{n}(x)}, taken over all sphenic numbers n, may contain arbitrarily large coefficients1.
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.
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 Script you can find at: https://sourceforge.net/projects/maxbox5/files/examples/1390_Sphenic_Numbers2TIO_12_py_uc.txt/download
