Problem 387

[robheus]

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)

21 21/3=7 (prime)

27 27/9=3 (prime)

42 42/6=7 (prime)

45 45/9=5 (prime)

63 63/9=7 (prime)

84 84/12=7 (prime)

201 201/3=67 (prime) 20/2=10

207 207/9=23 (prime) 20/2=10

209 209/11=19 (prime) 20/2=10

247 247/13=19 (prime) 24/6=4

402 402/6=67 (prime) 40/4=10

407 407/11=37 (prime) 40/4=10

423 423/9=47 (prime) 42/6=7

481 481/13=37 (prime) 48/12=4

603 603/9=67 (prime) 60/6=10

801 801/9=89 (prime) 80/8=10

803 803/11=73 (prime) 80/8=10

804 804/12=67 (prime) 80/8=10

846 846/18=47 (prime) 84/12=7

2007 2007/9=223 (prime) 200/2=100 20/2=10

2043 2043/9=227 (prime) 204/6=34 20/2=10

4086 4086/18=227 (prime) 408/12=34 40/4=10

4203 4203/9=467 (prime) 420/6=70 42/6=7

4809 4809/21=229 (prime) 480/12=40 48/12=4

8406 8406/18=467 (prime) 840/12=70 84/12=7


SUM: 32288

The problem description says however: 90619

[JiminP]

(I was wrong.. sorry..)

"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...

[LarryBlake]

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.

[robheus]

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.

100000000 now only takes 0m10.346s

[ParadiceCity9]

Can someone verify my number for 10^8? I get 130459097.

[sivakd]

yes

[robheus]

Can someone verify my number for 10^8? I get 130459097.

I get 130459097, so this seems to be correct. How much exution time did it take?

[hk]

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

[robheus]

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...

[blinder]

I get 90438. Where are the missing 181s?
My strong, right truncatable Harshad prime is 211. Are there any before 211?

[blinder]

Ok I found, 2 must be a prime

[halfpeaw]

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.

For up to 10000 My list is...

• 181
  211
  271
  421
  631
  2011
  2099
  2473
  4021
  4073
  4079
  4231
  4813
  8011
  8039
  8461

Sum: 54026

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.

[TripleM]

You aren't misinterpreting the problem.

There is at least one Harshad number ending in a 7

[beary605]

What are the strong right-truncatable Harshad primes below 10000?

I get 91662 for my answer :/

[Marcus_Andrews]

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.

[beary605]

Thanks. My is_prime function was returning True for 1. Solved!

[RishadanPort]

I'm having quite a lot of problem with the upper bound of 10^14.

Was the upper bound of this problem ever increased?

Even using a bitwise sieve, i have problems even allocating that much. Probably some better way to do it without a huge sieve then.

[hk]

I'm having quite a lot of problem with the upper bound of 10^14.

Was the upper bound of this problem ever increased?

No

Even using a bitwise sieve, i have problems even allocating that much. Probably some better way to do it without a huge sieve then.

Perhaps you have to invent another approach than using a sieve.

[MVMS1994]

Hi Admin,

Could you please confirm if the answer for
10^6 is: 1188721
10^7 is: 10057005

I'm still trying to improve my algo. Any hint/reference material is highly appreciated. Current for 10^7 takes ~7 seconds in my system.

[kenbrooker]

Please consider...

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