Problem 44448. Project Euler: Problem 14 Longest Collatz sequence

Created by li haitao

Solve Later

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!

Solve

Solution Stats

248 Solutions
8 Solvers

Last Solution submitted on Mar 14, 2020

Last 200 Solutions

Problem Comments

9 Comments

9 Comments

Show 6 older comments

li haitao on 14 Dec 2017

It's not possible to forbid cheat totally, because Cody can not hide test cases. It's all about Self-discipline.

goc3 on 4 Jan 2018

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.

Tim on 16 Jan 2018

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.

Athi on 24 Sep 2018

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.

Athi on 24 Sep 2018

Hi li haitao,
For my solution, the execution times for test case 9 is 2.0526 and for test case 10 is 22.1447.

li haitao on 10 Oct 2018

@Tim.
Now I delete "digit test", please submit your codes again, please.

li haitao on 10 Oct 2018

Hi Athi , to get rid of this server error, please speed up your codes.

li haitao on 10 Oct 2018

Hi goc3, now I delete the "digit test", and submit a correct solution.

Athi on 12 Oct 2018

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.

Solution Comments

Solution 1670190

2 Comments

2 Comments

li haitao on 11 Nov 2018

Srrickly speaking, it is a cheat solution,because It does not measure the running time of big data.

Binbin Qi on 11 Nov 2018

@li haitao, you are right.

Solution 1377971

4 Comments

4 Comments

Show 1 older comment

James on 12 Dec 2017

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.

li haitao on 13 Dec 2017

"cheat" can not be forbided, unless Cody can hide the test cases.

James on 13 Dec 2017

I was going to suggest a minimum time for your toc to help prevent look-up tables, but you already implemented it. Nice job!

li haitao on 14 Dec 2017

I added digit test to prevent "look-up tables", although it can not forbid cheat totally.

Problem Recent Solvers8

Problem Tags

projecteuler speed optimization