Quantos números da Lynch-Bell existem?

19

Desafio

Dado um número inteiro,, ncomo entrada onde 36 >= n >= 2, produz quantos números de Lynch-Bell existem na base n.

A saída deve estar na base 10.

Números de Lynch-Bell

Um número é um número da Lynch-Bell se:

  • Todos os seus dígitos são únicos (sem repetição de dígitos)
  • O número é divisível por cada um de seus dígitos
  • Não contém zero como um de seus dígitos

Como todos os dígitos precisam ser exclusivos e você tem um conjunto finito de números de um dígito em cada base, existe um número finito de números Lynch-Bell.

Por exemplo, na base 2, há apenas um número Lynch-Bell 1, pois todos os outros números repetem dígitos ou contêm um 0.

Exemplos

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

O Mathematica Online ficou sem memória acima da base 10. Você pode usar o seguinte código para gerar o seu próprio:

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

Ganhando

O menor código em bytes vence.

Beta Decay
fonte
11
@MagicOctopusUrn Por que precisamos de um dicionário? Não precisamos produzir nessa base.
user202729
2
você poderia adicionar um exemplo >10?
Rod
11
@ JonathanAllan Entendo, eu já esclareço isso agora
Decay Beta
3
Se apenas [2-36] precisar ser suportado, podemos listar todos eles.
Jonathan Allan
3
Acontece que ninguém conseguiu calcular f(36). Fazer um desafio de código mais rápido com base nisso provavelmente seria interessante.
user202729

Respostas:

8

Gelatina , 13 bytes

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

Experimente online!

Outra solução O (n n ) .

Explicação

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
milhas
fonte
16 bytes ṖŒPḊŒ!€Ẏ⁼g¥"ḅ¥³Se mais rápido
milhas
5

Gelatina , 15 bytes

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

Experimente online!

Complexidade .O(nn)

Freira Furada
fonte
5
Somente no code-golf é uma O(N^N)solução não apenas aceitável, mas boa.
DJMcMayhem
5
@DJMcMayhem Meh, acho que podemos aumentar esses números e obter #O(N↑↑N)
Beta Decay
Deveria ser O(N^(N+1))porque verifica a validade de cada número gerado O(N)? (embora eu não entendo Jelly)
user202729
@ user202729 N + 1 é apenas N na notação big-O.
mbrig
11
@mbrig Claro que entendo a notação big-O, que ( N+1está dentro O(N)) não implica que N^(N+1)está dentro O(N^N).
user202729
3

Java, 222 212 190 bytes

-10 bytes graças a Herman

-22 bytes graças 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;}

Ungolfed:

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;
}

Experimente online!

Fica muito lento para grandes números.

Okx
fonte
-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
Uma das primeiras vezes que eu vi um rótulo usado em uma resposta codegolf
Justin
A:e continue A;são 13 bytes enquanto {--c;break;}é 12. Isso instruiria algum bug que não vejo?
JollyJoker
Isso pode valer uma resposta separada, mas você pode fazer um loop pelos dígitos na base n, sendo cada dígito i%ae i/=aem cada loop. Você pode evitar o conjunto por meio de um int[]e de verificar quex[b]++<2
jollyjoker
java.util.Set<Character>‌​g=new java.util.HashSet<>();pode ser import java.util.*;+ Set g=new HashSet();; Long.toStringpode ser a.toString; e Long.parseLongpode ser a.parseInt.
Kevin Cruijssen
3

Perl 6 , 86 84 77 bytes

-2 bytes graças a Ramillies

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

Experimente online!

Funciona para n = 8 no TIO.

Nwellnhof
fonte
11
Eu acho que você pode salvar 2 bytes, fazendo em .allvez de all $_.
Ramillies
2

Na verdade , 24 bytes

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

Experimente online!

Explicação

Este programa consiste em duas partes principais: a geração de permutação e o teste de Lynch-Bell. Portanto, esta explicação examinará cada parte separadamente, para maior clareza.

Gerando Permutações

Entrada: n(um número inteiro [2, 36])

