## Problem 387

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

Don't post any spoilers
robheus
Posts: 31
Joined: Thu Jun 12, 2008 5:01 pm

### 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?

--------------------------------------------------------------------------
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
Posts: 14
Joined: Sun Nov 06, 2011 3:07 am
Location: Seoul, South Korea

### Re: Problem 387

(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...
Last edited by JiminP on Fri Jun 08, 2012 7:02 pm, edited 1 time in total. LarryBlake
Posts: 100
Joined: Sat Aug 29, 2009 8:49 pm

### Re: Problem 387

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
Posts: 31
Joined: Thu Jun 12, 2008 5:01 pm

### Re: Problem 387

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.

100000000 now only takes 0m10.346s

Posts: 15
Joined: Sat Dec 17, 2011 7:15 pm
Location: Charlottesville, Virginia

### Re: Problem 387

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

sivakd
Posts: 217
Joined: Fri Jul 17, 2009 9:37 am
Location: California, USA
Contact:

### Re: Problem 387

yes puzzle is a euphemism for lack of clarity

robheus
Posts: 31
Joined: Thu Jun 12, 2008 5:01 pm

### Re: Problem 387

ParadiceCity9 wrote: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
Posts: 10811
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: Problem 387

My prog needs 1 millisec for the limit 10^8. robheus
Posts: 31
Joined: Thu Jun 12, 2008 5:01 pm

### Re: Problem 387

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... blinder
Posts: 2
Joined: Sun Jun 10, 2012 10:48 pm

### Re: Problem 387

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

blinder
Posts: 2
Joined: Sun Jun 10, 2012 10:48 pm

### Re: Problem 387

Ok I found, 2 must be a prime halfpeaw
Posts: 1
Joined: Tue Jun 19, 2012 5:48 am

### Re: Problem 387

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.
Last edited by halfpeaw on Wed Jun 20, 2012 3:48 pm, edited 1 time in total.

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

### Re: Problem 387

You aren't misinterpreting the problem.

There is at least one Harshad number ending in a 7 beary605
Posts: 2
Joined: Tue Jun 19, 2012 7:46 pm

### Re: Problem 387

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

I get 91662 for my answer :/

Marcus_Andrews
Posts: 1473
Joined: Wed Nov 09, 2011 5:23 pm

### Re: Problem 387

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
Posts: 2
Joined: Tue Jun 19, 2012 7:46 pm

### Re: Problem 387

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

Posts: 78
Joined: Mon Jun 10, 2013 7:31 am

### Re: Problem 387

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. Rishada is the gateway to free trade—but the key will cost you.

hk
Posts: 10811
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: Problem 387

Wed Aug 21, 2019 4:31 am
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
Posts: 1
Joined: Fri May 15, 2020 5:30 pm

### Re: Problem 387

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
Posts: 156
Joined: Mon Feb 19, 2018 3:05 am
Location: Northern California, USA

### Re: Problem 387 