This is not the question of programming language, and I don't think that my question does not boil down to Kolmogorov complexity. Steve Whitman is right, it is a question akin to entropy-encoding the sequence of prime numbers, and my idea of delta-coding them worked. Obviously, and facetiously, the function f = NextPrime(Floor(f)) will work up to infinity regardless of the fractional part of the starting value, and may even be expressed quite efficiently (for integers, FRACTRAN did it quite well), but it is easy to notice that its computational complexity would not be O(1). If one limits themselves to function expressible as a combination of arithmetic operations and elementary functions (following the examples), regardless of its length, as it will still be computable in idealized O(1) time, is there a way to improve my result? The answer is yes; we can write any finite prefix to any of the examples in my original post in the form f(x) = if x < 3 then 3+frac(x) elsif x < 5 then 5 + frac(x) else (any of the original formulas). but as soon as the evaluation gets to the general case, the asymptotic efficiency will be different formulas. If we disallow conditionals and limit ourselves to the four arithmetic operations and Floor(), it will be easier to compare the efficiency of encoding, that's all. Thanks, Leo On Wed, Dec 2, 2020 at 4:07 PM Mike Stay <metaweta@gmail.com> wrote:
The question, of course, depends on the programming language. Fix one and then it'll make sense to play code golf. Otherwise, I can just define a language with a built-in operation that takes in an arbitrary pair and outputs the primes, so (0, op) would be the smallest.
On Wed, Dec 2, 2020 at 4:30 PM Leo Broukhis <leob@mailcom.com> wrote:
Apropos https://www.youtube.com/watch?v=_gCKX6VMvmU
There are many ways to produce the sequence of primes by iterating a function, e.g. starting with f_1 = ContinuedFraction(2, 3, 5, 7, 11, 13, ,,,) = 2.3130367364335829..., (http://oeis.org/A064442) and
f_n+1 = 1/(f_n - Floor(f_n))
the sequence of Floor(f_n) will be the sequence of primes.
Or, as in the clip, starting with the average of http://oeis.org/A053669
=
2.920050977316134712..., and f_n+1 = Floor(f_n) * (f_n - Floor(f_n) + 1) will do the same.
Or the Blazys continued fraction, see http://oeis.org/A233588
The question is, which constant/function pair encodes primes in the most compact way. More precisely, given a denominator for a rational approximation, which function will correctly produce the most primes starting from the approximation of the corresponding constant?
For example, with the IEEE double (64 bit floating point) approximations of the constants, the continued fraction starts diverging at 29, the Blazys continued fraction - at 47, the 2.92... constant - at 59.
I was able to come up with the function f_n+1 = Floor(f) + 1/(f_n-Floor(f_n)); which is the delta-coded continued fraction of the sequence of primes, gives rise to f_1 = 2.7101020234300968374... and given its IEEE double approximation, starts diverging at 67.
Improvements are welcome.
Thanks, Leo _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun