Project Euler # 43 in JavaScript โ Sub-String Divisiblity in Pandigital Numbers. by@ethan.jarrell

January 19th 2018 1,694 reads

I finished #43 from projecteuler.net. Iโm going to walk through my process here of how I came to the solution. Fair warning however, I am not a mathematician. Iโm barely a decent programmer, but definitely not a mathematician. As I was doing this problem, it became evidently clear that my ineptitude at math is definitely a stumbling block when it comes to problems like these. So most of my solutions are absolutely the โbrute forceโ approach for that reason. Anyway, with that out of the way, Hereโs the problem:

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let *d*1 be the 1st digit, *d*2 be the 2nd digit, and so on. In this way, we note the following:

*d*2*d*3*d*4=406 is divisible by 2*d*3*d*4*d*5=063 is divisible by 3*d*4*d*5*d*6=635 is divisible by 5*d*5*d*6*d*7=357 is divisible by 7*d*6*d*7*d*8=572 is divisible by 11*d*7*d*8*d*9=728 is divisible by 13*d*8*d*9*d*10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

So hereโs the way I thought of this. For better or worse, I looked at this as a problem where, instead of one long 10 digit number, what I was really looking at was a series of 3 digit numbers. In the example below, the first group [460] would need to be divisible by 2 in order to meet the criteria. Then the second group, [603] would need to be divisible by 3 in order to meet the criteria, and so on and so forth.

My thought was that I could simply grab all of the numbers between 100 and 999, and test each number to see if it was divisible by 2, 3, 5, 7, etc. But then I realized I needed to modify my search because just getting the numbers between 100 and 999 isnโt all I needed. I also needed numbers that started with 0.

Take the following for example:

If Iโm getting all the numbers between 100 and 999, and Iโm at, for example, 258. Thereโs no reason to modify this digit. If 2 is a, 5 is b, and 8 is c, I donโt also need the combination bca and cba, because simply continuing up to 999 will also grab both of those. However, it would not grab some of these:

If the current number Iโm grabbing is 300, my current method wonโt also get 003 or 030. Or, if Iโm on 205, I wouldnโt also get 052, but I would get 502. Then I realized that the pandigital numbers donโt repeat or duplicate any digits. So in the middle example, I wouldnโt need 300, 003 or 030, since it repeats the 0 twice. In the bottom example I would need 052, but 502 would already be part of my method, so no modification there either. In these examples, the only combinations of letters I need are โabcโ and โbcaโ, but only โbcaโ if the middle digit is 0. Hereโs how that part of my code looks:

let numbersToTest = [];

for(i = 100; i < 999; i += 1) {

let str = i.toString();

let split = str.split("");

let a = parseInt(split[0]);

let b = parseInt(split[1]);

let c = parseInt(split[2]);

let combo1 = [a,b,c];

let combo3 = [0,a,c];

if(a != b &&

a != c &&

b != c){

numbersToTest.push(combo1);

}

if(b == 0 &&

a !== c &&

c !== 0){

numbersToTest.push(combo3);

}

}

What I did was loop over the numbers 100 to 999. I turn it into a string, split it, and convert each array element back into a number. Then I have combo1 and combo2. if b is 0, I push combo3, and if b isnโt 0, I push combo1. I also donโt want a, b, or c to be equal to each other, to avoid duplicates, so if any of them do equal each other, they donโt get pushed at all. I end up with all the 3 digit combinations that have only unique digit combinations between 100 and 999.

Now, I realize that there are two different things I need to test for in each combination. First, I need to figure out whether itโs divisible by a given number, ie, 2, 3, 5, 7, 11, 13, or 17.

But, look again at this chart:

Since I now have these in groups of 3, Iโm eventually going to smoosh them together and create a 10 digit number. However, in the first group here [460], the second and third digit of this group are equal to the first and second digit of the next group [603], and so on.

So as I go through each group of 3, I need to test whether or not itโs divisible by a certain number, and also see if the digits match the digits in the previous group. If itโs not divisible by the number Iโm looking for, or the numbers arenโt a match, I will discard it.

