21
\$\begingroup\$

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 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)
\$\endgroup\$
  • \$\begingroup\$ Can we assume b ≤ 36 (many languages' built-in base conversion functions don't go higher)? \$\endgroup\$ – Doorknob Mar 16 '16 at 14:54
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – AdmBorkBork Mar 16 '16 at 14:58
  • \$\begingroup\$ Most numbers are repdigits in some base. For instance, 91 = 13 * 7 so it's 77 in base 12. \$\endgroup\$ – Neil Mar 16 '16 at 17:19
  • \$\begingroup\$ @Neil ... It's almost like you're on to something, there ... \$\endgroup\$ – AdmBorkBork Mar 16 '16 at 18:05

18 Answers 18

11
\$\begingroup\$

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).
\$\endgroup\$
9
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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)
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The offending quirk in this case is that b? would be a valid method name, so you can’t get rid of the space. \$\endgroup\$ – Jordan Jun 28 at 23:23
4
\$\begingroup\$

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
  🍉
🍉
\$\endgroup\$
4
\$\begingroup\$

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.

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

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Brad Gilbert b2gills Mar 17 '16 at 21:36
  • \$\begingroup\$ Oh good catch, I missed that \$\endgroup\$ – Hotkeys Mar 17 '16 at 22:40
3
\$\begingroup\$

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'

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for reminding me that I forgot the additional bases for 90 and 91 in my examples! \$\endgroup\$ – AdmBorkBork Mar 16 '16 at 13:37
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ @Jordan ah yes I keep forgetting that trick haha \$\endgroup\$ – Value Ink Jun 28 at 18:21
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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.

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