for-128-x-127-and-127-y-128-where-x-y-Z-Point-P-x-y-is-a-point-on-the-cartesian-plane-From-the-origin-angle-is-made-counter-clockwise-with-the-positive-x-axis-1-How-many-uniqu

Tinku Tara June 3, 2023 Algebra 0 Comments

Facebook Tweet Pin

Question Number 12883 by FilupS last updated on 05/May/17

for −128≤x≤127 and −127≤y≤128 where x,y∈Z Point P(x,y) is a point on the cartesian plane. From the origin, angle θ is made counter −clockwise with the positive x−axis. (1) How many unique angles θ exist if x,y∈P? (2) Furthermore, how many unique angles θ exist for the full range of x,y∈Z?

for - 128 ⩽ x ⩽ 127

and - 127 ⩽ y ⩽ 128

where x, y \in Z

Point P (x, y) is a point on the

cartesian plane .

From the origin, angle θ is made counter

- clockwise with the positive x - axis .

(1) How many unique angles θ exist

if x, y \in P ?

(2) Furthermore, how many unique

angles θ exist for the full range of x, y \in Z ?

Answered by mrW1 last updated on 10/May/17

This is an interesting question. We don′t neet to treat the case when the points lie on the x− or y−axis, the angles are 0° (x>0, y=0) 90° (x=0, y>0) 180° (x<0, y=0) 270° (x=0, y<0) Let′s begin with the case when the points lie in the first quadrant. x=i ∈ P, y=j ∈ P 1≤i≤m 1≤j≤n The angle θ for P(x,y) is defined by tan θ = (y/x)=(j/i) The number of unique angles is the number of unique values of (j/i) with 1≤i≤n and 1≤j≤m. There are m×n points, we have also m×n values of (j/i), but some of them are not unique, e.g. points (2,3), (4,6) have the same angle θ, since (3/2)=(6/4). To find the number of unique values of (j/i), we should simplify (j/i) to ((j′)/(i′)) with i′ = ((LCM(i,j))/j) and j′ = ((LCM(i,j))/i), since (j/i)=((LCM(i,j)×j)/(LCM(i,j)×i))=(((LCM(i,j))/i)/((LCM(i,j))/j))=((j′)/(i′)) e.g. for point (2,3): LCM(2,3)=6, i′=(6/3)=2, j′=(6/2)=3, (j/i)=((j′)/(i′))=(3/2) and for point (4,6): LCM(4,6)=12, i′=((12)/6)=2, j′=((12)/4)=3, (j/i)=((j′)/(i′))=(3/2) An other way to reduce the fraction (j/i) to ((j′)/(i′)) is: i′=(i/(GCD(i,j))) and j′=(j/(GCD(i,j))) e.g. for point (2,3): GCD(2,3)=1, i′=(2/1)=2, j′=(3/1)=3, (j/i)=((j′)/(i′))=(3/2) and for point (4,6): GCD(4,6)=2, i′=(4/2)=2, j′=(6/2)=3, (j/i)=((j′)/(i′))=(3/2) For all points (i,j) with 1≤i≤m and 1≤j≤n, we can construct m×n values of (j/i)=((j′)/(i′)). Now we only need to count how many of these values are unique. It is difficult to give a general formula for calculating the number of unique values ((j′)/(i′)), but for concrete numbers m and n, we can easily get the result with help of Excel. For m=10, n=20, for example, the result is 127 unique angles, see fig. in comment. For m=127, and n=128, the result is 9979 unique angles. But the table in this case is too big to be shown here.

T h i s i s a n i n t e r e s t i n g q u e s t i o n .

