Question and Answers Forum

All Questions      Topic List

Algebra Questions

Previous in All Question      Next in All Question      

Previous in Algebra      Next in Algebra      

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?

$$\mathrm{for}\:\:\:\:\:−\mathrm{128}\leqslant{x}\leqslant\mathrm{127} \\ $$$$\mathrm{and}\:\:\:−\mathrm{127}\leqslant{y}\leqslant\mathrm{128} \\ $$$$\mathrm{where}\:\:\:{x},{y}\in\mathbb{Z} \\ $$$$\: \\ $$$$\mathrm{Point}\:{P}\left({x},{y}\right)\:\mathrm{is}\:\mathrm{a}\:\mathrm{point}\:\mathrm{on}\:\mathrm{the} \\ $$$$\mathrm{cartesian}\:\mathrm{plane}. \\ $$$$\: \\ $$$$\mathrm{From}\:\mathrm{the}\:\mathrm{origin},\:\mathrm{angle}\:\theta\:\mathrm{is}\:\mathrm{made}\:\mathrm{counter} \\ $$$$−\mathrm{clockwise}\:\mathrm{with}\:\mathrm{the}\:\mathrm{positive}\:{x}−\mathrm{axis}. \\ $$$$\: \\ $$$$\left(\mathrm{1}\right)\:\mathrm{How}\:\mathrm{many}\:\mathrm{unique}\:\mathrm{angles}\:\theta\:\mathrm{exist} \\ $$$$\mathrm{if}\:{x},{y}\in\mathbb{P}? \\ $$$$\left(\mathrm{2}\right)\:\mathrm{Furthermore},\:\mathrm{how}\:\mathrm{many}\:\mathrm{unique} \\ $$$$\mathrm{angles}\:\theta\:\mathrm{exist}\:\mathrm{for}\:\mathrm{the}\:\mathrm{full}\:\mathrm{range}\:\mathrm{of}\:{x},{y}\in\mathbb{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.

$${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} \\ $$$$\mathrm{0}°\:\left({x}>\mathrm{0},\:{y}=\mathrm{0}\right) \\ $$$$\mathrm{90}°\:\left({x}=\mathrm{0},\:{y}>\mathrm{0}\right) \\ $$$$\mathrm{180}°\:\left({x}<\mathrm{0},\:{y}=\mathrm{0}\right) \\ $$$$\mathrm{270}°\:\left({x}=\mathrm{0},\:{y}<\mathrm{0}\right) \\ $$$$ \\ $$$${Let}'{s}\:{begin}\:{with}\:{the}\:{case}\:{when}\:{the} \\ $$$${points}\:{lie}\:{in}\:{the}\:{first}\:{quadrant}. \\ $$$${x}={i}\:\in\:\mathbb{P},\:{y}={j}\:\in\:\mathbb{P} \\ $$$$\mathrm{1}\leqslant{i}\leqslant{m} \\ $$$$\mathrm{1}\leqslant{j}\leqslant{n} \\ $$$$ \\ $$$${The}\:{angle}\:\theta\:{for}\:{P}\left({x},{y}\right)\:{is}\:{defined}\:{by} \\ $$$$\mathrm{tan}\:\theta\:=\:\frac{{y}}{{x}}=\frac{{j}}{{i}} \\ $$$${The}\:{number}\:{of}\:{unique}\:{angles}\:{is} \\ $$$${the}\:{number}\:{of}\:{unique}\:{values}\:{of} \\ $$$$\frac{{j}}{{i}}\:{with}\:\mathrm{1}\leqslant{i}\leqslant{n}\:{and}\:\mathrm{1}\leqslant{j}\leqslant{m}. \\ $$$$ \\ $$$${There}\:{are}\:{m}×{n}\:{points},\:{we}\:{have}\:{also} \\ $$$${m}×{n}\:{values}\:{of}\:\frac{{j}}{{i}},\:{but}\:{some}\:{of}\:{them} \\ $$$${are}\:{not}\:{unique},\:{e}.{g}.\:{points}\:\left(\mathrm{2},\mathrm{3}\right),\:\left(\mathrm{4},\mathrm{6}\right) \\ $$$${have}\:{the}\:{same}\:{angle}\:\theta,\:{since}\:\frac{\mathrm{3}}{\mathrm{2}}=\frac{\mathrm{6}}{\mathrm{4}}. \\ $$$$ \\ $$$${To}\:{find}\:{the}\:{number}\:{of}\:{unique}\:{values} \\ $$$${of}\:\frac{{j}}{{i}},\:{we}\:{should}\:{simplify}\:\frac{{j}}{{i}}\:{to}\:\frac{{j}'}{{i}'}\:{with} \\ $$$${i}'\:=\:\frac{{LCM}\left({i},{j}\right)}{{j}}\:{and}\:{j}'\:=\:\frac{{LCM}\left({i},{j}\right)}{{i}},\:{since} \\ $$$$\frac{{j}}{{i}}=\frac{{LCM}\left({i},{j}\right)×{j}}{{LCM}\left({i},{j}\right)×{i}}=\frac{\frac{{LCM}\left({i},{j}\right)}{{i}}}{\frac{{LCM}\left({i},{j}\right)}{{j}}}=\frac{{j}'}{{i}'} \\ $$$$ \\ $$$${e}.{g}.\:{for}\:{point}\:\left(\mathrm{2},\mathrm{3}\right):\:{LCM}\left(\mathrm{2},\mathrm{3}\right)=\mathrm{6}, \\ $$$${i}'=\frac{\mathrm{6}}{\mathrm{3}}=\mathrm{2},\:{j}'=\frac{\mathrm{6}}{\mathrm{2}}=\mathrm{3},\:\frac{{j}}{{i}}=\frac{{j}'}{{i}'}=\frac{\mathrm{3}}{\mathrm{2}} \\ $$$${and}\:{for}\:{point}\:\left(\mathrm{4},\mathrm{6}\right):\:{LCM}\left(\mathrm{4},\mathrm{6}\right)=\mathrm{12}, \\ $$$${i}'=\frac{\mathrm{12}}{\mathrm{6}}=\mathrm{2},\:{j}'=\frac{\mathrm{12}}{\mathrm{4}}=\mathrm{3},\:\frac{{j}}{{i}}=\frac{{j}'}{{i}'}=\frac{\mathrm{3}}{\mathrm{2}} \\ $$$$ \\ $$$${An}\:{other}\:{way}\:{to}\:{reduce}\:{the}\:{fraction}\:\frac{{j}}{{i}} \\ $$$${to}\:\frac{{j}'}{{i}'}\:{is}: \\ $$$${i}'=\frac{{i}}{{GCD}\left({i},{j}\right)}\:{and}\:{j}'=\frac{{j}}{{GCD}\left({i},{j}\right)} \\ $$$${e}.{g}.\:{for}\:{point}\:\left(\mathrm{2},\mathrm{3}\right):\:{GCD}\left(\mathrm{2},\mathrm{3}\right)=\mathrm{1}, \\ $$$${i}'=\frac{\mathrm{2}}{\mathrm{1}}=\mathrm{2},\:{j}'=\frac{\mathrm{3}}{\mathrm{1}}=\mathrm{3},\:\frac{{j}}{{i}}=\frac{{j}'}{{i}'}=\frac{\mathrm{3}}{\mathrm{2}} \\ $$$${and}\:{for}\:{point}\:\left(\mathrm{4},\mathrm{6}\right):\:{GCD}\left(\mathrm{4},\mathrm{6}\right)=\mathrm{2}, \\ $$$${i}'=\frac{\mathrm{4}}{\mathrm{2}}=\mathrm{2},\:{j}'=\frac{\mathrm{6}}{\mathrm{2}}=\mathrm{3},\:\frac{{j}}{{i}}=\frac{{j}'}{{i}'}=\frac{\mathrm{3}}{\mathrm{2}} \\ $$$$ \\ $$$${For}\:{all}\:{points}\:\left({i},{j}\right)\:{with}\:\mathrm{1}\leqslant{i}\leqslant{m}\:{and} \\ $$$$\mathrm{1}\leqslant{j}\leqslant{n},\:{we}\:{can}\:{construct}\:{m}×{n}\:{values} \\ $$$${of}\:\frac{{j}}{{i}}=\frac{{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}\:\frac{{j}'}{{i}'},\:{but}\:{for}\:{concrete}\:{numbers} \\ $$$${m}\:{and}\:{n},\:{we}\:{can}\:{easily}\:{get}\:{the}\:{result} \\ $$$${with}\:{help}\:{of}\:{Excel}. \\ $$$$ \\ $$$${For}\:{m}=\mathrm{10},\:{n}=\mathrm{20},\:{for}\:{example},\:{the} \\ $$$${result}\:{is}\:\mathrm{127}\:{unique}\:{angles},\:{see}\:{fig}. \\ $$$${in}\:{comment}. \\ $$$$ \\ $$$${For}\:{m}=\mathrm{127},\:{and}\:{n}=\mathrm{128},\:{the}\:{result} \\ $$$${is}\:\mathrm{9979}\:{unique}\:{angles}.\:{But}\:{the}\:{table}\:{in} \\ $$$${this}\:{case}\:{is}\:{too}\:{big}\:{to}\:{be}\:{shown}\:{here}. \\ $$

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

$${this}\:{picture}\:{shows}\:{which}\:\frac{{j}}{{i}}\:{value}\:{is}\:{unique}\: \\ $$$${and}\:{which}\:{is}\:{duplicate}\:\left({yellow}\right). \\ $$

Commented by FilupS last updated on 07/May/17

This is amazing! Thank you!

$$\mathrm{This}\:\mathrm{is}\:\mathrm{amazing}!\:\mathrm{Thank}\:\mathrm{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.

$${Here}\:{the}\:{explanation}\:{how}\:{it}\:{works}. \\ $$$$ \\ $$$${We}\:{have}: \\ $$$$\frac{{j}}{{i}}=\frac{{j}'}{{i}'} \\ $$$${with}\:{i}'=\frac{{LCM}\left({i},{j}\right)}{{j}}\:\left[{or}\:\frac{{i}}{{GCD}\left({i},{j}\right)}\right] \\ $$$${j}'=\frac{{LCM}\left({i},{j}\right)}{{i}}\:\:\left[{or}\:\frac{{j}}{{GCD}\left({i},{j}\right)}\right] \\ $$$$ \\ $$$${For}\:{each}\:{point}\:\left({i},{j}\right)\:{it}\:{can}\:{be}\:{one}\:{of} \\ $$$${following}\:{two}\:{cases}: \\ $$$$ \\ $$$${Case}\:\mathrm{1}: \\ $$$${i}'={i}\:{and}\:{j}'={j} \\ $$$$\Rightarrow{point}\:\left({i},{j}\right)\:{descripts}\:{a}\:{new}\:{angle}. \\ $$$${e}.{g}.\:{point}\:\left(\mathrm{2},\mathrm{7}\right): \\ $$$${LCM}\left(\mathrm{2},\mathrm{7}\right)=\mathrm{14} \\ $$$${i}'=\frac{\mathrm{14}}{\mathrm{7}}=\mathrm{2}={i} \\ $$$${j}'=\frac{\mathrm{14}}{\mathrm{2}}=\mathrm{7}={j} \\ $$$$\Rightarrow{point}\:\left(\mathrm{2},\mathrm{7}\right)\:{has}\:{a}\:{new}\:{angle}. \\ $$$$ \\ $$$${Case}\:\mathrm{2}: \\ $$$${i}'<{i}\:{and}\:{j}'<{j} \\ $$$$\Rightarrow{point}\:\left({i},{j}\right)\:{descripts}\:{no}\:{new}\:{angle}, \\ $$$${its}\:{angle}\:{is}\:{the}\:{same}\:{as}\:{for}\:{point}\left({i}',{j}'\right). \\ $$$${e}.{g}.\:{point}\:\left(\mathrm{8},\mathrm{20}\right): \\ $$$${LCM}\left(\mathrm{8},\mathrm{20}\right)=\mathrm{40} \\ $$$${i}'=\frac{\mathrm{40}}{\mathrm{20}}=\mathrm{2}<{i}=\mathrm{8} \\ $$$${j}'=\frac{\mathrm{40}}{\mathrm{8}}=\mathrm{5}<{j}=\mathrm{20} \\ $$$$\Rightarrow{point}\:\left(\mathrm{8},\mathrm{20}\right)\:{has}\:{no}\:{new}\:{angle},\:{since} \\ $$$${it}\:{has}\:{the}\:{same}\:{angle}\:{as}\:{point}\:\left(\mathrm{2},\mathrm{5}\right). \\ $$$$ \\ $$$${Case}\:\mathrm{1}\:{means}\:{also}\:{GCD}\left({i},{j}\right)=\mathrm{1}. \\ $$$${Case}\:\mathrm{2}\:{means}\:{also}\:{GCD}\left({i},{j}\right)>\mathrm{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:

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

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.

$${Cells}\:{with}\:{value}\:\mathrm{1}\:{have}\:{unique}\:\frac{{j}}{{i}}\:{and} \\ $$$${cells}\:{with}\:{value}\:\mathrm{0}\:{are}\:{duplicates}. \\ $$$$ \\ $$$${The}\:{sum}\:{of}\:{all}\:{values}\:{in}\:{this}\:{table}\:{is} \\ $$$${the}\:{number}\:{of}\:{unique}\:{angles}\:{for} \\ $$$$\mathrm{1}\leqslant{i}\leqslant{m}\:{and}\:\mathrm{1}\leqslant{j}\leqslant{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.

$${From}\:{this}\:{table}\:{you}\:{can}\:{easily}\:{get}\:{the} \\ $$$${number}\:{of}\:{unique}\:{angles}\:{for}\:{any}\: \\ $$$${number}\:{of}\:{points},\:{e}.{g}.\:\mathrm{7}×\mathrm{22}\:{points}. \\ $$

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?

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

Commented by FilupS last updated on 09/May/17

This is fascinating!

$$\mathrm{This}\:\mathrm{is}\:\mathrm{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

$$\mathrm{Creating}\:\mathrm{a}\:\mathrm{formula}\:\mathrm{for}\:{LCM}\left({i},{j}\right) \\ $$$$\mathrm{wouldn}'\mathrm{t}\:\mathrm{be}\:\mathrm{very}\:\mathrm{straight}\:\mathrm{forward}. \\ $$$$ \\ $$$$\mathrm{It}\:\mathrm{would}\:\mathrm{be}\:\mathrm{extremely}\:\mathrm{difficult}\:\mathrm{and}\:\mathrm{possibly} \\ $$$$\mathrm{involve}\:\mathrm{prime}\:\mathrm{number}\:\mathrm{distributions}, \\ $$$$\mathrm{which}\:\mathrm{is}\:\mathrm{going}\:\mathrm{into}\:\mathrm{number}\:\mathrm{theory}\:\mathrm{and} \\ $$$$\mathrm{the}\:\mathrm{prime}\:\mathrm{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

$$\mathrm{The}\:\mathrm{best}\:\mathrm{function}\:\mathrm{I}\:\mathrm{can}\:\mathrm{think}\:\mathrm{of}\:\mathrm{would} \\ $$$$\mathrm{be}\:\mathrm{something}\:\mathrm{like}\:\left(\mathrm{correct}\:\mathrm{if}\:\mathrm{wrong}\right): \\ $$$${i}'=\frac{\mathrm{LCM}\left({i},{j}\right)}{{j}}\:\:\:\:\:\:\:{j}'=\frac{\mathrm{LCM}\left({i},{j}\right)}{{i}} \\ $$$$\delta_{{ij}} =\begin{cases}{\mathrm{1}\:\:\:\:\:\Leftrightarrow\:\:\:\:\:{i}'={i}\:\:\wedge\:\:{j}'={j}}\\{\mathrm{0}\:\:\:\:\:\Leftrightarrow\:\:\:\:\:{i}'<{i}\:\:\wedge\:\:{j}'<{j}}\end{cases} \\ $$$$\Phi=\underset{{i}} {\overset{{m}} {\sum}}\underset{{j}} {\overset{{n}} {\sum}}\delta_{{ij}} \\ $$$$\: \\ $$$$\Phi=\mathrm{total}\:\mathrm{unique}\:\mathrm{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}\:{agree}\:{with}\:{you}. \\ $$$$ \\ $$$${We}\:{can}\:{write}: \\ $$$$\delta_{{ij}} =\mathrm{1}−{sign}\left({i}−\frac{{LCM}\left({i},{j}\right)}{{j}}\right) \\ $$$$\Rightarrow\Phi=\underset{{i}=\mathrm{1}} {\overset{{m}} {\sum}}\underset{{j}=\mathrm{1}} {\overset{{n}} {\sum}}\delta_{{ij}} \\ $$$$\Rightarrow\Phi={mn}−\underset{{i}=\mathrm{1}} {\overset{{m}} {\sum}}\underset{{j}=\mathrm{1}} {\overset{{n}} {\sum}}{sign}\left({i}−\frac{{LCM}\left({i},{j}\right)}{{j}}\right) \\ $$

Commented by FilupS last updated on 09/May/17

I think thats the best solution!

$$\mathrm{I}\:\mathrm{think}\:\mathrm{thats}\:\mathrm{the}\:\mathrm{best}\:\mathrm{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)

$${An}\:{other}\:{simple}\:{formula}\:{is}: \\ $$$$\delta_{{ij}} =\mathrm{1}−{sign}\left({GCD}\left({i},{j}\right)−\mathrm{1}\right) \\ $$$$\Phi={mn}−\underset{{i}=\mathrm{1}} {\overset{{m}} {\sum}}\underset{{j}=\mathrm{1}} {\overset{{n}} {\sum}}{sign}\left({GCD}\left({i},{j}\right)−\mathrm{1}\right) \\ $$

Commented by FilupS last updated on 09/May/17

can you explain how you got this?

$$\mathrm{can}\:\mathrm{you}\:\mathrm{explain}\:\mathrm{how}\:\mathrm{you}\:\mathrm{got}\:\mathrm{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}}{{GCD}\left({i},{j}\right)}}{\frac{{i}}{{GCD}\left({i},{j}\right)}} \\ $$$${when}\:{i}'={i}\:{and}\:{j}'={j},\:{it}\:{means}\:\frac{{j}}{{i}}\:{can} \\ $$$${not}\:{be}\:{simplified}\:{any}\:{more},\:{i}.{e}. \\ $$$${GCD}\left({i},{j}\right)=\mathrm{1}.\:{E}.{g}.\:{for}\:{point}\:\left(\mathrm{2},\mathrm{7}\right):\: \\ $$$${GCD}\left(\mathrm{2},\mathrm{7}\right)=\mathrm{1},\:\frac{\mathrm{7}}{\mathrm{2}}\:{is}\:{a}\:{fraction}\:{which} \\ $$$${is}\:{already}\:{simplified}\:{to}\:{lowest}\:{terms}. \\ $$$$ \\ $$$${when}\:{i}'<{i}\:{and}\:{j}'<{j},\:{it}\:{means}\:\frac{{j}}{{i}}\:{can} \\ $$$${be}\:{simplified}\:{further},\:{i}.{e}.\:{GCD}\left({i},{j}\right)>\mathrm{1}. \\ $$$${E}.{g}.\:{for}\:{point}\:\left(\mathrm{8},\mathrm{20}\right):\:{GCD}\left(\mathrm{8},\mathrm{20}\right)=\mathrm{4}, \\ $$$$\frac{\mathrm{20}}{\mathrm{8}}\:{can}\:{be}\:{simplified}\:{to}\:\frac{\mathrm{20}/\mathrm{4}}{\mathrm{8}/\mathrm{4}}=\frac{\mathrm{5}}{\mathrm{2}}. \\ $$$$ \\ $$$${if}\:{GCD}\left({i},{j}\right)=\mathrm{1},\: \\ $$$$\:\Rightarrow\mathrm{1}−{sign}\left({GCD}\left({i},{j}\right)−\mathrm{1}\right)=\mathrm{1}\:\Rightarrow\:{unique} \\ $$$${if}\:{GCD}\left({i},{j}\right)>\mathrm{1},\: \\ $$$$\Rightarrow\mathrm{1}−{sign}\left({GCD}\left({i},{j}\right)−\mathrm{1}\right)=\mathrm{0},\Rightarrow\:{duplicate} \\ $$

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}\:{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}. \\ $$

Commented by FilupS last updated on 10/May/17

Thank you for solving it

$$\mathrm{Thank}\:\mathrm{you}\:\mathrm{for}\:\mathrm{solving}\:\mathrm{it} \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com