Prime Chains

Back to Problem Solutions forum

Guy Gervais     2014-08-20 16:26:07
User avatar

Thank you Moriarty for the suggestion; I really enjoyed this problem. Lost a bit of sleep trying to figure out a not-to-slow solution. :)

Moff     2014-08-20 18:26:29
User avatar

I enjoyed this problem too. But I still don't like my solution (very slow). But i post it

Next i'll try to use a problem notes.

Rodion (admin)     2014-08-20 18:37:04
User avatar

By the way what do you mean by "very slow"? How many seconds / hours / days does it take? :)

UPD: I've uploaded my solution - one described in "notes" - it runs in about 3 seconds on my AMD A8-5600K. I do not dare to say the approach is optimal however...

Guy Gervais     2014-08-20 19:51:18
User avatar

Wow. That's a lot of Java

Rodion (admin)     2014-08-20 19:59:38
User avatar

Yes, until Java 8 it lacked such sweet functional abilities similar to ones demonstrated by your solutions (BTW thanks for uploading C# version!) Therefore all these loops for processing collections and collections of collections look so nasty and archaic...

Guy Gervais     2014-08-20 20:46:03
User avatar

Yes, functional additions to OO/procedural languages are very cool. Although I couldn't manage to get the middle part of my algo "LINQified". I know there's a way to do it, but I'm not yet proficient enough in functional programming.

The C# version is basically a line-by-line translation of the VB code. It's a bit less verbose (yay!) but is case-sensitive and requires all those "...();" everywhere (boo!).

Moriarty     2014-08-21 07:57:35
User avatar

woot! :) :P

Will post more questions. :)

Moff     2014-08-21 12:05:47
User avatar

My solution updated.

Guy Gervais     2014-08-21 16:43:37
User avatar

@MoffSerge:

The recursive calc_chains is very nice; but I don't understand what you're doing in get_chains with the prefixes and the tails...?

Moff     2014-08-22 06:25:35
User avatar

but I don't understand what you're doing in get_chains with the prefixes and the tails...?

If I use the full recursive calculation of chains list the solution took 6.5 sec.

It is obvious that the tails of all long chains consists of digits (1, 3, 7, 9). I calc short (9-length) chains and tails from "1379"-primes. After combination of them the solution took 1.2 sec.

During this combination appears 370 unnecessary chains (out of uniqueness), but it has not affect to solution.

Guy Gervais     2014-08-22 11:05:07
User avatar

Ah, yes. It is obvious now that you point it out to me. :)

Very smart solution.

Quandray     2014-12-24 13:22:23
User avatar

The example has a hash of 34475206 with a chain of length 49 with 4 leading zeroes
0000233331793979193911399793199139313339119333773.

For that hash, there is a chain of length 48, as in the example, but with only 3 leading zeroes.

Please login and solve 5 problems to be able to post at forum