Hackernoon logoProject Euler # 43 in JavaScript โ€” Sub-String Divisiblity in Pandigital Numbers. by@ethan.jarrell

Project Euler # 43 in JavaScript โ€” Sub-String Divisiblity in Pandigital Numbers.

Author profile picture

@ethan.jarrellEthan Jarrell

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 d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

  • d2d3d4=406 is divisible by 2
  • d3d4d5=063 is divisible by 3
  • d4d5d6=635 is divisible by 5
  • d5d6d7=357 is divisible by 7
  • d6d7d8=572 is divisible by 11
  • d7d8d9=728 is divisible by 13
  • d8d9d10=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:

  1. [4, 1, 0, 6, 3, 5, 7, 2, 8, 9]
  2. [4, 1, 3, 0, 9, 5, 2, 8, 6, 7]
  3. [4, 1, 6, 0, 3, 5, 7, 2, 8, 9]
  4. [1, 4, 0, 6, 3, 5, 7, 2, 8, 9]
  5. [1, 4, 3, 0, 9, 5, 2, 8, 6, 7]
  6. [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.

Tags

Join Hacker Noon

Create your free account to unlock your custom reading experience.