Day 64: Day 2⁶

What I'm doing today

Solving - Being out of the office for so long, I'm afraid my skills are going to start to atrophy. I've been helping colleagues with their online programming and data science classes, but I haven't done any hands-on coding in two months. At times like this I turn to Project Euler, a website that "exists to encourage, challenge, and develop the skills and enjoyment of anyone with an interest in the fascinating world of mathematics." Project Euler contains hundreds of recreational math problems that require some programming skill in order to solve. The twist is that the website challenges participants to device elegant solutions that obtain solutions efficiently and quickly. In other words, many of the problems can be done using brute force on a beefy computer in hours or days of compute time. However, solvers are encouraged to strive for solutions that can execute on an average computer in under one minute. Here is the problem I worked on:

Problem 70: Totient Permutation - Euler's Totient function is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6. Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180. Find the value of n, 1 < n < 10000000, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

For the sake of anyone who wants to come by the solution to this problem honestly, I will withhold the answer and the details here. First off, I normally do these problems using Ruby or Perl, because I have built a number of libraries full of utilities for solving these problems. But I've been living in Python land so much lately, that I decided to use Python for this problem. I'm not going to lie, I messed this up the first time around. My first approach would have worked, but the 50-ish lines of code would have produced the solution in several hours of run time. Unacceptable. When you examine some of the properties of the Totient function and what conditions are ideal for minimizing the ratio of n/φ(n), the correct approach eventually becomes clear. My solution ended up being around 20 lines of code and produced a solution in just under one second. There are better solutions out there, but, being as rusty as I am right now, I'm pretty happy with it.