High School Calculator Computes Analytical Number Theory

Most of the time Desmos is used to draw polynomials to find roots. However, not many people know how far you can go. This article is absolutely useless from a scientific point of view, yet it is interesting to trace how limitations force creativity. My goal was to build a prime generating function f(1)=p1=2f(1) = p\_1 = 2f(1)\=p1​\=2 without explicit `if` statements, conditional functions, and advanced functions like mod\\text{mod}mod and gcd\\text{gcd}gcd.

What Is a Prime Number?

Quick recap for those who may not be familiar with the topic. A prime number is a number that has no divisors besides one and itself. 111 is excluded from the set of primes.

Is This an Integer?

My thought process was the following: to check whether a number is prime, we have to know if it has any divisors. If a,b,ab∈Za,b,\\frac{a}{b} \\in \\mathbb{Z}a,b,ba​∈Z, then bbb is a divisor of aaa. This method is based on knowing that the inputs and output are integers. So, let’s build it.

cos⁡(πx)=±1\\cos(\\pi x) = \\pm 1cos(πx)\=±1 when xxx is an integer; everywhere else it’s strictly between −1-1−1 and 111. Take the absolute value, and integers give exactly 111; everything else gives something strictly less than 111. Discard everything after the decimal point (or floor it) and non-integers collapse to 000.

Z(x)=⌊ ∣cos⁡(πx)∣ ⌋Z(x) = \\left\\lfloor \\, |\\cos(\\pi x)| \\, \\right\\rfloorZ(x)\=⌊∣cos(πx)∣⌋

y=\left|\cos\left(\pi x\right)\right|
Z\left(x\right)=\operatorname{floor}\left(\left|\cos\left(\pi x\right)\right|\right)
y=Z\left(x\right)
\left(\left[-10,...,10\right],Z\left(\left[-10,...,10\right]\right)\right)

The wave, and the switch it collapses to. Drag and zoom it.

Z(x)Z(x)Z(x) is an “is this an integer” detector, built entirely out of trigonometry and a floor function. That’s the whole trick.

Divisibility Without Modulo

d(x,y)=Z(y)⋅Z ⁣(xy)d(x,y) = Z(y) \\cdot Z\\!\\left(\\frac{x}{y}\\right)d(x,y)\=Z(y)⋅Z(yx​)

This says: yyy is an integer, and x/yx/yx/y is an integer. If both hold, yyy divides xxx cleanly. We just built a divisibility test without a single modulo operator. Interestingly, a third factor, Z(x)Z(x)Z(x), is unnecessary. If yyy and x/yx/yx/y are both integers, x=y⋅(x/y)x = y \\cdot (x/y)x\=y⋅(x/y) has to be an integer too.

How Many?

D(x)=∑n=2x−1d(x,n)D(x) = \\sum\_{n=2}^{x-1} d(x,n)D(x)\=n\=2∑x−1​d(x,n)

This counts divisors of xxx strictly between 111 and xxx. It is a specific design choice. I didn’t want to map 222 to 111 (its two divisors are the number itself and 111). D(x)=0D(x) = 0D(x)\=0 exactly when xxx has no divisors in that range, which for x≥2x \\ge 2x≥2 is just the definition of prime. D(7)=0D(7)=0D(7)\=0 (prime), D(9)=1D(9)=1D(9)\=1, D(4)=1D(4)=1D(4)\=1.

p(x)=⌊11+D(x)⌋p(x) = \\left\\lfloor \\frac{1}{1 + D(x)} \\right\\rfloorp(x)\=⌊1+D(x)1​⌋

This is an old trick. 11=1\\frac{1}{1}=111​\=1 when D(x)=0D(x)=0D(x)\=0, so xxx is prime. The D(x)D(x)D(x) range is \[0,∞)\[0,\\infty)\[0,∞); therefore 11+n<1\\frac{1}{1+n}<11+n1​<1 if n>0n>0n\>0. Floor it and we get a boolean operator that outputs 111 if xxx is prime and 000 if xxx isn’t prime.

One real edge case worth knowing about: D(1)D(1)D(1) is an empty sum, so it’s 000 too. This means p(1)=1p(1)=1p(1)\=1, falsely flagging 111 as prime. It never causes a problem in my case because everywhere ppp actually gets used, the sum starts at n=2n=2n\=2, so p(1)p(1)p(1) is never called. But it’s a trap hidden in ppp on its own.

