19
\$\begingroup\$

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.

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

14 Answers 14

8
\$\begingroup\$

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

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

Jelly, 15 bytes

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

Try it online!

Complexity O(nn).

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

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.

\$\endgroup\$
  • \$\begingroup\$ -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;} \$\endgroup\$ – Herman L Sep 11 '17 at 18:58
  • \$\begingroup\$ One of the first times I've seen a label used in a codegolf answer \$\endgroup\$ – Justin Sep 11 '17 at 22:45
  • \$\begingroup\$ A: and continue A; are 13 bytes while {--c;break;} is 12. Would that instroduce some bug I don't see? \$\endgroup\$ – JollyJoker Sep 12 '17 at 7:58
  • \$\begingroup\$ 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 \$\endgroup\$ – JollyJoker Sep 12 '17 at 8:14
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Sep 12 '17 at 12:54
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you can save 2 bytes by doing .all instead of all $_. \$\endgroup\$ – Ramillies Sep 11 '17 at 20:58
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 82 79 76 bytes

Count[Join@@Permutations/@Subsets@Range[#-1],x_/;x==x~FromDigits~#~GCD~x]-1&
\$\endgroup\$
  • \$\begingroup\$ How do you pass a number into this? (sorry, Mathematica is new to me) \$\endgroup\$ – Beta Decay Sep 11 '17 at 16:12
  • \$\begingroup\$ Paste the function (e.g., to Wolfram sandbox), and then put [<parameter>] after that. With parameter being a number. \$\endgroup\$ – user202729 Sep 11 '17 at 16:13
  • \$\begingroup\$ Can you add a TIO, or equivalent? \$\endgroup\$ – Shaggy Sep 11 '17 at 16:21
  • 1
    \$\begingroup\$ @Shaggy wolframcloud.com/objects/025b270d-d293-4459-a8f4-2cfb7e769f21 \$\endgroup\$ – Beta Decay Sep 11 '17 at 16:24
  • 1
    \$\begingroup\$ Are f(5) and f(6) both really 10? That's odd... \$\endgroup\$ – Magic Octopus Urn Sep 11 '17 at 16:25
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I'm pretty sure a different approach can save more bytes, but in your current solution ε0KÙ} can be 0м€Ù to save a byte. \$\endgroup\$ – Kevin Cruijssen Feb 25 at 10:44
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This won't work for n>10 (because of "j.to_i") \$\endgroup\$ – G B Feb 25 at 9:42
  • \$\begingroup\$ Good catch, too bad it times out well before that :) \$\endgroup\$ – Kirill L. Feb 25 at 9:44
  • \$\begingroup\$ Anyway: you could call "digits" passing the base as argument and save a lot: ` ->n{(1..n**n).count{|i|(d=i.digits n)-[0]==d|d&&d.sum?{|j|i%j}<0}}` \$\endgroup\$ – G B Feb 25 at 9:58
  • \$\begingroup\$ 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 :) \$\endgroup\$ – Kirill L. Feb 25 at 10:25
  • \$\begingroup\$ I think my answer is too similar, it's the same approach with a couple of shortcuts, mostly stolen code. \$\endgroup\$ – G B Feb 25 at 11:57
1
\$\begingroup\$

Japt -x, 25 19 bytes

-6 bytes thanks to Shaggy

pU õìU ËeDâ f myDìU

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 20 bytes? \$\endgroup\$ – Shaggy Feb 26 at 10:52
  • \$\begingroup\$ Or 19 bytes with the -x flag. \$\endgroup\$ – Shaggy Feb 26 at 10:54
  • \$\begingroup\$ wow O_o i'm clearly terrible at golfing japt \$\endgroup\$ – ASCII-only Feb 26 at 11:11
  • \$\begingroup\$ You're doing well so far :) It takes time to get to grips with a new language, figure out all its features, tricks & quirks. \$\endgroup\$ – Shaggy Feb 26 at 11:14
  • \$\begingroup\$ @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 \$\endgroup\$ – ASCII-only Feb 26 at 11:50
0
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 184 bytes \$\endgroup\$ – ovs Sep 11 '17 at 19:03
  • \$\begingroup\$ 174 bytes \$\endgroup\$ – ovs Sep 11 '17 at 19:06
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.