Repdigit Base Finding

21

Un repdigit es un número natural que se puede escribir únicamente repitiendo el mismo dígito. Por ejemplo, 777es un repdigit, ya que está compuesto únicamente por el dígito 7repetido tres veces.

Sin embargo, esto no se limita simplemente a números decimales (base 10):

  • Cada número de Mersenne (de la forma M n = 2 n -1 ) es un digito cuando se escribe en binario (base 2).
  • Cada número es trivialmente un digito cuando se escribe en unario (base 1).
  • Cada número ntambién se puede escribir trivialmente como el dígito 11de referencia en base n-1(por ejemplo, 17cuando se escribe en hexadecimal (base 16) 11, y 3cuando se escribe en binario (base 2) también 11).

El desafío aquí es encontrar otras bases donde el número de entrada puede ser un digito.

Entrada

Un entero positivo x > 3, en cualquier formato conveniente.

Salida

Un entero positivo bcon (x-1) > b > 1donde la representación de xen base bes un digito.

  • Si no bexiste, salida 0o algún valor falso .
  • Si bexisten varios de estos , puede generar uno o todos ellos.

Reglas

  • La (x-1) > b > 1restricción es evitar las conversiones triviales a base unaria o "restar una". El número de salida se puede escribir en unario o en cualquier base conveniente, pero la base en sí no debe ser una de las conversiones triviales.
  • La entrada / salida puede ser a través de cualquier método adecuado .
  • Se aplican restricciones de escapatoria estándar .

Ejemplos

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)
AdmBorkBork
fuente
¿Podemos suponer b ≤ 36(las funciones de conversión de base incorporadas en muchos idiomas no van más arriba)?
Pomo de la puerta
2
@Doorknob Suponiendo b ≤ 36 que limita severamente el alcance de este problema, y ​​todas las respuestas existentes manejan correctamente bases más grandes, por lo que voy a decir que no, no puede asumir un límite superior bmás allá de lo que se da.
AdmBorkBork
La mayoría de los números son repdigits en alguna base. Por ejemplo, 91 = 13 * 7, por lo que es 77 en la base 12.
Neil
@Neil ... Es casi como si estuvieras en algo, allí ...
AdmBorkBork

Respuestas:

11

Jalea, 11 9 bytes

bRI¬P€TḊṖ

Devuelve una lista de bases, que está vacía (falso) si no hay ninguna. Pruébalo en línea!

Cómo funciona

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).
Dennis
fuente
9

Pyth 11 10

fqjQT)r2tQ

Aparentemente, el unario de Pyth qbusca una lista que tenga todos los valores únicos desde hace aproximadamente 10 días. Aparentemente, investigar los errores de Pyth mejora los puntajes de golf.

Filtra la lista [2..input-1)si el conjunto único de dígitos de la entrada en esa base es longitud 1.

Banco de pruebas

Explicación:

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
FryAmTheEggman
fuente
5

Rubí, 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}}

Tuve que implementar la conversión de base a mano, ya que los componentes integrados de Ruby solo suben a la base 36 ...

Devoluciones nilpor no encontradas.

->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)
Pomo de la puerta
fuente
5

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}

Sin recurrencia, solo prueba todas las bases y genera un conjunto de las que funcionan.

Es tentador codificar by den un solo número, pero se necesitan demasiadas expresiones entre paréntesis para extraerlas. 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

Emite el primero bque funciona, o0 si ninguno lo hace.

Una unidad xde rep de ddígitos de cen base btiene valor x==c*(b**d-1)/(b-1). Equivalentementex*(b-1)==c*(b**d-1) .

El valor cdebe ser x%b, el último dígito. Sin embargo, no veo una manera de determinard aritméticamente, por lo que el código prueba todas las posibilidades para ver si alguno de ellos funciona.

Ahorró 5 bytes copiando el truco de Dennis de dar una salida falsey cuando bllega x-1tomando el módulo de salida x-1. Otro byte salvado de Dennis recordándome que la exponenciación inexplicablemente tiene mayor prioridad que~ .

Una solución de igual longitud con en inlugar de 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
xnor
fuente
4

Ruby, 50 bytes.

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

Realmente me gustaría eliminar ese espacio molesto, pero como recién llegado a Ruby, todavía no estoy familiarizado con sus peculiaridades sintácticas.

xsot
fuente
La peculiaridad ofensiva en este caso es que b?sería un nombre de método válido, por lo que no puede deshacerse del espacio.
Jordan
4

Emojicode , 214 bytes

(77 caracteres):

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

Imprime resultados en la base 9.

He tenido la intención de hacer un código de golf con emojicode durante un par de semanas, pero el lenguaje se ha vuelto lo suficientemente estable como para realmente funcionar con 😉. Como beneficio adicional, esta pregunta hace uso de la única funcionalidad que emojicode es realmente buena para: representar números enteros en otras bases.

