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


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

  • 5
    \$\begingroup\$ 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? \$\endgroup\$ – Cruncher Jan 28 '20 at 18:09
  • \$\begingroup\$ @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. \$\endgroup\$ – RGS Jan 28 '20 at 18:12
  • 6
    \$\begingroup\$ @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 \$\endgroup\$ – Expired Data Jan 28 '20 at 18:41
  • 1
    \$\begingroup\$ @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? \$\endgroup\$ – Expired Data Jan 28 '20 at 18:54
  • 5
    \$\begingroup\$ Dank 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. \$\endgroup\$ – Expired Data Jan 28 '20 at 19:45

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\$.

  • \$\begingroup\$ Up to what p does your answer work? \$\endgroup\$ – RGS Jan 28 '20 at 18:28
  • \$\begingroup\$ 41 bytes * (1 + 1/3) = 54 + (2/3) score \$\endgroup\$ – Expired Data Jan 28 '20 at 19:19
  • \$\begingroup\$ @ExpiredData That's brilliant! Didn't know about the dunder method __import__. Thanks! :-) \$\endgroup\$ – Noodle9 Jan 28 '20 at 20:16
  • \$\begingroup\$ @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 \$\endgroup\$ – Expired Data Jan 28 '20 at 21:49
  • 2
    \$\begingroup\$ Fixed that - thanks! :-) \$\endgroup\$ – Noodle9 Jan 29 '20 at 6:32

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

-3 bytes/4 score thanks to Kevin Cruijssen


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


Try it online!

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

  • \$\begingroup\$ @JoKing The old question never prints any decimal places so it is not valid \$\endgroup\$ – RGS Jan 29 '20 at 0:01
  • \$\begingroup\$ @JoKing oh sorry, only noticed now they changed. Before the edit, the Python answer would print as many trailing zeroes as needed. \$\endgroup\$ – RGS Jan 29 '20 at 0:09

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

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

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

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


Mathematica, \$\approx\$ 7.67 score

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


-2 bytes, courtesy of @ExpiredData

Here is a benchmarking solution. Try it online!.

  • \$\begingroup\$ 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.? \$\endgroup\$ – Cruncher Jan 28 '20 at 18:16
  • \$\begingroup\$ @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. \$\endgroup\$ – RGS Jan 28 '20 at 18:19
  • \$\begingroup\$ Can't you get -2 bytes with N[#/Log@#,PrimePi@#+1]& \$\endgroup\$ – Expired Data Jan 28 '20 at 18:49
  • \$\begingroup\$ @ExpiredData yes I can, thanks \$\endgroup\$ – RGS Jan 29 '20 at 0:25
  • \$\begingroup\$ To fix the TIO link, run the outputs through ToString before Print. \$\endgroup\$ – Nick Kennedy Jan 29 '20 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.