Define a function or method that returns an integer greater than or equal to 0 given as a ** string ** and the remainder after dividing it by 3. This article uses Ruby, so it's a method.
However, no numerical value will be used. In other words, do not use numeric objects in the middle of processing. As a matter of course, the return value is also a character string.
I don't know if the built-in method has created a numeric object internally, so I'll assume that the code I wrote doesn't create a numeric object in the middle.
Let's name the method remainder_modulo_3. I'm not sure if the English is correct, but remainder is the remainder, and modulo 3 means "when divided by 3" [^ modulo 3].
[^ modulo3]: modulo 3 is said to be "3 as a law" in formal mathematical terms.
It should look like this:
p remainder_modulo_3("0") # => "0"
p remainder_modulo_3("8") # => "2"
p remainder_modulo_3("12") # => "0"
p remainder_modulo_3("22") # => "1"
Before thinking about the program, how to do it manually.
For example, the remainder of 1234567 divided by 3 can be seen at a glance as 1. eh? What do you mean?
First, consider the remainder of the simpler 87 divided by three. You can do the division seriously, but there are more ways to skip it.
\begin{eqnarray}
87 &=& 8 \times 10 + 7 \\
&=& 8 \times (9 + 1) + 7 \\
&=& 8 \times 9 + 8 + 7
\end{eqnarray}
However, $ 8 \ times 9 $ is a multiple of $ 9 $, so it is divisible by $ 3 $. Therefore, you can exclude $ 8 \ times 9 $ and find the remainder of $ 8 + 7 $ divided by $ 3 $.
Since $ 8 + 7 $ is $ 15 $, it is divisible by $ 3 $. The remainder is $ 0 $.
Thinking in the same way, even a large number like 1234567
\begin{eqnarray}
1234567 &=& 1 \times (999999 + 1) + 2 \times (99999 + 1) + 3 \times (9999 + 1) + 4 \times (999 + 1) + 5 \times (99 + 1) + 6 \times (9 + 1) + 7 \\
&=& (Multiple of 9) + 1 + 2 + 3 + 4 + 5 + 6 + 7
\end{eqnarray}
Therefore, the remainder of $ 1 + 2 + 3 + 4 + 5 + 6 + 7 $ divided by $ 3 $ can be obtained.
You don't have to seriously calculate $ 1 + 2 + 3 + 4 + 5 + 6 + 7 $,
(1 + 2) + (3) + (4 + 5) + (6) + 7
Since you can see multiples of $ 3 $, you can get $ 1 $ by excluding these and finding the remainder of $ 7 $ divided by $ 3 $.
So what about numbers like $ 78932705 $? Instead of this number
7 + 8 + 9 + 3 + 2 + 7 + 0 + 5
Of these numbers, $ 9 $, $ 3 $, and $ 0 $ are multiples of $ 3 $, so you can exclude them.
7 + 8 + 2 + 7 + 5
Just think about it. Also, considering $ 7 = 2 \ times 3 + 1 $, $ 7 $ was replaced with $ 1 $, $ 8 $ was replaced with $ 2 $, and $ 5 $ was replaced with $ 2 $.
1 + 2 + 2 + 1 + 2
You just have to think about it. (The numbers that come out can only be 1 and 2)
Humans can take a quick look at this and combine $ 1 $ with $ 2 $ to make $ 3 $ and exclude it, and the remainder is immediately apparent to be $ 2 $. But how to do this programmatically?
After all sort
1 + 1 + 2 + 2 + 2
Then, it would be better to create the string " 11222 ".
After that, it seems that you should delete the character strings such as " 111 ", " 222 ", and " 12 ".
I've done this:
def remainder_modulo_3(number)
s = number.delete("0369").tr("4578", "1212")
.chars.sort.join
.gsub(/(.)\1\1|1122|12/, "")
{"" => "0", "1" => "1", "11" => "2", "2" => "2", "22" => "1"}[s]
end
Gives an integer greater than or equal to 0 in the string and returns one of " 0 ", " 1 ", " 2 " in the string.
Let's give it a try:
1000000.times do |n|
puts n unless (n % 3).to_s == remainder_modulo_3(n.to_s)
end
Compare the one calculated with Integer normally with the one obtained with the remainder_modulo_3 method, and if they do not match, display it. When I tried it, nothing was displayed, so the code seems to match.
The method chain is a little long, but what we are doing is simple.
First
delete("0369")
However, since 0, 3, 6, and 9 are multiples of 3, these numbers are excluded.
next
tr("4578", "1212")
For example, 4 can be replaced with 1 because 4 is 3 + 1, and 5 can be replaced with 2.
Next
chars.sort.join
First separates the strings character by character, sorts them, and reconnects them.
This gives, for example, " 122 " from " 212 ".
The string obtained at this point is "0 or more"1"followed by 0 or more"2"". There can be no other pattern.
Next
gsub(/(.)\1\1|1122|12/, "")
Deletes specific strings from left to right, but the regular expression is a bit confusing.
The highlight is the (.) \ 1 \ 1 part. This uses a back reference. It means that two characters captured by (.) Follow it, and it matches "three same numbers in a row" as a whole.
It also matches the " 1122 " and " 12 " that can exist at the boundary between the"1"column and the"2"column.
These are deleted.
What kind of character string can be obtained after this conversion?
It's a little boring, but let's classify by the number of " 1 ".
First, since " 111 " is deleted first (because multiple"1"of 3 is deleted), if the number of"1"is 0, 1, 2 only. I know it's good.
When " 1 " is 0, it is a character string in which 0 or more " 2 " are connected. Considering that multiples of 3 " 2 " are deleted, there can be three, " ", " 2 ", and " 22 ".
Next, when there is one " 1 ", if there are 0"2"following", it is " 1 ", and if there is one " 2 ", it is the whole ("12"). Is deleted to become " ", and if there are two " 2 ", it becomes"2". If there are 3 or more " 2 "s, the"222"will be deleted, so you don't have to think about it (the possibilities are exhausted). In other words, there can be three, " 1 ", " ", and " 2 ".
Finally, when there are two " 1 ", if there are 0"2"following, it is"11", and if there is one"2", the"12"is deleted. It becomes " 1 ", and if there are two " 2 ", the whole ("1122") is deleted and it becomes an empty string. If there are three " 2 ", the " 1122 " will be deleted to become"2". You don't have to think about four or more. In other words, there can be four, " 11 ", " 1 ", " ", " 2 ".
Huh, it was annoying.
After all, the converted character string is
"""1""11""2""22"There are only five possibilities.
Hashes are used to guide too much about these. that's all.
The remainder after dividing by 9 can be done in exactly the same way.
You only need to look at the last digit (1's place) for the remainder divided by 2 or 5 (because 10 is divisible by 2 or 5).
For the remainder divided by 4, look at the last two digits (because 100 is divisible by 4).
Look at the last 3 digits for the remainder divided by 8 (because 1000 is divisible by 8).
The remainder after dividing by 6 should be quite confusing. I want to try it someday.
I'm not sure if the remainder after dividing by 7 can be calculated without creating a numeric object.
Even if someone asks me, "So what?" I've tagged it as "number theory", but it's not that big of a deal, it's not practical, and it's not very interesting. I just thought about it and tried it.
Recommended Posts