Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 Mn = 2n-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 a repdigit in base n-1 (for example, 17 when written in hexadecimal (base 16) is 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)
share|improve this question
    
Can we assume b ≤ 36 (many languages' built-in base conversion functions don't go higher)? – Doorknob Mar 16 at 14:54
1  
@Doorknob Assuming b ≤ 36 severely limits the scope of this problem, and all of the existing answers correctly handle larger bases, so I'm going to say no, you cannot assume an upper bound on b beyond what's given. – TimmyD Mar 16 at 14:58
    
Most numbers are repdigits in some base. For instance, 91 = 13 * 7 so it's 77 in base 12. – Neil Mar 16 at 17:19
    
@Neil ... It's almost like you're on to something, there ... – TimmyD Mar 16 at 18:05

14 Answers 14

up vote 9 down vote accepted

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).
share|improve this answer

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
share|improve this answer

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)
share|improve this answer

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.

condition

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)(bi / b - 1).

Code

The named lambda f test whether (b - 1)x is in the set {(i % b)(bi / 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.

share|improve this answer

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.

share|improve this answer

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
share|improve this answer

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;
}
share|improve this answer
1  
Actually since you are allowed to output "any or all" of the valid values, you can use the grep method instead of the first method. – Brad Gilbert b2gills Mar 17 at 21:36
    
Oh good catch, I missed that – LockOpeners Mar 17 at 22:40

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'

share|improve this answer

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.

share|improve this answer
1  
Thanks for reminding me that I forgot the additional bases for 90 and 91 in my examples! – TimmyD Mar 16 at 13:37

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
share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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
  🍉
🍉
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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