5 0 = ( 0 + 1 ) × 7 × 7 + 1
To "build" a number, you are allowed to perform only two operations, either adding 1 or multiplying by 7.
Starting with zero, what is the fewest number of operations you can perform to "build" 1,000,000?
For example, 50 could be built using 4 operations: + 1 → × 7 → × 7 → + 1 .
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.
Magically, this allows us to see that
1 0 0 0 0 0 0 = ( 1 1 7 ∗ 1 0 3 0 3 0 1 7 ) = 8 ∗ ( 1 0 1 7 ) 3 = ( 2 ∗ 5 0 ) 3 = 1 0 0 3 .
(Since ( x + 1 ) 3 = x 3 + 3 x 2 + 3 x + 1 ).
Did the same.
But how to prove that this is indeed the minimum?
Log in to reply
Indeed sir pls show how it is minimum
Log in to reply
Log in to reply
@Rajdeep Das – OK, lemme think about what I can come up with...
Nice fun problem!
Sir can you please suggest me some good books or resources on combinatorics ?
The book should start from a begginer's perspective to advance level.
Thanks!
Log in to reply
@Geoff Pilling sir
Try this
Log in to reply
Thanks for the awesome resources.
But i need a book that teaches me some combinatorial theory so that i can tackle all those wonderful problems.
Can you please suggest me some book for theory?Thanks!
Log in to reply
@Harsh Shrivastava – Books I know none, and have none. The internet is my only resource :(
@Harsh Shrivastava – If I come across any... I'll let you know...
Ah, a challenging bunch of problems! :)
Problem Loading...
Note Loading...
Set Loading...
Relevant wiki: Number Base - Problem Solving
Perhaps the most intuitive way to think about this question, is to consider base 7 :
1 0 0 0 0 0 0 1 0 = 1 1 3 3 3 3 1 1 7
In base 7 , multiplying by 7 is like shifting 1 .
So to "build" this number, you would "make" one digit at a time, i.e. add one, shift, add 1 , shift, add 3 , shift, etc.
Or translated into the operations in this problem, this would be equivalent to performing the following operations in order:
+ 1 × 7 + 1 × 7 + 1 + 1 + 1 × 7 + 1 + 1 + 1 × 7 + 1 + 1 + 1 × 7 + 1 + 1 + 1 × 7 + 1 × 7 + 1
And this is 2 3 operations.