Virtual NoSQL DB event for Java DevsProject Euler # 43 in JavaScript — Sub-String Divisiblity in Pandigital Numbers. by@ethan.jarrellProject Euler # 43 in JavaScript — Sub-String Divisiblity in Pandigital Numbers.
January 19th 2018 1,712 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 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:
- [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.
Tags
Join Hacker Noon
Create your free account to unlock your custom reading experience.