More iteration for fun!
Last time we talked about using iteration to compute Fibonacci numbers. In this week's lab, we'll explore iteration for iteration's sake, again motivated by Project Euler. Here's the $197^{\text{th}}$ problem:
Project Euler question 197
Given the function $$ f(x) = \left\lfloor 2^{30.403243784-x^2}\right\rfloor \times 10^{-9}, $$ the sequence $u_n$ is defined by $u_0=-1$ and $u_{n+1}=f(u_n)$.
Find $u_n+u_{n+1}$ for $n=10^{12}$ to an accuracy of $9$ digits past the decimal point.
Experimentation
First off, that $10^{12}$ looks a little intimidating. Iterating a million times might be a bit intimidating; this is a milion millions! Let's experiment a bit to get a clue as to how long this might take, Here's 10000 iterates:
Hmm... only around 2 one hundredths of a second. Not bad, but $10^{12}$ iterates will about take $10^9$, or a billion, times as long. That's not quite a year but it's getting close.
Check this out, though:
Can you see how to do the problem, now?
Problem 1
Let and let . Find the Googolth iterate of $f$ starting from $x_0$ to an accuracy of $10$ digits past the decimal point.
To submit your solution, you should respond to my email with subject line "Problems Lab 4 #1". Be sure to include the Sage Cell Server's Short link to the code that you wrote to generate your solution.
Collatz orbits
The famous Collatz conjecture deals with the itertion of the function $f:\mathbb N \to \mathbb N$ defined by $$ f(n) = \left\{ \begin{array}{cl} 3n+1 & \text{ if } n \text{ is odd} \\ n/2 & \text{ if } n \text{ is even}. \end{array}\right. $$ Note that, under iteration of $f$, we have $1\to4\to2\to1$; thus, we have an orbit of period 3. The Collatz conjecture states that every positive integer eventually lands on this orbit. Stated in 1937, the conjecture remains unresolved and, while it has supposedly been verified expermentally for all starting values up to $2^{60}\times87$, no essential progress has been made on a proof. As such, it's a very popular topic among computational hobbyists so it's not surprising to find a related Project Euler problem:
Project Euler question 14
Which starting number, under one million, produces the longest sequence under iteration of the Collatz function before reaching 1?
Problem 2
Try to solve Project Euler #14. Here are some functions that might help.
To submit your solution, you should respond to my email with subject line "Problems Lab 4 #2". Be sure to include the Sage Cell Server's Short link to the Python code that you wrote to generate your solution.