Code Golf Asked on December 17, 2020

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.

Standard code-golf rules apply. Shortest code in bytes wins.

```
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]
```

```
_2&’$
```

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

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

Answered by caird coinheringaahing on December 17, 2020

Answered by Razetime on December 17, 2020

```
⊃∧/⊤⎕-2 3
```

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.

```
⊃∧/⊤⎕-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
```

Answered by Bubbler on December 17, 2020

```
‹¹Σ⍘⊖⊖Ｎ²
```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-`

if RLD numbers exist otherwise no output. Explanation:

```
Ｎ 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`

.

Answered by Neil on December 17, 2020

```
.+
$*
^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.

Answered by Neil on December 17, 2020

Answered by user92069 on December 17, 2020

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

```
x=>x-2&x-3
```

Answered by user92069 on December 17, 2020

Answered by user92069 on December 17, 2020

Uses Kevin Cruijssen's formula.

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

Saved 2 bytes thanks to dingledooper!!!

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

Answered by Noodle9 on December 17, 2020

Uses Kevin Cruijssen's formula.

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

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

Answered by Noodle9 on December 17, 2020

Uses Kevin Cruijssen's formula.

Returns `True`

/`False`

.

Saved a byte thanks to dingledooper!!!

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

Answered by Noodle9 on December 17, 2020

```
Í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)=leftlfloor2^{n-1}+2rightrfloor$. 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+ytag1$$ where $dgeq1, 0<x<n, 0leq 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)xtag2$$ 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 $ygeq 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 $0leq 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-2equiv0pmod{p}$ so $nequiv 2pmod p$. Therefore, $$2n^dequiv1iff 2cdot2^dequiv1 iff 2^{d+1}equiv 1pmod p,$$ and by Fermat's little theorem, which states that $a^{p-1}equiv 1pmod 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.

Answered by Kevin Cruijssen on December 17, 2020

Get help from others!

Recent Answers

- Jon Church on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP