Tantangan

Diberikan bilangan bulat, nsebagai input di mana 36 >= n >= 2, menampilkan berapa banyak nomor Lynch-Bell yang ada di pangkalan n.

Output harus dalam basis 10.

Nomor Lynch-Bell

Angka adalah nomor Lynch-Bell jika:

• Semua digitnya unik (tidak ada pengulangan digit)
• Jumlahnya dapat dibagi dengan masing-masing digit
• Ini tidak mengandung nol sebagai salah satu digitnya

Karena, semua digit harus unik, dan Anda memiliki satu set nomor digit tunggal di setiap basis, ada sejumlah terbatas nomor Lynch-Bell.

Sebagai contoh, dalam basis 2 hanya ada satu nomor Lynch-Bell 1, karena semua angka lainnya dapat mengulangi angka atau mengandung angka 0.

Contohnya

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

Mathematica Online kehabisan memori di atas basis 10. Anda dapat menggunakan kode berikut untuk menghasilkan sendiri:

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

Kemenangan

Kode terpendek dalam byte menang.

Jelly , 13 byte

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

Cobalah online!

Lain O (n ⁿ ) solusi.

Penjelasan

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

Jelly , 15 byte

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

Cobalah online!

Kompleksitas .O(nn)

Java, 222 212 190 byte

-10 byte terima kasih kepada Herman

-22 byte terima kasih kepada 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;}

Tidak Disatukan:

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

Cobalah online!

Sangat lambat untuk jumlah besar.

Perl 6 , 86 84 77 byte

-2 byte terima kasih kepada Ramillies

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

Cobalah online!

Berfungsi untuk n = 8 pada TIO.

Sebenarnya , 24 byte

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

Cobalah online!

Penjelasan

Program ini terdiri dari dua bagian utama: generasi permutasi, dan tes Lynch-Bell. Jadi, penjelasan ini akan melihat masing-masing bagian secara terpisah, untuk kejelasan yang lebih besar.

Menghasilkan Permutasi

Input: n(bilangan bulat di[2, 36] )

Output: semua permutasi parsial dan total [1, n-1](urutan yang berisi nilai-nilai dari [1, n-1]tanpa pengulangan yang panjangnya [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

Tes Lynch-Bell

Input: daftar nbilangan bulat basis , direpresentasikan sebagai daftar basis-n angka

Output: jumlah nomor Lynch-Bell di pangkalan 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 byte

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

05AB1E , 22 byte

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

Cobalah online!

O_O juga wajah saya ketika ini akhirnya berhasil.

<ÝIBJ0Kæ¦Ù€œ˜ lebih cepat daripada cara yang saya gunakan untuk menghasilkan angka dalam jawaban aktual tetapi secara acak berhenti bekerja untuk apa pun yang lebih besar dari 7 (tanpa alasan yang jelas?)

Penjelasan

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 byte (75 + -p)

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

Menyalahgunakan $; untuk kesenangan dan keuntungan. Waktu kehabisan input> 8.

EDIT: -4 bytes dengan menggabungkan dua loop.

Ruby , 80 65 byte

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

Cobalah online!

Berkat GB untuk -15 byte.

Japt -x , 25 19 byte

-6 byte terima kasih kepada Shaggy

pU õìU ËeDâ f myDìU

Cobalah online!

Python 3 , 204 174 byte

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*

Cobalah online!

Untuk setiap permutasi dari setiap elemen rentang set daya (1, n) (tanpa nol, unik), konversi ke string numerik ke basis n. Jumlahkan semua yang dapat dibagi oleh setiap digit, kurangi 1 karena powerset menghasilkan set kosong.

-30 byte terima kasih kepada @ovs!

Haskell , 117 byte

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]

Cobalah online! Bekerja pada TIO hingga n=7sebelum waktu habis.

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

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

Cobalah online!

Itu babi. Tidak yakin apakah itu akan melakukan lebih dari basis 8 pada TIO tanpa batas waktu.

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

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

Telusuri semua angka dari 0 hingga ulong.MaxValue, dan pilih yang merupakan nomor Lynch-Bell di pangkalan yang ditentukan. Dibutuhkan selamanya untuk menjalankan, bahkan untuk 2, meskipun jika Anda mengatur~0UL bagian dalam loop untuk sesuatu yang lebih kecil, Anda bisa mendapatkan output untuk input hingga 7 dalam satu menit pada TIO.

Cobalah online!