Birthday Special #3 Aditya Raut

Number Theory Level 5

For positive integers a a , b b , and c c , define f ( a , b , c ) = a b c gcd ( a , b , c ) ⋅ lcm ( a , b , c ) . f(a,b,c)=\frac{abc}{\text{gcd}(a,b,c)\cdot\text{lcm}(a,b,c)}. We say that a positive integer n n is f ( λ ) f(\lambda) if there exist x , y , z ≤ 60 x,y,z\leq60 that satisfy f ( x , y , z ) = n f(x,y,z)=n . How many f ( λ ) f(\lambda) integers are there?

(x,y,z) are pairwise distinct positive integers
Happy Birthday Aditya Raut! (9th June)


The answer is 79.

Parth Lohomi by Parth Lohomi , 20, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Carsten Meyer
Apr 16, 2021

Introduce the short-hand x ⃗ : = ( x , y , z ) T \vec{x}:=(x,\:y,\:z)^T and define some helpful factors to simplify f ( x ⃗ ) f(\vec{x}) : g : = gcd ⁡ ( x , y , z ) u : = gcd ⁡ ( x , y ) g v : = gcd ⁡ ( x , z ) g w : = gcd ⁡ ( y , z ) g \begin{aligned} g &:= \gcd(x,\:y,\:z) &&& u &:= \frac{\gcd(x,\:y)}{g} &&& v &:= \frac{\gcd(x,\:z)}{g} &&& w &:= \frac{\gcd(y,\:z)}{g} \end{aligned} With those factors and x ′ , y ′ , z ′ ∈ N x',\:y',\:z'\in\mathbb{N} we rewrite x ⃗ \vec{x} as x ⃗ = ( x ′ u v g , y ′ u w g , z ′ v w g ) T , u , v , w , g , x ′ , y ′ , z ′ pairwise rel. prime \begin{aligned} \vec{x}&=(x'uvg,\: y'uwg,\:z'vwg)^T,&&&u,\:v,\:w,\:g,\:x',\:y',\:z'\text{ pairwise rel. prime} \end{aligned} It helps to visualize the relation of all these factors in a Venn-Diagram with three circles, representing x , y , z x,\:y,\:z . Common factors are represented by intersections, so g g lies in the middle. Now we simplify n = f ( x ⃗ ) = ( x ′ u v g ) ( y ′ u w g ) ( z ′ v w g ) g ⋅ ( x ′ y ′ z ′ u v w g ) = u v w g ⇒ n 2 = ( u v w g ) 2 ≤ ( x ′ y ′ z ′ u v w g ) 2 = x y z g ≤ 6 0 3 g \begin{aligned} n&=f(\vec{x})=\frac{ (x'uvg)(y'uwg)(z'vwg) }{ g\cdot(x'y'z'uvwg) }=uvwg&&&\Rightarrow &&&& n^2&=(uvwg)^2\leq (x'y'z'uvwg)^2=\frac{xyz}{g}\leq \frac{60^3}{g} \end{aligned}

Notice the symmetries. If x ⃗ \vec{x} is a solution, the following are true:

  • We can set u → g u , g = x ′ = y ′ = z ′ = 1 u\rightarrow gu,\:g=x'=y'=z'=1 and get a smaller solution to the same n n . We only need to consider this case
  • Any permutation of x ⃗ \vec{x} is another solution to the same n n , and permutes u , v , w u,\:v,\:w . We only need to consider 1 ≤ u ≤ v ≤ w 1\leq u \leq v\leq w
  • If u = 1 u=1 , we can set w → v w , v → 1 w\rightarrow vw,\:v\rightarrow 1 to get another solution to the same n n . We only need to consider the following two cases: 1 = u = v ≤ w 1=u=v\leq w or 2 ≤ u < v < w 2\leq u < v < w (because they are relatively prime, they cannot be equal)

In those two remaining cases, our solution has the form: x ⃗ = ( u v , u w , v w ) T , u v ≤ u w ≤ v w ≤ ! 60 , n = u v w \begin{aligned} \vec{x}&=(uv,\:uw,\:vw)^T, &&& uv&\leq uw\leq vw\overset{!}{\leq}60,&&& n&= uvw \end{aligned}

The special case u = v = 1 u=v=1 leads to the trivial solutions n = w ∈ { 1 ; … ; 60 } n=w\in\{1;\:\ldots;\:60\} . For the remaining solutions, we need to find all 2 ≤ u ≤ v < w 2\leq u \leq v < w rel. prime such that u v < u w < v w ≤ 60 uv<uw<vw\leq 60 and n = u v w > 60 n=uvw>60 . This is just case-work: u 2 < u v < v w ≤ 60 ∧ n = u v w > 60 ⇒ 2 ≤ u ≤ 7 , max ⁡ { v , ⌊ 60 u v ⌋ } < w ≤ ⌊ 60 v ⌋ \begin{aligned} u^2&<uv<vw\leq 60 & \wedge && n&=uvw>60 &&& \Rightarrow &&&& 2 &\leq u \leq 7, & \max\left\{v,\:\left\lfloor \frac{60}{uv} \right\rfloor\right\} &< w\leq \left\lfloor \frac{60}{v} \right\rfloor \end{aligned} The remaining cases are u 2 3 4 5 6 7 v 3 5 7 4 5 7 5 7 6 7 7 8 w 11 ; 13 ; 17 ; 19 7 ; 9 ; 11 % 7 ; 11 ; 13 7 ; 8 ; 11 8 7 ; 9 ; 11 % 7 8 % % \begin{aligned} \begin{array}{r|r|r|r||r|r|r||r|r||r|r||r||r} u & & & 2 & & &3 & & 4 & & 5 & 6 &7\\\hline v & 3 & 5 & 7 & 4 & 5 & 7 & 5 & 7 & 6 & 7 & 7 &8\\ w & 11;\: 13;\: 17;\: 19& 7;\:9;\:11 & \% & 7;\:11;\:13 & 7;\:8;\:11 & 8 & 7;\:9;\:11 & \%& 7 & 8 & \% & \% \end{array}\end{aligned} We notice all 19 19 cases in the table lead to distinct n > 60 n>60 . With the trivial solutions, we have 60 + 19 = 79 60+19=\boxed{79} solutions total.

0 Helpful 0 Interesting 0 Brilliant 0 Confused

And the brute force solution works just as well (takes 20s on an ancient PC): 

/* maxima program to find number of solutions */
N : 60$
list : makelist(0,          /* list[n] = 1: n is solution */
    k, 1, floor(N^(3 / 2))  /* list[n] = 0: n is not solution */
)$

/* iterate through domain 1 <= x <= y <= N */
for x : 1 thru N do(
    for y : x thru N do(
        for z : y thru N do(
            result : x * y * z / ( gcd(x, gcd(y, z)) * lcm(x, y, z) ),
            list[result] : 1
        )
    )
)$
disp(lsum(i, i, list))$     /* return number of distinct solutions */

Carsten Meyer - 1 month, 4 weeks ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...