I'm very active on the codegolf stackexchange, where the goal of codegolf is to complete a certain task/challenge in as few bytes as possible. Although the challenge isn't live yet, someone proposed this challenge, which I will also partially quote here:
Task
A Rotate-Left-Double number in base $n$ is a number $m$, when its base-$n$ digits are rotated left once, equals $2m$.
One example in base $7$ is the number $480=1254_7$. When rotated left once, the value becomes $2541_7=960$.
Given the base $n\geq2$, determine if there exists a Rotate-Left-Double number in base $n$.
You can use your language's convention to represent truthy/falsy, or use two distinct values for truthy and falsy respectively.
The challenge proposer also posted a reference implementation in Python.
When I was preparing a solution for when this challenge would go live, I noticed that all falsey test cases within the range $n=[2,500]$ seem to be forming the OEIS sequence A056469: number of elements in the continued fraction for $\sum_{k=0}^n (\frac{1}{2})^{2^k}$, which could be simplified to $a(n)=\left\lfloor2^{n-1}+2\right\rfloor$. Here a copy of the first 25 numbers in that sequence as reference:
2, 3, 4, 6, 10, 18, 34, 66, 130, 258, 514, 1026, 2050, 4098, 8194, 16386, 32770, 65538, 131074, 262146, 524290, 1048578, 2097154, 4194306, 8388610
So now I have two questions:
- Is my assumption correct, or is it simply a coincidence that the falsey test cases in the range $n=[2,500]$ are all powers of 2 after decreasing by 2?
- If my assumption is indeed correct, how can this be proven in relation to the 'Rotate-Left-Double numbers' for the given base $n$?
If $m$ is a $(d+1)$-digit Rotate-Left-Double number in base in base $n$ then $$m=xn^d+y\tag1$$ where $d\geq1,\ 0<x<n,\ 0\leq y<n^d.$ (I have adopted the rule that the number can't start with $0$.) Rotating $m$ gives $ny+x$ so we have $2xn^d+2y=ny+x$ or $$(n-2)y=(2n^d-1)x\tag2$$ If $n=2^k+2$ then $(2)$ gives $(n-2)|x$ since $2n^s-1$ is odd. But then $y\geq 2n^d-1$ which contradicts $y<n^d$.
To show that these are the only falsey numbers, let $p$ be an odd prime dividing $n-2$. (Such a $p$ exists because $n-2$ is not a power of $2$.) In $(2)$ we can take $x=\frac{n-2}p<n$ and we have to we have to show that there exist an exponent $d>0$ and $0\leq y<n^d$ such that $$py = 2n^d-1$$ If we can find a $d$ such that $p|(2n^d-1)$, we are done, for we can take $y = \frac{2n^d-1}p<n^d.$
By assumption, $n-2\equiv0\pmod{p}$ so $n\equiv 2\pmod p.$ Therefore, $$2n^d\equiv1\iff 2\cdot2^d\equiv1 \iff 2^{d+1}\equiv 1\pmod p,$$ and by Fermat's little theorem, we can take $d=p-2$.
This completes the proof.