Too many 3s

A number written in base 1010 is a string of 320133^{2013} digit 33s. No other digit appears. Find the highest power of 33 that divides this number.

Source: BMO, November 2013

#NumberTheory #OlympiadMath #MathProblem #Math

Note by Mark Hennings
5 years, 6 months ago

No vote yet
5 votes

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

The expression equals to 33…3=13(99…9)=13(1032013−1) 33 \ldots 3 = \frac {1}{3} (99 \ldots 9 ) = \frac {1}{3} (10^{3^{2013}} - 1)

We want to evaluate

vp(13(1032013−1))=−1+vp(1032013−1) v_p ( \frac {1}{3} (10^{3^{2013}} - 1)) = -1 + v_p (10^{3^{2013}} - 1)

With p=3,n=32013,x=10,y=−1p = 3, n = 3^{2013}, x = 10, y = -1 , we have

−1+v3(10+(−1))+v3(32013)=−1+2+2013=2014 -1 + v_3 (10 + (-1)) + v_3 (3^{2013} ) = -1 + 2 + 2013 = 2014

Hope I'm right, I'm still very new to Lifting The Exponent

Side question: How do you set on LaTeX to show that underneath 33…3 33 \ldots 3 , it has 320133^{2013} digits?

Pi Han Goh - 5 years, 6 months ago

Log in to reply

\underbrace{333...3}_{3^{2013}\ digits} gives 333...3⏟32013 digits\underbrace{333...3}_{3^{2013}\ digits}

EDIT: Also, 2014 is correct. I sat this exam last week.

Arkan Megraoui - 5 years, 6 months ago

Log in to reply

\text{digits} gives digits\text{digits} , which allows you to have 'words' within a mathematical statement, so that it does't appear in italic.

\underbrace{333 \ldots 3} _ {3^{2013} \text{ digits} } gives 333…3⏟32013 digits \underbrace{333 \ldots 3} _ {3^{2013} \text{ digits} } .

Calvin Lin Staff - 5 years, 6 months ago

Log in to reply

@Calvin Lin – THANKYOUTHANKYOU…THANKYOU⏟ gazillion times \underbrace{ \text{THANKYOUTHANKYOU} \ldots \text{THANKYOU}} _ { \text{ gazillion times} }

Pi Han Goh - 5 years, 6 months ago

Log in to reply

@Pi Han Goh – \mbox{digits} works just as well as \text{digits}, but is perhaps less memorable! The one to be careful with is \mathrm. If you \mathrm{use that one}, you losethespaces, \mathrm{lose the spaces,} since LaTeX ignores all spacing in mathematical typesetting, and \mathrm just forces an upright font, without switching out of Maths mode.

Mark Hennings - 5 years, 6 months ago

Log in to reply

@Mark Hennings – Thank you Sir Mark Hennings ,You′reAωesome! \mbox{Thank you} \space \text{Sir Mark Hennings }, \mathrm{You're A \omega esome}!

Pi Han Goh - 5 years, 6 months ago

Log in to reply

You don't have to appeal to LTE. If N(x,n)N(x,n) is the number obtained by concatenating the number xx a total of nn times, so that N(12,3)=121212N(12,3) = 121212, then N(x,3)  =  (102k+10k+1)x N(x,3) \; = \; (10^{2k} + 10^k + 1)x for any kk-digit number xx. Since the sum of the digits of 102k+10k+110^{2k} + 10^k + 1 is 33, it contains exactly one factor of 33, and so the exponent of 33 in N(x,3)N(x,3) is one more than the exponent of 33 in xx. Since N(3,3n+1)=N(N(3,3n),3) N(3,3^{n+1}) = N(N(3,3^n),3) an inductive argument finishes things off nicely.

Mark Hennings - 5 years, 6 months ago

Log in to reply

The ans is 32014 3^{2014}

The divisibility theory states that for any number to be divisible for 3, the sum of its digits must be divisible by 3. Similarly, for any number to be divisible for 323^{2}, the sum of its digits must be divisible by 323^{2} and so on.

for any number to be divisible for 3n3^{n}, the sum of its digits must be divisible by 3n3^{n}

for divisibility by 33 3^{3} , Consider any random number.

Let it be 2457396234. Sum of its digits is 2+4+5+7+3+9+6+2+3+4=45 Hence it is not divisible by 27 as 45 is not divisible by 27. But is is divisible by 9, as 45 is divisible by 9.

It leaves a remainder of 9 when divided by 27 with a quotient of 91014675.

It leaves a remainder of 0 when divided by 9 with a quotient of 273044026.

So the sum of the digits of the number in the question is 3∗32013=32014 3* 3^{2013} = 3^{2014}

hence it is divisible by 32014 3^{2014} .

Chandan Kumar Sahu - 3 years, 11 months ago

Log in to reply

The case for n=1 and 2 are true, but it is not true for n = 3. For instance, 27 is obviously divisible by 27 but 2+7=9 is not divisible by 27. That is why your answer is wrong.

Aloysius Ng - 3 years, 4 months ago

Log in to reply

Another way of writing this down. Let xnx_n represent the number that when written in decimal representation is a string of 3n3^n digits 1s only. We can see that xn=(102(3n−1)+103n−1+1)xn−1.x_n=(10^{2(3^{n-1})}+10^{3^{n-1}}+1)x_{n-1}. Therefore, it can be proved that xn=∏k=0n−1(102(3k−1)+103k−1+1)x_n=\prod_{k=0}^{n-1}(10^{2(3^{k-1})}+10^{3^{k-1}}+1). Each factor of this product is divisible by 33 but not by 32.3^2. Therefore the highest power of 3 that is a factor of xnx_n is 3n.3^n.. The number of the question is equal to 3x2013. 3x_{2013}. That is why the highest power of 3 that divides this number is 32014.3^{2014}.

Arturo Presa - 3 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...