algorithm - 3n+1 Optimization Idea for Larger Integers -

i got book "programming challenges" skiena , revilla , surprised when saw solution 3n+1 problem, brute forced. it's algorithm generates list of numbers, dividing 2 if , multiplying 3 , adding 1 if odd. occurs until n=1 reached, base case. trick find maximum length of list between integers , j in problem ranges between 1 , 1,000,000 both variables. wondering how more efficient (if so) program dynamic programming. basically, program 1 pass on first number, i, find total length, , check each individual number within array , store associated lengths within hashmap or other dictionary data type.

for example: let's = 22 , j = 23

for 22:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

this means in dictionary, structure store (22,16) , (11,15) , (34,14) , on... until (1,1)

now 23:

23 70 35 106 53 160 80 40 ...

since 40 hit, , in dictionary program length of 23 80, 7, , add length stored 40 9 resulting in total list length of 16. , of course program store lengths of 23, 70 , 35 etc... such if numbers bigger should compute faster.

so opinions of approaching such question in manner?

i tried both approaches , submitted them uvaoj, brute force solution got runtime ~0.3s , dp solution ~0.0s. gets pretty slow when range gets long (like on 1e7 elements).

i used array (memo) able memorize first 5 million (size) values:

int cyclelength(long long n) {     if(n < 1) //overflow         return 0;     if (n == 1)         return 1;      if (n < size && memo[n] != 0)         return memo[n];      int res = 1 + cyclelength(n % 2 == 0 ? n / 2 : 3 * n + 1);      if (n < size)         memo[n] = res;      return res; }