How To Make A Million

50 = ( 0 + 1 ) × 7 × 7 + 1 50 = ( 0 + 1) \times 7 \times 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 +1\rightarrow \times 7\ \rightarrow\times 7 \rightarrow + 1 .


The answer is 23.

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

Geoff Pilling
Jul 11, 2016

Relevant wiki: Number Base - Problem Solving

Perhaps the most intuitive way to think about this question, is to consider base 7 7 :

100000 0 10 = 1133331 1 7 1000000_{10} = 11333311_7

In base 7 7 , multiplying by 7 7 is like shifting 1 1 .

So to "build" this number, you would "make" one digit at a time, i.e. add one, shift, add 1 1 , shift, add 3 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 +1 \times 7 +1 \times 7 +1 +1 +1 \times 7 +1 +1 +1 \times 7 +1 +1 +1 \times 7 +1 +1 +1 \times 7 +1 \times 7 +1

And this is 23 \boxed{23} operations.

Magically, this allows us to see that

1000000 = ( 1 1 7 103030 1 7 ) = 8 ( 10 1 7 ) 3 = ( 2 50 ) 3 = 10 0 3 1000000 = (11_7 * 1030301_7) = 8* (101_7)^3 = (2*50)^3 = 100^3 .

(Since ( x + 1 ) 3 = x 3 + 3 x 2 + 3 x + 1 (x+1)^3 = x^3 + 3x^2 + 3x +1 ).

Manuel Kahayon - 4 years, 11 months ago

Log in to reply

Ah... That's pretty cool! ;)

Geoff Pilling - 4 years, 11 months ago

Did the same.

But how to prove that this is indeed the minimum?

Harsh Shrivastava - 4 years, 8 months ago

Log in to reply

Indeed sir pls show how it is minimum

rajdeep das - 4 years, 8 months ago

Log in to reply

@Geoff Pilling

rajdeep das - 4 years, 8 months ago

Log in to reply

@Rajdeep Das OK, lemme think about what I can come up with...

Geoff Pilling - 4 years, 8 months ago

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!

Harsh Shrivastava - 4 years, 8 months ago

Log in to reply

@Geoff Pilling sir

Harsh Shrivastava - 4 years, 8 months ago

Try this

Manuel Kahayon - 4 years, 8 months ago

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!

Harsh Shrivastava - 4 years, 8 months ago

Log in to reply

@Harsh Shrivastava Books I know none, and have none. The internet is my only resource :(

Manuel Kahayon - 4 years, 8 months ago

@Harsh Shrivastava If I come across any... I'll let you know...

Geoff Pilling - 4 years, 8 months ago

Ah, a challenging bunch of problems! :)

Geoff Pilling - 4 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...