Repdigit Base Finding

Question

A repdigit is a natural number that can be written solely by repeating the same digit. For example, 777 is a repdigit, since it's solely composed of the digit 7 repeated three times.

This isn't limited to simply decimal (base 10) numbers, however:

• Every Mersenne number (of the form M_n = 2ⁿ-1) is a repdigit when written in binary (base 2).
• Every number is trivially a repdigit when written in unary (base 1).
• Every number n can also trivially be written as the repdigit 11 in base n-1 (for example, 17 when written in hexadecimal (base 16) is 11, and 3 when written in binary (base 2) is also 11).

The challenge here is to find other bases where the input number may be a repdigit.

Input

A positive integer x > 3, in any convenient format.

Output

A positive integer b with (x-1) > b > 1 where the representation of x in base b is a repdigit.

• If no such b exists, output 0 or some falsey value.
• If multiple such b exist, you can output any or all of them.

Rules

• The (x-1) > b > 1 restriction is to prevent the trivial conversions to unary or the "subtract one" base. The output number can be written in unary or any convenient base, but the base itself must not be one of the trivial conversions.
• Input/output can be via any suitable method.
• Standard loophole restrictions apply.

Examples

In --> Out
11 --> 0            (or other falsey value)
23 --> 0            (or other falsey value)
55 --> 10           (since 55 is 55 in base 10)
90 --> 14           (since 90 is 66 in base 14 ... 17, 29, 44 also allowed)
91 --> 9            (since 91 is 111 in base 9 ... 12 also allowed)

Answer 1

Jelly, 11 9 bytes

bRI¬P€TḊṖ

Returns a list of bases, which is empty (falsy) if there is none. Try it online!

How it works

bRI¬P€TḊṖ  Main link. Argument: x (number)

 R         Range; yield [1, ..., x].
b          Base; convert x to base n, for each n in the range.
  I        Compute the increment (differences of successive values) of each array
           of base-n digits. This yields only 0's for a repdigit.
   ¬       Apply logical NOT to each increment.
    P€     Compute the product of all lists of increments.
      T    Get the indices of all truthy products.
       Ḋ   Discard the first index (1).
        Ṗ  Discard the last index (x - 1).

Answer 2

Pyth, 11 10

fqjQT)r2tQ

Apparently Pyth's unary q checks for a list that has all unique values as of about 10 days ago. Apparently investigating Pyth bugs improves golf scores.

Filters the list [2..input-1) on if the unique set of digits of the input in that base is length 1.

Test Suite

Explanation:

r2tQ     ##  generate the python range from 2 to the input (Q) - 1
         ##  python range meaning inclusive lower and exclusive upper bounds
f        ##  filter that list with lambda T:
  jQT    ##  convert the input to base T
 q    )  ##  true if the resulting list digits has all equal elements

Answer 3

Ruby, 87 69 63 bytes

->x{(2..x-2).find{|b|y=x;a=y%b;a=0if a!=y%b while(y/=b)>0;a>0}}

I had to implement base conversion by hand, since Ruby's builtins only go up to base 36...

Returns nil for not found.

->x{      # anonymous lambda that takes one argument
(2..x-2)  # range of the possible bases to search over
.find{    # return the first element that satisfies the block, or nil if none
|b|       # b represents the base currently being tested
y=x;      # a temporary value to avoid mutating the original value of x
a=y%b;    # the first (well, last) digit in base b, which will be compared to

                   y/=b      # divide the number by the base
   if a!=y%b                 # if this digit does not match (is different)...
a=0                          # set a to a value representing "failure"
             while(    )>0;  # keep doing this until we get zero (no digits left)

a>0       # return whether a has maintained its original value (no digit change)
}}        # find then returns the first element for which this is true (or nil)

Answer 4

Python, 71 72 78 bytes

lambda x:{b for b in range(2,x-1)for d in range(x)if x*~-b==x%b*~-b**d}

No recursion, just tries all bases and outputs a set of those that work.

It's tempting to encode b and d in a single number, but it takes too many parenthesized expressions to extract them. 77 bytes:

lambda x:{k/x for k in range(2*x,x*x-x))if x*~-(k/x)==x%(k/x)*~-(k/x)**(k%x)}

---

72 bytes:

f=lambda x,b=2:b*any(x*~-b==x%b*~-b**d for d in range(x))or f(x,b+1)%~-x

Outputs the first b that works, or 0 if none do.

A rep-unit x of d digits of c in base b has value x==c*(b**d-1)/(b-1). Equivalently, x*(b-1)==c*(b**d-1).

The value c must be x%b, the last digit. I don't see a way though to determine d arithmetically, so the code tries all possibilities to see if any of them work.

Saved 5 bytes by copying Dennis's trick of giving a falsey output when b reaches x-1 by taking the output modulo x-1. Another byte saved from Dennis reminding me that exponentiation inexplicably has higher precedence that ~.

An equal-length solution with in instead of any.

f=lambda x,b=2:b*(x*~-b in[x%b*~-b**d for d in range(x)])or f(x,b+1)%~-x

