A natural number m is adorable if you can write it as sum of three natural numbers m = a + b + c such that ( 2 ∣ a ) , ( 3 ∣ b ) , ( 4 ∣ c ) .
Find the sum of all natural numbers which are not adorable.
Details and assumptions :
a ∣ b means a divides b , i.e. b is divisible by a .
As an explicit example, the number 1 1 is adorable because 1 1 = 4 + 3 + 4 , and 2 ∣ 4 ; 3 ∣ 3 , 4 ∣ 4 . But the number 7 is not adorable because you can't find such a , b , c .
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.
you could have mentioned the Ketchup theorem.
It would have made your Chicken McNugget theorem that much more "delectable" 😜
Log in to reply
The McNugget Theorem is actually a real theorem :P
It's also known as the Postage Stamp Problem or the Frobenius Coin Problem.
That's what I got until google got me to believe that 0 is a natural number Never trust the internet!
Let a = 2 p , b = 3 q and c = 4 r . Now for p , q , r ≥ 2 ,we will show that if m is adorable, then m + 1 is also adorable. This can be proved as follows. If m = 2 p + 3 q + 4 r then m + 1 = 2 ( p − 1 ) + 3 ( q + 1 ) + 4 r So we see that all m ≥ 1 8 = 2 ∗ 2 + 2 ∗ 3 + 2 ∗ 4 are adorable. Also the least adorable number is 2 + 3 + 4 = 9 . And since the least increment possible is of 2 , 1 0 is not adorable. All numbers 9 ≤ m ≤ 1 8 can also be show to be adorable easily). So we have our list of non-adorable numbers as : 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 1 0 which sum to 4 6
For odd m ≥ 9 , m = ( m − 7 ) + 3 + 4 . Since m is odd, m − 7 is even. Also, m ≥ 9 ⟹ m − 7 ≥ 2 . Therefore all odd m ≥ 9 are adorable.
For even m ≥ 1 2 , we have m = ( m − 1 0 ) + 6 + 4 . Since m is even, m − 1 0 is also even and also, m ≥ 1 2 ⟹ m − 1 0 ≥ 2 . Therefore all even m ≥ 1 2 are adorable.
Now, a ≥ 2 , b ≥ 3 , c ≥ 4 ⟹ m = a + b + c ≥ 9 . Therefore [ 1 , 2 , 3 , . . , 6 , 7 , 8 ] are not adorable
The only number left to check is 1 0 . Since the smallest adorable number is 9 , and the smallest increment possible is 2 , 1 0 is also not adorable.
Adding all these numbers, we get 4 6 .
∙ First of all, note that if k is adorable, then any multiple of k is adorable.
∙ 2 ∣ a ; 3 ∣ b ; 4 ∣ c ⟹ a + b + c ≥ 2 + 3 + 4 = 9 . Thus all the numbers less than 9 are NOT adorable. (1 to 8)
∙ Note that if p > 7 is a prime, then p = ( p − 7 ) + 3 + 4 and this tells us that p is adorable. ( 2 always divides p − 7 as p will be odd).
Hence if any number is adorable, we conclude that it must be composed of only the primes ≤ 7 .
∴ m = 2 x 3 y 5 z 7 w
Now note that
2 4 = 1 6 = 6 + 6 + 4
3 2 = 9 = 2 + 3 + 4
5 2 = 2 5 = 2 + 3 + 2 0
7 2 = 4 9 = 2 + 3 + 4 4
This tells us x , y , z ≤ 1 and x ≤ 3 .
So if a number is adorable, it has very few possibilities, all will be divisors of 2 3 × 3 × 5 × 7 .
2 3 × 3 × 5 × 7 has ( 3 + 1 ) ( 1 + 1 ) ( 1 + 1 ) ( 1 + 1 ) = 3 2 divisors.
We now see
3 × 5 = 1 5 = 2 + 9 + 4 5 × 7 = 3 5 = 2 + 9 + 2 4 3 × 7 = 2 1 = 2 + 3 + 1 6
Hence 1 5 , 2 1 , 3 5 and all their multiples are Adorable, so out of the 32 factors, only those of the form 2 k × p are considered, which will be factors of
2 3 × 3 , 2 3 × 5 , 2 3 × 7 .
Now note that
2 2 × 3 = 1 2 = 2 + 6 + 4 ... This cancels 12 and 24
2 2 × 5 = 2 0 = 2 + 6 + 1 2 ... This cancels 20 and 40
2 × 7 = 1 4 = 4 + 6 + 4 ... This cancels 14,28 and 56
Number − − Divisors − − − − Adorable − − Not Adorable
2 3 × 3 − − 1 , 2 , 3 , 4 , 6 , 8 , 1 2 , 2 4 − − 1 2 , 2 4 − − 1 , 2 , 3 , 4 , 6 , 8 2 3 × 5 − − 1 , 2 , 4 , 5 , 8 , 1 0 , 2 0 , 4 0 − − 2 0 , 4 0 − − 1 , 2 , 4 , 5 , 8 , 1 0 2 3 × 7 − − 1 , 2 , 4 , 7 , 8 , 1 4 , 2 8 , 5 6 − − 1 4 , 2 8 , 5 6 − − 1 , 2 , 4 , 7 , 8
hence the only numbers NOT adorable are 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 and 1 0 .
Their sum is 4 6
A simpler solution exists with the Chicken McNugget Theorem. I like your idea here though.
Log in to reply
Wait, you were serious about the McNugget theorem......
First of all let's see that if a number n is adorable, then the number n+2 is also adorable.
Proof.
Let's take an adorable number n and write it like this: n = 2x + 3y + 4z
We can write the number n+2 like this:
n+2 = 2x + 3y + 4z + 2 = 2(x+1) + 3y + 4z
Which is also adorable. CVD.
So, since we know that 9 is the first adorable number ( 9 = 2 + 3 + 4) and since it is odd, we can deduce that every odd number over 9 is also adorable.
In the same way we prove that since 12 is the first adorable even number (12 = 2 + 3×2 + 4), every even number over 12 is also adorable.
Every other number is not adorable, so our list of non-adorable numbers is: 1,2,3,4,5,6,7,8,10.
The sum of these nine numbers is 46.
Let's say a is adorable. Which means a = 2 k + 3 d + 4 s where k , d , s are three integer numbers.
Now the next adorable number will be b = 2 ( k + 1 ) + 3 d + 4 s . This implies that adorable numbers are distributed at a distance of 2
The first adorable number is 9 so 1 1 , 1 3 , 1 5 , 1 7 , . . . would also be adorable. That means that all odd numbers greater that nine are adorable.
Also since 1 2 is adorable (which can be easily verify), all even numbers greater that twelve are also adorable.
Finally it's easy to check that 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 and 1 0 are not adorable
Problem Loading...
Note Loading...
Set Loading...
I claim that all numbers above 1 0 are adorable.
Let a = a ′ + 2 , b = b ′ + 3 , and c = 4 .
Then, m = a ′ + b ′ + 9 where a ′ , b ′ ≥ 0 and 2 ∣ a ′ , 3 ∣ b ′
Now by Chicken McNugget theorem, the smallest number not representable by a ′ + b ′ is 2 × 3 − 2 − 3 = 1 . Thus, a ′ + b ′ can equal 2 or any number greater than 2 .
Thus, a ′ + b ′ + 9 ≥ 1 1 so m ≥ 1 1 is not adorable.
It is a simple exercise now to check that all m ≤ 1 0 is adorable except m = 9 , where m = 2 + 3 + 4 .
Thus, the answer is 1 + 2 + 3 + ⋯ + 7 + 8 + 1 0 = 4 6