A repunit is an integer that consists of only copies of the digit 1 . Let R n be a repunit with n digits. Let a ministring be a sequence of digits composed of a nonnegative integer amount of the ' 0 ' digit followed by a positive integer number of the ' 1 ' digit. Find the number of divisors of R 2 0 that consist entirely of copies of a single ministring .
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.
You are making the (huge) assumption that the factors must be of this particular form. While I see that it is a sufficient condition, why is that a necessary condition?
Can you clarify what a ministring is? Currently, it is "a number of the digit 0 followed by a number of the digit 1", so it is just "01".
Log in to reply
I have changed the wording of the problem. I don't know if this is ideal, as it feels wordy, but [I think] it should at least be clear now.
I also don't quite understand the challenge master's note. I thought the point was to find the factors of this form.
Log in to reply
With the current definition, then the ministrings are of the form "0000011111", or just "11111".
Log in to reply
@Calvin Lin – That is the intention, yes. There does exist a factor of R 2 0 that does not consist of this pattern of digits (the copies of a ministring ) but does contain only 0's and 1's (specifically, the 1011001 factor you mentioned). This case is significantly more difficult to compute for and find, which is why the problem does not require finding these, and why it was worded in such a way.
I noted that I understood this when I posted my challenge note at the end of my solution. The next step is to challenge problem solvers to find these outside cases of factors.
Log in to reply
@Bufang Liang – As for the challenge: I can find factors for R n whenever n has four or more prime factors. For instance, a factorization of R 24 is 1001000000001001 x 1000001 x 111. But since R_20 has only three prime factors, it does not have solutions of this type.
Log in to reply
@Arjen Vreugdenhil – This is not sufficient (and also not necessary, but I do not explain that here). R 1 2 has 1 0 1 1 0 1 as a factor, and 1 2 has only two (or three, depending on how you define and count) prime factors.
With respect to the CM note, I agree that numbers that follow the given format are factors. IE You have a sufficient characterization.
But, how do you know that there aren't other numbers which do not follow that format, which could be factors? For example, why can't 1011001 be a factor? That is not immediately obvious. IE You do not have a necessary characterization.
Log in to reply
@Calvin Lin – The problem only asks to find factors that are the given format, and to NOT count the other factors. I do mention that the other factors exist in the "Challenge" section of my solution.
If I counted that factor, clearly the solution would be 17 and not 16.
Problem Loading...
Note Loading...
Set Loading...
Each of the factors that is this format follows a certain form. This form can be described as a groups of b digits, with c ones in each of these groups.
We can place a few restrictions on these variables, and then look for all of the possibilities of this form. (Example: One factor of R 2 0 is 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 : 5 groups of 4 digits, 2 ones in each group.)
For all factors, a b must be a factor of 20 (total digits cannot exceed 20, and the number of digits in a group cannot be larger than the group). b must be divisible by c .
b = c if and only if b = 1 , and a cannot be 1 unless b is also 1 (these two restrictions will prevent us from overcounting the case where R k is a factor).
Factors of 20 are: { 1 , 2 , 4 , 5 , 1 0 , 2 0 }
Factors of these factors (excluding itself) are { 1 , 1 , [ 2 , 1 ] , 1 , [ 5 , 2 , 1 ] , [ 1 0 , 5 , 4 , 2 , 1 ] }
Factors of these numbers (excluding itself, unless it is a 1) are: { 1 , 1 , [ 1 , 1 ] , 1 , [ 1 , 1 , 1 ] , [ ( 5 , 2 , 1 ) , 1 , ( 2 , 1 ) , 1 , 1 ] }
This totals to 1 6 numbers.
Challenge: There is at least one factor of R 2 0 that consists of only the digits 0 and 1 that is not composed of only copies of a single ministring . Can you find them? Can you figure out for what values of n does R n have these special factors?