¿Cuántos números de Lynch-Bell hay?

19

Desafío

Dado un número entero, ncomo entrada donde 36 >= n >= 2, salida cuántos números Lynch-Bell hay en la base n.

La salida debe estar en la base 10.

Números de Lynch-Bell

Un número es un número de Lynch-Bell si:

  • Todos sus dígitos son únicos (sin repetición de dígitos)
  • El número es divisible por cada uno de sus dígitos.
  • No contiene cero como uno de sus dígitos

Como todos los dígitos tienen que ser únicos y tiene un conjunto finito de números de un solo dígito en cada base, hay un número finito de números de Lynch-Bell.

Por ejemplo, en la base 2 solo hay un número de Lynch-Bell 1, ya que todos los demás números repiten dígitos o contienen un 0.

Ejemplos

Input > Output
2 > 1
3 > 2
4 > 6
5 > 10
6 > 10
7 > 75
8 > 144
9 > 487
10 > 548

Mathematica Online se quedó sin memoria por encima de la base 10. Puede usar el siguiente código para generar el suyo propio:

Do[Print[i," > ",Count[Join@@Permutations/@Rest@Subsets@Range[#-1],x_/;And@@(x\[Divides]FromDigits[x,#])]&[i]],{i,10,36,1}]

Victorioso

El código más corto en bytes gana.

Decaimiento Beta
fuente
1
@MagicOctopusUrn ¿Por qué necesitamos un diccionario? No necesitamos producir en esa base.
user202729
2
¿podrías agregar un ejemplo >10?
Rod
1
@ JonathanAllan Ya veo, lo he aclarado ahora
Beta Decay
3
Si solo se necesita [2-36], también podemos enumerarlos a todos.
Jonathan Allan
3
Resulta que nadie ha logrado calcular f(36). Hacer un desafío de código más rápido basado en esto sería probablemente interesante.
user202729

Respuestas:

8

Jalea , 13 bytes

Q⁼g
*`Ṗ©bç"®S

Pruébalo en línea!

Otra solución O (n n ) .

Explicación

Q⁼g  Helper link. Input: digits (LHS), integer (RHS)
Q    Unique (digits)
 ⁼   Match
  g  GCD between each digit and the integer

*`Ṗ©bç"®S  Main link. Input: integer n
*`         Compute n^n
  Ṗ        Pop, forms the range [1, n^n-1]
   ©       Store previous result in register
    b      Convert each integer to base n
     ç"    Call the helper link, vectorized, with
       ®   The register's value
        S  Sum
millas
fuente
16 bytes ṖŒPḊŒ!€Ẏ⁼g¥"ḅ¥³Sy más rápido
millas
5

Jalea , 15 bytes

*ḃ€’Q€Qḍḅ¥€⁸Ạ€S

Pruébalo en línea!

Complejidad .O(nn)

Monja permeable
fuente
55
Solo en code-golf es una O(N^N)solución no solo aceptable, sino buena.
DJMcMayhem
55
@DJMcMayhem Meh, creo que podemos aumentar esos números y obtenerO(N↑↑N)
Decaimiento Beta
¿Debería ser O(N^(N+1))porque verifica la validez de cada número generado O(N)? (aunque no entiendo Jelly)
user202729
@ user202729 N + 1 es solo N en notación big-O.
mbrig
1
@mbrig Por supuesto, entiendo la notación big-O, que ( N+1está en O(N)) no implica que N^(N+1)está en O(N^N).
user202729
3

Java, 222 212 190 bytes

-10 bytes gracias a Herman

-22 bytes gracias a Kevin

import java.util.*;a->{int c=0,i=1;A:for(;i<Math.pow(a,a);i++){Set g=new HashSet();for(char b:a.toString(i).toCharArray())if(!g.add(b)|b<49||i%a.parseInt(b+"",a)>0)continue A;c++;}return c;}

Sin golf:

a -> {
    int count = 0;
    OUTER:
    for (int i = 1; i < Math.pow(a, a); i++) {
        Set<Character> found = new HashSet<>();
        for (char b : Integer.toString(i, a).toCharArray()) {
            if (!found.add(b) || b == 48 || i % Integer.parseInt(b + "", a) != 0) {
                continue OUTER;
            }
        }
        count++;
    }
    return count;
}

Pruébalo en línea!

Se vuelve muy lento para grandes números.

Okx
fuente
-10 bytes:a->{int c=0,i=1;A:for(;i<Math.pow(a,a);i++){java.util.Set<Character>g=new java.util.HashSet<>();for(char b:Long.toString(i,a).toCharArray())if(!g.add(b)|b<49||i%Long.parseLong(b+"",a)>0)continue A;c++;}return c;}
Herman L
Una de las primeras veces que he visto una etiqueta utilizada en una respuesta de codegolf
Justin
A:y continue A;son 13 bytes mientras que {--c;break;}es 12. ¿Introduciría algún error que no veo?
JollyJoker
Esto podría valer una respuesta por separado, pero puede recorrer los dígitos en la base n por cada dígito i%ay i/=aen cada ciclo. Puedes evitar el set usando un int[]y verificando esox[b]++<2
JollyJoker
java.util.Set<Character>‌​g=new java.util.HashSet<>();puede ser import java.util.*;+ Set g=new HashSet();; Long.toStringpuede ser a.toString; y Long.parseLongpuede ser a.parseInt.
Kevin Cruijssen
3

Perl 6 , 86 84 77 bytes

-2 bytes gracias a Ramillies

->\n{n-1+grep {.Set==$_&&.reduce(* *n+*)%%.all},map {|[X] (1..^n)xx$_},2..^n}

Pruébalo en línea!

Funciona para n = 8 en TIO.

nwellnhof
fuente
1
Creo que puedes guardar 2 bytes haciendo en .alllugar de all $_.
Ramillies
2

En realidad , 24 bytes

;╗DR⌠╜DR╨i⌡M⌠;╜@¿♀%ΣY⌡MΣ

Pruébalo en línea!

Explicación

Este programa consta de dos partes principales: la generación de permutación y la prueba Lynch-Bell. Entonces, esta explicación analizará cada parte por separado, para mayor claridad.

Generando permutaciones

Entrada: n(un entero en [2, 36])

Salida: todas las permutaciones parciales y totales de [1, n-1](secuencias que contienen valores [1, n-1]sin repetición cuya longitud está en [1, n-1])

;╗DR⌠╜DR╨i⌡M
;╗            store a copy of n in register 0
  DR          range(1, n)
    ⌠╜DR╨i⌡M  do the following for each element k in range:
     ╜DR        range(1, n)
        ╨       k-permutations of [1, n-1]
         i      flatten

Prueba de Lynch-Bell

Entrada: una lista de nenteros base , representados como listas de ndígitos base

Salida: el número de números de Lynch-Bell en la base n

⌠;╜@¿♀%ΣY⌡MΣ
⌠;╜@¿♀%ΣY⌡M   for each base-n digit list a:
 ;╜             duplicate a, push n
   @¿           convert a from base-n to decimal
     ♀%         modulo a with each of its base-n digits
       Σ        sum
        Y       boolean negation (1 if all modulo results are 0, else 0)
           Σ  sum (count the 1s in the resultant list)
Mego
fuente
2

Mathematica, 82 79 76 bytes

Count[Join@@Permutations/@Subsets@Range[#-1],x_/;x==x~FromDigits~#~GCD~x]-1&
usuario202729
fuente
¿Cómo pasas un número en esto? (lo siento, Mathematica es nuevo para mí)
Beta Decay
Pegue la función (p. Ej., En el sandbox de Wolfram) y luego póngala [<parameter>]después. Con parameterser un número.
user202729
¿Se puede agregar un TIO o equivalente?
Shaggy
1
¿Son f (5) yf (6) ambos realmente 10? Eso es extraño ...
Magic Octopus Urn
1

05AB1E , 22 bytes

mLIBε0KÙ}ÙvyIöySIö%O_O

Pruébalo en línea!

O_O También era mi cara cuando esto finalmente funcionó.

<ÝIBJ0Kæ¦Ù€œ˜ es más rápido que la forma en que uso para generar los números en la respuesta real, pero deja de funcionar aleatoriamente para algo mayor que 7 (¿sin razón aparente?)

Explicación

mLIBε0KÙ}ÙvyIöySIö%O_O # (input = i)
m                      # Push i^i
 L                     # ...and get a range from one to this value
  IB                   # Map every element to their base i representation
    ε   }              # Map every element to ...
     0K                 # Itself without 0s
       Ù                # ...and only unique digits
         Ù             # Uniquify the resulting list
          v            # For each element...
           yIö          # Push it converted to base 10
              ySIö      # Push every digit of it converted to base 10 in a list
                  %     # Calculate the modulo for each digit
                   O    # Sum all results together
                    _   # Negate: Returns 0 for every positive number and 1 for 0
                     O  # Sum with the rest of the stack (Basically counting all Lynch-Bell-Numbers)
                       # Implicit print
Datboi
fuente
Estoy bastante seguro de que un enfoque diferente puede ahorrar más bytes, pero en su solución actual ε0KÙ}puede ser 0м€Ùguardar un byte.
Kevin Cruijssen
1

Perl 5, 80 76 bytes (75 + -p)

$\+=!grep$_?$;%$_|$|{0,$_}++:1,@@until($@[$}++]+=1)%=$_ and++$;,$}=$}==$_}{

Abusar $;por diversión y ganancias. Tiempo de espera en entradas> 8.

EDITAR: -4 bytes fusionando los dos bucles.

Mugriento
fuente
1

Rubí , 80 65 bytes

->n{(1..n**n).count{|i|(d=i.digits n)-[0]==d|d&&d.sum{|j|i%j}<1}}

Pruébalo en línea!

Gracias a GB por -15 bytes.

Kirill L.
fuente
Esto no funcionará para n> 10 (debido a "j.to_i")
GB
Buena captura, lástima que se agote mucho antes de eso :)
Kirill L.
De todos modos: podría llamar "dígitos" pasando la base como argumento y ahorrar mucho: `-> n {(1..n ** n) .count {| i | (d = i.digits n) - [0] == d | d && d.sum? {| j | i% j} <0}} `
GB
De hecho, absolutamente extrañé que los dígitos tengan este parámetro. Pero veo que publicaste esto como una respuesta separada y luego lo eliminaste. Yo diría, adelante, me
ganaste
Creo que mi respuesta es muy similar, es el mismo enfoque con un par de atajos, en su mayoría código robado.
GB
1

Japt -x , 25 19 bytes

-6 bytes gracias a Shaggy

pU õìU ËeDâ f myDìU

Pruébalo en línea!

Solo ASCII
fuente
20 bytes ?
Shaggy
O 19 bytes con la -xbandera.
Shaggy
wow O_o soy claramente terrible en el golf japt
solo ASCII
Lo estás haciendo bien hasta ahora :) Lleva tiempo familiarizarse con un nuevo lenguaje, descubrir todas sus características, trucos y peculiaridades.
Shaggy
@Shaggy, pero cuando usas un nuevo idioma tan a menudo como yo, debería esperarse que estaría más cerca de lo óptimo que un 25% XD
solo ASCII
0

Python 3 , 204 174 bytes

lambda x,r=range,i=chain:sum(0**any(int(''.join(map(str,y)),x)%z for z in y)for y in i(*map(permutations,i(*[combinations(r(1,x),e)for e in r(x)]))))-1
from itertools import*

Pruébalo en línea!

Para cada permutación de cada elemento del conjunto de potencias de rango (1, n) (sin ceros, único), convierta a cadena numérica a base n. Suma todos los que son divisibles por cada dígito, resta 1 debido a que el conjunto de potencia genera el conjunto vacío.

-30 bytes gracias a @ovs!

Conner Johnston
fuente
0

Haskell , 117 bytes

f n=sum[1|x<-id=<<[mapM(\_->[1..n-1])[0..m]|m<-[0..n]],all(\y->[mod(sum(zipWith((*).(n^))[0..]x))y|c<-x,c==y]==[0])x]

Pruébalo en línea! Funciona en TIO hastan=7 antes de que se agote el tiempo de espera.

Laikoni
fuente
0

Perl 5 , 108 + 1 (-p ) = 109 bytes

while(@a<$_){$r=%k=@a=();for($t=++$i;$t;$t=int$t/$_){push@a,$t%$_}$r||=!$_||$i%$_||$k{$_}++for@a;$r||$\++}}{

Pruébalo en línea!

Es un cerdo. No estoy seguro de si hará más que la base 8 en TIO sin tiempo de espera.

Xcali
fuente
0

C # (compilador interactivo de Visual C #) , 144 bytes

n=>{int j,i,p;for(j=i=0;i++<~0UL;){p=i;var a=new List<int>();for(;p>0;p/=n)a.Add(p%n);j+=a.All(c=>c>0&&i%c<1&a.Count(x=>x==c)<2)?1:0;}return j;}

Pasa por todos los números del 0 al ulong.MaxValue, y selecciona aquellos que son números de Lynch-Bell en la base especificada. Tarda una eternidad en ejecutarse, incluso para 2, aunque si configura la ~0ULparte del bucle for en algo más pequeño, puede obtener la salida para la entrada de hasta 7 en un minuto en TIO.

Pruébalo en línea!

Encarnación de la ignorancia
fuente