Últimos dígitos diferentes de zero de um fatorial na base

22

Você deve escrever um programa ou função que tenha fornecido três números inteiros positivos n b kcomo saída ou retorne os últimos kdígitos antes dos zeros à direita na brepresentação base de n!.

Exemplo

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

Entrada

  • 3 inteiros positivos n b konde 2 <= b <= 10.
  • A ordem dos números inteiros de entrada pode ser escolhida arbitrariamente.

Saída

  • Uma lista de dígitos retornados ou emitidos como um número inteiro ou lista inteira.
  • Os zeros à esquerda são opcionais.
  • Sua solução precisa resolver qualquer exemplo de caso de teste em menos de um minuto no meu computador (apenas testarei casos encerrados. Tenho um PC abaixo da média.).

Exemplos

Novos testes adicionados para verificar a exatidão dos envios. (Eles não fazem parte da regra de tempo de execução com menos de 1 minuto.)

Entrada => Saída (com a opção de omitir zeros à esquerda)

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

Isso é código-golfe, então a entrada mais curta vence.

randomra
fonte
1
menos de um minuto no meu computador é um pouco difícil de apontar se não soubermos detalhes específicos.
Dennis
1
Produziria 7 5 3"013" ou "13"?
Claudiu
1
@Claudiu baseado no 7 10 4caso de teste eu diria13
Maltysen
2
@Claudiu "Zeros à esquerda são opcionais." então ambas as versões estão corretas.
randomra
1
Devemos aceitar qualquer número inteiro positivo para nou k? Ou podemos limitá-los ao intervalo do tipo inteiro do idioma?
precisa saber é o seguinte

Respostas:

1

Dyalog APL , 23 bytes

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

Este programa funciona desde que o fatorial não exceda o limite de representação interna. No Dyalog APL, o limite pode ser aumentado por ⎕FR←1287.

Assume as variáveis n, b, e k foram definidos (por exemplo n b k←7 5 4), mas se você prefere deseja solicitar n , b , e k (nessa ordem), em seguida, substituir os três personagens com .

Adão
fonte
Cada caso de teste que joguei nele foi calculado em cerca de 11 microssegundos na minha máquina (M540).
Adám 20/01/16
7

Mathematica, 57 48 bytes

Economizou 9 bytes graças a @ 2012rcampion.

IntegerString[#!/#2^#!~IntegerExponent~#2,##2]&
alefalpha
fonte
Eu realmente nunca usei o mathematica, mas você não poderia trocar a ordem dos argumentos para fazer bprimeiro salvar 2 bytes?
FryAmTheEggman
@FryAmTheEggman Sou novo na comunidade de golfe, está trocando a ordem dos argumentos "kosher"?
precisa saber é o seguinte
1
Você pode realmente chegar a 47: IntegerString[#!#2^-#!~IntegerExponent~#2,##2]&(tanto isso e seu original são bastante rápido)
2012rcampion
O autor da pergunta escreveu: "A ordem dos números inteiros de entrada pode ser escolhida arbitrariamente". sob entrada, portanto, neste caso, é definitivamente muito bem
FryAmTheEggman
@ Fred Wow, parece que eu não li de perto o suficiente. No entanto, o SlotSequencetruque que usei no meu comentário funciona apenas com o pedido atual, portanto você não pode mais salvar.
usar o seguinte código
7

Python, 198 192 181 caracteres

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

É rápido o suficiente, ~ 23 segundos no maior exemplo. E nenhum fatorial embutido (estou olhando para você, Mathematica!).

Keith Randall
fonte
[2,3,2,5,3,7,2,3,5][b-2]pode ser int('232537235'[b-2])para salvar 3 bytes. [1,1,2,1,1,1,3,2,1][b-2]similarmente.
randomra
Para o último, uma tabela de pesquisa 111973>>2*(b-2)&3é ainda mais curta. É o mesmo número de bytes para o primeiro ( 90946202>>3*(b-2)&7).
Sp3000
nvm parece que você estava certo sobre a maior coisa dígitos
SP3000
Eu acredito que você pode salvar alguns bytes, tornando este um programa e não uma função.
FryAmTheEggman
6

Pitão, 26 35 bytes

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

Esta é uma função de 3 argumentos, número, base, número de dígitos.

Demonstração.

O caso de teste mais lento, o final, leva 15 segundos na minha máquina.

isaacg
fonte
@ Sp3000 Adicionei uma correção que considero suficiente.
Isaacg
2

PARI / GP, 43 bytes

A velocidade de negociação do espaço produz este algoritmo simples:

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

Cada um dos casos de teste é executado em menos de um segundo na minha máquina.

Charles
fonte
2

Mathematica - 48 bytes

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

Ungolfed:

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*)
]

Exemplo:

#!~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}} *)

Para os casos maiores, o fator limitante não está gerando os dígitos:

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

A correspondência de padrões parece ser O(n^2), fazendo com que os dois últimos casos de teste ultrapassem a marca de um minuto.

2012rcampion
fonte
2

Bash / coreutils / dc, 60 bytes

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

Usa o dcscript da minha resposta para Encontrar o fatorial , emitindo na base $2, com sedpara aparar zeros tailà direita e selecionar os últimos $3dígitos.

Toby Speight
fonte
Eu tenho que admitir que é extremamente lento com o testcase de base 2 de 40 bits. Tentei aliviar o trabalho de sed usando revpara reduzir recuo, mas é dcque está comendo a CPU ...
Toby Speight
2

Haskell, 111 109 bytes

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

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

Demora cerca de 8 segundos f 359221 2 40no meu laptop de 4 anos.

Como funciona: dobre a multiplicação ( *) na lista [1..n]. Converta todos os resultados intermediários em base bcomo uma lista de dígitos (menos significativos primeiro), retire os zeros à esquerda, pegue os primeiros kdígitos e converta na base 10 novamente. Por fim, converta bnovamente na base , mas primeiro com o dígito mais significativo.

nimi
fonte
você teve a idéia em minha mente, que eu estava interpretando-a usando Matlab, que coincidende: D
Abr001am
1

Python 3, 146 bytes

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]):])

Não tenho certeza de que todos os casos de teste serão executados com rapidez suficiente - os maiores são muito lentos (pois estão repetindo o número).

Experimente online aqui (mas tenha cuidado).

Tim
fonte
1

Java, 303 299 296 bytes

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

No meu computador, isso fica em média um pouco menos de um terço de segundo no 359221 2 40testcase. Recebe entrada por meio de argumentos de linha de comando.

SuperJedi224
fonte
1

bc, 75 bytes

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

Isso usa algumas extensões GNU para reduzir o tamanho do código; um equivalente em conformidade com POSIX pesa 80 bytes:

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

Para manter os tempos de execução razoáveis, recortamos os zeros à direita ( while(!x%b)x/=b) e truncamos para os kdígitos finais ( x%=b^k) à medida que calculamos o fatorial ( for(x=1;n;)x*=n--).

Programa de teste:

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

O tempo de execução do conjunto completo de testes é de aproximadamente 4 segundos na minha estação de trabalho vintage de 2006.

Toby Speight
fonte
Este é o meu primeiro bcprograma (golfe ou não), de modo que qualquer dicas são especialmente bem-vindas ...
Toby Speight
0

PHP, 80 bytes

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

Usado como f(359221,2,40)para o último caso de teste. É executado sem problemas em todos os casos de teste.

Tente aqui!

Paul Picard
fonte