IF YOU ARE IN 4440: Think about forming a group of 2-3 people for a poster. Read the poster info in the “Posters” tab above. Reach out on discord, in person, etc., if you like to find a group that way. Then fill in this form with your poster group situation so I can find out who is working with who or who needs helping finding a team.
IF YOU ARE IN 5440: You do an individual project *instead of a poster*. Send me an email with your thoughts on topic and your background and we can brainstorm.
Think about your topic.
Use the birthday paradox approximation formula (with the natural log e in it) to determine the minimal number of people who need to be in the classroom to have at least a 50% chance of a shared Ceres birthday. (You’ll need to look up how many earth days in a Ceres orbit.)
This problem outlines a proof that there are infinitely many primes from a CS perspective, using information theory (due to Chaitin).
Define the Komolgorov complexity $C(n)$ of an integer $n$ to be the length of the shortest computer program that will output $n$ in decimal form. (For concreteness, you can fix any programming language.) For example, the program for $2701$ might simply be ‘print(‘2701′)’. This gives a trivial upper bound on $C(n)$ of $O(\log n)$. Explain why.
For the numbers of the form $n=10^t$, prove that $C(n)$ is bounded above by $O(\log \log n)$ by giving an actual computer program.
Suppose there are only finitely many primes $p_1, \ldots, p_k$. The number $k$ is a constant. Show that for all $n$, $C(n)$ is bounded above by $O(\log \log n)$, by using unique factorization.
Prove that there must exist $n$ having $C(n) \ge \log n$, by using a counting argument.
Explain why this proves there are infinitely many primes.