Digit bukan nol terakhir dari sebuah faktorial di Base

22

Anda harus menulis sebuah program atau fungsi yang memberikan tiga bilangan bulat positif n b ksebagai input output atau mengembalikan kdigit terakhir sebelum nol trailing di brepresentasi dasar n!.

Contoh

n=7 b=5 k=4
factorial(n) is 5040
5040 is 130130 in base 5
the last 4 digits of 130130 before the trailing zeros are 3013
the output is 3013

Memasukkan

  • 3 bilangan bulat positif di n b kmana 2 <= b <= 10.
  • Urutan bilangan bulat input dapat dipilih secara sewenang-wenang.

Keluaran

  • Daftar digit yang dikembalikan atau dikeluarkan sebagai integer atau daftar integer.
  • Angka nol di depan adalah opsional.
  • Solusi Anda harus menyelesaikan contoh uji kasus di bawah satu menit di komputer saya (saya hanya akan menguji kasus tutup. Saya memiliki PC di bawah rata-rata.).

Contohnya

Tes baru ditambahkan untuk memeriksa kebenaran pengiriman. (Mereka bukan bagian dari aturan runtime di bawah 1 menit.)

Input => Output (dengan pilihan menghilangkan nol terkemuka)

3 10 1  =>  6

7 5 4  =>  3013

3 2 3  =>  11

6 2 10  =>  101101

9 9 6  =>  6127

7 10 4  =>  504

758 9 19  =>  6645002302217537863

158596 8 20  =>  37212476700442254614

359221 2 40  =>  1101111111001100010101100000110001110001

New tests:
----------

9 6 3  =>  144

10 6 3  =>  544

Ini adalah kode-golf, sehingga entri terpendek menang.

randomra
sumber
1
kurang dari satu menit di komputer saya agak sulit untuk dituju jika kita tidak tahu secara spesifik.
Dennis
1
Apakah 7 5 3menghasilkan "013" atau "13"?
Claudiu
1
@Cudiudiu berdasarkan pada 7 10 4test case yang akan saya katakan13
Maltysen
2
@Claudiu "Nol utama adalah opsional." jadi kedua versi sudah benar.
randomra
1
Harus kita menerima setiap bilangan bulat positif untuk natau k? Atau bisakah kita membatasi mereka pada rentang tipe integer bahasa?
Toby Speight

Jawaban:

1

Dyalog APL , 23 byte

⌽k↑⌽{⍵↓⍨-⊥⍨0=⍵}b⊥⍣¯1⊢!n

Program ini berfungsi selama faktorial tidak melebihi batas representasi internal. Di Dyalog APL, batas dapat dinaikkan oleh ⎕FR←1287.

Asumsikan variabel n, b, dan k telah disetel (mis. n b k←7 5 4), Tetapi jika Anda lebih suka meminta n , b , dan k (dalam urutan itu) maka ganti ketiga karakter dengan .

Adm
sumber
Setiap test case yang saya lemparkan dihitung sekitar 11 mikrodetik pada mesin saya (M540).
Adám
7

Mathematica, 57 48 byte

Disimpan 9 byte berkat @ 2012rcampion.

