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, under N, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above N.
See my problem 42673: Longest Collatz Sequence
Brilliant. Power in simplicity. An order of magnitude faster than my attempt.
Thanks. Don't know why mod(a,m) is slower than a-floor(a/m)*m.
Probably internal input/output argument checks. Multiply it via millions of iterations and you get significant difference. Your algorithm saves tons of time (in comparison) because you didn't bother to store all the steps, therefore you didn't fell into "dynamic indexing" trap which saves some steps, but drastically slows down the process during saving values to the main array.
I guess this is one of those times where saving the intermediate steps doesn't help your computation time. Nicely done. As a comparison, using mod(b,2) takes about two-thirds longer than 2*floor(b/2) on my machine; 18.8 sec vs 11.3 sec for n=1e8, and 38 sec vs 23 sec for 2e8. That's good to know for speeding things up in other codes I need to run millions of times!
mod(b,k) takes about 10x longer than b-k*floor(b/k) on my machine (2016b win64):
a = randi(1e7,1e8,1); m = 37;
tic, b = mod(a,m); toc;
tic, c = a - floor(a/m)*m; toc;
norm(b - c)
Elapsed time is 3.131306 seconds.
Elapsed time is 0.253768 seconds.
ans =
0
I did the same thing, minus the uint64. My Project Euler code timed out on the 1e7 and 1e8 test cases.
That's right. My code would pass the test suite if last test were changed from 1e8 to 2e7, but that's all. 1e8 would take approx 110 seconds on Cody servers.
766 Solvers
2151 Solvers
462 Solvers
Square Digits Number Chain Terminal Value (Inspired by Project Euler Problem 92)
149 Solvers
139 Solvers