2
$\begingroup$

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:

  1. 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?
  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$?
$\endgroup$
5
  • $\begingroup$ Sorry. I've been posting and deleting comments as I've gotten myself confused. (I have trouble distinguishing right and left.) My earlier comment was correct. Suppose we have a $(d+1)$-digit example in base $n$: $m=xn^d+y$ where $0\leq x<n$ and $0<y<n^d$. Rotating $m$ left gives $ny+x$, so the condition is $$(2n^d-1)x=(n-2)y$$ When $n=3$ this gives $(2\cdot3^d-1)x=y<3^d$ which is impossible unless $x=y=0$ which is excluded. How can there be an example with $n=3$? Where is my error? $\endgroup$
    – saulspatz
    Apr 1, 2020 at 16:25
  • $\begingroup$ @saulspatz I think you've flipped truthy/falsey. The sequence I posted applies to the falsey test cases, so the bases for which there there aren't any 'Rotate-Left-Double numbers' available. For all other bases (thus [5,7,8,9,11,12,13,14,15,16,17,19,20,...]) there are. So if you've found prove that for \$n=3\$ there aren't any possible solutions, this is correct. $\endgroup$ Apr 1, 2020 at 16:43
  • $\begingroup$ Off-topic, but regarding having trouble distinguishing right/left: the same user actually has a different challenge regarding 'Rotate-Right-Double numbers'. Unlike the 'Rotate-Left-Double numbers', these apparently always have a solution, for which the smallest number for each base \$n\$ can be found in the OEIS sequence A087502. Not really useful for my question, but figured I'd mention it anyway for those interested. $\endgroup$ Apr 1, 2020 at 16:45
  • 2
    $\begingroup$ Ah, I didn't read the question carefully, thanks. But now I have another question. If $01_2$ is rotated left, we get $10_2$ so $n=2$ isn't a falsey case, though it's listed in your sequence. Do you to mean to exclude that when you say it's a power of $2$ after decreasing by $2$? This doesn't seem very clear. $\endgroup$
    – saulspatz
    Apr 1, 2020 at 16:52
  • $\begingroup$ @saulspatz Hmm, good point. I will ask that challenge giver why $n=2$ is falsey. Although I assume it's because of that leading 0. $\endgroup$ Apr 1, 2020 at 17:55

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Thanks for the answer. My math skills are pretty bad, so I have two small questions: 1. what does the $|$ signify in $(n-2)|x$ and $j|2n^d-1$? 2. I'm a bit confused about the "If $n=2^k+2$ then $(2)$ gives $(n−2)|x$ since $2n^s−1$ is odd." I get the second part about it being odd, but I'm not sure how it went from $n=2^k+2$ in $(2)$ to $(n−2)|x$. It's probably obvious when I see some sub-steps, but feel free to do it here in the comments to not clutter the answer if you want. These two questions of mine are mostly clarifications for me personally. The proof as an entirety is clear, thanks! $\endgroup$ Apr 1, 2020 at 21:20
  • 1
    $\begingroup$ @Kevin Sure. $|$ means "divides" or "is a divisor of". If $n=2^k+2$ then $n-2=2^k$. Now $2^k$ divides the left-hand side of $(2)$, so it must divide the right-hand side. $2^k$ has no factors in common with an odd number, so it must divide $x$. $\endgroup$
    – saulspatz
    Apr 1, 2020 at 21:25
  • $\begingroup$ @KevinCruijssen I'm glad you asked the question. It made me look at the proof again, and I found a hole! $\endgroup$
    – saulspatz
    Apr 1, 2020 at 21:31
  • $\begingroup$ @KevinCruijssen I fixed it. It's simpler as well as being correct (I trust.) $\endgroup$
    – saulspatz
    Apr 1, 2020 at 22:19
  • 1
    $\begingroup$ If we set $d=p-2$ then $2^{d+1}=2^{p-2+1}=2^{p-1}\equiv1\pmod{p}$ by little Fermat. $\endgroup$
    – saulspatz
    Apr 2, 2020 at 14:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .