Últimos dígitos distintos de cero de un factorial en base

22

Debe escribir un programa o función que proporcione tres enteros positivos n b kcomo salidas de entrada o devuelva los últimos kdígitos antes de los ceros finales en la brepresentación base de n!.

Ejemplo

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 enteros positivos n b kdonde 2 <= b <= 10.
  • El orden de los enteros de entrada se puede elegir arbitrariamente.

Salida

  • Una lista de dígitos devueltos o generados como un entero o una lista de enteros.
  • Los ceros iniciales son opcionales.
  • Su solución tiene que resolver cualquier caso de prueba de ejemplo en menos de un minuto en mi computadora (solo probaré casos cercanos. Tengo una PC por debajo del promedio).

Ejemplos

Nuevas pruebas agregadas para verificar la exactitud de los envíos. (No forman parte de la regla de tiempo de ejecución de menos de 1 minuto).

Entrada => Salida (con la opción de omitir los ceros iniciales)

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

Este es el código de golf, por lo que gana la entrada más corta.

randomra
fuente
1
menos de un minuto en mi computadora es un poco difícil de apuntar si no conocemos ningún detalle.
Dennis
1
¿ 7 5 3Saldría "013" o "13"?
Claudiu
1
@Claudiu basado en el 7 10 4caso de prueba, diría13
Maltysen
2
@Claudiu "Los ceros iniciales son opcionales". entonces ambas versiones son correctas.
randomra
1
¿Debemos aceptar algún número entero positivo para no k? ¿O podemos limitarlos al rango del tipo entero del idioma?
Toby Speight

Respuestas:

1

Dyalog APL , 23 bytes

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

Este programa funciona siempre que el factorial no exceda el límite de representación interna. En Dyalog APL, el límite puede elevarse ⎕FR←1287.

Asume que las variables n, b y k se han establecido (por ejemplo n b k←7 5 4), pero si prefiere solicitar n , b y k (en ese orden), reemplace los tres caracteres con .

Adán
fuente
Cada caso de prueba que lancé fue calculado en aproximadamente 11 microsegundos en mi máquina (M540).
Adám
7

Mathematica, 57 48 bytes

Guardado 9 bytes gracias a @ 2012rcampion.

IntegerString[#!/#2^#!~IntegerExponent~#2,##2]&
alephalpha
fuente
Realmente nunca he usado Mathica, pero ¿no podrías cambiar el orden de los argumentos bpara guardar primero 2 bytes?
FryAmTheEggman
@FryAmTheEggman Soy nuevo en la comunidad de golf, ¿está cambiando el orden de argumentos "kosher"?
2012 Arcampion
1
De hecho, puedes llegar a 47: IntegerString[#!#2^-#!~IntegerExponent~#2,##2]&(tanto este como tu original son bastante rápidos)
2012 Arcampion
El autor de la pregunta escribió: "El orden de los enteros de entrada se puede elegir arbitrariamente". bajo entrada, así que en este caso definitivamente está bien
FryAmTheEggman
@Fry Wow, parece que no leí lo suficiente. Sin embargo, el SlotSequencetruco que utilicé en mi comentario solo funciona con el pedido actual, por lo que no podría guardar más.
Campamento 2012
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

Es lo suficientemente rápido, ~ 23 segundos en el mejor ejemplo. Y sin factorial incorporado (¡te estoy mirando, Mathematica!).

Keith Randall
fuente
[2,3,2,5,3,7,2,3,5][b-2]podría ser int('232537235'[b-2])guardar 3 bytes. [1,1,2,1,1,1,3,2,1][b-2]similar.
randomra
Para este último, una tabla de búsqueda 111973>>2*(b-2)&3es aún más corta. Sin embargo, es el mismo número de bytes para el primero ( 90946202>>3*(b-2)&7).
Sp3000
nvm parece que tenías razón sobre lo de los dígitos más altos
Sp3000
Creo que puede guardar algunos bytes haciendo de este un programa y no una función.
FryAmTheEggman
6

Pyth, 26 35 bytes

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

Esta es una función de 3 argumentos, número, base, número de dígitos.

Demostración.

El caso de prueba más lento, el último, toma 15 segundos en mi máquina.

isaacg
fuente
@ Sp3000 Agregué una solución que creo que debería ser suficiente.
isaacg
2

PARI / GP, 43 bytes

La velocidad de intercambio por espacio produce este algoritmo sencillo:

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

Cada uno de los casos de prueba se ejecuta en menos de un segundo en mi máquina.

Charles
fuente
2

Mathematica - 48 bytes

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

Sin golf:

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

Ejemplo:

#!~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 los casos más grandes, el factor limitante no es generar los dígitos:

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

La coincidencia de patrones parece ser O(n^2), lo que hace que los dos últimos casos de prueba superen la marca de un minuto.

Campeonato 2012
fuente
2

Bash / coreutils / dc, 60 bytes

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

Utiliza la dcsecuencia de comandos de mi respuesta para encontrar el factorial , que sale en base $2, sedpara recortar ceros finales y tailseleccionar los últimos $3dígitos.

Toby Speight
fuente
Tengo que admitir que es extremadamente lento con el caso de prueba de base 2 de 40 bits. Intenté facilitar el trabajo de sed usando revpara reducir el retroceso, pero es dceso lo que se está comiendo la 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]

Toma alrededor de 8 segundos para f 359221 2 40mi computadora portátil de 4 años.

Cómo funciona: dobla la multiplicación ( *) en la lista [1..n]. Convierta cada resultado intermedio a base bcomo una lista de dígitos (menos significativos primero), elimine los ceros a la izquierda, luego tome los primeros kdígitos y vuelva a convertir a base 10. Finalmente convierta a base bnuevamente, pero con el dígito más significativo primero.

nimi
fuente
tenías la idea en mi mente, que la estaba interpretando usando matlab, qué coincidencia: 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]):])

No estoy seguro de que todos los casos de prueba se ejecuten lo suficientemente rápido: los más grandes son muy lentos (ya que está recorriendo el número).

Pruébelo en línea aquí (pero tenga cuidado).

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

En mi computadora, esto promedia un poco menos de un tercio de segundo en el caso de 359221 2 40prueba. Toma entrada a través de argumentos de línea de comando.

SuperJedi224
fuente
1

a. C., 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}

Esto usa algunas extensiones de GNU para reducir el tamaño del código; un equivalente compatible con 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 mantener los tiempos de ejecución razonables, recortamos los ceros finales ( while(!x%b)x/=b) y truncamos a los kdígitos finales ( x%=b^k) mientras calculamos el factorial ( for(x=1;n;)x*=n--).

Programa de prueba:

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

El tiempo de ejecución del conjunto de pruebas completo es de aproximadamente 4¼ segundos en mi estación de trabajo vintage 2006.

Toby Speight
fuente
Este es mi primer bcprograma (golf o no), por lo que cualquier consejo es especialmente bienvenido ...
Toby Speight
0

PHP, 80 bytes

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

Utilizado como f(359221,2,40)para el último caso de prueba. Funciona bastante bien para todos los casos de prueba.

Intenta aquí !

Paul Picard
fuente