Minlcm

Four distinct positive integers a a , b b , c c , and d d are such that a + b + c + d = 1000. a+b+c+d=1000. Find the minimum value of lcm ( a , b , c , d ) . \text{lcm}(a,b,c,d).


The answer is 480.

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.

5 solutions

Mark Hennings
Jul 2, 2018

Suppose that a , b , c , d N a,b,c,d \in \mathbb{N} , with a < b < c < d a < b < c < d and a + b + c + d = 1000 a+b+c+d=1000 , and write N = l c m ( a , b , c , d ) N = \mathrm{lcm}(a,b,c,d) . Then 1000 < 4 d 1000 < 4d , and so d > 250 d > 250 . If N > d N > d , then N = k d N = kd for some k > 1 k > 1 , and hence N 2 d > 500 N \ge 2d > 500 . Thus values of N 500 N \le 500 are only obtained when N = d N = d .

Suppose now that N 500 N \le 500 , and that N = d N = d . Then a , b , c a,b,c all divide d d , and hence a 1 4 d a \le \tfrac14d , b 1 3 d b \le \tfrac13d , c 1 2 d c \le \tfrac12d , and hence 1000 = a + b + c + d ( 1 4 + 1 3 + 1 2 + 1 ) d = 25 12 d 1000 \; = \; a + b + c + d \; \le \; \big(\tfrac14 + \tfrac13 + \tfrac12 + 1\big)d \; = \; \tfrac{25}{12}d so that d 480 d \ge 480 . Thus we deduce that N 480 N \ge 480 in all cases.

The case a = 120 a = 120 , b = 160 b = 160 , c = 240 c=240 , d = 480 d=480 shows that N = 480 N=480 is possible. The smallest possible value of N N is 480 \boxed{480} .

Simple and elegant. Nice solution.

Kelvin Hong - 2 years, 11 months ago
John Ross
Jul 8, 2018

Suppose that lcm ( a , b , c , d ) = k a = l b = m c = n d \text{lcm}(a,b,c,d)=ka=lb=mc=nd where k , l , m k,l,m and n n are distinct. Rewriting b , c b,c and d d in terms of a a , gives the equation a + k l a + k m a + k n a = 1000 a+\frac kl a+\frac km a+\frac kn a=1000 This rearranges to lcm ( a , b , c , d ) = k a = 1000 1 k + 1 l + 1 m + 1 n \large \text{lcm}(a,b,c,d)=ka = \frac{1000}{\frac 1k + \frac 1l + \frac 1m + \frac 1n} We can see that this is minimized when k = 1 , l = 2 , m = 3 , n = 4 k=1, l=2, m=3, n=4 giving the answer 480 \boxed{480}

This is exactly a replica of my own solution.

EKENE FRANKLIN - 2 years, 11 months ago

Just awesome

Julien Blanchon - 2 years, 11 months ago

Wow!Keep up the good work man!

T C Adityaa - 2 years, 11 months ago
Binky Mh
Jul 9, 2018

If a a is the largest number of the four, it will be over 250 250 . This means any lcm \text{lcm} greater than a a will be significantly greater than a a . Best case scenario, we want lcm ( a , b , c , d ) = a \text{lcm}(a,b,c,d)=a .

To minimise a a , we need to make b b , c c & d d as large as possible, so we make these the largest distinct fractions of a a : a 2 \frac{a}{2} , a 3 \frac{a}{3} & a 4 \frac{a}{4} . Now we check to see if this gives us integer solutions for a a , b b , c c & d d :

a + a 2 + a 3 + a 4 = 1000 a+\frac{a}{2}+\frac{a}{3}+\frac{a}{4}=1000 a × 25 12 = 1000 a\times\frac{25}{12}=1000 a = 480 a=480 b = 480 2 = 240 b=\frac{480}{2}=240 c = 480 3 = 160 c=\frac{480}{3}=160 d = 480 4 = 120 d=\frac{480}{4}=120

As these are all integer solutions, we know that the minimum possible lcm \text{lcm} is 480 \boxed{480} .

We can't get a lower lcm \text{lcm} than this which is a multiple of a a , since the lower limit of a a is 250 250 , meaning any potential multiples of a a are greater than 500 500 . We know we can't get a lower lcm \text{lcm} that is equal to a a , as the other numbers are the highest possible distinct fractions of a a .

