12
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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.

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

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

| improve this answer | |
\$\endgroup\$
  • \$\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 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 at 7:33
3
\$\begingroup\$

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

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

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

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!

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

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

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

Charcoal, 41 bytes

Nθ≔⊖⊗θηI÷⌊ΦE×θη∨‹ι⊗θ∨‹﹪ιθ²×﹪ιθ⊖Xθ÷ιθ¬﹪ιηη

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:

Nθ

Input n.

≔⊖⊗θη

Calculate 2n-1.

E×θη

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.

×﹪ιθ⊖Xθ÷ιθ

Calculate x(nᵈ-1).

Φ...¬﹪ιη

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

I÷⌊...η

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

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

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!

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