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
    Commented Jan 28, 2020 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
    Commented Jan 28, 2020 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\$ Commented Jan 28, 2020 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\$ Commented Jan 28, 2020 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\$ Commented Jan 28, 2020 at 19:45

5 Answers 5


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
    Commented Jan 28, 2020 at 18:28
  • \$\begingroup\$ 41 bytes * (1 + 1/3) = 54 + (2/3) score \$\endgroup\$ Commented Jan 28, 2020 at 19:19
  • \$\begingroup\$ @ExpiredData That's brilliant! Didn't know about the dunder method __import__. Thanks! :-) \$\endgroup\$
    – Noodle9
    Commented Jan 28, 2020 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\$ Commented Jan 28, 2020 at 21:49
  • 2
    \$\begingroup\$ Fixed that - thanks! :-) \$\endgroup\$
    – Noodle9
    Commented Jan 29, 2020 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
    Commented Jan 29, 2020 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
    Commented Jan 29, 2020 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
    Commented Jan 28, 2020 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
    Commented Jan 28, 2020 at 18:19
  • \$\begingroup\$ Can't you get -2 bytes with N[#/Log@#,PrimePi@#+1]& \$\endgroup\$ Commented Jan 28, 2020 at 18:49
  • \$\begingroup\$ @ExpiredData yes I can, thanks \$\endgroup\$
    – RGS
    Commented Jan 29, 2020 at 0:25
  • \$\begingroup\$ To fix the TIO link, run the outputs through ToString before Print. \$\endgroup\$ Commented Jan 29, 2020 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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