Binky MH - 2 years, 11 months ago

this is written so simply that I feel stupid now, good problem

Kyle T - 2 years, 11 months ago

I still don't understand the first line where you said " If a is the largest number of the four, it will be over 250 . This means any greater than a will be significantly greater than a . Best case scenario, we want lcm (a, b , c ,d ) = a . Please explain this to me by giving any example or something i can't understand this

Shahzad Hassan - 2 years, 10 months ago

Log in to reply

I'm labelling the largest of the four numbers 'a'. The largest number must be greater than 250, because if it is not, the four numbers cannot add up to 1000. The lowest common multiple of the numbers must be a multiple of the largest number. If the lowest common multiple is 2x the largest number, it will be greater than 500. If we assume the lowest common multiple can be exactly 1x the largest number, we may find a solution which is less than 500. (this assumption turns out to be correct, as it gives us a solution of 480).

Binky MH - 2 years, 10 months ago
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from functools import reduce

def sum_to_n(n, how_many, limit=None):
   # Produce all lists of `how_many` positive integers in decreasing order
   # that add up to `n`.
    if how_many == 1:
        yield [n]
        return
    if limit is None:
        limit = n
    start = (n + how_many - 1) // how_many
    stop = min(limit, n - how_many + 1) + 1
    for i in range(start, stop):
        for tail in sum_to_n(n - i, how_many - 1, i):
            if len(set([i]+tail)) == how_many:
                yield [i] + tail

def list_lcm(n):
    return reduce(lambda x,y: (lambda a,b: next(i for i in range(max(a,b),a*b+1) \
        if i%a==0 and i%b==0))(x,y), n)

sum_to = 100
factor  = 1000/sum_to

lowest_lcm = 'inf'          
for partition in sum_to_n(sum_to, 4):
    lcm = list_lcm(partition)
    if lcm*factor < lowest_lcm:
        lowest_lcm = lcm*factor
        list_ = partition
        list_ = [i * factor for i in list_]
print lowest_lcm, list_

1
480 [480, 240, 160, 120]

that's best solution so far

Aaditya Prakash - 2 years, 11 months ago

Log in to reply

tx Aaditya..appreciate that!! Please don't hesitate to give me an Upvote

Michael Fitzgerald - 2 years, 11 months ago

Log in to reply

😶😐😐😐😐😐😐😐😐😐😐😐😐😐😐😐😐😐😐🤮🤮🤮🤮🤮🤮🤮🤢🤢🤢🤢🤢🤢🤢🤧🤧🤧🤧😷😷😷🤒🤒🤒🤒🤬🤬🤬🤬🤬😡😡😡🤯🤯🤯🤯😰😨😱😫😩😢😭😖😟🤩😎😎🤓🤓🤓🤓😛😉🤣🤣😡😡😡😡🧠🧠🧠🧠👨🏾‍🔬👩🏿‍🔬👩🏿‍🔬👩🏿‍🔬👩🏿‍🔬👩🏿‍🔬👨🏾‍🔬👨🏾‍🔬👩🏾‍🎨👩🏾‍🎨👩🏾‍🎨👩🏾‍🎨📇📅📅📅📅📅📅📅♊️✒️🉐🚷🉑🛑⚛️♏️🈹🈺🈵🈸🈹🈺🈲📳🉐🈶㊗️✴️🔅🔤🔱🛅🌐🚼💹🚻💹🆖🕦🕦🕦🕦📣📣📣🔉🔉🔉🔊🔊🔊🔇🔇🔈🔈©️🆗🆗🆙🆒🆕4️⃣🈳🛅🛂🚺🚼🚻♿️🚼🛄🅿️Ⓜ️❇️🆙❇️1️⃣2️⃣⏺

Satoru Liu - 2 years, 11 months ago
Yvonne Killian
Aug 9, 2018

If a, b, c, d are integers and if d < c < b < a and if a+b+c+d = p, a given number,

lcm (a,b,c,d) has the lowest possible value if b = 1/2 a, c = 1/3 a and d = 1/4 a, and then this value (for lcm) equals a.

If p = 1000, a + 1/2a + 1/3a + 1/4a = a + 13/12 a = 25/12 a = 1000, hence a = 12 x 1000/25 = 12 x 40 = 480, hence lcm (a,b,c,d) = 480.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...