-5
0
Background
We define the prime-counting function, \$\pi(x)\$, as the number of prime numbers less than or equal to \$x\$. You can read about it here.
For example, \$\pi(2) = 1\$ and \$\pi(6) = 3\$.
It can be shown, using dark magic, that
\$ \lim_{x \to \infty} \frac{\pi(x)}{x/\log x} = 1 \$
which means we can approximate \$ \pi(x) \$ by \$ x/\log x\$.
Your task
Your purpose is to write a function/program that takes x
as input and outputs the approximation of \$\pi(x)\$ as given by the ratio of the input and the logarithm of the input, with exactly \$\pi(x)\$ decimal places. Either rounding works fine.
Test cases
f(4) = 2.89
f(10) = 4.3429
f(19.3) = 6.52003877
f(60) = 14.6543602005583370
f(173) = 33.570776430488395580723956088340374417691
f(499) = 80.3205598921264941447922062868184315657020413225943243128931714242910058741601601524983152243502
f(1024) = 147.73197218702985291365628733459375487248854570526575965547001926974558404415335218027792618429504967649254587490842053177273361276604002741459580500208428403451262667619517
Scoring
This is code-golf so shortest solution wins... With a twist! If the code you wrote gives the right answer for results with up to p
decimal places and your code has b
bytes, then your score is
\$(e^{-p/64} + \frac13)b \$
which essentially means you get a better score if the precision is really high, as the factor multiplying by b
decays rapidly as the precision increases until flattening at \$\frac13\$.
If you can't tell for sure the precision up to which your code works, you can take p
to be the number of decimal places of the last test case your code can handle exactly.
For this challenge, the minimum score is 1/3
, which would be attainable by a 1-byte long submission with arbitrary precision.
Admissible solution
To wrap up, your code is a valid solution if and only if it computes the approximation of \$\pi(x)\$ as given by the formula and, when it gives the output, the output has exactly \$\pi(x)\$ decimal places. The p
for the scoring will be how many decimal places you can get right.
Notice the distinction. The code linked outputs square root of 2 with 1000 decimal places BUT python only gets some of the decimal places right.
Standard loopholes are forbidden
4
with exactly () decimal places.
How do we know how many decimal places there are? Doesn't that imply that we have to calculate () exactly as a part of this challenge, and not just estimate it? – Cruncher – 2020-01-28T18:09:40.930@Cruncher either your programming language has a built-in for
pi(x)
, or you compute for small values ofx
(with a sieve, for example) or you investigate how well the approximation works and round it down/up to get the correct number of decimal places to be used. – RGS – 2020-01-28T18:12:55.920So if we give more decimal places it's wrong? and if we give less decimal places it's right but negatively affects score? – Expired Data – 2020-01-28T18:26:04.703
@Noodle9 there are
8
primes below 19.3 so the function should return the approximation for pi(19.3) with 8 decimal places. – RGS – 2020-01-28T18:38:46.780@ExpiredData you have to give that exact number of decimal places. I am just giving the possibility that at some point they start being wrong. Check the python answer below, for larger inputs the decimals all become 0 – RGS – 2020-01-28T18:39:35.560
5@RGS what do you mean by at some point they start being wrong. Either it is a requirement of the challenge that it would work for arbitrary values or it isn't? Why can't that at some point be the first point and hence p = 0. and if it can't then you need to much more clearly define at what point that at some point is – Expired Data – 2020-01-28T18:41:50.113
@ExpiredData the requirement is the amount of decimals, not their correctness. – RGS – 2020-01-28T18:47:24.567
1@RGS I'm not sure I understand, which I think probably means your question is not very clear. Is the requirement that there is exactly pi(x) decimals for all possible x? In which case are you saying a language cannot answer if it does not have arbitrary decimal precision, or are you saying the answer is still valid? – Expired Data – 2020-01-28T18:54:48.940
@ExpiredData I tried rewriting the final section to make it better. Is it clearer now? – RGS – 2020-01-28T19:43:29.330
5Dank so basically just need to append pi(x) zeroes on to my solution.. I've downvoted as I don't think this is a good challenge - It wasn't very clear and appears to have lots of very arbitrary steps. – Expired Data – 2020-01-28T19:45:57.583
Is rounding to $ \pi (x) $ precision mandatory or optional? You say you have to do it exactly, but then you base scoring on how accurate the precision is? – Jo King – 2020-01-28T23:13:33.200
@JoKing you have to display pi(x) decimal places. If you get all those decimal places right, then that boosts your score. If you know your code can never get the decimal places from the 17th onward right, then your p is 16. So basically you can always append enough zeros to the output to have as many decimal places as requested,but then those 0s won't be correct so they won't boost your score. – RGS – 2020-01-28T23:33:27.780
Do we have to display trailing
– Jo King – 2020-01-28T23:36:39.7300
decimal places? Is the current Python 3 answer valid?@JoKing as of the time of writing, the Python answer is not valid because it doesn't print any decimal places whatsoever. – RGS – 2020-01-29T00:10:22.037
@RGS Something seems wrong here: $\pi(19.3)$ is 6.52..., but you seem to be saying it must return 8 decimal places because the non-approximate value is 8? This seems to be saying we must not only calculate the approximation, but also the non-approximation? Shouldn't we be expected to return 6 digits for $\pi(19.3)$? – David G. – 2020-01-29T21:44:14.433
@DavidG. Supposedly I was requiring you to return 8 decimal places. But I don't know what to do to my life anymore :/ – RGS – 2020-01-29T21:56:49.333
@RGS: OK, even more confused. I wrote a new solution in a partly new language to do both calculations, and the test cases seem to be missing a few digits in some cases. like $\pi(60)=17$ so f(60) should be 14.65436020055833703 (nearest) or 14.65436020055833702 (down). Did you mean the test cases to be off? – David G. – 2020-01-29T22:15:10.307