Collatz Conjecture
Ok so here's what I've been tasked with......
"Possibly the most notorious algorithm termination puzzle of all time - among mathematicians anyways - is the Collatz Conjecture, sometimes called the 3x+1 problem. Start with any positive integer and repeat: If it is even, divide by two; if it is odd, multiply by 3 and add 1. For example if you start with 22, you get 11, 34, 17, 52, 26, 13, 40, 20, 10, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, ...
The conjecture no matter what number you start with you will eventually get down to the same cycle 4, 2, 1 repeating over and over.
1. Write a C++ program to verify the Collatz Conjecture for the numbers 1 to 10. Your program should consist of a for loop which runs from 1 to 10 which in turn contains a while loop that prints the numbers generated by the Collatz algorithm. How will you know when to terminate the while loop? Hint: if you generate the number 1, by definition you have entered in the infinitely repeating sequence 4, 2, 1 .... Note this program contains no input.
2. Using the program you have developed in Step 2, see how long it might take to verify the Collatz Conjecture for the numbers 1 to 10000. Warning: Be prepared to wait a long time. Do NOT produce a hard copy for this experiment. Investigate the use of the time function in the C++ ctime library^2.
3. Plot the execution time of your program for limiting values of 10, 50, 100, 500, 1000, 5000, 10,000, 20,000. What kind of curve is produced? (Use excel)
4. Place a counter inside the inner loop to determine how many distinct values are produced before the loop terminates. Is there any relationship between the initial value and the number of values in the series.
Questions:
1. Why do you suppose it takes so long?
2. Can a computer be used to verify whether this algorithm terminates? Can a computer be used to determine whether any algorithm terminates? Investigate the "Halting Problem."
....and that's it. I'll be posting whatever code I come up with and would appreciate any advice. In the meantime feel free to comment or give ideas for a flow chart.
"Possibly the most notorious algorithm termination puzzle of all time - among mathematicians anyways - is the Collatz Conjecture, sometimes called the 3x+1 problem. Start with any positive integer and repeat: If it is even, divide by two; if it is odd, multiply by 3 and add 1. For example if you start with 22, you get 11, 34, 17, 52, 26, 13, 40, 20, 10, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, ...
The conjecture no matter what number you start with you will eventually get down to the same cycle 4, 2, 1 repeating over and over.
1. Write a C++ program to verify the Collatz Conjecture for the numbers 1 to 10. Your program should consist of a for loop which runs from 1 to 10 which in turn contains a while loop that prints the numbers generated by the Collatz algorithm. How will you know when to terminate the while loop? Hint: if you generate the number 1, by definition you have entered in the infinitely repeating sequence 4, 2, 1 .... Note this program contains no input.
2. Using the program you have developed in Step 2, see how long it might take to verify the Collatz Conjecture for the numbers 1 to 10000. Warning: Be prepared to wait a long time. Do NOT produce a hard copy for this experiment. Investigate the use of the time function in the C++ ctime library^2.
3. Plot the execution time of your program for limiting values of 10, 50, 100, 500, 1000, 5000, 10,000, 20,000. What kind of curve is produced? (Use excel)
4. Place a counter inside the inner loop to determine how many distinct values are produced before the loop terminates. Is there any relationship between the initial value and the number of values in the series.
Questions:
1. Why do you suppose it takes so long?
2. Can a computer be used to verify whether this algorithm terminates? Can a computer be used to determine whether any algorithm terminates? Investigate the "Halting Problem."
....and that's it. I'll be posting whatever code I come up with and would appreciate any advice. In the meantime feel free to comment or give ideas for a flow chart.
lmao so ur trying to do this stupid assignment for langsam by tomorrow too!
lmao good luck
lmao good luck
this is what i got, i need help in getting the time, but more importantly, i need help getting it to go from 1 to 10, i did it with a user input integer, but thats not what the assignment asks for. but here it is
Last edited on
closed account (48T7M4Gy)
I'll have a look. In the meantime please put code tags at the top and bottom of your code block. :)
Last edited on
closed account (48T7M4Gy)
| i need help in getting the time |
http://www.cplusplus.com/reference/ctime/difftime/
Get the time at the start and end using time(@now) and use difftime( ... ) to calculate time taken.
| i need help getting it to go from 1 to 10 |
You wrote the above code and don't understand a for loop?
Maybe it just slipped your memory, so here's a refresher:
http://www.cplusplus.com/doc/tutorial/control/
This one might be helpful too:
https://answers.yahoo.com/question/index?qid=20111201123906AAqYo6H
Last edited on
lol, thank you, but the only problem is that when i pair the "if..else" with the for loop, it gets weird. here's what i have:
Last edited on
closed account (48T7M4Gy)
All you have to do now is see how your last piece of genius programming cut and paste is relevenat to the OP. But you'll get there!
Topic archived. No new replies allowed.