[Ruby] Find the remainder divided by 3 without using a number

6 minute read

theme

Define a function or method that is given an integer >= 0 as a string, and returns the remainder divided by 3. This article uses Ruby, so it’s a method.

However, no numerical value is used. That is, do not use a numeric object during the process. Of course, the return value is also a character string.

I don’t know if the built-in method is creating a numeric object internally, so I’m fine if my code doesn’t create a numeric object on the way.

Let’s name the method remainder_modulo_3. I’m not sure if English is correct, but remainder is a remainder, and modulo 3 means “when divided by 3” 1.

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"

How to do it by hand

Before thinking about the program, how to do it manually.

For example, the remainder of 1234567 divided by 3 is 1 at a glance. eh? What do you mean?

First, consider the remainder, which is a simpler 87 divided by 3. You can take 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, since $8 \times 9$ is a multiple of $9$, it is divisible by $3$. Therefore, you can exclude $8 \times 9$ from the list, and finally find the remainder of $8 + 7$ divided by $3$.

Since $8 + 7$ is $15$, it is divisible by $3$. The remainder is $0$.

Considering the same way, even a large number such as 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 \\
  &=& (a multiple of 9) + 1 + 2 + 3 + 4 + 5 + 6 + 7
\end{eqnarray}

Therefore, we need to find the remainder by dividing $1 + 2 + 3 + 4 + 5 + 6 + 7$ by $3$.

You don’t have to calculate $1 + 2 + 3 + 4 + 5 + 6 + 7$ seriously,

(1 + 2) + (3) + (4 + 5) + (6) + 7

As you can see the multiples of $3$, you can get $1$ by excluding them and finding the remainder of dividing $7$ by $3$.

Then how about a number like $78932705$? Instead of this number

7 + 8 + 9 + 3 + 2 + 7 + 0 + 5

However, among these numbers, $9$, $3$, and $0$ are multiples of $3$, so you can exclude them.

7 + 8 + 2 + 7 + 5

You should think about. Also, considering $7 = 2 \times 3 + 1$, etc., we replaced $7$ with $1$, $8$ with $2$, and $5$ with $2$.

1 + 2 + 2 + 1 + 2

You should think about. (Only 1 and 2 can appear)

A human can take a quick look at this and combine $1$ with $2$ to make $3$, and then remove it, and the remainder is immediately $2$. However, how to do this with the character string processing by the program?

After all sort

1 + 1 + 2 + 2 + 2

Then, it would be good to make a string ““11222”`.

After that, it seems good to delete the character strings such as "111", "222", and ““12”`.

Code

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

Given a string as an integer greater than or equal to 0, returns one of "0", "1", and "2" as a string.

Let’s try for a moment:

1000000.times do |n|
  puts n unless (n %3).to_s == remainder_modulo_3(n.to_s)
end

Compare what you normally calculate with Integer with what you get with the method remainder_modulo_3, and if it doesn’t match, display it. When I tried it, nothing was displayed, so the code seems to match.

Commentary

The method chain is a bit long, but what you are doing is simple.

First

delete("0369")

However, 0, 3, 6, and 9 are multiples of 3, so these numbers are excluded.

next

tr("4578", "1212")

Means, for example, 4 can be replaced by 1 because 4 is 3 + 1, and 5 can be replaced by 2.

Next

chars.sort.join

First separates the character strings one by one, sorts them, and connects them again. This yields "122" from "212", for example.

The string obtained at this point is “0 or more characters ““1” followed by 0 or more characters ""2"”. No other pattern is possible.

Next

gsub(/(.)\1\1|1122|12/, "")

Deletes a specific character string from the left, but the regular expression is a little complicated.

The highlight is the part of (.)\1\1. This uses back references. It means that the character captured by (.) is followed by two characters, and as a whole, it matches “three lines of the same number”.

It also matches any "1122" and "12" that may exist at the boundary of the "1" and "2" columns.

We’ll remove these.

What kind of character string can be obtained after this conversion? It’s a bit boring, but let’s divide it by the number of ““1”`s.

First of all, since "111" is deleted first (because "1" which is a multiple of 3 is deleted), consider only when the number of "1" is 0, 1, 2. I know it’s good.

When "1" is 0, it is a string of 0 or more ““2” strings. There are three possible ””, “2”, and “22”, given that multiples of “2”` are removed.

Next, when there is one "1", if there are 0 ““2”s behind it, it is “1”, and if there is one ""2", the whole ("12") Is deleted to become "", and if there are two "2", it becomes "2". If there are more than two "2", don’t worry because "222" will be deleted. In other words, there can be three, ““1”, ””, and ""2".

Finally, when there are two "1", if there are 0 ““2”s following it, it is “11”. If there is one ""2", then ““12” is deleted. It becomes “1”, and if there are two “2”, the whole (“1122”) is deleted and becomes an empty string. If there are three “2”, the ""1122" is deleted and becomes ““2”. You don't have to think of four or more. That is, there can be four, ""11", "1", "", and ““2”`.

Whew, it was a pain.

After all, the converted string is

  • ""
  • "1"
  • "11"
  • "2"
  • "22"

There are only five possibilities.

Hashing leads to too much of these. that’s all.

Application

The remainder divided by 9 is exactly the same.

For the remainder divided by 2 or 5, you only have to look at the last digit (one’s place) (since 10 is divisible by 2 or 5).

Look at the last two digits of the remainder divided by 4 (since 100 is divisible by 4).

Look at the last 3 digits of the remainder divided by 8 (since 1000 is divisible by 8).

The remainder divided by 6 should be rather complicated. I want to try it someday.

I’m not sure if the remainder divided by 7 can be found without generating a numeric object.

Finally

Even if he asks, “What then?” I added the tag “Number theory”, but it’s not that big, it’s not practical, and it’s not very interesting. I just tried to think about it.

  1. modulo 3 is called “modulo 3” in formal mathematical terminology.