The primitive circle problem is the problem of determining how many coprime integer lattice points \$x,y\$ there are in a circle centered at the origin and with radius \$r \in \mathbb{Z}^+ \$ such that \$x^2+y^2 \le r^2 \$. It's a generalization of Code-Golf: Lattice Points inside a Circle.
Input
Radius \$r \in \mathbb{Z}^+\$
Output
Number of coprime points
Taken from sequence A175341 in the OEIS.
| Radius | Number of coprime points |
|---|---|
| 0 | 0 |
| 1 | 4 |
| 2 | 8 |
| 3 | 16 |
| 4 | 32 |
| 5 | 48 |
Based on A000089, the number of solutions to:
$$x^2+1\equiv 0 \pmod n$$
which allows to compute A304651 and eventually A175341.
f=(n,k=N=n*n)=>N&&4*(--k*k%N>N-2)+f(n,k||--N)
-1 thanks to @ceilingcat
The recursion is convenient in JS but otherwise really pointless. It is replaced with a single loop below.
k,N;f(n){for(k=N=n*n,n=0;N;k=k?:--N)n+=--k*k%N>N-2;k=4*n;}
f(m,r,n,x){for(r=n=0;n++<m*m;)for(x=n;x--;)r+=x*x%n>n-2;m=r*4;}
Port of @enzo's python answer (very surprised that it matches byte count with the python answer)
r4I~If[Abs@+##>r,Sign@r,#~#0~+##+#2~#0~+##]&~1
Counts edges of that star formed by the points in the first quadrant.
I~ &~1 initial edge: 1-I
If[Abs@+##>r, , ] can this edge be split?
#~#0~+##+#2~#0~+## yes: split the edge
Sign@r no: count if input≠0
4 * 4 quadrants
lambda m:4*sum(x*x%n>n-2for n in range(m*m+1)for x in range(n))
x*x%n>n-2 instead of (x*x+1)%n<1 saves 2 bytes
\$\endgroup\$
Commented
Feb 11 at 15:52
f[n_]=Sum[Boole[GCD[x,y]==1&&x^2+y^2<=n^2],{x,-n,n},{y,-n,n}]
=iferror(4*sum(map(sequence(1,A2+1,0),lambda(x,map(sequence(A2),lambda(y,(1=gcd(x,y))*(x^2+y^2<=A2^2)))))),0)
Put the radius in cell A2 and the formula in cell C2.
The formula creates a \$(n+1)×n\$ matrix for the upper right quadrant, excluding the \$x\$ axis (\$y ≠ 0\$). The matrix contains ones and zeros. The result is 4 times the sum of the matrix.
This would be much simpler to implement with an array formula, but unfortunately gcd() is an aggregating function that only gives one result per evaluation rather than a result matrix, so we need to test every lattice point separately.
iferror() be removed to reduce -11 bytes?
\$\endgroup\$
0, the formula would give #N/A, because sequence() errors out when its argument is less than 1.
\$\endgroup\$
Commented
Feb 11 at 18:48
(k=0;Do[k+=4Tr[1^PowerModList[-1,1/2,n]],{n,#^2}];k)&
Sum[4,{,#^2},{i,},{,,Mod[i^2,]+1}]&
ŒRṗ2²S>ɗÐḟ²g/€ċ1
A monadic Link that accepts the non-negative integer* radius and yields the count of coprime lattice points in or on the circle of that radius centred at the origin.
ŒRṗ2²S>ɗÐḟ²g/€ċ1 - Link: non-negative integer, r
ŒR - abs-range -> [-r..r]
ṗ2 - Cartesian power {2}
-> LatticePoints of the enclosing, axis-aligned square
Ðḟ - filter discard those {LatticePoints} for which:
ɗ ² - last three links as a dyad - f(LatticePoint, r^2)
² - square {each coordinate of LatticePoint}
S - sum {these}
> - {that} greater than {r^2}?
g/€ - reduce each {remaining LatticPoint} by GCD
ċ1 - {that} count occurrences of one
* Also works for floats, up to floating-point errors, since while ŒR implicitly floors its input no lattice point will be in or on the circle if one of its coordinates is further out.
f(n)=4\sum_{a=0}^n\sum_{b=1}^n0^{\gcd(a,b)-1}\{aa+bb<=nn,0\}
Try It On Desmos! - Prettified
I really feel like this can be golfed but I can't really think of anything at the moment. I also have this other version without the piecewise but it is 62 bytes:
f(n)=4∑_{a=0}^n∑_{b=1}^n0^{gcd(a,b)-1}sgn(sgn(nn-aa-bb)+1)
(Ÿn¬sãʒ¿}€O@O
Straight-forward modification (adding ʒ¿}€) of my 05AB1E answer for the related challenge.
Try it online or verify all test cases.
Explanation:
( # Negate the (implicit) input-integer
Ÿ # Push a list in the range [(implicit) input,-input]
n # Square each inner value
¬ # Push the first item (without popping the list), which is input²
s # Swap so the list is at the top again
ã # Cartesian power of 2 to get all possible pairs
ʒ } # Filter this list of pairs by:
¿ # Where the Greatest Common Divisor (gcd) of the pair is 1
# (note: only 1 is truthy in 05AB1E)
€O # Sum all remaining inner pairs together
# (note: the `€` is only for n=0, so [] remains [], instead of becoming 0)
@ # Check for each whether the input² is >= this value
O # Sum to get the amount of truthy values
# (which is output implicitly as result)
\(n)sum(sapply(1:n^2,\(a)4*sum(!((1:a)^2+1)%%a)))
Uses the same OEIS chain A000089 → A304651 → A175341 as in @Arnauld's answer.
×4/+≥⌵▽◰∩♭⊞⊃÷ℂ↘1.⇡+1.
Try on Uiua Pad! Takes \$r\$ as input and outputs the number of points
×4/+≥⌵▽◰∩♭⊞⊃÷ℂ↘1.⇡+1.
⇡+1. # push 0, 1, ... , r
↘1. # push 1, 2, ... , r
⊞ # make tables of each possible pair (a,b)...
⊃÷ℂ # with b/a and b+a*i
∩♭ # flatten both tables into lists
◰ # mask of unique quotients
▽ # apply mask to list of complex numbers
⌵ # magnitudes
≥ # test less than or equal to r
/+ # sum the number of such points
×4 # multiply by 4
💎
Created with the help of Luminespire.
.+
*_,$&*_,$&*
Lw`_+,_+,_*(?=_)
Am`^(__+)\1*,_+,\1*$
_+
$.&*$&
Cm`^(_+),\1(_*)(_*),\2$
.+
$.(4**
Try it online! Link includes test cases. Explanation:
.+
*_,$&*_,$&*
Create a list [r, r, r] (in unary).
Lw`_+,_+,_*(?=_)
Create r² lists [x=r..1, r, y=0..r-1].
Am`^(__+)\1*,_+,\1*$
Keep only the lists where x and y are coprime. (This particular implementation of the test assumes x is positive.)
_+
$.&*$&
Square x, r and y.
Cm`^(_+),\1(_*)(_*),\2$
Count (in decimal) the number of lists where x²+y²<=r².
.+
$.(4**
Multiply by 4.
Ｉ×⁴ΣＥ⊕ＸＮ²№Ｅι﹪⊕Ｘλ²ι⁰
Try it online! Link is to verbose version of code. Explanation: Uses the formulae from OEIS, A175341(n)=A304651(n²)=4ΣA000089(n²).
Ｎ Input `n` as an integer
Ｘ Raised to power
² Literal integer `2`
⊕ Incremented
Ｅ Map over implicit range
№ Count of
⁰ Literal integer `0` in
ι Current value
Ｅ Map over implicit range
λ Inner value
Ｘ Raised to power
² Literal integer `2`
⊕ Incremented
﹪ Modulo
ι Current value
Σ Take the sum
× Times
⁴ Literal integer `4`
Ｉ Cast to string
Implicitly print
Note that the newer version of Charcoal on ATO allows you to vectorise the inner loop making it slightly more efficient, although the byte count is the same:
Ｉ×⁴ΣＥ⊕ＸＮ²№﹪⊕Ｘ…⁰ι²ι⁰
Attempt This Online! Link is to verbose version of code.
+/{(1=∨/⍵)∧0≥-/2⌽∊2*⍨r⍵}¨,∘.,⍨r..-r←⎕
test:
+/{(1=∨/⍵)∧0≥-/2⌽∊2*⍨r⍵}¨,∘.,⍨r..-r←⎕
⎕:
10
192
+/{(1=∨/⍵)∧0≥-/2⌽∊2*⍨r⍵}¨,∘.,⍨r..-r←⎕
⎕:
0
0
+/{(1=∨/⍵)∧0≥-/2⌽∊2*⍨r⍵}¨,∘.,⍨r..-r←⎕
⎕:
5
48
5.7, but the post does not clarify this. \$\endgroup\$