What I set out to do, was start with an array of all โxโs. Then, as I loop through my array of numbers to test, if the group is divisible by 2, then I push those three digits into my array of โxโs and replace and x with a number from that array. In my head, it should look like this:

Then I should have the same array I had before, but just with xโs along with the 3 digit numbers divisible by 2 occupying the 2nd, 3rd and 4th space in the array. My code looks something like this:

let testArr2 = [];

for (var i = 0; i < numbersToTest.length; i++) {

let testArr1 = ["x","x","x","x","x","x","x","x","x","x"];

let numbersJoin = numbersToTest[i].join("");

let number = parseInt(numbersJoin);

if (number % 2 == 0) {

testArr1[1] = numbersToTest[i][0];

testArr1[2] = numbersToTest[i][1];

testArr1[3] = numbersToTest[i][2];

testArr2.push(testArr1);

}

}

At this point, testArr2 holds the data that looks like the weird array in the diagram above with numbers and xโs. Next, I want to do the same thing, but with numbers divisible by 3, which would look like this:

And the JavaScriptโฆ

let testArr3 = [];

for (var i = 0; i < numbersToTest.length; i++) {

let testArr1 = ["x","x","x","x","x","x","x","x","x","x"];

let numbersJoin = numbersToTest[i].join("");

let number = parseInt(numbersJoin);

if (number % 3 == 0) {

testArr1[2] = numbersToTest[i][0];

testArr1[3] = numbersToTest[i][1];

testArr1[4] = numbersToTest[i][2];

testArr3.push(testArr1);

}

}

Once I get through all of the groups, Iโll have all these arrays with xโs, and a group of 3 numbers. Then, Iโll have to go back through, and see which groups match with each other. Here are the rest of my loops for numbers divisible by 5, 7, 11, 13, and 17:

let testArr4 = [];

for (var i = 0; i < numbersToTest.length; i++) {

let testArr1 = ["x","x","x","x","x","x","x","x","x","x"];

let numbersJoin = numbersToTest[i].join("");

let number = parseInt(numbersJoin);

if (number % 5 == 0) {

testArr1[3] = numbersToTest[i][0];

testArr1[4] = numbersToTest[i][1];

testArr1[5] = numbersToTest[i][2];

testArr4.push(testArr1);

}

}

let testArr5 = [];

for (var i = 0; i < numbersToTest.length; i++) {

let testArr1 = ["x","x","x","x","x","x","x","x","x","x"];

let numbersJoin = numbersToTest[i].join("");

let number = parseInt(numbersJoin);

if (number % 7 == 0) {

testArr1[4] = numbersToTest[i][0];

testArr1[5] = numbersToTest[i][1];

testArr1[6] = numbersToTest[i][2];

testArr5.push(testArr1);

}

}

let testArr6 = [];

for (var i = 0; i < numbersToTest.length; i++) {

let testArr1 = ["x","x","x","x","x","x","x","x","x","x"];

let numbersJoin = numbersToTest[i].join("");

let number = parseInt(numbersJoin);

if (number % 11 == 0) {

testArr1[5] = numbersToTest[i][0];

testArr1[6] = numbersToTest[i][1];

testArr1[7] = numbersToTest[i][2];

testArr6.push(testArr1);

}

}

let testArr7 = [];

for (var i = 0; i < numbersToTest.length; i++) {

let testArr1 = ["x","x","x","x","x","x","x","x","x","x"];

let numbersJoin = numbersToTest[i].join("");

let number = parseInt(numbersJoin);

if (number % 13 == 0) {

testArr1[6] = numbersToTest[i][0];

testArr1[7] = numbersToTest[i][1];

testArr1[8] = numbersToTest[i][2];

testArr7.push(testArr1);

}

}

let testArr8 = [];

for (var i = 0; i < numbersToTest.length; i++) {

let testArr1 = ["x","x","x","x","x","x","x","x","x","x"];

let numbersJoin = numbersToTest[i].join("");

let number = parseInt(numbersJoin);

if (number % 17 == 0) {

testArr1[7] = numbersToTest[i][0];

testArr1[8] = numbersToTest[i][1];

testArr1[9] = numbersToTest[i][2];

testArr8.push(testArr1);

}

}

