That's one big repeating binary expansion

Suppose it takes S S digits in the binary expansion of 1 3 10 \frac{1}{{3}^{10}} for it to repeat. What is the minimum value of S S ?

As an example, 1 3 = 0.01010101... \frac{1}{3} = 0.01010101... in base two, which takes two digits to repeat.


The answer is 39366.

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.

2 solutions

Pranshu Gaba
Jul 2, 2015

If we multiply any number written in binary with 2 S 2^{S} , ( S S is an integer), then the decimal point of the number shifts right by S S digits.

If we multiply 2 S 2^S to 1 3 10 \frac{1}{3^{10}} , the decimal point will shift right by S S digits. Since the binary expansion of 1 3 10 \frac{1}{3^{10}} repeats after S S digits, it means fractional part of 2 S 3 10 = \frac{2^{S}}{3^{10}} = fractional part of 1 3 10 \frac{1}{3^{10}}

This means 2 S 1 ( m o d 3 10 ) 2^{S} \equiv 1 \pmod{3^{10}} .

Since 2 S 2^{S} and 3 10 3^{10} are coprime integers, a solution to this congruence exists. By definition of multiplicative order , the minimum possible value of S S will be ord 3 10 ( 2 ) \text{ord}_{3^{10}} (2) . We know that 2 2 is a primitive root of 3 3 as well as 3 2 3^2 , so by lemma 14 in this document 2 2 is a primitive root of 3 10 3^{10} also.
By definition of primitive root, ord 3 10 ( 2 ) = ϕ ( 3 10 ) \text{ord}_{3^{10}} (2)= \phi(3^{10}) .

S = ϕ ( 3 10 ) = 3 10 ( 1 1 3 ) = 2 × 3 9 = 39366 S = \phi (3^{10} )= 3^{10} \left( 1 - \frac{1}{3}\right) = 2 \times 3^9 = \boxed{39366} _\square


Generalization: To find the smallest length k k , of the repetend of recurring decimal of a rational number r r when written in integral base b 2 b \geq 2 . Let the prime factorization of b b be i = 1 n p i a i \prod _{i = 1} ^{n} p_{i} ^{a_{i}} .

We are given a rational number r r . Since we are studying the decimal part, it would easier if we talk about the fractional part of r r , i.e. { r } \{ r \} .

We can write { r } = m n \{ r \} = \frac{m}{n} such that m , n m, n are positive integers such that n 0 n \neq 0 , and 0 m < n 0 \leq m < n . If m m is 0 0 then the decimal won't repeat, k k is zero and r r is an integer.

Otherwise we will simplify m n \frac{m}{n} into m n \frac{m'}{n'} such that m m' and n n' are coprime integers. Then k k will be independent of m m' , it will only depend on n n' .

If n n' is divisible by any of the p i p_{i} 's, then divide n n' by p i p_{i} until it does not divide any of the p i p_{i} 's. For example if r r was 5 60 \frac{5}{60} and base was 10 = 2 × 5 10 = 2 \times 5 , then 60 60 is divisible by 2 2 and 5 5 , so we divide it by 2 2 and 5 5 until it is not divisible by either, we will end up with 60 2 2 × 5 = 3 \frac{60}{2^{2} \times 5} = 3 . Let the new number that we end up with be q q .

We can do this because multiplying a rational number by factors of the base will not change the value of k k , and by removing all the factors of b b from n n' , we are making the both of them coprime. This is important because if they are not coprime, then there will be no solution to the following congruence.

b k 1 ( m o d q ) b^{k} \equiv 1 \pmod {q}

The smallest length of the repetend will be k = ord q ( b ) k = \boxed{\text{ord}_{q} (b)} _\square

Moderator note:

Great exposition!