W e {d o n}^{'} t n e e t t o t r e a t t h e c a s e w h e n

t h e p o i n t s l i e o n t h e x - o r y - a x i s,

t h e a n g l e s a r e

0 ° (x > 0, y = 0)

90 ° (x = 0, y > 0)

180 ° (x < 0, y = 0)

270 ° (x = 0, y < 0)

{L e t}^{'} s b e g i n w i t h t h e c a s e w h e n t h e

p o i n t s l i e i n t h e f i r s t q u a d r a n t .

x = i \in P, y = j \in P

1 ⩽ i ⩽ m

1 ⩽ j ⩽ n

T h e a n g l e θ f o r P (x, y) i s d e f i n e d b y

\tan θ = \frac{y}{x} = \frac{j}{i}

T h e n u m b e r o f u n i q u e a n g l e s i s

t h e n u m b e r o f u n i q u e v a l u e s o f

\frac{j}{i} w i t h 1 ⩽ i ⩽ n a n d 1 ⩽ j ⩽ m .

T h e r e a r e m \times n p o i n t s, w e h a v e a l s o

m \times n v a l u e s o f \frac{j}{i}, b u t s o m e o f t h e m

a r e n o t u n i q u e, e . g . p o i n t s (2, 3), (4, 6)

h a v e t h e s a m e a n g l e θ, s i n c e \frac{3}{2} = \frac{6}{4} .

T o f i n d t h e n u m b e r o f u n i q u e v a l u e s

o f \frac{j}{i}, w e s h o u l d s i m p l i f y \frac{j}{i} t o \frac{j^{'}}{i^{'}} w i t h

i^{'} = \frac{L C M (i, j)}{j} a n d j^{'} = \frac{L C M (i, j)}{i}, s i n c e

\frac{j}{i} = \frac{L C M (i, j) \times j}{L C M (i, j) \times i} = \frac{\frac{L C M (i, j)}{i}}{\frac{L C M (i, j)}{j}} = \frac{j^{'}}{i^{'}}

e . g . f o r p o i n t (2, 3) : L C M (2, 3) = 6,

i^{'} = \frac{6}{3} = 2, j^{'} = \frac{6}{2} = 3, \frac{j}{i} = \frac{j^{'}}{i^{'}} = \frac{3}{2}

a n d f o r p o i n t (4, 6) : L C M (4, 6) = 12,

i^{'} = \frac{12}{6} = 2, j^{'} = \frac{12}{4} = 3, \frac{j}{i} = \frac{j^{'}}{i^{'}} = \frac{3}{2}

A n o t h e r w a y t o r e d u c e t h e f r a c t i o n \frac{j}{i}

t o \frac{j^{'}}{i^{'}} i s :

i^{'} = \frac{i}{G C D (i, j)} a n d j^{'} = \frac{j}{G C D (i, j)}

e . g . f o r p o i n t (2, 3) : G C D (2, 3) = 1,

i^{'} = \frac{2}{1} = 2, j^{'} = \frac{3}{1} = 3, \frac{j}{i} = \frac{j^{'}}{i^{'}} = \frac{3}{2}

a n d f o r p o i n t (4, 6) : G C D (4, 6) = 2,

i^{'} = \frac{4}{2} = 2, j^{'} = \frac{6}{2} = 3, \frac{j}{i} = \frac{j^{'}}{i^{'}} = \frac{3}{2}

F o r a l l p o i n t s (i, j) w i t h 1 ⩽ i ⩽ m a n d

1 ⩽ j ⩽ n, w e c a n c o n s t r u c t m \times n v a l u e s

o f \frac{j}{i} = \frac{j^{'}}{i^{'}} .

N o w w e o n l y n e e d t o c o u n t h o w m a n y

o f t h e s e v a l u e s a r e u n i q u e .

I t i s d i f f i c u l t t o g i v e a g e n e r a l f o r m u l a

f o r c a l c u l a t i n g t h e n u m b e r o f u n i q u e

v a l u e s \frac{j^{'}}{i^{'}}, b u t f o r c o n c r e t e n u m b e r s

m a n d n, w e c a n e a s i l y g e t t h e r e s u l t

w i t h h e l p o f E x c e l .

F o r m = 10, n = 20, f o r e x a m p l e, t h e

r e s u l t i s 127 u n i q u e a n g l e s, s e e f i g .

i n c o m m e n t .

F o r m = 127, a n d n = 128, t h e r e s u l t

i s 9979 u n i q u e a n g l e s . B u t t h e t a b l e i n

t h i s c a s e i s t o o b i g t o b e s h o w n h e r e .

Commented by mrW1 last updated on 07/May/17

Commented by mrW1 last updated on 07/May/17

this picture shows which (j/i) value is unique and which is duplicate (yellow).

t h i s p i c t u r e s h o w s w h i c h \frac{j}{i} v a l u e i s u n i q u e

a n d w h i c h i s d u p l i c a t e (y e l l o w) .

Commented by FilupS last updated on 07/May/17

This is amazing! Thank you!

This is amazing! Thank you!

Commented by mrW1 last updated on 11/May/17

Here the explanation how it works. We have: (j/i)=((j′)/(i′)) with i′=((LCM(i,j))/j) [or (i/(GCD(i,j)))] j′=((LCM(i,j))/i) [or (j/(GCD(i,j)))] For each point (i,j) it can be one of following two cases: Case 1: i′=i and j′=j ⇒point (i,j) descripts a new angle. e.g. point (2,7): LCM(2,7)=14 i′=((14)/7)=2=i j′=((14)/2)=7=j ⇒point (2,7) has a new angle. Case 2: i′<i and j′<j ⇒point (i,j) descripts no new angle, its angle is the same as for point(i′,j′). e.g. point (8,20): LCM(8,20)=40 i′=((40)/(20))=2<i=8 j′=((40)/8)=5<j=20 ⇒point (8,20) has no new angle, since it has the same angle as point (2,5). Case 1 means also GCD(i,j)=1. Case 2 means also GCD(i,j)>1.

H e r e t h e e x p l a n a t i o n h o w i t w o r k s .

W e h a v e :

\frac{j}{i} = \frac{j^{'}}{i^{'}}

w i t h i^{'} = \frac{L C M (i, j)}{j} [o r \frac{i}{G C D (i, j)}]

j^{'} = \frac{L C M (i, j)}{i} [o r \frac{j}{G C D (i, j)}]

F o r e a c h p o i n t (i, j) i t c a n b e o n e o f

f o l l o w i n g t w o c a s e s :

C a s e 1 :

i^{'} = i a n d j^{'} = j

\Rightarrow p o i n t (i, j) d e s c r i p t s a n e w a n g l e .

e . g . p o i n t (2, 7) :

L C M (2, 7) = 14

i^{'} = \frac{14}{7} = 2 = i

j^{'} = \frac{14}{2} = 7 = j

\Rightarrow p o i n t (2, 7) h a s a n e w a n g l e .

C a s e 2 :

i^{'} < i a n d j^{'} < j

\Rightarrow p o i n t (i, j) d e s c r i p t s n o n e w a n g l e,

i t s a n g l e i s t h e s a m e a s f o r p o i n t (i^{'}, j^{'}) .

e . g . p o i n t (8, 20) :

L C M (8, 20) = 40

i^{'} = \frac{40}{20} = 2 < i = 8

j^{'} = \frac{40}{8} = 5 < j = 20

\Rightarrow p o i n t (8, 20) h a s n o n e w a n g l e, s i n c e

i t h a s t h e s a m e a n g l e a s p o i n t (2, 5) .

C a s e 1 m e a n s a l s o G C D (i, j) = 1 .

C a s e 2 m e a n s a l s o G C D (i, j) > 1 .

Commented by mrW1 last updated on 08/May/17

Commented by mrW1 last updated on 08/May/17

Commented by mrW1 last updated on 09/May/17

Now we create a table with m columns (for i=1 to m) and n rows (for j=1 to n). We give the cell (i,j) the value 1 if it is case 1 and the value 0 if it is case 2. In Excel you can do this by entering following formula into the first cell, let′s say it is B5: =1−SIGN(GCD($A5,B$4)−1) and then copy this cell to all cells of the table. In this way we get a table like this:

N o w w e c r e a t e a t a b l e w i t h m c o l u m n s

(f o r i = 1 t o m) a n d n r o w s (f o r j = 1 t o n) .

W e g i v e t h e c e l l (i, j) t h e v a l u e 1 i f i t i s

c a s e 1 a n d t h e v a l u e 0 i f i t i s c a s e 2 .

I n E x c e l y o u c a n d o t h i s b y e n t e r i n g

f o l l o w i n g f o r m u l a i n t o t h e f i r s t c e l l,

{l e t}^{'} s s a y i t i s B 5 :

= 1 - S I G N (G C D ($ A 5, B $ 4) - 1)

a n d t h e n c o p y t h i s c e l l t o a l l c e l l s o f t h e

t a b l e .

I n t h i s w a y w e g e t a t a b l e l i k e t h i s :

Commented by mrW1 last updated on 08/May/17

Commented by mrW1 last updated on 09/May/17

Cells with value 1 have unique (j/i) and cells with value 0 are duplicates. The sum of all values in this table is the number of unique angles for 1≤i≤m and 1≤j≤n.

C e l l s w i t h v a l u e 1 h a v e u n i q u e \frac{j}{i} a n d

c e l l s w i t h v a l u e 0 a r e d u p l i c a t e s .

T h e s u m o f a l l v a l u e s i n t h i s t a b l e i s

t h e n u m b e r o f u n i q u e a n g l e s f o r

1 ⩽ i ⩽ m a n d 1 ⩽ j ⩽ n .

Commented by mrW1 last updated on 09/May/17

From this table you can easily get the number of unique angles for any number of points, e.g. 7×22 points.

F r o m t h i s t a b l e y o u c a n e a s i l y g e t t h e

n u m b e r o f u n i q u e a n g l e s f o r a n y

n u m b e r o f p o i n t s, e . g . 7 \times 22 p o i n t s .

Commented by mrW1 last updated on 09/May/17

Commented by mrW1 last updated on 09/May/17

The big question now is: is it possible to find a formula to calculate the number of unique angles for m×n points?

T h e b i g q u e s t i o n n o w i s :

i s i t p o s s i b l e t o f i n d a f o r m u l a t o

c a l c u l a t e t h e n u m b e r o f u n i q u e a n g l e s

f o r m \times n p o i n t s ?

Commented by FilupS last updated on 09/May/17

This is fascinating!

This is fascinating!

Commented by FilupS last updated on 09/May/17

Creating a formula for LCM(i,j) wouldn′t be very straight forward. It would be extremely difficult and possibly involve prime number distributions, which is going into number theory and the prime numbers

Creating a formula for L C M (i, j)

{wouldn}^{'} t be very straight forward .

It would be extremely difficult and possibly

involve prime number distributions,

which is going into number theory and

the prime numbers

Commented by FilupS last updated on 09/May/17

The best function I can think of would be something like (correct if wrong): i′=((LCM(i,j))/j) j′=((LCM(i,j))/i) δ_(ij) = { ((1 ⇔ i′=i ∧ j′=j)),((0 ⇔ i′<i ∧ j′<j)) :} Φ=Σ_i ^m Σ_j ^n δ_(ij) Φ=total unique angles

The best function I can think of would

be something like (correct if wrong) :

i^{'} = \frac{LCM (i, j)}{j} j^{'} = \frac{LCM (i, j)}{i}

δ_{i j} = {\begin{cases} 1 \Leftrightarrow i^{'} = i \land j^{'} = j \\ 0 \Leftrightarrow i^{'} < i \land j^{'} < j \end{cases}

Φ = \underset{i}{\sum^{m}} \underset{j}{\sum^{n}} δ_{i j}

Φ = total unique angles

Commented by mrW1 last updated on 09/May/17

I agree with you. We can write: δ_(ij) =1−sign(i−((LCM(i,j))/j)) ⇒Φ=Σ_(i=1) ^m Σ_(j=1) ^n δ_(ij) ⇒Φ=mn−Σ_(i=1) ^m Σ_(j=1) ^n sign(i−((LCM(i,j))/j))

I a g r e e w i t h y o u .

W e c a n w r i t e :

δ_{i j} = 1 - s i g n (i - \frac{L C M (i, j)}{j})

\Rightarrow Φ = \underset{i = 1}{\sum^{m}} \underset{j = 1}{\sum^{n}} δ_{i j}

\Rightarrow Φ = m n - \underset{i = 1}{\sum^{m}} \underset{j = 1}{\sum^{n}} s i g n (i - \frac{L C M (i, j)}{j})

Commented by FilupS last updated on 09/May/17

I think thats the best solution!

I think thats the best solution!

Commented by mrW1 last updated on 09/May/17

An other simple formula is: δ_(ij) =1−sign(GCD(i,j)−1) Φ=mn−Σ_(i=1) ^m Σ_(j=1) ^n sign(GCD(i,j)−1)

A n o t h e r s i m p l e f o r m u l a i s :

δ_{i j} = 1 - s i g n (G C D (i, j) - 1)

Φ = m n - \underset{i = 1}{\sum^{m}} \underset{j = 1}{\sum^{n}} s i g n (G C D (i, j) - 1)

Commented by FilupS last updated on 09/May/17

can you explain how you got this?

can you explain how you got this ?

Commented by mrW1 last updated on 10/May/17

(j/i)=((j′)/(i′))=((j/(GCD(i,j)))/(i/(GCD(i,j)))) when i′=i and j′=j, it means (j/i) can not be simplified any more, i.e. GCD(i,j)=1. E.g. for point (2,7): GCD(2,7)=1, (7/2) is a fraction which is already simplified to lowest terms. when i′<i and j′<j, it means (j/i) can be simplified further, i.e. GCD(i,j)>1. E.g. for point (8,20): GCD(8,20)=4, ((20)/8) can be simplified to ((20/4)/(8/4))=(5/2). if GCD(i,j)=1, ⇒1−sign(GCD(i,j)−1)=1 ⇒ unique if GCD(i,j)>1, ⇒1−sign(GCD(i,j)−1)=0,⇒ duplicate

\frac{j}{i} = \frac{j^{'}}{i^{'}} = \frac{\frac{j}{G C D (i, j)}}{\frac{i}{G C D (i, j)}}

w h e n i^{'} = i a n d j^{'} = j, i t m e a n s \frac{j}{i} c a n

n o t b e s i m p l i f i e d a n y m o r e, i . e .

G C D (i, j) = 1 . E . g . f o r p o i n t (2, 7) :

G C D (2, 7) = 1, \frac{7}{2} i s a f r a c t i o n w h i c h

i s a l r e a d y s i m p l i f i e d t o l o w e s t t e r m s .

w h e n i^{'} < i a n d j^{'} < j, i t m e a n s \frac{j}{i} c a n

b e s i m p l i f i e d f u r t h e r, i . e . G C D (i, j) > 1 .

E . g . f o r p o i n t (8, 20) : G C D (8, 20) = 4,

\frac{20}{8} c a n b e s i m p l i f i e d t o \frac{20 / 4}{8 / 4} = \frac{5}{2} .

i f G C D (i, j) = 1,

\Rightarrow 1 - s i g n (G C D (i, j) - 1) = 1 \Rightarrow u n i q u e

i f G C D (i, j) > 1,

\Rightarrow 1 - s i g n (G C D (i, j) - 1) = 0, \Rightarrow d u p l i c a t e

Commented by mrW1 last updated on 10/May/17

I didn′t expect that the solution could be expressed in such a simple formula, eventhough it is no formula with which one can directly get the result. Thank you for this interesting and challenging question. To solve it has made a lot of fun.

I {d i d n}^{'} t e x p e c t t h a t t h e s o l u t i o n c o u l d b e

e x p r e s s e d i n s u c h a s i m p l e f o r m u l a,

e v e n t h o u g h i t i s n o f o r m u l a w i t h

w h i c h o n e c a n d i r e c t l y g e t t h e r e s u l t .

T h a n k y o u f o r t h i s i n t e r e s t i n g a n d

c h a l l e n g i n g q u e s t i o n . T o s o l v e i t

h a s m a d e a l o t o f f u n .

Commented by FilupS last updated on 10/May/17

Thank you for solving it

Thank you for solving it

Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Facebook Tweet Pin

Leave a Reply Cancel reply