# Challenge

Create a program that outputs a square grid showing visible and non-visible points $$\(x, y)\$$ from the origin based on their greatest common divisor (GCD).

A point $$\(x, y)\$$ is considered visible from the origin $$\(0, 0)\$$ if the $$\\gcd(x, y) = 1\$$. Otherwise, it's non-visible.

Input

An integer $$\n\$$, representing the radius of the square grid from the origin along both $$\x\$$ and $$\y\$$ axes.

Output

A square grid centered at the origin, where each cell is:

• ". " (dot followed by a space) for a visible point
• "$$\\ \ \$$" (two spaces) for a non-visible point

# Examples

Length from the origin: n = 6

  .       .   .       .
.   . . . .   . . . .   .
.   .   .   .   .   .
. .   . .   . .   . .
.   .   .   .   .   .
. . . . . . . . . . . . .
.   .
. . . . . . . . . . . . .
.   .   .   .   .   .
. .   . .   . .   . .
.   .   .   .   .   .
.   . . . .   . . . .   .
.       .   .       .


Length from the origin: n = 5

  . . . .   . . . .
.   .   .   .   .   .
. .   . .   . .   . .
.   .   .   .   .   .
. . . . . . . . . . .
.   .
. . . . . . . . . . .
.   .   .   .   .   .
. .   . .   . .   . .
.   .   .   .   .   .
. . . .   . . . .


Length from the origin: n = 4

  .   .   .   .
.   . .   . .   .
.   .   .   .
. . . . . . . . .
.   .
. . . . . . . . .
.   .   .   .
.   . .   . .   .
.   .   .   .


Length from the origin: n = 3

  . .   . .
.   .   .   .
. . . . . . .
.   .
. . . . . . .
.   .   .   .
. .   . .


Length from the origin: n = 2

  .   .
. . . . .
.   .
. . . . .
.   .


Length from the origin: n = 1

. . .
.   .
. . .


# References

Visible Points in a Lattice

Visible Point -- from Wolfram MathWorld

Lattice points visible from the origin

• Is it necessary to output the trailing spaces on each line? Commented Mar 11 at 16:05
• Shouldn’t the lattice point (0, 0) a. k. a. the origin be marked, too? I mean it is “visible” from the origin. The line of sight has a length of zero, but this should not harm the mathematical conception of “visibility”, right? May we be allowed to mark or leave the origin unmarked at our discretion? Commented Mar 11 at 16:36
• Is it allowed to output with a different format (e.g. as a matrix, graphical output, etc.)? Commented Mar 11 at 23:29
• @wheatwizard, why remove the image from the post? The text in the first section now refers to four dashed line segments, but they're nowhere to be seen. Commented Mar 12 at 9:58
• @ilkkachu Unfortunately (potential) copyright infringement: The (most probable) source of the image does not indicate that the image may be re‑released under a CC‑By‑SA license here, nor did vengy disclose he/she is known as Austin, אבא, or Jasmine (the authors’ first names of the original source) in real life (thus a co‑owner of copyright). Commented Mar 12 at 13:37

# Jelly, 12 bytes

rNgþ=1ị⁾. G


Try It Online!

-3 bytes thanks to totallyhuman (-1 myself on top of this)

### Explanation

rNgþ=1ị⁾. G    Main Link
rN              [n, ..., -n]
gþ           Outer product table over GCD
=1         Check if equal to 1 (vectorizes)
ị⁾. G    Index into [".", " "] and display as grid

• 13 bytes. Palindromizing is expensive. Commented Mar 11 at 16:20
• @totallyhuman Oh neat, I didn't realize that'd work properly for negatives. I had a feeling bounce was inefficient but didn't know how else to do it; thanks! Commented Mar 11 at 16:32
• Thanks for making me feel stupid in turn with the rN. :P All these years and I still can't get the hang of this language... Commented Mar 11 at 16:41
• @totallyhuman lol, chain rules are hard can't blame you :P Commented Mar 11 at 16:48

-7 bytes thanks to Lynn.

f n|r<-[-n..n]=unlines[do x<-r;" . "!!min(gcd x y)2:" "|y<-r]


