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.


9 Answers 9


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.


JavaScript (ES7),  90 88 86  85 bytes

A recursive port of the Maple function.


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

Or, for +5 bytes, a BigInt version:


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

  • \$\begingroup\$ Would it help if d has a known maximum value? (Spoiler: it is \$2n-2\$ since \$ d \le \varphi(2n-1) \le 2n-2 \$.) \$\endgroup\$
    – Bubbler
    Apr 6, 2020 at 7:23
  • \$\begingroup\$ @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. \$\endgroup\$
    – Arnauld
    Apr 6, 2020 at 7:33

05AB1E, 15 11 bytes


-4 thanks to @Grimmy

Try it online!


∞ 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)
  • 1
    \$\begingroup\$ Rotate right is a built-in. ¤s¨sš => Á \$\endgroup\$
    – Grimmy
    Apr 6, 2020 at 7:47

Japt, 11 bytes


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.

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


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.


Implicitly initialize Q to be the input


Initialize K to be 2Q-1


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


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


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


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


Your Answer

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

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