Now, what Iโm thinking is that I can cycle through each array like this:

I would be checking to see if index 2 and 3 of array1, and index 2 and 3 of array2 match. If thereโs a match, I create a new array, including the first number from array1, and the last number from array2. Then, I would do the same thing, comparing the new array, with the array of numbers divisible by 5, like so:

With each loop, I would add one digit onto my magical set of numbers. Hereโs the actual JavaScript code, using nested for loops to make each match.

let finalArr9 = [];

for (var i = 0; i < testArr2.length; i++) {

for (var k = 0; k < testArr3.length; k++) {

let tempArr = ["x","x","x","x","x","x","x","x","x","x"];

if(testArr2[i][2] == testArr3[k][2] &&

testArr2[i][3] == testArr3[k][3]){

tempArr[1] = testArr2[i][1];

tempArr[2] = testArr2[i][2];

tempArr[3] = testArr2[i][3];

tempArr[4] = testArr3[k][4];

finalArr9.push(tempArr);

}

}

}

let finalArr10 = [];

for (var i = 0; i < finalArr9.length; i++) {

for (var k = 0; k < testArr4.length; k++) {

let tempArr = ["x","x","x","x","x","x","x","x","x","x"];

if(finalArr9[i][3] == testArr4[k][3] &&

finalArr9[i][4] == testArr4[k][4]){

tempArr[1] = finalArr9[i][1];

tempArr[2] = finalArr9[i][2];

tempArr[3] = finalArr9[i][3];

tempArr[4] = finalArr9[i][4];

tempArr[5] = testArr4[k][5];

finalArr10.push(tempArr);

}

}

}

let finalArr11 = [];

for (var i = 0; i < finalArr10.length; i++) {

for (var k = 0; k < testArr5.length; k++) {

let tempArr = ["x","x","x","x","x","x","x","x","x","x"];

if(finalArr10[i][4] == testArr5[k][4] &&

finalArr10[i][5] == testArr5[k][5]){

tempArr[1] = finalArr10[i][1];

tempArr[2] = finalArr10[i][2];

tempArr[3] = finalArr10[i][3];

tempArr[4] = finalArr10[i][4];

tempArr[5] = finalArr10[i][5];

tempArr[6] = testArr5[k][6];

finalArr11.push(tempArr);

}

}

}

let finalArr12 = [];

for (var i = 0; i < finalArr11.length; i++) {

for (var k = 0; k < testArr6.length; k++) {

let tempArr = ["x","x","x","x","x","x","x","x","x","x"];

if(finalArr11[i][5] == testArr6[k][5] &&

finalArr11[i][6] == testArr6[k][6]){

tempArr[1] = finalArr11[i][1];

tempArr[2] = finalArr11[i][2];

tempArr[3] = finalArr11[i][3];

tempArr[4] = finalArr11[i][4];

tempArr[5] = finalArr11[i][5];

tempArr[6] = finalArr11[i][6];

tempArr[7] = testArr6[k][7];

finalArr12.push(tempArr);

}

}

}

let finalArr13 = [];

for (var i = 0; i < finalArr12.length; i++) {

for (var k = 0; k < testArr7.length; k++) {

let tempArr = ["x","x","x","x","x","x","x","x","x","x"];

if(finalArr12[i][6] == testArr7[k][6] &&

finalArr12[i][7] == testArr7[k][7]){

tempArr[1] = finalArr12[i][1];

tempArr[2] = finalArr12[i][2];

tempArr[3] = finalArr12[i][3];

tempArr[4] = finalArr12[i][4];

tempArr[5] = finalArr12[i][5];

tempArr[6] = finalArr12[i][6];

tempArr[7] = finalArr12[i][7];

tempArr[8] = testArr7[k][8];

finalArr13.push(tempArr);

}

}

}

let finalArr14 = [];

