# Solving the Rule of Divisibility by 13 in Java ## The challenge

“A divisibility rule is a shorthand way of determining whether a given integer is divisible by a fixed divisor without performing the division, usually by examining its digits.”

wikipedia.com

When you divide the successive powers of `10` by `13` you get the following remainders of the integer divisions:

`1, 10, 9, 12, 3, 4` because:

(For “mod” you can see: https://en.wikipedia.org/wiki/Modulo_operation)

Then the whole pattern repeats. Hence the following method:

Multiply the right most digit of the number with the left most number in the sequence shown above, the second right most digit to the second left most digit of the number in the sequence. The cycle goes on and you sum all these products. Repeat this process until the sequence of sums is stationary.

### Example:

What is the remainder when `1234567` is divided by `13`?

```.wp-block-code {
border: 0;
}

.wp-block-code > div {
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```7      6     5      4     3     2     1  (digits of 1234567 from the right)
×      ×     ×      ×     ×     ×     ×  (multiplication)
1     10     9     12     3     4     1  (the repeating sequence)```Code language: JavaScript (javascript)```

Therefore following the method we get:

`7×1 + 6×10 + 5×9 + 4×12 + 3×3 + 2×4 + 1×1 = 178`

We repeat the process with the number 178:

`8x1 + 7x10 + 1x9 = 87`

and again with 87:

`7x1 + 8x10 = 87`

From now on the sequence is stationary (we always get `87`) and the remainder of `1234567` by `13` is the same as the remainder of `87` by `13` (i.e `9`).

Call `thirt` the function which processes this sequence of operations on an integer `n (>=0)``thirt` will return the stationary number.

`thirt(1234567)` calculates 178, then 87, then 87 and returns `87`.

`thirt(321)` calculates 48, 48 and returns `48`

## The solution in Java code

Option 1 (using `dual while loops`):

``````class Thirteen {

public static long thirt(long n) {
int[] numbers = {1, 10, 9, 12, 3, 4};
while (n > 99){
long nr = ;
int i = ;
while (n > ){
nr += n%10 * numbers[i++%6];
n /= 10;
}
n = nr;
}
return n;
}
}
```Code language: Java (java)```

Option 2 (using `StringBuilder`):

``````class Thirteen {

private static final int[] remainders = {1, 10, 9, 12, 3, 4};

public static long thirt(long n) {
long count = ;
int i = ;
for (String number: new StringBuilder().append(n).reverse().toString().split("")) {
count += Integer.parseInt(number) * remainders[i%6];
i++;
}
return count == n ? count : thirt(count);
}
}
```Code language: Java (java)```

Option 3 (using a `while case`):

``````class Thirteen {

public static long thirt(long n) {

long previous = n;
long sum = ;

while (n != ){
sum += (n % 10);
n = n / 10;
sum += ((n % 10) * 10);
n = n / 10;
sum += ((n % 10) * 9);
n = n / 10;
sum += ((n % 10) * 12);
n = n / 10;
sum += ((n % 10) * 3);
n = n / 10;
sum += ((n % 10) * 4);
n = n / 10;
}

if (sum == previous) return sum;

return thirt(sum);
}
}
```Code language: Java (java)```

Option 4 (using a `char array`):

See also  My smallest code interpreter in Java
``````class Thirteen {

public static long thirt(long n) {
long sum = ;
int len = (""+n).length(), i = ;
for (char c : (""+n).toCharArray()) sum += (c-'0') * new int[]{1,10,9,12,3,4}[(len-i++-1) % 6];
return sum == n ? n : thirt(sum);
}

}
```Code language: Java (java)```

Option 5 (using a `stack`):

``````import java.util.Arrays;
import java.util.Stack;
class Thirteen {
public static long calculation(long input) {
Stack<Long> stack = new Stack<>();
Arrays
.asList(String.valueOf(input)
.split(""))
.forEach(x ->
stack.push(Long.parseLong(x))
);

int size = stack.size();
long[] numbers = new long[]{1, 10, 9, 12, 3, 4};

long sum = ;
for (int i = ; i < size; i++) {
sum = sum + stack.pop() * numbers[i % 6];
}

return sum;
}

public static long thirt(long input) {
long lastCalc = calculation(input);
while (true) {
if(calculation(lastCalc)==lastCalc){
return lastCalc;
}else{
lastCalc= calculation(lastCalc);
}
}
}
}
```Code language: Java (java)```

## Test cases to validate our Java solution

``````import static org.junit.Assert.*;
import org.junit.Test;

public class ThirteenTest {

private static int randInt(int min, int max) {
return min + (int)(Math.random() * ((max - min) + 1));
}
private static void testing(long actual, long expected) {
assertEquals(expected, actual);
}
@Test
public void test1() {
System.out.println("Fixed Tests: thirt");
testing(Thirteen.thirt(8529), 79);
testing(Thirteen.thirt(85299258), 31);
testing(Thirteen.thirt(5634), 57);
testing(Thirteen.thirt(1111111111), 71);
testing(Thirteen.thirt(987654321), 30);
}
public static long thirtSol(long n) {
int[] w = new int[] {1, 10, 9, 12, 3, 4};
while (true) {
long r = n; long q = -1; long c = ; int j = ;
while (q != ) {
q = (long)(r / 10);
c += (r % 10) * w[j % 6];
r = q;
j++;
}
if (c == n)
return c;
n = c;
}
}
@Test
public void test4() {
System.out.println("Random Tests");
for (int i = ; i < 200; i++) {
int p0 = randInt(150, 1500000000);
testing(Thirteen.thirt(p0), thirtSol(p0));
}
}
}
```Code language: Java (java)```

See also  The Benefits and Dangers of Artificial Intelligence
Tags:
Subscribe
Notify of 