Approximating the amount of prime numbers below `x`

-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 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

RGS

Posted 2020-01-28T18:03:52.747

Reputation: 5 047

4with 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 of x (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.920

So 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 0 decimal places? Is the current Python 3 answer valid?

– Jo King – 2020-01-28T23:36:39.730

@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

Answers

3

Python 3, 61 bytes \$\approx\$ 77.6375 score

import math
def f(x):p=x/math.log(x);print(f"{p:.{int(p)}f}")

Try it online!

Correct up to 4 decimals for \$\pi(10)\$.

Original post solution:

Python 3, 41 bytes \$\approx\$ 54.66 score

lambda x:int(x/__import__('math').log(x))

Try it online!

Saved 20 bytes thanks to Expired Data!!!

Taking a leaf out of Expired Data's book and going for zero precision so \$p=0\$.

Noodle9

Posted 2020-01-28T18:03:52.747

Reputation: 2 776

Up to what p does your answer work? – RGS – 2020-01-28T18:28:19.443

41 bytes * (1 + 1/3) = 54 + (2/3) score – Expired Data – 2020-01-28T19:19:38.547

@ExpiredData That's brilliant! Didn't know about the dunder method __import__. Thanks! :-) – Noodle9 – 2020-01-28T20:16:47.703

@Noodle9 Yeah I found it on google, I don't really speak python. It's probably smaller if you said the import is counted in the byte count and then just specify it as the extra 11 bytes. Relevant

– Expired Data – 2020-01-28T21:49:01.250

Your solution doesn't meet the requirement of "outputting a number with exactly pi(x) decimal places. – RGS – 2020-01-29T00:26:19.847

2Fixed that - thanks! :-) – Noodle9 – 2020-01-29T06:32:45.860

3

05AB1E, 17 14 bytes - Score = 22.6... 18.6...

-3 bytes/4 score thanks to Kevin Cruijssen

žr.n÷'.0IÅPg×J

Try it online!

As far as I'm aware 05ab1e doesn't have arbitrary length decimal precision. You can probably come up with an answer which calculates pi(x) decimal points of x/log(x) in less than 68 bytes and then concats them but frankly I'm not interested in this question any more.


Old answer before the question was revised

05AB1E, 6 bytes = 8 score

žr.n/ò

Try it online!

Does x/ln(x) and then rounds to the nearest integer, hence p = 0

Expired Data

Posted 2020-01-28T18:03:52.747

Reputation: 3 129

@JoKing The old question never prints any decimal places so it is not valid – RGS – 2020-01-29T00:01:19.593

@JoKing oh sorry, only noticed now they changed. Before the edit, the Python answer would print as many trailing zeroes as needed. – RGS – 2020-01-29T00:09:39.720

2

bc, 61,51,46,45 bytes +2 for -l, (almost) arbitrary precision, final score \$\approx{47\over3} \approx 15.6666744835...\$

define f(x){scale=999
return(scale=x/l(x))/1}

Try it online!

Unlike the test cases, I don't give too many digits. I give the number of digits based on the approximation, not the counted value.

Precision degrades with this solution when the result reaches 1000, at f(9119). At that point, one must add another 9 on the first line. A general solution would be possible, but longer. I guess this makes the score for this version 15.6666744835...

It turns out, with initial scale=99 the score is 25.127..., and with initial scale=9999 the score is 16 + 6.75...E-67.

I could write scale=9^9, get 387420489 digits of precision (probably a few less accurate), but it would take too long to run. TIO doesn't even let 9^4 get passed the second test case. This would get a score of 15.6666666666..., but still slightly more the 15⅔.

Edit: Saved 10 bytes by eliminating scale=0 and rounding on scale=a

Edit: saved 5 bytes by eliminating a temporary

Edit: saved 1 byte by eliminating whitespace

David G.

Posted 2020-01-28T18:03:52.747

Reputation: 541

2

Bash + bc, 89 bytes, arbitrary precision, final score \${89\over3} \approx 29.67\$

f(){
a=`primes 1 $((${1%.*}+1))|wc -l`
echo "scale=$a+20;a=$1/l($1);scale=$a;a/1"|bc -l
}

Try it online!

${1%.*} strips off the fraction

$(( ... +1))) adds one, as primes doesn't output the final number if prime.

primes 1... outputs the list of primes

|wc -l counts them

At this point, a contains \$\pi(x)\$.

The echo puts together a bc program, which is then piped to bc.

  • Set the scale to 20 more than needed (to get the accuracy)
  • do the approximation
  • set the scale to the exact number of digits
  • do a division by 1 so the scale is applied

David G.

Posted 2020-01-28T18:03:52.747

Reputation: 541

1

Mathematica, \$\approx\$ 7.67 score

25 23 bytes, arbitrary precision, final score \$ \frac{23}{3}\$

N[#/Log@#,PrimePi@#+1]&

-2 bytes, courtesy of @ExpiredData

Here is a benchmarking solution. Try it online!.

RGS

Posted 2020-01-28T18:03:52.747

Reputation: 5 047

2.88539008177792681482 doesn't this output only make sense for f(4) if 4 has 20 primes lower than it? Or am I misunderstanding the requirement with exactly () decimal places.? – Cruncher – 2020-01-28T18:16:11.340

@Cruncher you are not interpreting it wrong, TIO just doesn't work really well with N, for some reason. Running this function locally, the roundings are done well. In TIO they show up after the ` at the end of the number. – RGS – 2020-01-28T18:19:34.220

Can't you get -2 bytes with N[#/Log@#,PrimePi@#+1]& – Expired Data – 2020-01-28T18:49:09.000

@ExpiredData yes I can, thanks – RGS – 2020-01-29T00:25:28.703

To fix the TIO link, run the outputs through ToString before Print. – Nick Kennedy – 2020-01-29T17:29:16.927

@NickKennedy Thanks a lot! Can you explain me what was happening under the hood? – RGS – 2020-01-29T17:40:39.343

@RGS I don’t know why it wasn’t working on TIO, but I reasoned that the output of N is storing the data and the number of digit, but converting the output of N to a string should fix the formatting using that number of digits. – Nick Kennedy – 2020-01-29T18:00:16.117

@NickKennedy good thinking – RGS – 2020-01-29T18:01:33.840