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

Don't post any spoilers
pjt33
Posts: 28
Joined: Mon Oct 06, 2008 5:14 pm

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

1 is not a prime.

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

### Problem 37a

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.

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

### Re: Problem 37 Error

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

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

Thanks.

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

### Re: Problem 37 Error

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

### Re: Problem 037

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

never mind, found my mistake.

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

### Re: Problem 037

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.

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

### Re: Problem 037

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&egrave;tes sont l&agrave;.

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

### Re: Problem 037

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

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

### Re: Problem 037

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

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

### Re: Problem 037

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

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

### Re: Problem 037

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

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.

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

### Re: Problem 037

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

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?

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

### Re: Problem 037

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

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

### Re: Problem 037

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.

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

### Re: Problem 037

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

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?