Not always adorable!

A natural number m m is adorable if you can write it as sum of three natural numbers m = a + b + c m = a+b+c such that ( 2 a ) , ( 3 b ) , ( 4 c ) (2 \mid a), (3 \mid b), (4 \mid c) .

Find the sum of all natural numbers which are not adorable.

Details and assumptions :

  • a b a\mid b means a a divides b b , i.e. b b is divisible by a a .

  • As an explicit example, the number 11 11 is adorable because 11 = 4 + 3 + 4 11 = 4+3+4 , and 2 4 ; 3 3 , 4 4 2\mid 4 ; 3\mid 3 , 4\mid 4 . But the number 7 7 is not adorable because you can't find such a , b , c a,b,c .


The answer is 46.

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.

6 solutions

Daniel Liu
Jan 29, 2015

I claim that all numbers above 10 10 are adorable.

Let a = a + 2 a=a'+2 , b = b + 3 b=b'+3 , and c = 4 c=4 .

Then, m = a + b + 9 m=a'+b'+9 where a , b 0 a',b'\ge 0 and 2 a 2\mid a' , 3 b 3\mid b'

Now by Chicken McNugget theorem, the smallest number not representable by a + b a'+b' is 2 × 3 2 3 = 1 2\times 3-2-3=1 . Thus, a + b a'+b' can equal 2 2 or any number greater than 2 2 .

Thus, a + b + 9 11 a'+b'+9\ge 11 so m 11 m\ge 11 is not adorable.

It is a simple exercise now to check that all m 10 m \le 10 is adorable except m = 9 m=9 , where m = 2 + 3 + 4 m=2+3+4 .

Thus, the answer is 1 + 2 + 3 + + 7 + 8 + 10 = 46 1+2+3+\cdots +7+8+10=\boxed{46}

you could have mentioned the Ketchup theorem.

It would have made your Chicken McNugget theorem that much more "delectable" 😜

Trevor Arashiro - 6 years, 4 months ago

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.

Daniel Liu - 6 years, 4 months ago

Log in to reply

There's always the Sandwich theorem!

Calvin Lin Staff - 6 years, 4 months ago

That's what I got until google got me to believe that 0 is a natural number Never trust the internet!

Alex Li - 5 years, 11 months ago
Vikram Waradpande
Jan 30, 2015

Let a = 2 p , b = 3 q a=2p, b=3q and c = 4 r c=4r . Now for p , q , r 2 p,q,r\geq 2 ,we will show that if m m is adorable, then m + 1 m+1 is also adorable. This can be proved as follows. If m = 2 p + 3 q + 4 r m = 2p+3q+4r then m + 1 = 2 ( p 1 ) + 3 ( q + 1 ) + 4 r m+1 = 2(p-1)+3(q+1) + 4r So we see that all m 18 = 2 2 + 2 3 + 2 4 m \geq 18 = 2*2+2*3+2*4 are adorable. Also the least adorable number is 2 + 3 + 4 = 9 2+3+4=9 . And since the least increment possible is of 2 2 , 10 10 is not adorable. All numbers 9 m 18 9\leq m\leq18 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 , 10 1,2,3,4,5,6,7,8,10 which sum to 46 \boxed{46}

For odd m 9 m \geq 9 , m = ( m 7 ) + 3 + 4 m = (m-7) + 3 + 4 . Since m m is odd, m 7 m -7 is even. Also, m 9 m 7 2 m \geq 9 \implies m-7 \geq 2 . Therefore all odd m 9 m \geq 9 are adorable.

For even m 12 m \geq 12 , we have m = ( m 10 ) + 6 + 4 m = (m-10) + 6 + 4 . Since m m is even, m 10 m -10 is also even and also, m 12 m 10 2 m \geq 12 \implies m - 10 \geq 2 . Therefore all even m 12 m \geq 12 are adorable.

Now, a 2 , b 3 , c 4 m = a + b + c 9 a \geq 2, b \geq 3 , c \geq 4 \implies m = a + b + c \geq 9 . Therefore [ 1 , 2 , 3 , . . , 6 , 7 , 8 ] [1,2,3,..,6,7,8] are not adorable

The only number left to check is 10 10 . Since the smallest adorable number is 9 9 , and the smallest increment possible is 2 2 , 10 10 is also not adorable.

Adding all these numbers, we get 46 \boxed{46} .

Yes! Non-standard induction makes this easy! Obvious if n n is adorable, then so is n + 2 n + 2 .

Calvin Lin Staff - 6 years, 4 months ago
Aditya Raut
Jan 29, 2015

\bullet First of all, note that if k k is adorable, then any multiple of k k is adorable.

