5
\$\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\$
  • 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 at 7:19
  • \$\begingroup\$ @xnor I didn't, but Kevin Cruijssen apparently has a proof. \$\endgroup\$ – Bubbler Apr 2 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 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 at 7:30
  • 1
    \$\begingroup\$ Make that n-2&n-3. \$\endgroup\$ – xnor Apr 2 at 7:38

10 Answers 10

12
\$\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.

| improve this answer | |
\$\endgroup\$
  • 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 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\$ – Kevin Cruijssen Apr 2 at 8:06
  • 1
    \$\begingroup\$ The real use of that site is for speed hehehe. :D \$\endgroup\$ – Noodle9 Apr 2 at 15:06
  • 1
    \$\begingroup\$ Cool proof! Alternative 5: Í.²θĀ (legacy 05AB1E only, this seems like a bug with modern θ). \$\endgroup\$ – Grimmy Apr 7 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\$ – Kevin Cruijssen Apr 7 at 6:30
1
\$\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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 18 bytes by replacing !=0 with >0. \$\endgroup\$ – dingledooper Apr 3 at 3:08
  • \$\begingroup\$ @dingledooper Nice one - thanks! :-) \$\endgroup\$ – Noodle9 Apr 3 at 5:49
1
\$\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.

| improve this answer | |
\$\endgroup\$
0
\$\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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 16 bytes with zero for falsy and nonzero for truthy \$\endgroup\$ – S.S. Anne Apr 15 at 23:08
0
\$\begingroup\$

Ruby, 14 bytes

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

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

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

GolfScript, 5 bytes

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

2-.(&

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\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!

| improve this answer | |
\$\endgroup\$
0
\$\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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 20 bytes \$\endgroup\$ – dingledooper Apr 3 at 3:09
  • \$\begingroup\$ @dingledooper Ah yes, good one - thanks! :-) \$\endgroup\$ – Noodle9 Apr 3 at 5:52
0
\$\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.

| improve this answer | |
\$\endgroup\$
0
\$\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
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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