Programming Limitations and Project Euler (1 Viewer)

[SpiralFlex]

Hello all,

Also, is there perhaps a way to make my program more efficient? Technical or Mathematical?

With Sy's solution you're essentially searching the array twice one for value/index value. Since the array is pretty large this is undesirable.

Also iterate two if statements aren't necessary, either n is even or odd so check one you can check one only.

public int iterate(int n){

   if (n%2 == 0){
      return n/2;
   } 

   return 3*n+1;

}

 

[Squar3root]

Which part/code do you not understand?

I'm not sure. I think i understand the problem as in choose a number and then see how long the string is and the code is sort of alien to me. It has a similar structure to C (for loop and all) but the other stuff confused me

 

[Squar3root]

With Sy's solution you're essentially searching the array twice. Since the array is pretty large this is undesirable.

Also iterate two if statements aren't necessary, if one is even other is odd.

if (n%2 == 0){

   return n/2;

} 

return 3*n+1;

I did something like that. I am going places

 

[SpiralFlex]

I'm not sure. I think i understand the problem as in choose a number and then see how long the string is and the code is sort of alien to me. It has a similar structure to C (for loop and all) but the other stuff confused me

For the most part, while/for work similarly.

 

[SpiralFlex]

btw I like your use of sublime text squarer00t so pretty

 

[Squar3root]

btw I like your use of sublime text squarer00t so pretty

I like all the pretty colours.

are you a compSci major as well?

 

[SpiralFlex]

I like all the pretty colours.

are you a compSci major as well?

majoring in tf2/counterstrike

 

[Squar3root]

majoring in tf2/counterstrike

noce

 

[RealiseNothing]

Could you do it working backwards. So run a program that starts at 1, and reverses the process. So it simultaneously doubles (reverse of half) or subtracts 1 and divides by 3 (reverse of multiplying by 3 and adding 1).

Then all possible sequences will be produced. So after every step you double the amount of sequences you have since there are two possibilities.

All you would have to do is somehow terminate a sequence if the reverse step is not possible. i.e. if you start at 1 you obviously must double, since which isn't possible given our set of initial conditions.

Then to find the answer, tell the program to stop once all numbers have been found somewhere in the sequences. Then check for the longest sequence. Also some how tell the program to terminate a sequence once a number is repeated as this will just lead to an infinite loop.

 

[SpiralFlex]

Could you do it working backwards. So run a program that starts at 1, and reverses the process. So it simultaneously doubles (reverse of half) or subtracts 1 and divides by 3 (reverse of multiplying by 3 and adding 1).

Then all possible sequences will be produced. So after every step you double the amount of sequences you have since there are two possibilities.

All you would have to do is somehow terminate a sequence if the reverse step is not possible. i.e. if you start at 1 you obviously must double, since which isn't possible given our set of initial conditions.

Then to find the answer, tell the program to stop once all numbers have been found somewhere in the sequences. Then check for the longest sequence. Also some how tell the program to terminate a sequence once a number is repeated as this will just lead to an infinite loop.

So basically you will have a tree at each number have two choices.

 

[Squar3root]

I wrote a program that tells you if it a leap year or not:

 

[RealiseNothing]

So basically you will have a tree at each number have two choices.

Yep but some branches will not be possible and so to reduce the size you can set some rule that tells the program to terminate a sequence once it reaches a dead end.

 

[SpiralFlex]

I wrote a program that tells you if it a leap year or not:

nicenice 1st assignment of COMP1917

 

[Squar3root]

nicenice 1st assignment of COMP1917

4th lab task of COMP1911.

Do you know Jocelyn?

 

[SpiralFlex]

4th lab task of COMP1911.

Do you know Jocelyn?

nup.

 

[GoldyOrNugget]

Words cannot contain my excitement at seeing a PROJECT EULER PROBLEM ON BOREDOFSTUDIES I'M SO HAPPY

 

[GoldyOrNugget]

Use 64bit JVM?

Still doesnt explain why it works when its changed to double.

doubles are 64 bit data types, so it does explain it...

As someone else pointed out, the maximum value attained during iteration is above 2^31. It's 28495741760. Your integers were overflowing and then weird stuff happened. doubles don't overflow like this. In future, use java.math.BigInteger if you need arbitrarily large integers.

And yes, there is a sweet optimisation you can make. Say you check the sequence length for n=3, so you do 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1. And then you check the sequence length for n=4 -- but wait, we already know that the length for n=4 will be 3, because we found that when we considered n=3.

And later, when we check say n=10, we do 10 -> 5, but then we recall that 5 has a sequence length of 6 based on our earlier calculations, so 10 must have a sequence length of 1+6=7.

This method is cool because it leads us to an upper bound on the number of times we process a number. Each number is processed exactly once, so we process at most 28495741760 numbers (in practice it's a lot less than that because some numbers never turn up).

Implementation left as exercise for the reader.

 

[GoldyOrNugget]

Could you do it working backwards. So run a program that starts at 1, and reverses the process. So it simultaneously doubles (reverse of half) or subtracts 1 and divides by 3 (reverse of multiplying by 3 and adding 1).

Then all possible sequences will be produced. So after every step you double the amount of sequences you have since there are two possibilities.

All you would have to do is somehow terminate a sequence if the reverse step is not possible. i.e. if you start at 1 you obviously must double, since which isn't possible given our set of initial conditions.

Then to find the answer, tell the program to stop once all numbers have been found somewhere in the sequences. Then check for the longest sequence. Also some how tell the program to terminate a sequence once a number is repeated as this will just lead to an infinite loop.

There are a number of problems with this approach!! (I'm still very excited)

Problem 1 is that one of the branches of the tree will go 1 -> 2 -> 4 -> 8 -> 16 -> ... which is valid, but your program could easily keep exploring down this branch forever.

"But can't you just tell it to stop at 1 million?", you ask naively. No! You can't tell it to stop at the highest power of 2 less than 1 million, because there are many integers in [1, 1m] whose maximum hailstone sequence element exceeds 1m. In fact, I don't believe that you can tell it to stop at any specific integer. For instance, say you were looking for the longest sequence starting with n in [1, 9]. 5 is a valid n, and yet you can't reach 5 by doing the reverse process from 1 unless your sequence contains an integer exceeding 9.

There is a solution to this infinite search problem, and it's the same one that's used for AIs that perform game tree searches. Rather than doing a depth-first search that exhausts each branch at a time, we can proceed in a breadth first manner. For instance we do 1 -> 2 -> 4 -> 8 -> 16 -> 32, but the next thing we process is not 64, but 5, because it's also true that 16 -> 5. We can keep a list of all the possible "expansions" of terms that we have yet to process and we process them in the order they enter the queue. This is known as a breadth-first search and solves the problem above.

Unfortunately, this is theoretically at most as fast as Sy's original method, and practically much slower due to manipulating all the stack frames (recursive method) or overhead of the queue (iterative method). So Sy's method with my caching approach is the best.

 

[GoldyOrNugget]

For another problem about integer chains that deals with exactly the same concepts at a much much higher level, see Euler 425.

 

[brent012]

doubles are 64 bit data types, so it does explain it...

Yeah, hence why I suggested it...

Sy suggested it might be hanging somewhere and that the number wasn't going over integer.max_value which is why I said that it must be since it works with double.