How many Lynch-Bell numbers are there?

Question

Challenge

Given an integer, n, as input where 36 >= n >= 2, output how many Lynch-Bell numbers there are in base n.

The output must be in base 10.

Lynch-Bell Numbers

A number is a Lynch-Bell numbers if:

• All of its digits are unique (no repetition of digits)
• The number is divisible by each of its digits
• It doesn't contain zero as one of its digits

Since, all of the digits have to be unique, and you have a finite set of single digit numbers in each base, there is a finite number of Lynch-Bell numbers.

For example, in base 2 there is only one Lynch-Bell number, 1, since all other numbers either repeat digits or contain a 0.

Examples

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

Mathematica Online ran out of memory above base 10. You can use the following code to generate your own:

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

Winning

Shortest code in bytes wins.

Answer 1

Jelly, 13 bytes

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

Try it online!

Another O(nⁿ) solution.

Explanation

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

Answer 2

Jelly, 15 bytes

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

Try it online!

Complexity O(nn).

Answer 3

Java, 222 212 190 bytes

-10 bytes thanks to Herman

-22 bytes thanks to 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;
}

Try it online!

Gets very slow for large numbers.

Answer 4

Perl 6, 86 84 77 bytes

-2 bytes thanks to Ramillies

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

Try it online!

Works for n=8 on TIO.

Answer 5

Mathematica, 82 79 76 bytes

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

Answer 6

Actually, 24 bytes

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

Try it online!

Explanation

This program consists of two main parts: the permutation generation, and the Lynch-Bell test. So, this explanation will look at each part separately, for greater clarity.

Generating Permutations

Input: n (an integer in [2, 36])

Output: all partial and total permutations of [1, n-1] (sequences containing values from [1, n-1] without repetition whose length is in [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

Lynch-Bell Test

Input: a list of base-n integers, represented as lists of base-n digits

Output: the number of Lynch-Bell numbers in 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)

Answer 7

05AB1E, 22 bytes

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

Try it online!

O_O was also my face when this finally worked.

<ÝIBJ0Kæ¦Ù€œ˜ is faster than the way I use to generate the numbers in the actual answer but randomly stops working for anything bigger than 7 (for no apparent reason?)

Explanation

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

Answer 8

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

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

Abusing $; for fun and profit. Times out on inputs > 8.

EDIT: -4 bytes by merging the two loops.

Answer 9

Ruby, 80 65 bytes

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

Try it online!

Thanks to G B for -15 bytes.

Answer 10

Japt -x, 25 19 bytes

-6 bytes thanks to Shaggy

pU õìU ËeDâ f myDìU

Try it online!

Answer 11

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*

Try it online!

For each permutation of each element of powerset of range(1,n) (no zeros, unique), convert to numerical string to base n. Sum all that are divisible by each digit, subtract 1 due to powerset generating the empty set.

-30 bytes thanks to @ovs!

Answer 12

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]

Try it online! Works on TIO up to n=7 before timing out.

Answer 13

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

Try it online!

It's a pig. Not sure if it will do more than base 8 on TIO without timing out.

Answer 14

C# (Visual C# Interactive Compiler), 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;}

Goes through all the numbers from 0 to ulong.MaxValue, and selects those that are Lynch-Bell numbers in the specified base. Takes forever to run, even for 2, though if you set the ~0UL part in the for loop to something smaller, you can get output for input up to 7 within a minute on TIO.

Try it online!