Homework 1

Due Date: Friday, February 5

Instructions: Feel free to work together with other students in the class, though you must turn in your own copy of the solutions, and you must acknowledge anyone that you worked with. You can turn in your homework assignment by e-mailing me all of your associated files.

1. Define a sequence \(a_1,a_2,a_3,\ldots\) recursively by \(a_1 = 2\) and \(a_{n+1} = a_n(a_n+1)\) for \(n\geq 1\). Prove that each \(a_n\) is divisible by at least \(n\) different primes. (This gives another proof that there are infinitely many primes.)
2. Let \(P_{3,4} = \{p\in\mathbb{N} \mid p\text{ is prime and }p \equiv 3\text{ (mod }4\text{)}\}\). Prove that \(P_{3,4}\) is infinite.
3. Given a positive integer \(a_1\), the corresponding Collatz sequence \(a_1,\ldots,a_n\) is defined recursively by the formula \[ a_{k+1} \,=\, \begin{cases}a_k/2 & \text{if }a_k\text{ is even}, \\[3pt] 3a_k+1 & \text{if }a_k\text{ is odd and }a_k\ne 1.\end{cases} \] The sequence terminates when it reaches 1. For example, the Collatz sequence for 17 is \[ 17,\;\;52,\;\;26,\;\;13,\;\;40,\;\;20,\;\;10,\;\;5,\;\;16,\;\;8,\;\;4,\;\;2,\;\;1. \] The Collatz conjecture states that the Collatz sequence starting at any positive integer reaches 1 after finitely many steps.
   1. Write a computer program that computes the length of the Collatz sequence for a given positive integer.
   2. Use your program to determine which number between 1 and 10,000 has the longest Collatz sequence.
   3. Make a scatter plot showing the numbers 1 through 10,000 on the horizontal axis and the length of the corresponding Collatz sequence on the vertical axis.