Ask Your Question

Finding coprime integers near a lattice point

asked 2018-11-26 03:58:03 +0100

cihan gravatar image

I have a list $L$ of ordered pairs $(n,m)$ where $n$ and $m$ are integers. I would like to know which elements $(n,m)$ in $L$ satisfy the property that $\gcd(n+i,m+j) \neq 1$ for $i =-1,0,1$ and $j =-1,0,1.$ For example the point $(55,21)$ has this property since $[(55+i,21+j) ] = [(54,20),(54,21),(54,22),(55,20),(55,21),(55,22),(56,20),(56,21),(56,22)].$ I have tried the following : for (n,m) in L: for i in range(-1,2): for j in range(-1,2): if gcd(n+i,m+j)!=1: print(n,m) which returns any point with $gcd =1$ which is not what I want. Thanks very much for your help!

edit retag flag offensive close merge delete


I suppose you test only for (i,j) different from (0,0), otherwise (55,21) wouldn't be a solution.

logomath gravatar imagelogomath ( 2018-11-26 10:23:27 +0100 )edit

(1275, 1309) work even with (i,j)=(0,0)

logomath gravatar imagelogomath ( 2018-11-26 11:13:29 +0100 )edit

I am not quite sure what you mean, since $\gcd(1275,1309)=17$.

cihan gravatar imagecihan ( 2018-11-27 03:15:55 +0100 )edit

I mean that (1275,1309) is a solution for the same problem (with same notations as in my answer) with R=[(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)]

logomath gravatar imagelogomath ( 2018-11-27 05:33:29 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2018-11-26 10:39:12 +0100

logomath gravatar image

That seems to work:



L=[(n,m) for n in xsrange(2,N) for m in xsrange(n,N)];

v=[(n,m) for (n,m) in L if len([(i,j) for (i,j) in R if gcd(n+i,m+j)==1])==0];

print v

edit flag offensive delete link more


This works! Thanks!

cihan gravatar imagecihan ( 2018-11-27 03:16:34 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2018-11-26 03:58:03 +0100

Seen: 300 times

Last updated: Nov 26 '18