# 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.