Answer 5

Ruby, 50 bytes

->n{(2..n-2).find{|b,i=n|i%b==(i/=b)%b ?redo:i<1}}

I would really like to remove that annoying space but as a newcomer to ruby, I'm still quite unfamiliar with its syntactic quirks.

Answer 6

Emojicode, 214 bytes

(77 characters):

🐇🐹🍇🐇🐖🏁➡🚂🍇🍦b🍺🔲🗞🔷🔡😯🔤🔤🚂🍮i 2🍮n 0🔁◀i➖b 1🍇🍦v🔷🔡🚂b i🍊▶🐔🔫v🔪v 0 1📏v🍇🍮n i🍉🍫i🍉😀🔷🔡🚂n 9🍎0🍉🍉

Prints results in base 9.

I've been meaning to do a code golf with emojicode for a couple weeks now, but the language has only recently become stable enough to actually work with 😉. As a bonus, this question makes use of the one piece of functionality emojicode is actually really good at: representing integers in other bases.

Ungolfed (👴 is a line comment in emojicode)

🐇🐹🍇         👴 define main class "🐹"
  🐇🐖🏁➡🚂🍇  👴 define main method

    👴 read an integer from stdin, store it in frozen variable "b"
    🍦 b 🍺 🔲 🗞 🔷🔡😯🔤🔤 🚂

    🍮 i 2  👴 i = 2
    🍮 n 0  👴 n = 0

    🔁◀i➖b 1🍇     👴 while i < b - 1
      🍦 v 🔷🔡🚂b i  👴 v = the string representation of b in base i

      👴 Split v on every instance of the first character of v.
      👴 If the length of that list is greater than the actual length of v,
      👴 n = i
      🍊▶🐔🔫v🔪v 0 1📏v🍇
        🍮 n i
      🍉

      🍫 i  👴 increment i
    🍉
    😀 🔷🔡🚂 n 9  👴 represent n in base 9 instead of 10, to save a byte 😜
    🍎 0          👴 return error code 0
  🍉
🍉

Answer 7

Python 2, 79 bytes

f=lambda x,b=2:~-b*x in[i%b*~-b**(i/b)for i in range(b*x)]and b or f(x,-~b)%~-x

Try it on Ideone.

Idea

Any repdigit x of base b > 1 and digit d < b satisfies the following.

Since d < b, the map (b, d) ↦ cb + d is injective.

Also, since b, x > 1, we have c < x, so cb + d < cb + b = (c + 1)b ≤ xb.

This means that, to find suitable values for c and d for a given base b, we can iterate through all i in [0, …, bx) and check whether (b - 1)x == (i % b)(b^{i / b} - 1).

Code

The named lambda f test whether (b - 1)x is in the set {(i % b)(b^{i / b} - 1) | 0 ≤ i < bx}, beginning with the value b = 2.

• If the test was successful, we return b.

• Else, we call f again, with the same x and b incremented by 1.

Since b may eventually reach x - 1, we take the final result modulo x - 1 to return 0 in this case. Note that this will not happen if b = 2 satisfies the condition, since it is returned without recursing. However, the question guarantees that b = 2 < x - 1 in this case.

Answer 8

Perl 6, 45 43 42 bytes

{grep 2..$^x-2: {[==] $x.polymod($_ xx*)}}

Explained (sort of)

For reference, a variable $^x in { ... } is the same as doing -> $x { ... }

{grep 2..$^x-2: {[==] $x.polymod($_ xx*)}}
{                                          # Anonymous function taking $x
 grep                                      # Return the all values in
      2..$^x-2: {                          # Range from 2 to $x - 2 satisfying:
                 [==]                      #     Reduce with ==:
                      $x.polymod(          #         (See below for polymod)
                                 $_ xx*    #         An infinite list containing
                                           #         the current value
                                       )}}

Polymod (TL;DR): $n.polymod($b xx *) gives you a reversed list of digits/'digits' for $n in base $b

Polymod (For real): The polymod method is almost like a more powerful version of python's divmod function. $n.polymod(*@args) divides $n by each value in *@args, adding the remainder ($n mod $x) to the list it returns, and using the quotient for the next division. I feel I explained it poorly so here's some examples (written in perl 6, but clean enough to be understood by most I hope):

12.polymod(7)    # returns (5, 1)
# Roughly equivalent to:
(12 mod 7, 12 div 7)

86400.polymod(60,60,24) # returns (0, 0, 0, 1)
# Roughly equivalent to (this will give you an array rather than a list):
my $n = 86400;
my @remainders; # Here lies the end result
for (60, 60, 24) -> $divisor {
    @remainders.push( $n mod $divisor );
    $n div= $divisor;
}
@remainders.push($n)

# This is essentially the base conversion algorithm everyone
# knows and loves rolled into a method.
# Given an infinite list of divisors, polymod keeps going until
# the remainder given is 0.     
0xDEADBEEF.polymod(16 xx *) # returns (15 14 14 11 13 10 14 13)
# Roughly equivalent to (but gives an array rather than a list):
my $n = 0xDEADBEEF;
my @remainders; # Here lies the end result
while $n > 0 {
    @remainders.push( $n mod 16 );
    $n div= 16;
}