Try it online!

unlines can be dropped if a list of lines is okay.

• Some byte saves: f n|r<-[-n..n]=unlines[do x<-r;" . "!!min(gcd x y)2:" "|y<-r]
– lynn
Commented Mar 20 at 2:40
• @Lynn min! min!! I can't believe I spent that long trying to shorten that conditional and didn't think of min. Also interesting that do-notation is shorter here... Thanks! Commented Mar 20 at 3:19

# APL (Dyalog Unicode), 30 bytes SBCS

Assume ⎕io←0

{↑,⌿'. ' '  '[1≠∘.∨⍨⍵-⍳1+⍵+⍵]}


Try it on APLgolf!

{↑,⌿'. ' '  '[1≠∘.∨⍨⍵-⍳1+⍵+⍵]}
⍵-⍳1+⍵+⍵   ⍝ indices ⍵ ⍵-1 ⍵-2 ... 2-⍵ 1-⍵ -⍵
∘.∨⍨           ⍝ pairwise GCD
1≠               ⍝ is not 1
'. ' '  '[              ]  ⍝ Choose between strings '. ' and '  '.
↑,⌿                           ⍝ Combine the strings

• Nice! The output looks great! Commented Mar 11 at 15:58

# JavaScript (V8), 89 bytes

n=>{for(y=~n;y++-n;)print((g=(a,b=y)=>x-~n?b?g(b,a%b):(a*a-1?"  ":". ")+g(--x):"")(x=n))}


Try it online!

### Commented

n => {                  // n = input
for(                  // main loop:
y++ - n;            //   stop when y = n / increment y afterwards
)                     //
print(                // print the next line:
( g = (             //   g is a recursive function taking:
a,              //     an integer a
b = y           //     and an integer b initialized to y
) =>              //
x - ~n ?          //   if x is greater than -n - 1:
b ?             //     if b is not 0:
g(b, a % b)   //       do a recursive call with [a, b] = [b, a mod b]
:               //     else:
( a * a - 1 ? //       if a² is not equal to 1:
"  "      //         append two spaces
:           //       else:
". "      //         append a period and a space
) + g(--x)    //       decrement x and do a recursive call
:                 //   else:
""              //     stop
)(x = n)            //   initial call to g with a = x = n
)                     // end of print()
}                       //


# Ruby, 74 51 bytes

-23 (!) bytes thanks to Sisyphus

->n{a=-n..n
a.map{|y|a.map{" ."[2[_1.gcd y]]+" "}}}


Attempt This Online!

• double map is shorter than each_slice: Attempt This Online! Commented Mar 12 at 0:29
• @Sisyphus Thansks for the assist. That's a nice trick, indexing into 2's bits. Commented Mar 12 at 14:36

# C (gcc), 107 bytes

-8 bytes, thanks to ceilingcat

g(a,b){return b?g(b,a%b):a*a;}x,y;f(l){for(y=~l;y++<l;puts(""))for(x=~l;x++<l;)printf(g(x,y)-1?"  ":". ");}


Try it online!

# Python+Numpy+Pandas, 152 bytes

import numpy as np,pandas
def p(n):pandas.DataFrame([c for c in np.dstack(np.mgrid[-n:n+1,-n:n+1]).reshape(-1,2)if np.gcd(*c)==1]).plot.scatter(x=0,y=1)