Saída: todas as permutações parciais e totais de [1, n-1](sequências contendo valores [1, n-1]sem repetição, cujo comprimento esteja dentro [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

Teste de Lynch-Bell

Entrada: uma lista de nnúmeros inteiros base , representada como listas de ndígitos base

Saída: o número de números de Lynch-Bell na 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
fonte
2

Mathematica, 82 79 76 bytes

Count[Join@@Permutations/@Subsets@Range[#-1],x_/;x==x~FromDigits~#~GCD~x]-1&
user202729
fonte
Como você passa um número para isso? (desculpe, o Mathematica é novo para mim)
Decay Beta
Cole a função (por exemplo, na caixa de areia Wolfram) e depois coloque- [<parameter>]a. Com parametersendo um número.
user202729
Você pode adicionar um TIO ou equivalente?
Shaggy
11
F (5) ef (6) são ambos realmente 10? Isso é estranho ...
Magia Octopus Urna
1

05AB1E , 22 bytes

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

Experimente online!

O_O também era meu rosto quando isso finalmente funcionou.

<ÝIBJ0Kæ¦Ù€œ˜ é mais rápido do que o jeito que eu uso para gerar os números na resposta real, mas para de funcionar aleatoriamente por algo maior que 7 (sem motivo aparente?)

Explicação

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
fonte
Tenho certeza de que uma abordagem diferente pode salvar mais bytes, mas na sua solução atual ε0KÙ}pode ser 0м€Ùsalvar um byte.
Kevin Cruijssen em 25/02
1

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

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

Abusar $;por diversão e lucro. Tempo limite excedido nas entradas> 8.

EDIT: -4 bytes, mesclando os dois loops.

Grimmy
fonte
1

Ruby , 80 65 bytes

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

Experimente online!

Graças a GB por -15 bytes.

Kirill L.
fonte
Isso não funcionará para n> 10 (por causa de "j.to_i")
GB
Boa captura, muito ruim, expira bem antes disso :)
Kirill L.
De qualquer forma: você pode chamar "dígitos" passando a base como argumento e economizar muito: `-> n {(1..n ** n) .count {| i | (d = i.digits n) - [0] == d | d && d.sum? {| j | i% j} <0}} `
GB
Na verdade, eu absolutamente perdi que os dígitos têm esse parâmetro. Mas vejo que você postou isso como uma resposta separada e depois excluiu. Eu diria que, vá em frente, você chegou antes de mim :)
Kirill L.
Acho que minha resposta é muito semelhante, é a mesma abordagem com alguns atalhos, principalmente códigos roubados.
GB
1

Japonês -x , 25 19 bytes

-6 bytes graças a Shaggy

pU õìU ËeDâ f myDìU

Experimente online!

Somente ASCII
fonte
20 bytes ?
Shaggy
Ou 19 bytes com o -xsinalizador.
Shaggy
wow O_o eu sou claramente péssimo no golfe japt
ASCII-only
Você está indo bem até agora :) Leva tempo para entender um novo idioma, descobrir todos os seus recursos, truques e peculiaridades.
Shaggy
@ Shaggy, mas quando você usa um novo idioma sempre que eu, é de se esperar que eu esteja mais próximo do ideal do que 25% XD
ASCII-only
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*

Experimente online!

Para cada permutação de cada elemento do conjunto de potências do intervalo (1, n) (sem zeros, exclusivo), converta em sequência numérica na base n. Soma tudo o que é divisível por cada dígito, subtrai 1 devido ao conjunto de geradores que gera o conjunto vazio.

-30 bytes graças a @ovs!

Conner Johnston
fonte
184 bytes
ovs 11/09/17
174 bytes
ovs 11/11/17
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]

Experimente online! Funciona no TIO até n=7antes do tempo limite.

Laikoni
fonte
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||$\++}}{

Experimente online!

É um porco. Não tenho certeza se ele fará mais do que a base 8 no TIO sem tempo limite.

Xcali
fonte
0

C # (compilador interativo do 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;}

Percorre todos os números de 0 a ulong.MaxValuee seleciona aqueles que são números Lynch-Bell na base especificada. Demora uma eternidade para executar, mesmo para 2, embora se você definir a ~0ULparte no loop for para algo menor, poderá obter saída para entrada de até 7 dentro de um minuto no TIO.

Experimente online!

Modalidade de ignorância
fonte