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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
robheus
Posts: 31
Joined: Thu Jun 12, 2008 5:01 pm

Problem 387

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

Re: Problem 387

Post by 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...
Last edited by JiminP on Fri Jun 08, 2012 7:02 pm, edited 1 time in total.
Image

LarryBlake
Posts: 100
Joined: Sat Aug 29, 2009 8:49 pm

Re: Problem 387

Post by 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.
Image

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

Re: Problem 387

Post by robheus »

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

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

Re: Problem 387

Post by ParadiceCity9 »

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

Post by sivakd »

yes
Image
puzzle is a euphemism for lack of clarity

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

Re: Problem 387

Post by robheus »

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?

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

Re: Problem 387

Post by hk »

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

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

Re: Problem 387

Post by robheus »

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

Post by blinder »

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

Post by blinder »

Ok I found, 2 must be a prime :D

halfpeaw
Posts: 1
Joined: Tue Jun 19, 2012 5:48 am

Re: Problem 387

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

Post by TripleM »

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

Post by beary605 »

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

I get 91662 for my answer :/

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

Re: Problem 387

Post by 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.
Image

beary605
Posts: 2
Joined: Tue Jun 19, 2012 7:46 pm

Re: Problem 387

Post by beary605 »

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

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

Re: Problem 387

Post by 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.
Image

Rishada is the gateway to free trade—but the key will cost you.

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

Re: Problem 387

Post by hk »

RishadanPort wrote:
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.
Image

MVMS1994
Posts: 1
Joined: Fri May 15, 2020 5:30 pm

Re: Problem 387

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

User avatar
kenbrooker
Posts: 156
Joined: Mon Feb 19, 2018 3:05 am
Location: Northern California, USA

Re: Problem 387

Post by kenbrooker »

Please consider...
Don't start begging others to give partial answers to problems
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

Post Reply