12
\$\begingroup\$

Challenge

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.

primitive_circle

Input

Radius \$r \in \mathbb{Z}^+\$

Output

Number of coprime points

Test Cases

Taken from sequence A175341 in the OEIS.

Radius Number of coprime points
0 0
1 4
2 8
3 16
4 32
5 48
\$\endgroup\$
7
  • \$\begingroup\$ It looks from your test cases that input may be considered to only be non-negative integers, but you don't explicitly state that - could you please confirm? \$\endgroup\$ Feb 11 at 18:05
  • \$\begingroup\$ @JonathanAllan I truly hope that there is no circle with negative radius \$\endgroup\$
    – enzo
    Feb 11 at 20:30
  • 1
    \$\begingroup\$ @enzo, I'm not sure if your comment was just a bit of fun - my point was that it looks from the test cases like we don't need to handle an input like 5.7, but the post does not clarify this. \$\endgroup\$ Feb 11 at 21:10
  • 1
    \$\begingroup\$ @JonathanAllan Yes! I was only joking about the fact that by explicitly saying "non-negative", it could look like that you were interested in negative integers as well. But the focus here is the numeric domain indeed, very interesting observation. \$\endgroup\$
    – enzo
    Feb 11 at 22:03
  • \$\begingroup\$ @JonathanAllan: I'm not sure decimal values make sense to begin with when considering prime factorization (which is inherently required to check if numbers are coprime). Prime numbers only exist within the space of positive integers. \$\endgroup\$
    – Flater
    Feb 13 at 4:55

16 Answers 16

10
\$\begingroup\$

JavaScript (ES6), 45 bytes

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)

Try it online!


C (gcc), 58 bytes

-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;}

Try it online!

\$\endgroup\$
0
5
\$\begingroup\$

C (gcc), 63 bytes

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;}

Try it online!

Port of @enzo's python answer (very surprised that it matches byte count with the python answer)

\$\endgroup\$
5
\$\begingroup\$

Wolfram Language (Mathematica), 49 bytes

r4I~If[Abs@+##>r,Sign@r,#~#0~+##+#2~#0~+##]&~1

Try it online!

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
\$\endgroup\$
4
\$\begingroup\$

Python 3, 70 63 bytes

lambda m:4*sum(x*x%n>n-2for n in range(m*m+1)for x in range(n))

Try it online!

  • -7 bytes thank to Mukundan314 by removing the double sum and parenthesis
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 65 bytes \$\endgroup\$ Feb 11 at 15:42
  • \$\begingroup\$ @Mukundan314 Yeah, no need for the double sum. Thanks! \$\endgroup\$
    – enzo
    Feb 11 at 15:46
  • 1
    \$\begingroup\$ doing x*x%n>n-2 instead of (x*x+1)%n<1 saves 2 bytes \$\endgroup\$ Feb 11 at 15:52
3
\$\begingroup\$

Wolfram Language (Mathematica), 61 bytes

f[n_]=Sum[Boole[GCD[x,y]==1&&x^2+y^2<=n^2],{x,-n,n},{y,-n,n}]

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 50 bytes \$\endgroup\$
    – att
    Feb 12 at 0:25
3
\$\begingroup\$

Google Sheets, 109 bytes

=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.

coprime lattice points.png

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.

\$\endgroup\$
2
  • \$\begingroup\$ can the iferror() be removed to reduce -11 bytes? \$\endgroup\$
    – vengy
    Feb 11 at 18:34
  • 1
    \$\begingroup\$ Sure, but when radius is 0, the formula would give #N/A, because sequence() errors out when its argument is less than 1. \$\endgroup\$ Feb 11 at 18:48
2
\$\begingroup\$

Jelly, 16 bytes

Œ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.

Try it online!

How?

Œ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.

\$\endgroup\$
2
\$\begingroup\$

PARI/GP, 54 bytes

f(n)=sum(x=-n,n,sum(y=-n,n,gcd(x,y)==1&&x^2+y^2<=n^2))

Attempt This Online!

\$\endgroup\$
2
\$\begingroup\$

Desmos, 61 bytes


f(n)=4\sum_{a=0}^n\sum_{b=1}^n0^{\gcd(a,b)-1}\{aa+bb<=nn,0\}

Try It On Desmos!

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)
\$\endgroup\$
2
  • \$\begingroup\$ The Desmos function looks nice! $$f(n) = 4\sum_{a=0}^{n}\sum_{b=1}^{n}0^{\gcd\left(a,b\right)-1}\left\{aa+bb\le nn,0\right\}$$ \$\endgroup\$
    – vengy
    Feb 12 at 15:37
  • \$\begingroup\$ @vengy Thanks! Though I strongly suspect there is a golfier formula than the one I came up with; I just can't seem to think of any golfs at the moment. \$\endgroup\$
    – Aiden Chow
    Feb 13 at 9:17
2
\$\begingroup\$

05AB1E, 13 bytes

(Ÿ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)

Try it online with step-by-step output lines.

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 53 bytes

(k=0;Do[k+=4Tr[1^PowerModList[-1,1/2,n]],{n,#^2}];k)&

Try it online!

\$\endgroup\$
2
\$\begingroup\$

R, 49 bytes

\(n)sum(sapply(1:n^2,\(a)4*sum(!((1:a)^2+1)%%a)))

Attempt This Online!

Uses the same OEIS chain A000089A304651A175341 as in @Arnauld's answer.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the OEIS chain! \$\endgroup\$
    – vengy
    Feb 12 at 13:53
2
\$\begingroup\$

Uiua 0.9.0, 21 bytes SBCS

×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.

\$\endgroup\$
1
\$\begingroup\$

Retina, 96 bytes

.+
*_,$&*_,$&*
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 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.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 19 bytes

I×⁴ΣE⊕XN²№Eι﹪⊕Xλ²ι⁰

Try it online! Link is to verbose version of code. Explanation: Uses the formulae from OEIS, A175341(n)=A304651(n²)=4ΣA000089(n²).

       N            Input `n` as an integer
      X             Raised to power
        ²           Literal integer `2`
     ⊕              Incremented
    E               Map over implicit range
         №          Count of
                  ⁰ Literal integer `0` in
           ι        Current value
          E         Map over implicit range
               λ    Inner value
              X     Raised to power
                ²   Literal integer `2`
             ⊕      Incremented
            ﹪       Modulo
                 ι  Current value
   Σ                Take the sum
 ×                  Times
  ⁴                 Literal integer `4`
I                   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:

I×⁴ΣE⊕XN²№﹪⊕X…⁰ι²ι⁰

Attempt This Online! Link is to verbose version of code.

\$\endgroup\$
1
\$\begingroup\$

APL(NARS), 37 chars

+/{(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
\$\endgroup\$

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.