IntegerString[#!/#2^#!~IntegerExponent~#2,##2]&
alephalpha
sumber
Saya tidak pernah benar-benar menggunakan Mathematica, tetapi tidak bisakah Anda menukar urutan argumen dengan membuat bterlebih dahulu untuk menghemat 2 byte?
FryAmTheEggman
@FryAmTheEggman Saya baru mengenal komunitas golf, apakah bertukar argumen menjadi "halal"?
Arcampion
1
Anda benar-benar dapat mencapai 47: IntegerString[#!#2^-#!~IntegerExponent~#2,##2]&(baik ini dan sumber asli Anda cukup cepat)
2012rcampion
Penanya menulis: "Urutan bilangan bulat input dapat dipilih secara sewenang-wenang." di bawah masukan, jadi dalam hal ini jelas baik
FryAmTheEggman
@Fry Wow, sepertinya saya tidak cukup membaca. Namun, SlotSequencetrik yang saya gunakan dalam komentar saya hanya berfungsi dengan pesanan saat ini, sehingga Anda tidak dapat menyimpan lagi.
Arcampion
7

Python, 198 192 181 karakter

def F(n,b,k):
 p=5820556928/8**b%8;z=0;e=f=x=1
 while n/p**e:z+=n/p**e;e+=1
 z/=1791568/4**b%4;B=b**(z+k)
 while x<=n:f=f*x%B;x+=1
 s='';f/=b**z
 while f:s=str(f%b)+s;f/=b
 return s

Cukup cepat, ~ 23 detik pada contoh terbesar. Dan tidak ada faktorial bawaan (Saya melihat Anda, Mathematica!).

Keith Randall
sumber
[2,3,2,5,3,7,2,3,5][b-2]bisa int('232537235'[b-2])untuk menghemat 3 byte. [1,1,2,1,1,1,3,2,1][b-2]demikian pula.
randomra
Untuk yang terakhir, tabel pencarian 111973>>2*(b-2)&3bahkan lebih pendek. Ini adalah jumlah byte yang sama untuk yang sebelumnya ( 90946202>>3*(b-2)&7).
Sp3000
nvm sepertinya Anda benar tentang angka yang lebih tinggi
Sp3000
Saya percaya Anda dapat menyimpan beberapa byte dengan membuat program ini dan bukan fungsi.
FryAmTheEggman
6

Pyth, 26 35 byte

M?G%GHg/GHH.N>ju%g*GhHT^T+YslNN1T_Y

Ini adalah fungsi dari 3 argumen, angka, basis, jumlah digit.

Demonstrasi.

Kasing uji paling lambat, yang terakhir, membutuhkan waktu 15 detik pada mesin saya.

isaacg
sumber
@ Sp3000 saya menambahkan perbaikan yang saya pikir sudah cukup.
isaacg
2

PARI / GP, 43 byte

Kecepatan perdagangan untuk ruang menghasilkan algoritma langsung ini:

(n,b,k)->digits(n!/b^valuation(n!,b)%b^k,b)

Masing-masing kotak uji beroperasi dalam waktu kurang dari satu detik di mesin saya.

Charles
sumber
2

Mathematica - 48 byte

#!~IntegerDigits~#2/.{l__,0...}:>{l}~PadLeft~#3&

Tidak Disatukan:

Function[{n, b, k},
  IntegerDigits[n!, b] (* list of the base-b digits in n! *)
  /. {l__, 0...} (* match a sequence of elements l and some number of zeros*)
                 (* lucky for me, __ defaults to match the shortest number *)
     :> PadLeft[List[l], k] (* pad l to be k elements long with zeros on the left *)
                            (* this truncates the list if it is too long*)
]

Contoh:

#!~IntegerDigits~#2/.{l__,0...}:>{l}~PadLeft~#3 &
%[758, 9, 19] // Timing

(* {0.031250, {6, 6, 4, 5, 0, 0, 2, 3, 0, 2, 2, 1, 7, 5, 3, 7, 8, 6, 3}} *)

Untuk kasus terbesar, faktor pembatas tidak menghasilkan digit:

Length@IntegerDigits[359221!, 2] // Timing
(* {0.109375, 6111013} 6.1M digits in 100 ms *)

Pencocokan pola tampaknya O(n^2), menyebabkan dua kasus uji terakhir melampaui batas satu menit.

2012 Arcampion
sumber
2

Bash / coreutils / dc, 60 byte

dc<<<"1 `seq -f%g* $1`$2op"|sed -r s/0+$//|tail -c$(($3+1))

Menggunakan dcskrip dari jawaban saya untuk Find the Factorial , menghasilkan basis $2, dengan sedmemotong tailgaris nol dan untuk memilih $3digit terakhir .

Toby Speight
sumber
Saya harus mengakui bahwa ini sangat lambat dengan testcase 40-bit base-2. Saya mencoba meredakan pekerjaan sed yang digunakan revuntuk mengurangi backtracking, tapi itu dcyang memakan CPU ...
Toby Speight
2

Haskell, 111 109 byte

import Data.Digits
f n b k=digits b$foldl(((unDigits b.reverse.take k.snd.span(<1).digitsRev b).).(*))1[1..n]

Penggunaan: f 158596 8 20->[3,7,2,1,2,4,7,6,7,0,0,4,4,2,2,5,4,6,1,4]

Memakan waktu sekitar 8 detik untuk f 359221 2 40laptop saya yang berumur 4 tahun.

Cara kerjanya: lipat multiplikasi ( *) ke dalam daftar [1..n]. Konversikan setiap hasil antara menjadi basis bsebagai daftar angka (paling tidak penting terlebih dahulu), lepaskan nol di depan, lalu ambil kangka pertama dan konversikan ke basis 10 lagi. Akhirnya konversikan ke basis blagi, tetapi dengan digit paling signifikan terlebih dahulu.

nimi
sumber
Anda punya ide di benak saya, bahwa saya menafsirkannya menggunakan matlab, sungguh kebetulan: D
Abr001am
1

Python 3, 146 byte

import math
i,f=input(),int
n=i.split()
e=math.factorial(f(n[0]))
d=''
while e>0:
 d=str((e%f(n[1])))+d;e=e//f(n[1])
print(d.strip('0')[-f(n[2]):])

Saya tidak yakin semua test case akan berjalan cukup cepat - yang lebih besar sangat lambat (karena perulangan melalui angka).

Cobalah online di sini (tapi hati-hati).

Tim
sumber
1

Java, 303 299 296 byte

import java.math.*;interface R{static void main(String[]a){BigInteger c=new BigInteger(a[1]),b=c.valueOf(1);for(int i=new Integer(a[0]);i>0;i--){b=b.multiply(b.valueOf(i));while(b.mod(c).equals(b.ZERO))b=b.divide(c);b=b.mod(c.pow(new Integer(a[2])));}System.out.print(b.toString(c.intValue()));}}

Di komputer saya, ini rata-rata sedikit di bawah sepertiga detik di 359221 2 40testcase. Mengambil input melalui argumen baris perintah.

SuperJedi224
sumber
1

bc, 75 byte

define void f(n,b,k){
obase=b
for(x=1;n;x%=b^k){
x*=n--
while(!x%b)x/=b}
x}

Ini menggunakan beberapa ekstensi GNU untuk mengurangi ukuran kode; setara dengan POSIX-sesuai memiliki 80 byte:

define f(n,b,k){
obase=b
for(x=1;n;x%=b^k){
x*=n--
while(x%b==0)x/=b}
return(x)}

Agar waktu berlari masuk akal, kami memotong nol trailing ( while(!x%b)x/=b) dan memotong ke kangka akhir ( x%=b^k) saat kami menghitung faktorial ( for(x=1;n;)x*=n--).

Program uji:

f(3, 10, 1)
f(7, 5, 4)
f(3, 2, 3)
f(6, 2, 10)
f(9, 9, 6)
f(7, 10, 4)
f(758, 9, 19)
f(158596, 8, 20)
f(359221, 2, 40)
f(9, 6, 3)
f(10, 6, 3)
quit

Runtime dari test suite lengkap kira-kira 4¼ detik pada workstation 2006-vintage saya.

Toby Speight
sumber
Ini adalah bcprogram pertama saya (golf atau tidak), jadi setiap tips sangat disambut ...
Toby Speight
0

PHP, 80 byte

function f($a,$b,$c){echo substr(rtrim(gmp_strval(gmp_fact($a),$b),"0"),-1*$c);}

Digunakan sebagai f(359221,2,40) kasus uji terakhir. Berjalan cukup lancar untuk semua test case.

Coba di sini!

Paul Picard
sumber