Défi

Étant donné un entier,, ncomme entrée où 36 >= n >= 2, sortez combien de nombres Lynch-Bell il y a dans la base n.

La sortie doit être en base 10.

Numéros de Lynch-Bell

Un numéro est un numéro de Lynch-Bell si:

• Tous ses chiffres sont uniques (pas de répétition de chiffres)
• Le nombre est divisible par chacun de ses chiffres
• Il ne contient pas zéro comme l'un de ses chiffres

Étant donné que tous les chiffres doivent être uniques et que vous avez un ensemble fini de numéros à un chiffre dans chaque base, il existe un nombre fini de numéros Lynch-Bell.

Par exemple, dans la base 2, il n'y a qu'un seul numéro Lynch-Bell 1, car tous les autres numéros répètent des chiffres ou contiennent un 0.

Exemples

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

Mathematica Online a manqué de mémoire au-dessus de la base 10. Vous pouvez utiliser le code suivant pour générer le vôtre:

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

Gagnant

Le code le plus court en octets gagne.

Gelée , 13 octets

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

Essayez-le en ligne!

Une autre solution O (n ⁿ ) .

Explication

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

Gelée , 15 octets

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

Essayez-le en ligne!

Complexité .O(nn)

Java, 222 212 190 octets

-10 octets grâce à Herman

-22 octets grâce à 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;}

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

Essayez-le en ligne!

Obtient très lent pour les grands nombres.

Perl 6 , 86 84 77 octets

-2 octets grâce aux Ramillies

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

Essayez-le en ligne!

Fonctionne pour n = 8 sur TIO.

En fait , 24 octets

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

Essayez-le en ligne!

Explication

Ce programme comprend deux parties principales: la génération de permutation et le test de Lynch-Bell. Ainsi, cette explication examinera chaque partie séparément, pour plus de clarté.

Génération de permutations

Entrée: n(un entier dans [2, 36])

Sortie: toutes les permutations partielles et totales de [1, n-1](séquences contenant des valeurs [1, n-1]sans répétition dont la longueur 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

Test de Lynch-Bell

Entrée: une liste d' nentiers de base , représentés sous forme de listes de nchiffres de base

Sortie: le nombre de numéros de Lynch-Bell en 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)

Mathematica, 82 79 76 octets

Count[Join@@Permutations/@Subsets@Range[#-1],x_/;x==x~FromDigits~#~GCD~x]-1&

05AB1E , 22 octets

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

Essayez-le en ligne!

O_O était aussi mon visage quand cela a finalement fonctionné.

<ÝIBJ0Kæ¦Ù€œ˜ est plus rapide que la façon dont j'utilise pour générer les nombres dans la réponse réelle, mais cesse de fonctionner au hasard pour quelque chose de plus grand que 7 (sans raison apparente?)

Explication

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

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

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

Abuser $;pour le plaisir et le profit. Expiration des entrées> 8.

EDIT: -4 octets en fusionnant les deux boucles.

Rubis , 80 65 octets

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

Essayez-le en ligne!

Merci à GB pour -15 octets.

Japt -x , 25 19 octets

-6 octets grâce à Shaggy

pU õìU ËeDâ f myDìU

Essayez-le en ligne!

Python 3 , 204 174 octets

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*

Essayez-le en ligne!

Pour chaque permutation de chaque élément de l'ensemble de puissance de la plage (1, n) (pas de zéros, unique), convertissez en chaîne numérique en base n. Additionnez tout ce qui est divisible par chaque chiffre, soustrayez 1 en raison du jeu de puissance générant l'ensemble vide.

-30 octets grâce à @ovs!

Haskell , 117 octets

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]

Essayez-le en ligne! Fonctionne sur TIO jusqu'à n=7avant expiration.

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

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

Essayez-le en ligne!

C'est un cochon. Je ne sais pas s'il fera plus que la base 8 sur TIO sans expiration.

C # (Visual C # Interactive Compiler) , 144 octets

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

Parcourt tous les numéros de 0 à ulong.MaxValueet sélectionne ceux qui sont des numéros de Lynch-Bell dans la base spécifiée. Il faut une éternité pour fonctionner, même pour 2, bien que si vous définissez la ~0ULpartie de la boucle for sur quelque chose de plus petit, vous pouvez obtenir une sortie pour une entrée jusqu'à 7 en une minute sur TIO.

Essayez-le en ligne!