1

$$f\left(m\right)=\sum_{i=0}^{m^{2}}⌊cos\left(⌊ \frac{\sum_{o=1}^{i}\left(\prod_{n=2}^{⌊\sqrt{o}⌋}\left(1-⌊\cos\left(\pi\frac{o}{n}\right)^{2}⌋\right)\right)}{m+1}⌋\right)^{2}⌋$$

I was watching a video about how a formula for finding the nth prime, Willan's formula, and how it did that.

What this function does is similar, and can be broken down into a few different parts.

Part 1

$$g\left(o\right)=\prod_{n=2}^{⌊\sqrt{o}⌋}\left(1-⌊\cos\left(\pi\frac{o}{n}\right)^{2}⌋\right)$$

This section of the function is a primality detector. If a number is prime, It outputs a $1$, but if it is composite, It outputs a $0$.

Part 2

$$h\left(i\right)=\sum_{o=1}^{i}\left(\prod_{n=2}^{⌊\sqrt{o}⌋}\left(1-⌊\cos\left(\pi\frac{o}{n}\right)^{2}⌋\right)\right)$$

This part of the function uses the primality detector to find the number of primes before a given number $i$.

Part 3

$$k\left(i,m\right)=⌊cos\left(⌊ \frac{\sum_{o=1}^{i}\left(\prod_{n=2}^{⌊\sqrt{o}⌋}\left(1-⌊\cos\left(\pi\frac{o}{n}\right)^{2}⌋\right)\right)}{m+1}⌋\right)^{2}⌋$$

This part of the function finds if the number of primes before $i$ is greater than $m+1$. If i>m+1, it outputs 0, if i<m+1, it outputs a 1

This means that this whole equation is saying that, for every number between 0 and m^2, checks to see if the number of the primes below that number is less than m+1, and adds together all of the outputs.

https://www.youtube.com/watch?v=j5s0h42GfvM&t=558s

https://www.desmos.com/calculator/9hywncio5g

Benjamin Trumpy
  • 19
  • Welcome to [math.se] SE. Take a [tour]. You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an [edit]): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance. – Another User Nov 22 '22 at 22:51
  • 3
    Please add some context on how you ended up at this function. The more detail you provide, the better chance you have that someone will respond. – Arkady Nov 22 '22 at 22:55
  • Will do. Thank you. – Benjamin Trumpy Nov 22 '22 at 23:01
  • 1
    You have four different functions all named $f$ here. That's really confusing. Each function should have a different name from every other function in a particular exercise such as this question. If you don't want to give a function a different name, don't name it at all. – David K Nov 22 '22 at 23:40

1 Answers1

0

This is certainly not a good way to find primes, but it is clever, and it seems to have a different computational bottleneck than Willan's formula. Remember: these are more like "prime detectors" as you mention than constructive formulas. After a rough sketch, I achieved $ O(n^{14}) $. Maybe someone can confirm this, but it is wildly inefficient nonetheless. Willan's formula cannot work because the numbers in the sum quickly get too large for computers to handle.

If you are curious about better ways to calculate the nth prime, check out the AKS primality test. You would be much better off just calculating this sequence for n terms, as the test is $ O(log^{6} n) $.

Scott Sobolewski
  • 93
  • 1
    Applying the primality test for every number is still far too slow. The best method is to use the efficient $\pi(x)$-routine. – Peter Nov 23 '22 at 21:44