Rotating Integers

While working on the Project Euler problem, Circular Primes, I needed to write a function which would rotate the digits of an integer. An example would be where we start with \(197\) and rotate by a digit to yield \(971\), followed by \(719\).

I thought about the problem and my first instinct was to decompose the integer into a vector of integer digits, e.g. [1, 9, 7], and then subsequently manipulate the list, popping off the first element and re-attaching it to the back. However, this seemed to be computationally expensive because either I would be dynamically reallocating memory \(n\) times for an integer of length \(n\) or for a vector of the same length I would need to shift the position of each element \(n\) times with \(n\) assignments for each rotation.

Another approach would be to do this computationally in a much more efficient manner. I would still be executing a large number of operations, but all of those operations are fairly cheap in Julia.

Since I want to pre-allocate an array to store all of the rotations, I need to know the number of digits in the number. I used a snippet of code from my post on Counting Digits to handle determining the length of an integer.

function countdigits(x::Integer)
    digit_len = 1
    k = 10
    while x % k != x
        digit_len += 1
        k *= 10
    end
    digit_len
end

The algorithm I constructed works as follows. I have a function, rotate, of arity \(1\) which accepts a single integer, \(n\).

We use the countdigits function to determine the length, \(l\), of the integer and assign that to a variable, since we'll need to re-use this value several times.

We pre-allocate an array, \(R\), of length \(l\) and assign \(n\) to the first index of \(R\).

Next, we will iterate over the range where \(1 \leq k \leq l-1\). For each iteration, we make two computations to determine \(p_1\) and \(p_2\) where,

\[p_1 = \Big\lfloor \frac{R_k}{10^{l-1}} \Big\rfloor \text{ and }\,, \] \[R_{k} \equiv p_2 \pmod{10^{l-1}}\,.\]

Once we have determined the \(p_i\) values, we set the \(k+1\) index of \(R\) by,

\[ R_{k+1} = p_1 + p_2 \cdot 10\,. \]

Finally, \(R\) is returned. The Julia implementation of this algorithm is provided below.

function rotate(n::Integer)
    len = countdigits(n)
    rots = zeros(Int, len)
    rots[1] = n

    for k in 1:len-1
        (p1, p2) = (fld(rots[k], 10^(len-1)), 
                    mod(rots[k], 10^(len-1)))
        rots[k+1] = p1 + p2 * 10
    end

    return rots
end

One point of note that if \(n\) has any \(0\) digits, then it will impact the overall symmetry of the rotated sequence since when any number is preceeded with \(0\), the \(0\) is generally ignored.

@testset "rotate" begin
    @test rotate(12) == [12, 21]
    @test rotate(123) == [123,231,312]
    @test rotate(1234) == [1234, 2341, 3412, 4123]
    @test rotate(120804) == [120804, 208041, 80412, 
                             804120, 41208, 412080]
end

>  Test Summary: | Pass  Total
>  rotate        |    4      4

Later on I found there is actually a Julia function which handles the behavior of circular rotation of elements of a vector, circshift, which accepts a vector and a shift amount. Left and right shifts can be done by passing in positive or negative integers for the shift amount.