Answer 9

Dyalog APL, 28 bytes

 {b/⍨⍵{1=≢∪⍵⊥⍣¯1⊢⍺}¨b←1+⍳⍵-3}

{…⍵…} anonymous function to be applied to x (represented by ⍵)
b←1+⍳⍵-3 integers from 2 – ⍵-2 stored as b
⍵{…}¨ for each element in b (⍵), apply the function {…} with x as left argument ⍺
⍵⊥⍣¯1⊢⍺ convert x to that base
1=≢∪ is 1 equal to the tally of unique digit?
b/⍨ elements of b where true (that there is only one unique digit).

Example cases

If no base exists, the output is empty (which is falsey), as can be demonstrated by this program:

 WhatIsEmpty
 →''/TRUE ⍝ goto (→) TRUE: if (/) emptystring ('')
 'False'
 →END       
TRUE:       
 'True'     
END:        

This prints 'False'

Answer 10

Pyth, 26 19 bytes

hMfql{eT1m,djQdr2tQ

Try it here!

Will add an explanation after I golfed this. Look at this answer for a shorter implementation and explanation.

Answer 11

MATL, 15 14 bytes

3-:Q"G@:YAd~?@

This works with current version (14.0.0) of the language/compiler.

If no base exists, the output is empty (which is falsey).

Try it online!

3-:Q    % take input x implicitly. Generate range of possible bases: [2,3,...,x-2]
"       % for each base b
  G     %   push input again
  @:    %   generate vector of (1-based) digits in base b: [1,2,...,b]
  YA    %   convert to that base
  d~    %   differences between consecutive digits; negate
  ?     %   if all values are true (that is, if all digits were equal)
    @   %     push that base
        %   end if implicitly
        % end for each implicitly
        % display implicitly

Answer 12

Mathematica, 55 bytes

Cases[4~Range~#-2,a_/;Equal@@#~IntegerDigits~a]/.{}->0&

Anonymous function, not too complicated. Just filters out bases based on repdigit-ness.

Answer 13

Python 2, 75 bytes

n=input()
b=1
while b<n-2:
 i=n;b+=1
 while i%b==i/b%b:i/=b
 if i<b:print b

A port of my ruby answer. Prints all valid bases if any exists.

Answer 14

Julia, 45 bytes

n->filter(b->endof(∪(digits(n,b)))<2,2:n-2)

This is an anonymous function that accepts an integer and returns an integer array. To call it, assign it to a variable. It will return all applicable bases or an empty array. There are no issues with large bases.

First we generate the inclusive range [2, n - 2], where n is the input. We then filter the list to only integers b for which n in base b has fewer than 2 unique digits. To do this, for each integer b in the range, we get the digits of n in base b as an array using digits, get unique items using ∪, and get the index of the last element (i.e. the length) using endof.

Answer 15

Brachylog, 12 bytes

>>.ℕ₂≜&ḃ↙.=∧

Try it online! (as a generator!)

Takes input through the input variable and outputs a base through the output variable in the case that this is possible, failing otherwise. At the same time, it also works as a generator which outputs a list of all bases, where that list can be empty.

Ideally this could look something like ḃ↙.=&>>, possibly sacrificing generator functionality in that form or a similar one (since it would eventually hit unary), but as of now 12 bytes is the shortest I know how to get it.

     ≜          Assign an integer value to
  .             the output variable
   ℕ₂           which is greater than or equal to 2
 >              and less than a number
>               which is less than the input.
      &         The input
       ḃ↙.      in base-(the output)
          =     is a repdigit.
           ∧    (which is not necessarily the output)

Answer 16

Ruby, 46 43 bytes

Uses the Integer#digits function introduced in Ruby 2.4 to avoid needing to manually divide.

-3 bytes thanks to @Jordan.

->n{(2..n-2).find{|i|!n.digits(i).uniq[1]}}

Try it online!

Answer 17

05AB1E, 7 bytes

ÍL¦ʒвÙg

Outputs all possible values, or an empty list as falsey value (although technically valid outputs are falsey as well, since only 1 is truthy in 05AB1E, and everything else is falsey).

Try it online or verify all test cases.

Explanation:

Í        # Decrease the (implicit) input-integer by 2
 L       # Create a list in the range [1, input-2]
  ¦      # Remove the first value to make the range [2, input-2]
   ʒ     # Filter this list by:
    в    #  Convert the (implicit) input to the base of the number we're filtering
     Ù   #  Uniquify it, leaving only distinct digits
      g  #  Get the length of this, which is truthy (1) if all digits were the same
         # (and then output the filtered list implicitly as result)

Answer 18

Perl 5 -Minteger -na, 63 bytes

map{$r=$,=($c="@F")%$_;$r*=$c%$_==$,while$c/=$_;$r&&say}2..$_-2

Try it online!

Outputs all possible answers or nothing if no solution exists.