7_division_criterium.Rmd

---
title: "Division by $7$ criterium"
author: "Youssef Allouah"
date: "15/03/2014"
output: html_document
---

```{r setup, include=FALSE}
knitr::opts_chunk$set(echo = TRUE)
```

## How to check if we can divide by $7$?

It can be useful in many situations to know whether a given integer can be divided by another. Imagine you are a teacher and have a classroom of $21$ students. Also, imagine you want to break them into groups of a certain size for a field research. If you don't think carefully about what integer you are dividing $21$, you could end up with a group of only one student and $5$ groups of $4$, for example.

There are very nice criteria to figure out pretty quickly whether an integer can divide another. The simplest would be the division by $2$: even numbers have a unit digit that is either $2$,$4$,$6$ or $8$. Another one is division by $3$: if the sum of the digits of your input number is a multiple of $3$, then your original number is itself dividible by $3$. This useful when you have very large numbers.

Now, for the sake of Science, let us think about a similar criterium for division by $7$. To my knwoledge, there is simple way to decide whether a large number can be divided by $7$ only by using hands. If you are not convinced: Can $265461$ be divided by $7$? How about $33626741281$?

I tried to use the thinking process that led to the other simple criteria. The idea is to write the integer $n \in \mathbb{N}$ we are interested in the decimal base:

$n = \sum_k a_k.10^k$ where $a_k$ is an integer s.t. $a_k \in \{1,2,\dots,9\}$ and $a_k \equiv \left\lfloor\dfrac{n}{10^k}\right\rfloor (\bmod 10)$

Then, what remains is to compute the euclidean division remainders of the powers of $10$ by $7$. 

The sequence of remainders to keep in mind is: $1, 3, 2, 6, 4, 5$.
We do not need the remainders of all the powers of $10$. In fact, we only needed those of the $6$ first powers of $10$ because $10^6 \equiv 1 (\bmod 7)$.

## An algorithm to check the divisibility by $7$
### Idea
Let $n = \sum_k a_k.10^k \in \mathbb{N}$ be the decimal base writing of the input integer $n$. 

We will be mapping each digit $a_k$ to one of the six remainders of the previous section ($1, 3, 2, 6, 4, 5$) based on the remainder of $k$ by $6$. The buckets are defined as follows: $b_p = \{a_k | k \equiv p (\bmod 6)\}$.

This mapping will then enable us to perform operations on these six buckets to get back to a very simple verification of divisibility by $7$.

### Example
Let us consider our previous example $33626741281$. 

We group the digits in the following buckets: $b_0 = \{1,6\}, b_1 = \{8,2\}, b_2 = \{2,6\}, b_3 = \{1,3\}, b_4 = \{4,3\}, b_5 = \{7\}$. The buckets are themselves respectively mapped respectively to the remainders $1, 3, 2, 6, 4, 5$.

We then compute a weighted sum of the values within the buckets. The weights are the remainders mapped to each bucket. In this example, the weighted sum is equal to $140$.

$140$ can be divided by $7$, therefore $33626741281$ can be divided by $7$ as well! You can verify that using a calculator.

As you can see in the example, we went from a 11-digit number to a 3-digit number only by regrouping digits together and computing a simple weighted sum.

### Code
```{python}
import numpy as np

def check_divisibility(n):
  #First, we embed the input integer into a list of its digits
  x = str(n)
  digits = list(x)
  
  #We fill with zeros on the left to have length multiple of 6
  t = 6-len(digits)%6
  for i in range(t):
    digits = ['0']+digits
  
  #We now get our digits matrix
  matrix = np.array(digits).reshape((-1,6))
  matrix = np.flipud(matrix)
  matrix = matrix.astype('int32')
  
  remainders = np.array([5, 4, 6, 2, 3, 1])
  
  #We now compute the weighted sum
  
  #We can use this chunk as it is simple implementation
  
  #s = 0
  #for i in range(6):
  #  s += matrix[:, i].sum()*remainders[i]
  
  #To make use of vectorization, we can use this implementation
  s = np.sum(matrix@remainders)
  
  print('Simplified number: ', s)
  print('Is', n,'divisible by 7?: ',s%7 == 0)
  
check_divisibility(33626741281)
```