In my previous post I shared some code to generate permutations. We can use this code to solve a problem I’ve posted about previously. Find the only 10 digit number which uses each of the digits 0 – 9 and has the following property:
The first digit should be divisible by 1.
The number formed by the first 2 digits should be divisible by 2.
The number formed by the first 3 digits should be divisible by 3.
And so on until the number formed by the first 10 digits should be divisible by 10.
The 5th digit in our number will obviously need to be 5 and the tenth digit will need to be 0. This still leaves us with 8 digits to place in the number. 8 digits can be selected in 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 ways. This is usually written as 8! (pronounced factorial 8). In general, the factorial of an integer is the result of multiplying it and all lower integers down to 1. 8! is 40,320 which is a lot of numbers to try.
Luckily, we can reduce this in a few ways. For a number to be divisible by an even digit (2, 4, 6 or 8), it has to be an even number, ie end in a 0, 2, 4, 6 or 8. So, the digits in the 2nd, 4th, 6th and 8th position in our final number have to be even, which means the digits in the first, 3rd, 7th and 9th position have to be odd.
So, we can generate a list of the possible permutations of the odd digits, and another list of the possible permutations of the even digits. Interleave these with the 5 and the 0 to create a 10 digit number and test that against the conditions. There are 4! possible permutations of the 4 odd digits, and the same for the even digits. 4! is 24, so we have a possible 24 * 24 numbers to test. This is 576, which is a vast reduction on our original 3,628,800.
For example, one of the possible combinations is ‘7139’ with ‘4268’. Combining these with the ‘5’ and the ‘0’ gives ‘7412563890’. Obviously, this does not satisfy the conditions of the puzzle, so we would need to look at the next permutation.
I’ve created a small html page to demonstrate this. Most of it is self-explanatory, line 22 is a button which runs the Javascript code. Lines 24 and 25 are two placeholders, one for the result and the second for any messages. Line 26 links to the Javascript code.
1<!DOCTYPE html>
2<html>
3 <head>
4 <title>Ten Digit Puzzle</title>
5 </head>
6 <body>
7 <h1>10 Digit Number</h1>
8 <h5>
9 <p>Find the only 10 digit number which uses each of the digits 0 - 9 and has the following property.</p>
10 <p>The number formed by the first n digits should be divisible by n, ie
11 <ul>
12 <li>The number formed by the first digit should be divisible by 1, a given.</li>
13 <li>The number formed by the first 2 digits should be divisible by 2.</li>
14 <li>The number formed by the first 3 digits should be divisible by 3.</li>
15 <li>The number formed by the first 4 digits should be divisible by 4.</li>
16 <li>And so on until the number formed by the first 10 digits should be divisible by 10.</li>
17 </ul>
18 </p>
19 <p>Click on the button for the solution.</p>
20 </h5>
21 <div>
22 <input id="clickMe" type="button" value="Solution" />
23 </div>
24 <div id="results"></div>
25 <div id="message"></div>
26 <script type="text/javascript" src="tendigits.js"></script>
27 </body>
28</html>
This is the Javascript code: Line 1 adds a listener for the button click. Lines 4 and 5 get the placeholders for the results and messages. The string sOdd is initialised with ‘1379’ and cycles through the 24 permutations at line 30. For each iteration of sOdd, the string sEven is initialised with ‘2468’ and cycles through the 24 permutations at line 28. Lines 13 and 14 create the 10 digit number; this is checked in the loop from line 23. If successful, the result is displayed else a running count is displayed in the messages.
1document.getElementById("clickMe").addEventListener("click", getSolution, false);
2
3function getSolution() {
4 message = document.getElementById("message");
5 results = document.getElementById("results");
6 tested = 0;
7 sOdd = '1379';
8 while (sOdd != "") {
9 sEven = "2468";
10 while (sEven != "") {
11 tested++;
12 //create candidate number
13 s = sOdd.substring(0, 1) + sEven.substring(0, 1) + sOdd.substring(1, 2) + sEven.substring(1, 2) + "5" +
14 sEven.substring(2, 3) + sOdd.substring(2, 3) + sEven.substring(3, 4) + sOdd.substring(3, 4) + "0";
15 //check number
16 success = true;
17 for (z = 2; z < 9; z++) {
18 x = parseInt(s.substring(0, z));
19 if ((x % z) != 0) {
20 success = false;
21 break;
22 }
23 }
24 if (success) results.innerHTML = results.innerHTML + "<p> Success " + tested + " " + s + "</p>"; else {
25 if (message.innerText == "") message.innerHTML = "Failed: ";
26 message.innerHTML = message.innerHTML + tested.toString().padStart(3, "0") + " ";
27 }
28 sEven = getNextPerm(sEven);
29 }
30 sOdd = getNextPerm(sOdd);
31 }
32}
33
34function getNextPerm(s) {
35 //create array of elements
36 n = s.length;
37 const elements = [];
38 for (z = 0; z < n; z++) elements[z] = s.substring(z, z + 1);
39 //find the largest index k such that elements[k] < elements[k + 1]
40 for (k = n - 2; k >= 0; k--) {
41 if (elements[k] < elements[k + 1]) {
42 //find the largest index l greater than k such that elements[k] < elements[l]
43 for (l = n - 1; l > k; l--) {
44 if (elements[k] < elements[l]) {
45 //swap elements k and l
46 sTemp = elements[k];
47 elements[k] = elements[l];
48 elements[l] = sTemp;
49 //reverse remainder of string
50 k++;
51 n--;
52 while (k < n) {
53 sTemp = elements[k];
54 elements[k] = elements[n];
55 elements[n] = sTemp;
56 k++;
57 n--;
58 }
59 //create string from array elements
60 t = "";
61 for (z = 0; z < elements.length; z++) t = t + elements[z];
62 return t;
63 }
64 }
65 }
66 }
67 //not found
68 return "";
69}
70
You can test the code here.
