9
\$\begingroup\$

Task

A Rotate-Left-Double number in base \$n\$ is a number \$m\$, when its base-\$n\$ digits are rotated left once, equals \$2m\$. The base-\$n\$ representation of \$m\$ cannot have leading zeros.

One example in base 7 is the number 480, or \$1254_7\$. When rotated left once, the value becomes \$2541_7 = 960\$.

Given the base \$n \ge 2\$, 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.

Scoring and winning criterion

Standard rules apply. Shortest code in bytes wins.

Test cases

n -> answer (example if true)
-----------------------------
2 -> false
3 -> false
4 -> false
5 -> true (13 x 2 = 31)
6 -> false
7 -> true (1254 x 2 = 2541)
8 -> true (25 x 2 = 52)
9 -> true (125 x 2 = 251)
10 -> false
11 -> true [3,7]
12 -> true [2,4,9,7]
13 -> true [1,2,4,9,5,11,10,8,3,7]
14 -> true [4,9]
15 -> true [1,2,4,9,3,6,13,12,10,5,11,8]
16 -> true [2,4,9]
17 -> true [1,2,4,9]

Reference implementation in Python.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Did you wind up figuring out if these numbers are those of the form 2^k+2 and 2? I think it's likely true. \$\endgroup\$
    – xnor
    Apr 2, 2020 at 7:19
  • 1
    \$\begingroup\$ @xnor I didn't, but Kevin Cruijssen apparently has a proof. \$\endgroup\$
    – Bubbler
    Apr 2, 2020 at 7:21
  • \$\begingroup\$ Is the challenge then "determine if n-2 is a power of 2 or is zero"? I think this is likely a dupe. Or do we have to prove the fact ourselves? \$\endgroup\$
    – xnor
    Apr 2, 2020 at 7:22
  • 1
    \$\begingroup\$ That strikes me as a bad idea. It basically seems like a race to post m&-m==m with m=n-2 after a proof is posted, or prove it yourself. Would it be too late to change the challenge to something like counting Rotate-Left-Double numbers, which is hopefully less shortcuttable? \$\endgroup\$
    – xnor
    Apr 2, 2020 at 7:30
  • 1
    \$\begingroup\$ Make that n-2&n-3. \$\endgroup\$
    – xnor
    Apr 2, 2020 at 7:38

12 Answers 12

18
\$\begingroup\$

05AB1E, 6 5 bytes

ÍD<&Ā

-1 byte thanks to @xnor and @Noodle9.

Try it online or verify the first \$[2,100]\$ test cases.

Explanation:

Í       # Decrease the (implicit) input-integer by 2
        # Check that this input-2 is a power of 2 by:
 D      #  Duplicating it
  <     #  Decrease the copy by 1 (so integer-3)
   &    #  Take the bitwise-AND of input-2 and input-3
    Ā   #  Check that this is NOT 0
        # (after which the result is output implicitly)

But wait, I don't see any use of bases nor rotation!

When I saw the challenge in the Sandbox and was working on a solution, I noticed that the only falsey values in the first \$n=[2,500]\$ bases formed the 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

