Prime Chains (Task 149)
Back to General discussions forum
Hello there ! Sorry for my poor english. I find this web site great and a bit too addictive.
Well, I need an explication on the task 149:
I found that the number :
343133317939791939113931333113997931991393133391
was correct for the 3 constraint :
- is a chain number (for 5-digits primes numbers)
- its hash is equal to 93993876
- has 48 digits or more
but it was answered to me that it was wrong and that the expected number is :
84809173331793979193911399793199139313339119333773
it certainly does fit also to the constraints, but I don't undertstand why there should be only one number expected since the hash function is not injective ? What did I miss ?
I got a similar problem with numbers that begin with zeroes. My proposition begun with less zeroes than the expected number. One more submission and the task was done.
Hello!
Thank you for your kind words and for your message:
> it certainly does fit also to the constraints, but I don't understand why there should be only one number
Well, I'm afraid that probably you have find a flaw in the statement / checker for this problem: it may happen that I used too weak "hash-function" and still hoped that there would be no collisions. And it seems I was wrong :(
I'll investigate this further, but meanwhile you really can try the advice of Nicolas - retrying the submit with another input data. If your solution is correct (and I suspect it is so) then it should work after another few attempts :)
I'm quite sorry for this inconvenience! I'll try to see and fix it soon...
OK, thanks for the hints. Note that at my first attempt there were 5 collisions : I found 2 solutions for the 1st hasch and 1 for the 2de that were different from the "expected" ones, only the third did match.
Wow, it is quite suspicious! I'll have a look at your code - probably it has some unique feature which leads to that many collisions... Probably then I'll be able to tune up checker somehow :)
Thanks a lot for pointing this interesting issue!
The code I posted will not work because it's a concatenation of the two scripts I used : I'm afraid some lines are missing. I hope it will be readable enough !
I have just completely rewritten the checking code for this task, so it should work for any values satisfying the three conditions, as you expect. (I've tested it with values you kindly posted and it returned 'ok')
I would be quite thankful if you or Nicolas will give a try to this task again to see whether new checker is better!
I know it sounds stupid, but the first version of the checker simply contained precalculated pairs of "chains" and hashes and chose randomly few of them to generate test data. I could not imagine there is a big chance for collisions, but I was wrong - mainly because chains have very unequal distribution of digits in them...
Here I go ! But my script do not exceed 48 digits for the moment, so I don't know if I'll be successfull this time.
Values of exactly 48 digits should be OK, I think! I've tried new checker with the first of your values (which had exactly 48).
At last, it works ! A previous attemp failed because there was only two 48-digits which match to the 4 hasch requested.
I'm glad you've done it! Congratulations! :)
Thanks a lot once more for figuring out the trouble with this task!
Thanks a lot Nicolas! I hope that evidence of three people (including me) is enough for me to think that new checker is ok :)
Hi, laurentypetit. in task says - prime substrings should be unique!
in you answer
343133317939791939113931333113997931991393133391
i see repeats
--31333---------------31333--------------31333--
Maybe more, did not look.
For hash 93993876 I got one result - 84809173331793979193911399793199139313339119333773
But for a test hash - 34475206 I got two results - 0000233331793979193911399793199139313339119333773 and 000233331793979193911399793199139313339119333773
Hi !
3 years later, I do not remember very well the problem, thanks for the enlightenment which is usefull anyway !