On Mon, Dec 7, 2020 at 6:03 PM M F Hasler <mhasler@dsi972.fr> wrote:
Le jeu. 3 déc. 2020 à 01:37, Mike Stay <metaweta@gmail.com> a écrit :
In the end, this all boils down to Kolmogorov complexity, which depends on the choice of language.
Yes and no, Kolmogorov complexity is universal in the sense that it depends on the language or machine only up to a constant.
But I feel you didn't reply to what I wrote, specifically what I think is the the core idea: the function f : R -> R which yields a map A(f) from reals to integer sequences, A(f) : R -> Z^N ; c -> a = (floor(f^n(c))) = (floor(c), floor(f(c)), floor(f(f(c))), ...) which should be continuous (i.e., constants c, c' which are sufficiently close should produce integer sequences with as many common terms as possible) but still "efficiently" code these sequences, which might translate to a differential function with a large derivative.
If c and c' straddle an integer, all bets are off. But yes, thinking about it in these clarified mathematical terms shows that
we have a kind of dilemma, if we get many primes with not so many decimals of c = c(primes), then probably it will / must(?) do less well for a different sequence....
Naturally. Given that the function is pure, i.e. it does not have any internal state, to encode primes efficiently it would have to be "hardwired" specifically for the primes. Plotting the functions, it is possible to see, by the range and the slope of the graph, how the value of the next prime is "predicted". The continued fraction is clearly wasteful because it does not use the monotonicity. The function from the clip is bounded, as NextPrime(p) < 2p, but it is linear, that is, it assumes equal probability over the whole possible range, which is unlikely to match reality. My function and Blazys' function look similar but mine is not as steep over the "sweet" range near the current prime, thus performs better than the Blazys'. I guess, the trick would be to find out what is the asymptotic shape of the probability distribution of the next prime over [p+2, 2p-1] (is that distribution known?) and to construct the corresponding iterative function.
So IMHO, rather than a sequence, we must fix the test cases on which the function is to be evaluated. Where "evaluation" is as specified in my earlier mail, the (asymptotic?) ratio of number of correct terms of the sequence, per number of correct digits in c. Maybe you can "reverse engineer" that scoring system by knowing the test suite if it is finite, (i.e., your function f would guess which sequence is "wanted" for a given constant c and artificially produce the required terms) but for a sufficiently well conceived infinite test suite, I doubt that would be possible.
That I didn't get, sorry. Thanks, Leo