\bullet 2 a ; 3 b ; 4 c a + b + c 2 + 3 + 4 = 9 2 \mid a\quad ; 3\mid b\quad ; 4\mid c \implies a+b+c \geq 2+3+4 = 9 . Thus all the numbers less than 9 are NOT adorable. (1 to 8)

\bullet Note that if p > 7 p>7 is a prime, then p = ( p 7 ) + 3 + 4 p = (p-7) +3 +4 and this tells us that p p is adorable. ( 2 2 always divides p 7 p-7 as p p will be odd).


Hence if any number is adorable, we conclude that it must be composed of only the primes 7 \leq 7 .

m = 2 x 3 y 5 z 7 w \therefore m = 2^x 3^y 5^z 7^w

Now note that

2 4 = 16 = 6 + 6 + 4 2^4= 16 = 6 + 6 +4

3 2 = 9 = 2 + 3 + 4 3^2 = 9 = 2+3+4

5 2 = 25 = 2 + 3 + 20 5^2 = 25= 2+3 +20

7 2 = 49 = 2 + 3 + 44 7^2 = 49= 2+3+44

This tells us x , y , z 1 x,y,z \leq 1 and x 3 x \leq 3 .

So if a number is adorable, it has very few possibilities, all will be divisors of 2 3 × 3 × 5 × 7 2^3\times 3\times 5\times 7 .


2 3 × 3 × 5 × 7 2^3 \times 3\times 5\times 7 has ( 3 + 1 ) ( 1 + 1 ) ( 1 + 1 ) ( 1 + 1 ) = 32 (3+1)(1+1)(1+1)(1+1) = 32 divisors.

We now see

3 × 5 = 15 = 2 + 9 + 4 5 × 7 = 35 = 2 + 9 + 24 3 × 7 = 21 = 2 + 3 + 16 3\times 5 = 15 = 2+ 9 + 4\\ 5\times 7 = 35 = 2 + 9 + 24 \\ 3\times 7 = 21 = 2 + 3 + 16

Hence 15 , 21 , 35 15,21,35 and all their multiples are Adorable, so out of the 32 factors, only those of the form 2 k × p 2^k \times p are considered, which will be factors of

2 3 × 3 , 2^3 \times 3 ,\quad 2 3 × 5 , 2 3 × 7 2^3 \times 5, \quad 2^3 \times 7 .

Now note that

2 2 × 3 = 12 = 2 + 6 + 4 2^2 \times 3 = 12 = 2+6+4 ... This cancels 12 and 24

2 2 × 5 = 20 = 2 + 6 + 12 2^2 \times 5 = 20 = 2+6+12 ... This cancels 20 and 40

2 × 7 = 14 = 4 + 6 + 4 2\times 7 = 14 = 4+6+4 ... This cancels 14,28 and 56


Number Divisors Adorable Not Adorable \\ \text{Number}-- \text{Divisors}---- \text{Adorable} --\text{Not Adorable}

2 3 × 3 1 , 2 , 3 , 4 , 6 , 8 , 12 , 24 12 , 24 1 , 2 , 3 , 4 , 6 , 8 2 3 × 5 1 , 2 , 4 , 5 , 8 , 10 , 20 , 40 20 , 40 1 , 2 , 4 , 5 , 8 , 10 2 3 × 7 1 , 2 , 4 , 7 , 8 , 14 , 28 , 56 14 , 28 , 56 1 , 2 , 4 , 7 , 8 2^3\times 3 --1,2,3,4,6,8,12,24-- 12,24 -- 1,2,3,4,6,8\\ 2^3\times 5 -- 1,2,4,5,8,10,20,40 -- 20,40 -- 1,2,4,5,8,10\\ 2^3\times 7 -- 1,2,4,7,8,14,28,56 -- 14,28,56 -- 1,2,4,7,8 \\


hence the only numbers NOT adorable are 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 1,2,3,4,5,6,7,8 and 10 10 .

Their sum is 46 \boxed{46}

A simpler solution exists with the Chicken McNugget Theorem. I like your idea here though.

Daniel Liu - 6 years, 4 months ago

Log in to reply

Wait, you were serious about the McNugget theorem......

Trevor Arashiro - 6 years, 4 months ago
Luca Bruni
Aug 9, 2016

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 a is adorable. Which means a = 2 k + 3 d + 4 s a=2k+3d+4s where k , d , s k, d, s are three integer numbers.

Now the next adorable number will be b = 2 ( k + 1 ) + 3 d + 4 s b=2(k+1)+3d+4s . This implies that adorable numbers are distributed at a distance of 2 2

The first adorable number is 9 9 so 11 , 13 , 15 , 17 , . . . 11, 13, 15, 17, ... would also be adorable. That means that all odd numbers greater that nine are adorable.

Also since 12 12 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 1, 2, 3, 4, 5, 6, 7, 8 and 10 10 are not adorable

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...