1 × 3 × 5 × ⋅ ⋅ ⋅ × 3 1 × 3 3 × 3 5
Find the largest power of 3 that divides the number above.
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.
There's a slightly easier method to do this. Can you solve it the number of terms multiplied became much larger, i.e.: 3 × 5 × 7 × ⋅ ⋅ ⋅ × 1 0 0 0 0 1 ? Hint: Which of these numbers being multiplied are multiples of 3 ? Can you spot a pattern?
@challenge master ... Can you please give a small hint so that I can get to know of which method you are talking about?
Beautiful solution 😍
NIce Solution @Vighnesh Raut . Exactly the same way As I solved it :)
I'm gonna give a general solution to this.
First we find the first and last numbers divisible by 3 ( 3 and 3 3 here) which are formed by multiplying 3 by 1 and 1 1
This is an A.P of 1 to 1 1 with d = 2 Thus, there are n = 6 terms in the sequence. Now, we find the smallest power x of 3 greater than 1 ( 2 here) and find all of it's odd multiples, except the ones containing any multiple of 3 in the sequence y and write this as ( x − 1 ) × y ( which is equal to 1 for 3 2 and 2 for 3 3 here). We go on till there are no more powers of 3 in the sequence. Now sum these and add it to the original n i.e:- 6 + 2 + 1 = 9 here.
This can be used for any huge sequence for 3 or any other odd number except one( probably not even).
the largest power of 3 for 35! is 15, deleting the even numbers of the set, gives us 6 powers of 3, thus 15 -6 = 9 largest remaining powers of 3 for the given set.
1 1 is the largest number for which 1 1 ⋅ 3 ≤ 3 5 .
Therefore powers of three are enclosed within this series:
( 1 ⋅ 3 ) ( 3 ⋅ 3 ) ( 5 ⋅ 3 ) . . . ( 1 1 ⋅ 3 )
Now we need to find the largest power of 3 which can divide the above series.
Since we have already simplified the sum, we just need to count the threes from above series. By doing that, we find out that that the largest power of 3 is 6 .
Now, the simplified series (after removing the powers of 3 which we have counted):
1 ⋅ 3 ⋅ 5 . . . 1 1
But we are not done yet as some terms still contain powers of three. We separate these terms and rewrite the series:
3 ⋅ 9
Since there are only two terms, we can count the largest power 3 which can divide the above product which is three.
We add the two powers 6 + 3 . So the answer is 9 .
Good approach.
How can this be generalized?
The multiples of 3 are the terms whose index gives a remainder of 2 when divided by 3. There are 18 terms total, so there are 6 terms which have a factor of 3. Of those, 2 have a factor of 9, and 1 of those has a factor of 27. Thus we have 6 + 2(2-1) + 1(3-2) = 6 + 2 + 1 = 9.
However, the question is a bit ambiguous. I put 3^9 = 19683 as my answer at first. Maybe it's just me though.
Trying an easier (but lazier) approach: Among 1, 3, 5, ... , 33 and 35, there are six numbers that are divisible by 3: 3,9,15,21,27, and 33.
With 9=3^2 , and 27=3^3, and the other four numbers having 3 in a single multiplicity, then 3+2+1+1+1+1 = 9.
Yes, often times the simplest straightforward method works. However, it's very impractical to use this method if the number of terms multiplied became much larger, i.e.: 3 × 5 × 7 × ⋅ ⋅ ⋅ × 1 0 0 0 0 1 . But obviously there's still a shortcut to this. Can you find it?
What's your shortcut challenge master?
Problem Loading...
Note Loading...
Set Loading...
1 × 3 × 5 × . . . . × 3 5 = 2 × 4 × 6 × 8 × . . . . . × 3 6 1 × 2 × 3 × 4 × 5 × . . . . . . × 3 5 × 3 6 = 2 1 8 × 1 8 ! 3 6 !
Now, power of 3 in 36! is ⌊ 3 3 6 ⌋ + ⌊ 9 3 6 ⌋ + ⌊ 2 7 3 6 ⌋ = 1 2 + 4 + 1 = 1 7
And the power of 3 in 18! is ⌊ 3 1 8 ⌋ + ⌊ 9 1 8 ⌋ = 6 + 2 = 8
So, 1 × 3 × 5 × . . . . × 3 5 can be written as m × 3 8 k × 3 1 7 for some constants k & m and in simple power of 3 it can be further reduced to A × 3 9 where mA=k