This problem is a hard version of "Problem 42673. Longest Collatz Sequence", because of time limits. https://ww2.mathworks.cn/matlabcentral/cody/problems/42673-longest-collatz-sequence
The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even) n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, no more than N, produces the longest chain, and how long? Don't cheat!
It's not possible to forbid cheat totally, because Cody can not hide test cases. It's all about Self-discipline.
li haitao: all answers are currently scored as wrong. On the problem edit/update page, please put your own function in the Reference Solution field and test it to ensure that the problem is solvable before updating or making changes to the test suite.
There appears to be something wrong with the test suite--solutions fail the "digit test" even though they do not include 5, 6, 7, 8, or 9.
Hi li haitao,
when I run my solution. It throws the following error in the server.
"While evaluating the solution, the server encountered an error caused by long running MATLAB code. Edit the code if needed and then submit."
When I tested my solution in my pc, it takes two times the execution time mentioned in the test cases.
How to get rid of this server error. Please help.
regards,
Athi.
Hi li haitao,
For my solution, the execution times for test case 9 is 2.0526 and for test case 10 is 22.1447.
@Tim.
Now I delete "digit test", please submit your codes again, please.
Hi Athi , to get rid of this server error, please speed up your codes.
Hi goc3, now I delete the "digit test", and submit a correct solution.
Hi li haitao,
I like this problem very much. I was trying to solve it for 3 three days.
The best running time reached by my solution 1643182 is,
Test Case #9 : 1.7022 sec
Test Case #10: 17.8276 sec
Test Case #11: 15.0268 sec (Random)
Thanks for such a wonderful problem and test case.
Good problem. However, you might want to try some values in between the powers of 10 (like N=50000, for example) so a cheat like this doesn't work.
"cheat" can not be forbided, unless Cody can hide the test cases.
I was going to suggest a minimum time for your toc to help prevent look-up tables, but you already implemented it. Nice job!
I added digit test to prevent "look-up tables", although it can not forbid cheat totally.
13756 Solvers
506 Solvers
Increment a number, given its digits
497 Solvers
Reverse the Words (not letters) of a String
238 Solvers
Sum all integers from 1 to 2^n
6115 Solvers