# Minimal Rotate-Right-Double numbers in base n

For a given base $$\n \ge 3\$$, find the smallest positive integer $$\m\$$, when written in base $$\n\$$ and rotated right once, equals $$\2m\$$. The base-$$\n\$$ representation of $$\m\$$ cannot have leading zeroes.

The corresponding OEIS sequence is A087502, and its base-$$\n\$$ representation is A158877 (this one stops at $$\n=11\$$ because the answer for $$\n=12\$$ has a digit higher than 9). The OEIS page has some information about how to calculate the number:

a(n) is the smallest integer of the form x*(n^d-1)/(2n-1) for integer x and d, where 1 < x < n and d > 1. x is the last digit and d is the number of digits of a(n) in base n.

Maple code:

A087502 := proc(n) local d, a; d := 1; a := n; while a>=n do
d := d+1; a := denom((2^d-1)/(2*n-1)); od;
return(max(2, a)*(n^d-1)/(2*n-1)); end proc;


You may output the result as a single integer or a list of base-10 or base-$$\n\$$ digits.

## Examples and test cases

For $$\ n = 3 \$$, the answer is $$\ m = 32 \$$. $$\ n = 4 \$$ should give $$\ m = 18 \$$.

$$m = 32_{10} = 1012_3 \rightarrow 2m = 64_{10} = 2101_3 \\ m = 18_{10} = 102_4 \rightarrow 2m = 36_{10} = 210_4$$

n = 3
m = 32
m (base n) = 1012 or [1,0,1,2]
------------------------------
n = 4
m = 18
m (base n) = 102 or [1,0,2]
------------------------------
n = 10
m = 105263157894736842
m (base n) = 105263157894736842 or [1,0,5,2,6,3,1,5,7,8,9,4,7,3,6,8,4,2]
------------------------------
n = 33
m = 237184
m (base n) = 6jqd or [6,19,26,13]
------------------------------
n = 72
m = 340355112965862493
m (base n) = [6,39,19,45,58,65,32,52,26,13]


More I/O examples can be found on OEIS.

## Scoring and winning criterion

Standard rules apply. Shortest solution in bytes wins.

# Python 2, 7776 70 bytes

f=lambda n,m=1,i=1:i<m and f(n,m,i*n)or(m+m%n*i)/n-m*2and f(n,m+1)or m


Try it online!

Input: base n
Output: The smallest integer m satisfies the requirement.

Saved 6 bytes thanks to @Bubbler!

This is a brute-force search that starts at m = 1 and works its way up. Will run out of recursion limit if the actual solution is too large.

For each m, i keeps track of the current power of n, which is increased until i>m.

# JavaScript (ES7),  90 88 86  85 bytes

A recursive port of the Maple function.

n=>(d=1,x=n,g=(a=2**++d-1,b=q=n+~-n)=>b?g(b,a%b):(x=q/a)<n?(x+!~-x)*(n**d-1)/q:g())()


Try it online! ($$\a(3)\$$ to $$\a(9)\$$)

Or, for +5 bytes, a BigInt version:

n=>(d=1n,x=n,g=(a=2n**++d-1n,b=q=n+~-n)=>b?g(b,a%b):(x=q/a)<n?(~-x?x:2n)*~-(n**d)/q:g())()


Try it online! ($$\a(3)\$$ to $$\a(50)\$$)

• Would it help if d has a known maximum value? (Spoiler: it is $2n-2$ since $d \le \varphi(2n-1) \le 2n-2$.) – Bubbler Apr 6 '20 at 7:23
• @Bubbler Well, it may allow some exec"my_loop;"*2*n in Python, but I don't think I can take advantage of it in JS. – Arnauld Apr 6 '20 at 7:33

# 05AB1E, 15 11 bytes

∞.ΔxsIвÁIβQ


-4 thanks to @Grimmy

Try it online!

explanation:

∞ get all positive numbers
.Δ find the first number for which:
xs the number doubled and itself (e.g. 64, 32)
Iв convert to base input (e.g. [1, 0, 1, 2])
Á rotate right (e.g. [2, 1, 0, 1])
Iβ convert back from base input to a number (e.g. 64)
Q compare to the number doubled (that's in the stack from xs)

• Rotate right is a built-in. ¤s¨sš => Á – Grimmy Apr 6 '20 at 7:47

# Japt, 11 bytes

_Ñ¶ZsU'é}a1


Try it

_Ñ¶ZsU'é}a1     :Implicit input of integer U
_               :Function taking an integer Z as an argument
Ñ              :  Multiply by 2
¶             :  Check for equality with
ZsU          :  Convert Z to a string in base U
'é        :    Rotate right (string is converted back to decimal afterwards)
}       :End function
a1     :Starting with 1, return the first integer that returns true when passed through that function


The ' trick prevents the é method from being applied to U (sidenote: there is no é method for numbers in Japt), instead applying it to the base-U string, and saves 2 bytes over the alternative ZsU,_éÃ.

# Python 2, 78 bytes

Simple direct solution. Increments x and d until we obtain the appropriate answer.

n=input()
j=x=d=2;k=2*n-1
while j%k:j=x*n**d-x;x=[2,x+1][x<n];d+=x<3
print j/k


Try it online!

# Bash + bc, 103 bytes

for((m=1;2*m!=p;));do((m++));t=$(bc<<<"obase=$1;$m");p=$(bc<<<"ibase=$1;${t: -1}${t::-1}");done;echo$m


Try it online!

# Pyth, 30 bytes

Fdr2Kt*2QVr2hQI!%J*Nt^QdK/JK.q


Try it online!

Uses a similar approach to my Python 2 answer. Note: I also used the upper bound of 2n-2 on d that @Bubbler mentioned in a comment.

(Q)


Implicitly initialize Q to be the input

Kt*2Q


Initialize K to be 2Q-1

Fdr2K


For d in range(2, 2Q-1):

Vr2hQ


- For N in range(2, Q+1):

J*Nt^Qd


--> Set J to N * (Q^d - 1)

I!%JK/JK.q


--> If J%K==0, print J/K and exit the program

# Charcoal, 41 bytes

Ｎθ≔⊖⊗θηＩ÷⌊ΦＥ×θη∨‹ι⊗θ∨‹﹪ιθ²×﹪ιθ⊖Ｘθ÷ιθ¬﹪ιηη


Try it online! Link is to verbose version of code. Uses the OEIS quote plus the additional information provided by @Bubbler in a comment whereby d < 2n-1. Explanation:

Ｎθ


Input n.

≔⊖⊗θη


Calculate 2n-1.

Ｅ×θη


Loop nd + x from 0 to n(2n-1).

∨‹ι⊗θ


Ensure d > 1 by returning 1 if it is not, which is never divisible by 2n-1.

∨‹﹪ιθ²


Ensure x > 1 in the same way.

×﹪ιθ⊖Ｘθ÷ιθ


Calculate x(nᵈ-1).

Φ...¬﹪ιη


Keep only those values that are multiples of 2n-1.

Ｉ÷⌊...η


Divide the minimum of those values by 2n-1 and output the result.

# Scala, 80 bytes

n=>Stream.iterate(1)(n*_)map(p=>p to p*n-1 find(x=>2*x==x%n*p+x/n))find(_!=None)


Try it online!

Takes an integer n, returns an Option[Option[Int]] (really a Some[Some[Int]]).