Project Euler 387 - Harshad Numbers

Official link:

Thought Process

Generating primes will take way too long so I wanted to find a way to generate right truncatable numbers first, to do this I made a function

  1. RightTruncHarshadGen(digits)

    • This function will generate all right truncatable numbers less than 10^digits

    • The way I do this is by using a stack. I start with stack = [1,2,3,4,5,6,7,8,9] and a list righttrunc = [1,2,3,4,5,6,7,8,9]

      1. I then pop off the first element of the stack, I then check if that number, with all numbers 0 to 9 appended to the end is a harshad number

      2. For example imagine we pop off 2, then we will check if 20, 21, 22, ..., 29 are Harshad numbers, if they are then we append them to righttrunc

    • This way we start from bottom to top and generate all the right truncatable numbers, we stop once the stack is empty. Make sure to add a condition to not append number > 10^digits

I then made a second function to finish off the problem

  1. compute(digits)

    • Function takes an input digits and this function will generate a list = RightTruncHarshadGen(digits)

    • Then, I create a candidate list, I go through the RightTruncHarshadGen(digits) list and add all numbers such that when divided by the sum of their digits, is a prime to the candidates list

    • Lastly, we go through candidates and I append [1,3,5,7,9] to the end of the number and check if the new number is a prime, if it is then we have found a number that when we remove the last digit, is Right Truncatable Harshad number from step 1 and a Strong Harshad Number from step 2, therefore it is a Strong, Right Truncatable Harshad Primes and add that to a total and return it at the end

Interactive Code

Enter an integer (yourinput)

Code will output the sum of the Strong, Right Truncatable Harshad Primes < 10^yourinput