It can also be note that all the numbers in this sequence are of the form \$a(n)=2^n+2\$, so checking whether \$n-2\$ is a power of \$2\$ will verify whether it's in this sequence. Since we want to do the invert here, and having a falsey result if it's in this sequence (or truthy if it's NOT in this sequence), we'll do just that, resulting in the code above.

Mathematical proof that all falsey cases of the Left-Rotate-Double numbers are of the form \$2^n+2\$:

Quote from @saulspatz at the Math SE, who provided me with this Mathematical proof to back up my theory I based on the first \$n=[2,500]\$ test cases. So all credit for this proof goes to him/her.

If \$m\$ is a \$(d+1)\$-digit Rotate-Left-Double number in base \$n\$, then $$m=xn^d+y\tag1$$ where \$d\geq1,\ 0<x<n,\ 0\leq y<n^d\$. (Includes 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\$ (which means \$x\$ is divisible by \$(n-2)\$), 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 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, which states that \$a^{p-1}\equiv 1\pmod p\$, we can take \$d=p-2\$, because $$2^{p-2+1}\equiv 1 \iff 2^{p-1}\equiv 1 \pmod p$$

This completes the proof.

\$\endgroup\$
14
  • 1
    \$\begingroup\$ Amazing. That also explains the pattern in the minimal answers: the minimal digit length is the multiplicative order of 2 modulo p. But the proof makes the challenge itself not a very good one :( \$\endgroup\$
    – Bubbler
    Apr 2, 2020 at 8:01
  • 2
    \$\begingroup\$ @Bubbler Yeah, unfortunately this proof kinda makes it a chameleon challenge. :( I did still upvote it, since it was fun figuring all this out based on your Python reference implementation, the OEIS sequence, and the mathematical proof provided from the Math SE. But I can imagine most people would just create a port of this or the comment provided by xnor, and not look at the bases or rotation at all. :( \$\endgroup\$ Apr 2, 2020 at 8:06
  • 1
    \$\begingroup\$ The real use of that site is for speed hehehe. :D \$\endgroup\$
    – Noodle9
    Apr 2, 2020 at 15:06
  • 1
    \$\begingroup\$ Cool proof! Alternative 5: Í.²θĀ (legacy 05AB1E only, this seems like a bug with modern θ). \$\endgroup\$
    – Grimmy
    Apr 7, 2020 at 6:22
  • 1
    \$\begingroup\$ @Grimmy Ah, I like that alternative. My original 6-byter used \$\log_2\$ as well, but didn't think about the θĀ, that's pretty smart! :) (And weird θ doesn't work on decimal numbers in the new version, even though it does with integers.. I would expect the implementation of θ to be something along the pseudo-code lines of: Convert to string, take first character of string.) \$\endgroup\$ Apr 7, 2020 at 6:30
2
\$\begingroup\$

Python 3, 19 18 bytes

Uses Kevin Cruijssen's formula.

Returns True/False.

Saved a byte thanks to dingledooper!!!

lambda n:n-2&n-3>0

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 18 bytes by replacing !=0 with >0. \$\endgroup\$ Apr 3, 2020 at 3:08
  • \$\begingroup\$ @dingledooper Nice one - thanks! :-) \$\endgroup\$
    – Noodle9
    Apr 3, 2020 at 5:49
2
\$\begingroup\$

Retina 0.8.2, 21 bytes

.+
$*
^11(1(11)+)\1*$

Try it online! Link includes test cases. Explanation: The first stage converts to unary, while the last stage uses @KevinCruijssen's observation that a solution exists if n-2 has a nontrivial odd factor.

\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Extended), 9 bytes

⊃∧/⊤⎕-2 3

Try it online!

A full program that takes a single number \$n\$ from stdin, and prints 1 for true, 0 otherwise. APL doesn't have bitwise functions, so we need to explicitly convert to binary and apply boolean functions on each bit.

How it works

⊃∧/⊤⎕-2 3  ⍝ Input: n (from stdin)
    ⎕-2 3  ⍝ [n-2, n-3]
   ⊤       ⍝ Convert to binary
           ⍝ (each number becomes a column in a matrix, aligned to bottom)
⊃∧/        ⍝ Check if the MSB of both numbers are 1,
           ⍝   i.e. the bit lengths of the two are the same
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 19 bytes

Uses Kevin Cruijssen's formula.

Returns \$1\$ for falsy and \$0\$ for truthy.

f(n){n=!(n-2&n-3);}

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ 16 bytes with zero for falsy and nonzero for truthy \$\endgroup\$
    – S.S. Anne
    Apr 15, 2020 at 23:08
1
\$\begingroup\$

Ruby, 14 bytes

Port of Kevin Cruijssen's answer, remember to upvote them!

->x{x-2&x-3>0}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

GolfScript, 5 bytes

In GolfScript 0 is falsy while any other value is truthy.

2-.(&

Try it online!

\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 10 bytes

In JS 0 is falsy and everything else is truthy. Again, another port of Kevin Cruijssen's answer!

x=>x-2&x-3

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Bash, 22 20 bytes

Uses Kevin Cruijssen's formula.

Returns \$1\$ for falsy and \$0\$ for truthy.

Saved 2 bytes thanks to dingledooper!!!

echo $[!($1-2&$1-3)]

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 20 bytes \$\endgroup\$ Apr 3, 2020 at 3:09
  • \$\begingroup\$ @dingledooper Ah yes, good one - thanks! :-) \$\endgroup\$
    – Noodle9
    Apr 3, 2020 at 5:52
1
\$\begingroup\$

Charcoal, 8 bytes

‹¹Σ⍘⊖⊖N²

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if RLD numbers exist otherwise no output. Explanation:

      N     Input as a number
    ⊖⊖      Decremented twice
   ⍘   ²    Converted to base 2
  Σ         Digital sum
‹¹          Is greater than 1

The only binary numbers with a digital sum of 1 or less are 0 and powers of 2, so by @KevinCruijssen's proof a solution exists for all other values of n.

\$\endgroup\$
1
\$\begingroup\$

Husk, 6 bytes

¬εΣḋ≠2

Try it online!

This one got simplified really quickly.

\$\endgroup\$
1
\$\begingroup\$

Jelly, 5 bytes

_2&’$

Try it online!

Uses the fact that a given \$n\$ returns \$0\$ iff \$n-2\$ is a power of \$2\$, as pointed out by Kevin Cruijssen and the n-2 & n-3 trick

How they work

_2&’$ - Main link. Takes n on the left
_2    - n-2
    $ - To n-2:
   ’  -   Decrement; n-3
  &   -   n-2 & n-3
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.