Ungolfed (👴 es un comentario de línea en 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
  🍉
🍉
Orez
fuente
4

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

Pruébalo en Ideone .

Idea

Cualquier repdigit x de la base b> 1 y el dígito d <b satisface lo siguiente.

condición

Como d <b , el mapa (b, d) ↦ cb + d es inyectivo.

Además, dado que b, x> 1 , tenemos c <x , entonces cb + d <cb + b = (c + 1) b ≤ xb .

Esto significa que, para encontrar valores adecuados para c y d para una base dada b , podemos iterar a través de todo i en [0, ..., bx) y comprobar si (b - 1) x == (i% b) (b i / b - 1) .

Código

El lambda con nombre f prueba si (b - 1) x está en el conjunto {(i% b) (b i / b - 1) | 0 ≤ i <bx} , comenzando con el valor b = 2 .

  • Si la prueba fue exitosa, devolvemos b .

  • De lo contrario, llamamos a f nuevamente, con las mismas x y b incrementadas en 1 .

Como b eventualmente puede llegar a x - 1 , tomamos el módulo de resultado final x - 1 para devolver 0 en este caso. Tenga en cuenta que esto no sucederá si b = 2 cumple la condición, ya que se devuelve sin recurrir. Sin embargo, la pregunta garantiza que b = 2 <x - 1 en este caso.

Dennis
fuente
3

Perl 6, 45 43 42 bytes

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

Explicado (más o menos)

Como referencia, una variable $^xen { ... }es lo mismo que hacer-> $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 *)le ofrece una lista inversa de dígitos / 'dígitos' para la $nbase$b

Polymod (de verdad): el método polymod es casi como una versión más poderosa de la divmodfunción de Python . $n.polymod(*@args)divide $ n por cada valor en * @ args, agrega el resto ( $n mod $x) a la lista que devuelve y utiliza el cociente para la siguiente división. Siento que lo expliqué mal, así que aquí hay algunos ejemplos (escritos en Perl 6, pero lo suficientemente limpios como para que la mayoría los entienda):

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;
}
Teclas de acceso rápido
fuente
1
En realidad, dado que se le permite generar " cualquiera o todos " de los valores válidos, puede usar el grepmétodo en lugar del firstmétodo.
Brad Gilbert b2gills
Oh buena captura, me perdí eso
Hotkeys
3

Dyalog APL , 28 bytes

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

{... ... la }función anónima que se aplicará a x(representada por )
b←1+⍳⍵-3enteros de 2 - ⍵-2 almacenados como b
⍵{... para cada elemento en b ( ), aplique la función {... }con x como argumento izquierdo,
⍵⊥⍣¯1⊢⍺convertir x a esa base
1=≢∪es 1 igual a la cuenta de dígito único?
b/⍨elementos de b donde true (que solo hay un dígito único).

Casos de ejemplo

Si no existe una base, la salida está vacía (que es falsey), como puede ser demostrado por este programa:

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

Esto imprime 'Falso'

Adán
fuente
2

Pyth, 26 19 bytes

hMfql{eT1m,djQdr2tQ

Pruébalo aquí!

Agregaré una explicación después de jugar golf. Mire esta respuesta para una implementación y explicación más cortas.

Denker
fuente
1
¡Gracias por recordarme que olvidé las bases adicionales para 90y 91en mis ejemplos!
AdmBorkBork
2

MATL , 15 14 bytes

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

Esto funciona con la versión actual (14.0.0) del lenguaje / compilador.

Si no existe una base, la salida está vacía (que es falsey).

Pruébalo en línea!

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
Luis Mendo
fuente
2

Mathematica, 55 bytes

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

Función anónima, no demasiado complicada. Simplemente filtra las bases basadas en la repdigit-ness.

LegionMammal978
fuente
2

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

Un puerto de mi respuesta rubí. Imprime todas las bases válidas si existe alguna.

xsot
fuente
2

Julia, 45 bytes

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

Esta es una función anónima que acepta un entero y devuelve una matriz de enteros. Para llamarlo, asígnelo a una variable. Devolverá todas las bases aplicables o una matriz vacía. No hay problemas con grandes bases.

Primero generamos el rango inclusivo [2, n - 2], donde n es la entrada. Luego, filterla lista solo contiene enteros b para los cuales n en la base b tiene menos de 2 dígitos únicos. Para hacer esto, para cada número entero b en el rango, obtenemos los dígitos de n en la base b como una matriz , utilizamos digitselementos únicos y utilizamos el índice del último elemento (es decir, la longitud) endof.

Alex A.
fuente
1

Brachylog , 12 bytes

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

Pruébalo en línea! (como generador!)

Toma entrada a través de la variable de entrada y emite una base a través de la variable de salida en el caso de que esto sea posible, de lo contrario falla. Al mismo tiempo, también funciona como un generador que genera una lista de todas las bases, donde esa lista puede estar vacía.

Idealmente, esto podría ser algo así ḃ↙.=&>>, posiblemente sacrificando la funcionalidad del generador en esa forma o una similar (ya que eventualmente llegaría a unario), pero a partir de ahora 12 bytes es lo más corto que sé cómo obtenerlo.

     ≜          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)
Cadena no relacionada
fuente
1

Rubí , 46 43 bytes

Utiliza el Entero # dígitos introducida en Ruby 2.4 para evitar la necesidad de dividir manualmente.

-3 bytes gracias a @Jordan.

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

Pruébalo en línea!

Tinta de valor
fuente
@ Jordan ah sí, sigo olvidando ese truco jaja
Value Ink
0

05AB1E , 7 bytes

ÍL¦ʒвÙg

Emite todos los valores posibles, o una lista vacía como valor de falsey (aunque las salidas técnicamente válidas también son falsey, ya que solo 1 es verdad en 05AB1E, y todo lo demás es falsey).

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

Í        # 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)
Kevin Cruijssen
fuente
0

Perl 5 -Minteger -na , 63 bytes

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

Pruébalo en línea!

Emite todas las respuestas posibles o nada si no existe una solución.

Xcali
fuente