For those who are unfamiliar with primitive roots, we can still use Euler's Theorem to approach this problem. It gives us that 2 2 × 3 9 1 ( m o d 3 10 ) 2 ^ { 2 \times 3^9} \equiv 1 \pmod{3^{10}} , and so it remains to show that 2 × 3 9 ≢ 1 ( m o d 3 10 ) 2 ^ { \times 3^9} \not \equiv 1 \pmod{3^{10}} and 2 2 × 3 8 ≢ 1 ( m o d 3 10 ) 2 ^ { 2 \times 3^8} \not \equiv 1 \pmod{3^{10}} . This can be done by using the Binomial Theorem and expanding 2 = ( 3 1 ) 2 = (3-1) .

Of course, the deeper reason why this is true, is encapsulated in the work of understanding primitive elements, so I would encourage you to check it out!

Very elegant solution! Very different from what I did, which I might post later :)

Also to the mods, I think this problem was rated too low - I found a 110 point problem where 25% of users had solved it yet 6% have solved this. I think this should be changed to a level 4 or 5.

Dylan Pentland - 5 years, 11 months ago

Log in to reply

Thank you! I found this problem very interesting! I agree with you, this question must be level 4 or 5. Its is definitely tougher than level 3. I am waiting to see your solution...

Pranshu Gaba - 5 years, 11 months ago
Dylan Pentland
Jul 2, 2015

We want a similar summation with a power of two being raised to the nth power on the bottom to achieve a repeating decimal with a value of 1 3 10 \frac{1}{3^{10}} .In other words, let n = 1 a ( 2 k ) n = 1 3 10 \sum _{ n=1 }^{ \infty }{ \frac { a }{ { { ({ 2 }^{ k }) }^{ n } } } =\frac { 1 }{ { 3 }^{ 10 } } } We also can create an expression for the infinite sum in terms of a a and k k : n = 1 a ( 2 k ) n = a 1 1 2 k a = a 2 k 1 \sum _{ n=1 }^{ \infty }{ \frac { a }{ { { ({ 2 }^{ k }) }^{ n } } } =\frac { a }{ 1-\frac { 1 }{ { 2 }^{ k } } } -a } =\frac { a }{ { 2 }^{ k }-1 } hence we are looking for when 3 10 {3}^{10} divides 2 k 1 2^k-1 , and we set a = 2 k 1 3 10 a=\frac{2^k-1}{{3}^{10}} . Suppose that 3 n 3^n divides 2 k 1 2^k-1 , then 2 3 a 1 = ( 2 a 1 ) ( 1 + 2 a + 2 2 a ) { 2 }^{ 3a }-1=({ 2 }^{ a }-1)(1+{ 2 }^{ a }+{ 2 }^{ 2a }) Since if we use this recurrence starting from a = 2 a=2 every a is even, 1 + 2 a + 2 2 a 1+{ 2 }^{ a }+{ 2 }^{ 2a } is 0 mod 3. Hence 3 n + 1 3^{n+1} divides 2 3 k 1 2^{3k}-1 . Applying this, the period of 1 3 10 \frac{1}{3^{10}} is 2 3 3 10 \frac{2}{3}3^{10} and by setting a a we may obtain the exact decimal sequence that is repeating.


There exists no other solution 2 k 2^k for k < 3 n k<3^{n} because 2 is a primitive root modulo 3 n 3^{n} . Simply put, this means that the sequence { 2 , 2 2 , 2 3 . . . 2 3 n } \{2,2^2,2^3... 2^{3^{n}}\} contains all numbers relatively prime to 3 n 3^{n} when put in modulo 3 n 3^{n} , or in our case precisely 2 3 3 10 \frac{2}{3}3^{10} numbers. Suppose there exists another one in this sequence: then some sequence containing these 2 3 3 10 \frac{2}{3}3^{10} elements must repeat at least twice yet this is impossible because that would require more elements than there are in the sequence. Hence 2 3 3 10 \frac{2}{3}3^{10} is the minimum solution.

Moderator note:

Not quite complete. You have shown that 2 × 3 9 2 \times 3 ^ 9 works, but have not shown that it is indeed the minimum value of S S .

Challenge master: Thanks, that was a big oversight... I've added a quick proof that the solution is the minimum value by showing there exists no other solution less than 3 10 3^{10} .

Dylan Pentland - 5 years, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...