A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.

Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one

Someone already tried problem 387?
It's about numbers that can be divided by their digitsum, called harshad.
For this problem I'll need a prime table up to 10 ^ 7 to check the full range of number up to 10 ^ 14.

Anyway, running the script till 10 ^ 4 does not yet give me a correct result.

EDIT:
I am struggling with the right definition. A harshad number is dividable by the digitsum, and therefore can't be prime.
So, what does the property strong, right truncatable harshad prime mean?
1) The number is harshad (dividable by it's digitsum) and the resulting number is prime.
2) The number is right truncatable (recursivably) harshad.

I guess my code got confused about the various definitions.

Q. are numbers below 10 all harshad?

Table (less then 10000) strong hashad and truncatable harshad
--------------------------------------------------------------------------
18 18/9=2 (prime)

"Strong, right truncatable Harshad primes" are prime numbers, which becomes strong, right truncatable Harshad numbers when the last digit is omitted.

For example(it's in the problem), 2011 is a strong, right truncatable Harshad prime number, because the number 201, not 2011, is a right truncatable Harshad number.

By the way, I got 90619 (for 10^4) correctly, but I constantly gets '2527xxx6317xxx7' (for 10^14) which is not correct...

Last edited by JiminP on Fri Jun 08, 2012 7:02 pm, edited 1 time in total.

Take the number 7. It is divisible by its digit sum, so it's a Harshad. However, 7 / 7 (the digit sum) = 1, which is not prime. It's not a Strong Harshad Number.

201 / 3 = 67, which is prime. 201 is a Strong Harshad Number.

You're looking for numbers which:
1. Are prime,
2. When right-truncated, yield a Strong Harshad Number.

LarryBlake wrote:Take the number 7. It is divisible by its digit sum, so it's a Harshad. However, 7 / 7 (the digit sum) = 1, which is not prime. It's not a Strong Harshad Number.

201 / 3 = 67, which is prime. 201 is a Strong Harshad Number.

You're looking for numbers which:
1. Are prime,
2. When right-truncated, yield a Strong Harshad Number.

Thanks. I now at least got the correct answer for n=10000.

But unfortunately the script does not scale well enough, 100000000 is already taking an awfull lot of time (5m27.109s).

So I guess a smarter algorithm is needed.

EDIT: changing the order of evaluation already made a significant speed up.

hk wrote:My prog needs 1 millisec for the limit 10^8.

I haven't keep track of it but some minutes I guess. I assume your script does not check every n individually for the three properties involved, but maybe constructs the numbers with the right properties in a different way. Think I have to figure that out myself.

EDIT: in fact the timing is some seconds instead minutes, it were the debug printf statements that consumed so much time...

I think I may be misinterpreting the problem. To my understanding I need to find all prime numbers that when you truncate the right digit the the number becomes a Harshad number, where the first division of the summation parts is prime, but future right digit truncation just needs to result in more harshad numbers.

So for example 8461 is prime, when you truncate you get 846 thus 846/18 = 47 which is prime and then 84 / 12 and 8/8 not prime but still Harshad. So either my conditions are wrong or I'm making a stupid mistake is there a number from the above list that I am missing?

Edit*
Definitely Fat Fingered my issue to skip all primes ending in 7, serves me right for coding something after midnight. Plus side 5 minute fix later everything worked like a champ.

Last edited by halfpeaw on Wed Jun 20, 2012 3:48 pm, edited 1 time in total.

If oftentimes helps to make a brute-force program first just so you have something to compare against.

Make sure all the numbers in your <10000 list are actually prime. Then lop off the rightmost digit of each and check if the resulting numbers are strong Harshad numbers. Next, continue lopping off the rightmost digits, verifying that the resulting numbers are still Harshad numbers.