Problems & Puzzles: Problems
Problem 38. Sebastián Martín Ruiz- Prime formulas
Sebastián Martín Ruiz, a high school teacher from Chipiona, Cadiz, Spain, has came up  with his own prime formulas p(n) and nxt(p)
(here means the largest integer less than or equal to x; in Ubasic this corresponds to the function "int(x)" or "floor(x)")
Sebastian does not claim that his formulas satisfy one of the desiderata asked by Hardy and Wright for these mathematical targets:
because he recognizes that both functions should work slower than the corresponding algorithms based in the sieve of Erathostenes.
(This happens due to the very nature of one concept at the core of both formulas: the exhaustive calculation of the number of divisors of a number n; this calculation is needed to evaluate the so-called Smarandache Prime function, a binary one, that constitutes - at the end - the essential calculation)
Nevertheless - with this feature against - Sebastián hopes indeed that at least his formulas are better than the previously produced by others - like Sierpinski, Willans & Gandhi. See  - in two specific aspects:
As a matter of fact Sebastián claims that both formulas are of a polynomial order - k*(n log n)^3 - while the previous ones are factorial or exponential order.
1) Do you agree with the Sebastian's two before claims?
In the Ribenboim's interpretation of the Hardy & Wright desiderata for the prime formula he says:
2) Dou you think that the Sebastian's formulas are in terms of n, closed, computable and classical?
3) From a computational point of view, are the Sebastian's prime formulas an improvement or a back step regarding the Liu Fenghsui' s prime formula? (See Problem 37 in these pages)
4) Do you devise any way to optimize the Sebastian's prime formulas?
: Sebastián Martín Ruiz original publications can be found here: p(n) and nxt(p). The formulas were developed in 1999 but published in the SJN at Spring 2000. At the time of the publications he was considering to be the only author of the main inner functions [ d(n) and G(n) ]. Only recently he found that d(n) was already developed, according to "Introducción al la teoría de números", Ivan Niven & H. S. Zuckerman. Editorial Limusa-Wiley, S.A. México, 1969. pp. 88-89-90.
 & : Here are my Ubasic-codes to calculate these functions, and below the Sebastian's ones for Mathematica.
 P. Ribenboim, The New Book of Prime Number Records, pp. 179-186
Jud McCranie has suggested to eliminate the 'floor' or the 'int' functions in the codes that I originally wrote in Ubasic, using - instead - the integer division operator (x\y). I have followed his suggestion and the savings in time of computation has been of .... 33.3%... nothing bad!
Now the codes shown in the table above reflect that idea.
The Jud's idea also can be applied to the formulas writing, eliminating the clumsy floor brackets so hard to write in a basic word processor... And I would like if that idea can be implemented also in the codes for Mathematica, with the same good results in time savings that we got in Ubasic
I (CR) have devised another important improvement in the codes based in the fact that the calculation of the number of divisors of a number n, exhaustive via, needs run only from 1 to isqrt(n) and then multiply for 2 the result obtained. The changes needed in my codes are:
The times spent in calculation drop dramatically!
BTW nxt(p): while nxt(p) is the following prime to the number p, p itself needs not to be prime!
The Sebastian's formulas introducing the ideas given by Jud and me (CR), and homogenizing the sub-indexes in both formulas, look the following way:
in these formulas all the divisions are integer-divisions
The new programs for Mathematica, sent by Sebastián, are:
Patrick De Geest sent the following ideas to improve the programs a bit more:
only once instead of twice. (in large loops the gain in speed can become important) Therefore I changed:
S3 = S3 + J\L-(J-1)\L into S3 += J\L-(J-1)\L
2. Using shortest possible variable names.(in large loops the gain can become noticable) Therefore I changed S1 to S, S2 to T and S3 to U.
3. Cramming all the for-next lines into one long line saves a little time when dealing with large loops. Of course that clarity in structure is lost but maybe that is not so important in small routines as p(n).
Combining all these 'shortcuts' gave me the above mentioned runtime reduction. My final version of p(n) looks like :
The final version of nxt(p) looks like :(gain in speed is less pronounced here. I give them anyway as these optimizations might come handy when developing other future time critical algorithms)
Sebastian Ruiz has made a very interesting discovery to his prime formula p(n). You may calculate p(n) not starting the summa for k since 1 but since any number m less or equal to p(n)
But this means that of m is the previous prime to p(n), then this formula is also a formula to calculate recursively prime by prime starting in any of these. This also means that this formula used this way is a competitor formula for the nxt(p) formula of Sebastian.
As a matter of fact, according to my (C.R.) implementation of the Ubasic code of the p(n) formula modified to calculate the series of primes, p(n) is better (faster) than nxt(p)...!!!.
Jud McCranie was asked to confirm the Rivera's result and this is what he aswered: "Using p(n), it takes 0.4 seconds to calculate p(75), but it takes 8.4 seconds to calculate p(1) ...p(75). Using NxtPrm, it takes 0.8 seconds to calculate p(75) from p(74), and 16.4seconds to calculate p(1) then p(2) ... p(75). So for these tests, NxtPrm takes twice as long."
Sebastian announces that his nxt(p) function can be formulated in order to obtain, recursively, only the primes of an arithmetic progression a+d.n, n=>0, gcd(a, d)=1. If you want to know the expression of that formula and/or the corresponding code in Mathematica, please request them to Sebastian.
One more communication came from S. M. Ruiz (31/10/2002):
Here are the corresponding codes in Mathematica and Ubasic, sent by himself:
We can also reduce the order of the explicit
formula p(n) from O(n log n)^(5/2) to O(n log
SMR reported (May, 2003) the following interesting old reference:
An explicit Formula for the k-th prime number, Sthephen Regimbal, Mathematics Magazine, Volume 48, Issue 4 (Sep. 1975), pp. 230-232.
New improvements to the nextprm function came from William Bouris. When Sebastian revised the Bouris improvement he made one more improvement to the Bouris work. Here are the successive codes and their outputs, as ran by Sebastian (who asks where does come from the limit for the line 15?)
SMR has developed (March 2004) another formula for the p(n) function, now based in a totally distinct characteristic function for the prime numbers recalling the basic arithmetic function LCM:
His new p(n) formula is this one:
which he improved as a calculating tool using the Rosen and Schoenfeld bound:
This last formula (for the prime p(200) ) is approximately 8.5 times faster than the previous one, and 65 times faster than the faster p(n) function not using the LCM characteristic function.
SMR now is investigating the following question "Which is the order of this algorithm?"