Brute Force Without Memory

∑n=2kp(n)=π(k)\\sum\_{n=2}^{k}p(n)=\\pi(k)∑n\=2k​p(n)\=π(k), the count of primes up to kkk. Let’s define an intermediate function g(n,k)=n−π(k)g(n,k)=n-\\pi(k)g(n,k)\=n−π(k). Say, n=3n=3n\=3, π(4)=2\\pi(4)=2π(4)\=2, π(5)=3\\pi(5)=3π(5)\=3. We can observe that the moment kkk is pnp\_npn​, g(n,k)g(n,k)g(n,k) becomes 000. Now take an absolute value to make sure it stays non-negative.

f(n,k)=⌊11+∣ n−π(k) ∣⌋f(n,k) = \\left\\lfloor \\frac{1}{1 + \\left|\\, n - \\pi(k) \\,\\right|} \\right\\rfloorf(n,k)\=⌊1+∣n−π(k)∣1​⌋

f(n,k)f(n,k)f(n,k) is the same trick again: 111 when π(pn)=n<π(pn+1)\\pi(p\n)=n<\\pi(p\{n+1})π(pn​)\=n<π(pn+1​). This is bad. f(3,5)=f(3,6)=1f(3,5)=f(3,6)=1f(3,5)\=f(3,6)\=1; we need to track the value of kkk not when fff is 111 but when fff changes. This is a simple discrete derivative: Δn(k)=f(n,k)−f(n,k−1)\\Delta\_n(k)=f(n,k)-f(n,k-1)Δn​(k)\=f(n,k)−f(n,k−1). As soon as kkk is pnp\_npn​, f(n,k)=1f(n,k)=1f(n,k)\=1, f(n,k−1)=0f(n,k-1)=0f(n,k−1)\=0, so the difference is 111. The next kkk will evaluate both functions to 111 and therefore the difference is 000, as we wanted.

Isolating pnp\_npn​

Δn(k)\\Delta\n(k)Δn​(k) tracks both rise and fall. Therefore, when kkk becomes pn+1p\{n+1}pn+1​, the difference evaluates to −1-1−1. In order to track when the positive change occurs, we construct a simple function: 12−Δn(k)\\frac{1}{2-\\Delta\_n(k)}2−Δn​(k)1​; it evaluates to 111 when Δn(k)=1\\Delta\_n(k)=1Δn​(k)\=1 and 1/31/31/3 when Δn(k)=−1\\Delta\_n(k)=-1Δn​(k)\=−1. The last thing is to floor the expression so it equals 111 exactly once when k=pnk=p\_nk\=pn​.

pn=∑k=2Nk⌊12−Δn(k)⌋p\n = \\sum\{k=2}^{N} k \\left\\lfloor \\frac{1}{2 - \\Delta\_n(k)} \\right\\rfloorpn​\=k\=2∑N​k⌊2−Δn​(k)1​⌋

Sum from k=2k=2k\=2 up to some NNN. Once the fraction is 111, we multiply it by kkk, which is precisely pnp\_npn​. Voila, we got a prime generating function from the simple idea of an “is this an integer” detector.

When to Stop

The interesting part is the upper bound NNN, which has to be sufficiently large to guarantee pnp\_npn​ actually falls inside the range being summed. N=⌊n(ln⁡n+ln⁡ln⁡n)⌋N = \\left\\lfloor n(\\ln n + \\ln \\ln n) \\right\\rfloorN\=⌊n(lnn+lnlnn)⌋ is the real theorem (Rosser–Schoenfeld) but is only proven to exceed pnp\_npn​ for n≥6n \\ge 6n≥6. N=⌊n(ln⁡(n+1)+2)⌋N = \\left\\lfloor n(\\ln(n+1) + 2) \\right\\rfloorN\=⌊n(ln(n+1)+2)⌋ fixes the small cases but overcounts as nnn goes further from 111.

The Actual Point

The same move gets reused at every layer here: build a test that’s exactly 111 at the one case you care about and 000 everywhere else, then let a sum or a gate pick that one case out. Integer detector, divisibility test, divisor sum, prime function. None of the individual steps are hard, and each one is just the last idea reused. Give yourself `%` and a `for` loop and the whole chain is a few lines. Without them, you are rebuilding most of elementary number theory from first principles.