Minimal Rotate-Right-Double numbers in base n

Question

Task

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 code-golf rules apply. Shortest solution in bytes wins.

Answer 1

Python 2, 77 76 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.

Answer 2

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)\$)

Answer 3

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)

Answer 4

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,_éÃ.

Answer 5

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!

Answer 6

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!

Answer 7

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

Answer 8

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.

Answer 9

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]]).