Problem 037

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.
pjt33
Posts: 28
Joined: Mon Oct 06, 2008 5:14 pm

Re: problem 37 : on truncatable primes [1373 left-truncatable?]

Post by pjt33 »

1 is not a prime.

wbmstrmjb
Posts: 2
Joined: Wed Nov 19, 2008 9:50 pm

Problem 37a

Post by wbmstrmjb »

According to the definition of Problem 37, there exist 26 numbers that are prime truncatable (just counting the ones under 10,000,000) from both directions, not 11 as stated in the problem. I have double checked each number and all fit the description. They are (### deleted - ed_r ###). These are the ones under 10,000,000. Is the problem worded incorrectly or did I miss something? Thanks.

User avatar
ed_r
Posts: 1009
Joined: Sun Jul 29, 2007 9:57 am

Re: Problem 37 Error

Post by ed_r »

Please don't post answers (or attempted answers). I edited your post to remove the spoiler.

11 was one of the ones in your list. I'll leave you to work out why that's wrong ...
!647 = &8FDF4C

wbmstrmjb
Posts: 2
Joined: Wed Nov 19, 2008 9:50 pm

Re: Problem 37 Error

Post by wbmstrmjb »

Sorry about posting possible answer.

I guess I had to check my prime number definition again. Always thought 1 was prime.

Thanks.

User avatar
Georg
Posts: 157
Joined: Mon Jan 21, 2008 7:00 am
Location: Mannheim, Germany
Contact:

Re: Problem 37 Error

Post by Georg »


payprplayn
Posts: 2
Joined: Wed Jun 24, 2009 8:17 pm

Re: Problem 037

Post by payprplayn »

I've found 11 such primes so far (all are under 10000) that satisfy the conditions. Before you ask, I didn't make the mistake of considering 1prime. The sum of these numbers is returned as incorrect, but I've checked and rechecked them and they all meet the requirements.

payprplayn
Posts: 2
Joined: Wed Jun 24, 2009 8:17 pm

Re: Problem 037

Post by payprplayn »

never mind, found my mistake.

bearturtle
Posts: 2
Joined: Fri Aug 14, 2009 9:56 pm

Re: Problem 037

Post by bearturtle »

Having some trouble understanding where I'm going wrong on this one. If anyone can give me a hint, PM me and I'll explain what I've done so far.

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Problem 037

Post by daniel.is.fischer »

First of all, if you've been told otherwise before: 1 is not a prime.
If that is not where you went wrong, PM me.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

bearturtle
Posts: 2
Joined: Fri Aug 14, 2009 9:56 pm

Re: Problem 037

Post by bearturtle »

Thanks to elendiastarman for the help. I figured out my problem, and no I wasn't counting 1 as a prime.

Shahzaad
Posts: 2
Joined: Mon Jan 04, 2010 11:52 pm

Re: Problem 037

Post by Shahzaad »

I am confused - aren't five of the primes given to you in the question?!
i.e 3797, 797, 97, 379 and 37

User avatar
elendiastarman
Posts: 410
Joined: Sat Dec 22, 2007 8:15 pm

Re: Problem 037

Post by elendiastarman »

You still have to find the other 6...
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Image

Diadem
Posts: 11
Joined: Tue Jan 05, 2010 8:57 pm

Re: Problem 037

Post by Diadem »

Whoops, I almost crashed windows :)

My algoritm (written in c) searched the first 100M numbers in under 4 seconds So I thought "Oh, I can do the first 1G too". But then my prime sieve started trying to allocate 4 gigabytes of memory and that didn't work. First time memory has been a limit so far!

Not that it matters. I have more tricks up my sleeve, and found the right answer :)

Fenrisulvur
Posts: 1
Joined: Sat Jan 09, 2010 3:54 pm

Re: Problem 037

Post by Fenrisulvur »

Dear god, really? There are combinatoric strategies which will easily give you blink-of-eye performance, there is absolutely no need for an upper bound. In fact a lot of the problems in the 30-40 range have very nice combinatoric solutions - especially 34. ;)

Also, developing and maintaining a separate prime generator/checker component that you can link in really pays off.


Anyway, I've really liked the 30-40 range, I've written some of my best answers of the whole project here. My answers are meeting my collective-blink-of-eye execution-time goals well, and I'm really proud of the arbitrary-radix solutions I've cooked up for most of the radix-dependent problems.

I'm going to have to dig up/start the Problem 040 thread, though. My answer is a comprehensive arbitrary-radix beast that takes an arbitrary array of digit indices and appears to be bug-free (it gave the right answer), but the algorithm is borderline black magic.

EDIT: Also, lol at the amount of times "1 is not a prime number" have been repeated here.

Diadem
Posts: 11
Joined: Tue Jan 05, 2010 8:57 pm

Re: Problem 037

Post by Diadem »

Fenrisulvur wrote:Dear god, really? There are combinatoric strategies which will easily give you blink-of-eye performance, there is absolutely no need for an upper bound. In fact a lot of the problems in the 30-40 range have very nice combinatoric solutions - especially 34. ;)
I know. I had long ago solved the problem, and was just fooling around seeing if I could make the code faster, and seeing how its timing behaved with higher upper bounds. It's always fun to perfect code once you've solved a problem.

I just thought it was funny that my memory actually gives the upper bound on how many primes I can generate. Though I could always use bits. Still that's only an order of magnitude.

But I'm pretty proud that my code is that fast.

Osprey
Posts: 2
Joined: Wed Apr 13, 2011 8:21 pm

Problem 037

Post by Osprey »

In Problem 37 you are supposed to find 11 primes. My program finds 10 primes pretty quickly, but then takes forever and bumps into the limit I have set up.

My method is a pretty brute force algorithm.

The question I have is: Is the 11th number considerably bigger than the 10th number, or is my program simply wrong in some way?

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

Re: Problem 037

Post by hk »

Please don't start a new topic for a problem when there already exists one.
Image

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: Problem 037

Post by thundre »

Osprey wrote:In Problem 37
The question I have is: Is the 11th number considerably bigger than the 10th number, or is my program simply wrong in some way?
Yes, the 11th and final number is quite a bit larger than the 10th. Raise your limit.

You could also try to figure out a more clever algorithm. My Java program finishes in less than a second, and it does not have a limit of 11 solutions or any maximum number. It knows when to give up.
Image

Osprey
Posts: 2
Joined: Wed Apr 13, 2011 8:21 pm

Re: Problem 037

Post by Osprey »

Thanks you for the assertion, I'll try to make my program a little intelligent :)

panther-tamer
Posts: 4
Joined: Mon Aug 15, 2011 3:38 pm

Re: Problem 037

Post by panther-tamer »

Just how bigger the eleventh number is?

It takes 7 seconds for my algorithm to produce 10 numbers, but the 11th is still way too far away. Approximately how faster should my algorithm be?

Post Reply