Prime Chains
Back to Problem Solutions forum
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. :)
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.
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...
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...
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!).
@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...?
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.
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.