How many Lynch-Bell numbers are there?

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.

• @MagicOctopusUrn Why do we need a dictionary? We don't need to output in that base. – user202729 Sep 11 '17 at 16:01
• could you add an example >10? – Rod Sep 11 '17 at 16:05
• @JonathanAllan I see, I've cleared that up now – Beta Decay Sep 11 '17 at 16:08
• If only [2-36] need be supported we may as well list them all. – Jonathan Allan Sep 11 '17 at 16:09
• Turns out that no one has managed to calculate f(36). Make a fastest-code challenge based on this would be probably interesting. – user202729 Sep 25 '17 at 10:15

Jelly, 13 bytes

Q⁼g
*Ṗ©bç"®S

Try it online!

Another O(nn) solution.

Explanation

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

*         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
• 16 bytes ṖŒPḊŒ!€Ẏ⁼g¥"ḅ¥³S and faster – miles Sep 11 '17 at 18:46

Jelly, 15 bytes

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

Try it online!

Complexity O(nn).

• Only in code-golf is an O(N^N) solution not only acceptable, but good. – DJMcMayhem Sep 11 '17 at 16:55
• @DJMcMayhem Meh, I think we can pump those numbers up and get O(N↑↑N) – Beta Decay Sep 11 '17 at 17:15
• Should it be O(N^(N+1)) because check the validity of each generated number takes O(N)? (although I don't understand Jelly) – user202729 Sep 12 '17 at 9:44
• @user202729 N+1 is just N in big-O notation. – mbrig Sep 12 '17 at 14:10
• @mbrig Of course I understand big-O notation, that (N+1 is in O(N)) does not implies N^(N+1) is in O(N^N). – user202729 Sep 12 '17 at 14:16

Java, 222212 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.

• -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 Sep 11 '17 at 18:58
• One of the first times I've seen a label used in a codegolf answer – Justin Sep 11 '17 at 22:45
• A: and continue A; are 13 bytes while {--c;break;} is 12. Would that instroduce some bug I don't see? – JollyJoker Sep 12 '17 at 7:58
• This might be worth a separate answer, but you can loop through the digits in base n by each digit being i%a and i/=a at each loop. You can avoid the set by using an int[] and checking that x[b]++<2 – JollyJoker Sep 12 '17 at 8:14
• java.util.Set<Character>‌​g=new java.util.HashSet<>(); can be import java.util.*; + Set g=new HashSet();; Long.toString can be a.toString; and Long.parseLong can be a.parseInt. – Kevin Cruijssen Sep 12 '17 at 12:54

Perl 6, 8684 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.

Abusing $; for fun and profit. Times out on inputs > 8. EDIT: -4 bytes by merging the two loops. Ruby, 80 65 bytes ->n{(1..n**n).count{|i|(d=i.digits n)-==d|d&&d.sum{|j|i%j}<1}} Try it online! Thanks to G B for -15 bytes. • This won't work for n>10 (because of "j.to_i") – G B Feb 25 at 9:42 • Good catch, too bad it times out well before that :) – Kirill L. Feb 25 at 9:44 • Anyway: you could call "digits" passing the base as argument and save a lot:  ->n{(1..n**n).count{|i|(d=i.digits n)-==d|d&&d.sum?{|j|i%j}<0}}` – G B Feb 25 at 9:58 • Indeed I absolutely missed that digits has this parameter. But I see you had posted this as a separate answer and then deleted. I'd say, go ahead, you beat me to it :) – Kirill L. Feb 25 at 10:25 • I think my answer is too similar, it's the same approach with a couple of shortcuts, mostly stolen code. – G B Feb 25 at 11:57 Japt-x, 25 19 bytes -6 bytes thanks to Shaggy pU õìU ËeDâ f myDìU Try it online! • – Shaggy Feb 26 at 10:52 • Or 19 bytes with the -x flag. – Shaggy Feb 26 at 10:54 • wow O_o i'm clearly terrible at golfing japt – ASCII-only Feb 26 at 11:11 • You're doing well so far :) It takes time to get to grips with a new language, figure out all its features, tricks & quirks. – Shaggy Feb 26 at 11:14 • @Shaggy but when you use a new language as often as I do it should be expected that I'd be closer to optimal than like 25% XD – ASCII-only Feb 26 at 11:50 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! • 184 bytes – ovs Sep 11 '17 at 19:03 • 174 bytes – ovs Sep 11 '17 at 19:06 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]==)x] Try it online! Works on TIO up to n=7 before timing out. 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.

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!