In the Inaugural Sydney Competitive Programming meetup Project Euler #35 was the theoretical problem presented at the meetup. Interestingly, most people went for this problem instead of the practical or data problems that were prepared.

I had coded up a solution in Julia to Project Euler #35, and it was the fastest solution there. Although I had used the excellent Primes.jl library in the solution whereas the other participants had chosen to write their own prime related functions. Another interesting thing I just found out is that the Primes.jl library is written purely in Julia.

Problem statement

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?

Other Julia Solutions

Out of curiosity, I had a quick search of the other Julia solutions, and I found these two 1 and 2. I also found this 3: two-liner solution, but I couldn't find where the author defined the function crop. However, it's an elegant solution too.

I realised that my solution is slightly different to the above so I've decided to post it here.

Solution Discussion

I think the most interesting part of the problem is how to generate the circular numbers. The most common way that people have described is to treat the number as a string and take off the last letter and append it to the front. However, string manipulations are generally computationally intensive than operating on numbers. So I think a better way to generate the number in the next cycle is to use divrem to break the number into non-last digit vs. last digit, e.g.

n = 101
next_cycle(n) = sum(divrem(n, 10) .* (1, 10^(ndigits(n)-1))) # 110

My Solution

I had used Julia's amazing broadcasting syntax in my solution and I got the following code which wasn't exactly the same as the one I had coded in the meetup but was inpisred by [3].

using Primes
p = primes(Int64(1e6))
circularn(n,d) = [sum(divrem(n,10^i).*(1,10^(d-i))) for i = 1:d-1]
sum(all_circular_are_primes.(p))

Sydney-sider and interested in Competitive programming and/or Julia?

Why not check out the Sydney Julia meetup and the Sydney competitive programming meetup.