Ponder This - March 2023

[Xyzzy]

https://research.ibm.com/haifa/ponde...March2023.html

[Tyler Busby]

My best candidate so far using a moderately unoptimized stochastic solver is 25 digits. It's an interesting problem that seems to resist being broken down into subproblems, as it's not guaranteed that taking the "exception" later rather than earlier will always be optimal.

[dg211]

Like the previous poster, I can't really see a smart way to do this problem. My single-threaded code for the base problem took nearly 2 hours, and the bonus problem is substantially harder. I've now multi-threaded my code, but it looks like it's going to take about 2 days to find an answer. I'm using python and primefac, not sure if other languages might be faster but I assume primefac is using C or something behind the scenes, and the isprime function seems to be similar in speed to Pari/GP. Without giving any spoilers as to the details, has anyone come up with a smarter approach?

[EdH]

My approach was less smart, brute force, with C++, but it took a couple hours (maybe - I didn't time it) for the base problem and I haven't seen a solution to the bonus part after many days. I didn't time anything, but I also ran a version that included all the 0-5 for the basic and it completed 0-4 toward the bonus. They also haven't posted or responded to my email, so I don't even know if I'm on the right track. I have been in error in the past, but at least then they told me, so I could try something else.

I'm going to entirely rework what I did, in C this time, and see if it does better and also use it to check my previous solutions.

[uau]

Originally Posted by dg211

Without giving any spoilers as to the details, has anyone come up with a smarter approach?

My Python code (using is_prime from gmpy2) was faster, but not by so much that it'd likely indicate a fundamentally different search.

[dg211]

Just did a quick test and seems like gmpy2 is about 6 times faster than the library I was using, so I'll switch to that, thanks!

[Citrix]

Originally Posted by dg211

Like the previous poster, I can't really see a smart way to do this problem.

For a number to be prime the last digit must be odd and not 5
Also can avoid numbers that will be divisible by 3.

This significantly limits the search space.

[SmartMersenne]

How large (in terms of number of digits) are the best solutions people found so far (for both problems)?

[tgan]

How can we know that a solution is the optimal

[SmartMersenne]

Originally Posted by tgan

How can we know that a solution is the optimal

By checking with your friends

[uau]

Originally Posted by tgan

How can we know that a solution is the optimal

Do an exhaustive search of all possible solutions.