Outputs a graphical plot (even though this isn't strictly the challenge, but when do you see Pandas in code golf?). Ex, p(3):

# Charcoal, 33 bytes

Ｅ⊕Ｎ⭆⊕ι§ .∧∨ιλ⬤…²⊕ι∨﹪ιν﹪λν‖Ｏ↗↑←ＵＥ¹


Try it online! Link is to verbose version of code. Explanation:

Ｅ⊕Ｎ⭆⊕ι§ .∧∨ιλ⬤…²⊕ι∨﹪ιν﹪λν


Draw one octant of the diagram.

‖Ｏ↗↑←


Reflect to complete the diagram. (The reflections are performed serially, so first the octant is reflected diagonally to create the quadrant, then the other two reflections complete the negative axes.)

ＵＥ¹


Space the .s horizontally.

## Pascal, 238 Bytes

This is a complete program as per ISO standard 7185 “Standard Pascal”.

program p(input,output);type Z=integer;var n,y:Z;function f(a,b:Z):Z;begin f:=a;if b>0 then f:=f(b,a mod b)end;begin read(n);n:=abs(n);for y:=-n to n do begin for n:=-n to n do write((' .')[ord(f(abs(n),abs(y))=1)+1],' ');writeLn end end.


Ungölfed:

program latticePointsVisibleFromOrigin(input, output);
const
mark = ' .';
type
Z = integer;
var
n, y: Z;
{ GreatestCommonDivisor for _non­negative_ _integers_ _only_. }
function greatestCommonDivisor(a, b: Z): Z;
begin
greatestCommonDivisor ≔ a;
if b > 0 then
begin
greatestCommonDivisor ≔ greatestCommonDivisor(b, a mod b)
end
end;
{ ─── main ────────────────────────────────────────────────── }
begin
n ≔ abs(n);

{ In Pascal for‑loop limits are evaluated (exactly) once. }
for y ≔ n downto −n do
begin
for n ≔ −n to n do
begin
{ +1 because in Pascal string indices are one‑based. }
write(output,
mark[ord(greatestCommonDivisor(abs(n), abs(y)) = 1) + 1],
' ')
end;
writeLn(output)
end
end.


# Scala 3, 148 bytes

A port of @Jordan's Ruby answer in Scala.

Golfed version. Attempt This Online!

n=>{val a=(-n to n);(for(x<-a;y<-a)yield(x,y)).map{case(x,y)=>if(BigInt(x).gcd(y)==1)". " else"  "}.grouped(n*2+1).foreach(r=> println(r.mkString))}


Ungolfed version. Attempt This Online!

object Main extends App {
def F(n: Int): Unit = {
val a = (-n to n).toList
val pairs = for (x <- a; y <- a) yield (x, y)
val pattern = pairs.map { case (x, y) => if (BigInt(x).gcd(y) == 1) ". " else "  " }
pattern.grouped(n * 2 + 1).foreach(row => println(row.mkString))
}

F(6)
}


# PARI/GP, 64 bytes

n->[print(concat([if(gcd(i,j)-1,"  ",". ")|j<-r]))|i<-r=[-n..n]]


Attempt This Online!

# TI-Basic, 65 bytes

Input N
For(I,~N,N
".
For(J,~N,N
Ans+sub(" .",1=gcd(abs(I),abs(J)),1)+"
End
Disp sub(Ans,2,2N+1
End


~ represents the negative sign. The fifth line ends with a space. The output may be cut off if the input is too large.

# UiuaSBCS, 31 bytes

⊏:" ."=1◌⊞⍢⊃◿∘±:↘1♭≡⊂0.⌵-⇡+1×2.


Try it!

⊏:" ."=1◌⊞⍢⊃◿∘±:↘1♭≡⊂0.⌵-⇡+1×2.
-⇡+1×2.  # [-n..n]
⌵         # abs
.          # duplicate
:↘1♭≡⊂0           # interleave zeros
⊞⍢⊃◿∘±                  # table by gcd
◌                        # pop
=1                         # where is it equal to one?
⊏:" ."                           # change to string


# 05AB1E, 13 bytes

(ŸÄDδ¿Θ»T„. ‡


Explanation:

(              # Negate the (implicit) input-integer
Ÿ             # Push a list in the range [(implicit) input, -input]
Ä            # Take the absolute value of each: [n,n-1,...,0,...,n-1,n]
Dδ¿         # Create a GCD-table of this list:
D           #  Duplicate the list:
δ          #  Pop both lists, and apply double-vectorized:
¿         #   Greatest Common Divisor
Θ        # Check which values are 1 (1 if 1; 0 otherwise)
»       # Join each inner list by spaces, and then each string by newlines
T      # Push 10
„.    # Push ". "
‡  # Transliterate all 1s to "."s and all 0s to spaces
# (after which the result is output implicitly)
`