Prime Coordinates
I need to figure out the unique angles created by the coordinates in a 2d grid of a given size. (E.g. 200x200)
Starting from 3 and working up, I realized that I could eliminate any coordinate that did not have at least one prime. (2,4. 100,340 etc). That doesn't guarantee that the remaining ones are unique. For example 3,9 would not be.
Is there a concept of 'prime coordinates' ?
....or possibility an algorithm that determines if a given coordinate is 'prime' (or whatever the correct term would be). It would describes a unique angle that cannot be described by a simpler coordinate. (3.9 would not be because 1,3 would be a simpler way)
My current thought is to check if the coordinate pair is a GCD pair, but that might be more time consuming than necessary.
Thoughts?
Edit. I suspect I mean LCD
Posted Sep 25, 2017, 12:39 AM UTC · edited
The term you're looking for is "relatively prime", meaning they have no shared factor. Checking GCDs is the proper method, and can be done quickly.
Thanks u/ApproxKnowledgeSite, I'll see where that rabbit hole leads.
FYI, when you reply to someone they get a notification regardless of whether you explicitly write out their username.
The way to find out if two numbers are relatively prime is to follow the Euclidean algorithm. If the result is 1, then you have relatively prime numbers.
But if you’re trying to enumerate all of the possible ratios up to a certain size, you can also do something like following the Stern–Brocot tree or looking at the appropriate Farey sequence.
With numbers as small as 200 by 200, you can also just find the angle for every ratio using brute force, and then eliminate duplicates at the end.
How is it that you intend to represent your angles? (And what are you ultimately doing this for?) For many purposes I recommend using the stereographic projection (half-angle tangent) representation rather than angle measure per se. So for a given pair (x, y), that would be the ratio y / [√(x^(2) + y^(2)) + x] = [√(x^(2) + y^(2)) – x] / y. If x and y are sides of a Pythagorean triangle then this will be a rational number.
My current approach is to first create a list of primes using the Sieve of E.
Then I enumerate through all cords in my grid (brute force, threaded)
If one of the coordinates is prime it passes. If not it is excluded.
Then I check its modulus. If 0 then I exclude it.
There separate calcs to deal with 0, 1 & 2 and then 0 coord pairs and same # pairs are excluded.
If the coord passes then I am calculating and saving the associated angle along with some other cached calcs (cos, sin, etc).
The grid is defined by integers -200 to +200. I think i can reduce that to 0 to +200 but that is down the road.
This is for a comp program and the input data is a bunch of line segments. I compare each against my grid angle list of objects to find the closest angle. These angles are stored as radians along with the raw data and then used later in the program.
I am going to look into your links. My brief glance at them gave me the impression that it is different than anything I've done before so I'll get to flex my brain.
Thank you.
You’re doing a nice job working on this for yourself, but that is not a complete method. 14/15 are relatively prime but neither is prime itself.
The cosine and sine are just the normalized coordinates. That is, (x / √(x^(2) + y^(2)), y / √(x^(2) + y^(2))). If your programming language supports complex numbers, you might consider just saving this as one complex number ẑ = (x + iy) / √(x^(2) + y^(2)) , and skip saving the angle measure, cosine, or sine separately. If you need the angle measure (in radians) later, you can just take the imaginary part of the logarithm of this complex number, i.e.
θ = imag(log(ẑ)) = atan2(imag(ẑ), real(ẑ))
What's the broader purpose of the program? Where are the line segments from, and what do you do with the angles later? Why do you want angles from an integer grid like this?