for (var i = 0; i < finalArr13.length; i++) {

for (var k = 0; k < testArr8.length; k++) {

let tempArr = ["x","x","x","x","x","x","x","x","x","x"];

if(finalArr13[i][7] == testArr8[k][7] &&

finalArr13[i][8] == testArr8[k][8]){

tempArr[1] = finalArr13[i][1];

tempArr[2] = finalArr13[i][2];

tempArr[3] = finalArr13[i][3];

tempArr[4] = finalArr13[i][4];

tempArr[5] = finalArr13[i][5];

tempArr[6] = finalArr13[i][6];

tempArr[7] = finalArr13[i][7];

tempArr[8] = finalArr13[i][8];

tempArr[9] = testArr8[k][9];

finalArr14.push(tempArr);

}

}

}

At this point, I should have all of my arrays, completely full of numbers, except for the first digit, so I loop through all my new arrays, and I find out which digit of 0โ9 is missing, and add that digit to index 1 of the array.

let finalArr15 = [];

for (var i = 0; i < finalArr14.length; i++) {

let tempArr = ["x","x","x","x","x","x","x","x","x","x"];

tempArr[1] = finalArr14[i][1];

tempArr[2] = finalArr14[i][2];

tempArr[3] = finalArr14[i][3];

tempArr[4] = finalArr14[i][4];

tempArr[5] = finalArr14[i][5];

tempArr[6] = finalArr14[i][6];

tempArr[7] = finalArr14[i][7];

tempArr[8] = finalArr14[i][8];

tempArr[9] = finalArr14[i][9];

if (finalArr14[i].includes(0)==false){

tempArr[0] = 0;

}

else if (finalArr14[i].includes(1)==false){

tempArr[0] = 1;

}

else if (finalArr14[i].includes(2)==false){

tempArr[0] = 2;

}

else if (finalArr14[i].includes(3)==false){

tempArr[0] = 3;

}

else if (finalArr14[i].includes(4)==false){

tempArr[0] = 4;

}

else if (finalArr14[i].includes(5)==false){

tempArr[0] = 5;

}

else if (finalArr14[i].includes(6)==false){

tempArr[0] = 6;

}

else if (finalArr14[i].includes(7)==false){

tempArr[0] = 7;

}

else if (finalArr14[i].includes(8)==false){

tempArr[0] = 8;

}

else if (finalArr14[i].includes(9)==false){

tempArr[0] = 9;

}

if(tempArr[0] !== 0){

finalArr15.push(tempArr);

}

}

Now, If you did it this way, which I hope you didnโt because I know itโs garbage, but whatever. Like I said, Iโm definitely not a great mathematician. But, whatever. If you did it like me, you ended up with a butt load of duplicates. So, I looped through them all again, and if they included a digit twice, I donโt use it.

let finalArr16 = [];

for (var i = 0; i < finalArr15.length; i++) {

if(

finalArr15[i].includes(0) == true &&

finalArr15[i].includes(1) == true &&

finalArr15[i].includes(2) == true &&

finalArr15[i].includes(3) == true &&

finalArr15[i].includes(4) == true &&

finalArr15[i].includes(5) == true &&

finalArr15[i].includes(6) == true &&

finalArr15[i].includes(7) == true &&

finalArr15[i].includes(8) == true &&

finalArr15[i].includes(9) == true

){

finalArr16.push(finalArr15[i]);

}

}

After all that, you end up with only six matches:

- [4, 1, 0, 6, 3, 5, 7, 2, 8, 9]
- [4, 1, 3, 0, 9, 5, 2, 8, 6, 7]
- [4, 1, 6, 0, 3, 5, 7, 2, 8, 9]
- [1, 4, 0, 6, 3, 5, 7, 2, 8, 9]
- [1, 4, 3, 0, 9, 5, 2, 8, 6, 7]
- [1, 4, 6, 0, 3, 5, 7, 2, 8, 9]

Then, itโs simply a matter of converting the arrays back to numbers, and adding them together.

I know this is by far not the best solution, but, for a not mathematician, I think I did okay. Iโm going to go give myself a bit pat on the back, drink an ice cold root beer, and eat a half pint of ice cream.

Join Hacker Noon

Create your free account to unlock your custom reading experience.