Problem 037

[pjt33]

1 is not a prime.

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

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

[wbmstrmjb]

Sorry about posting possible answer.

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

Thanks.

[Georg]

Problem 37
Problem #37

[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]

never mind, found my mistake.

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

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

[bearturtle]

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

[Shahzaad]

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

[elendiastarman]

You still have to find the other 6...

[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]

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]

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]

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]

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

[thundre]

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]

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

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