Derniers chiffres non nuls d'une factorielle dans la base

22

Vous devez écrire un programme ou une fonction qui a donné trois entiers positifs n b kcomme sorties d'entrée ou renvoie les derniers kchiffres avant les zéros de fin dans la breprésentation de base de n!.

Exemple

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

Contribution

  • 3 entiers positifs n b k2 <= b <= 10.
  • L'ordre des entiers d'entrée peut être choisi arbitrairement.

Sortie

  • Une liste de chiffres retournés ou sortis sous forme de nombre entier ou de liste entière.
  • Les zéros non significatifs sont facultatifs.
  • Votre solution doit résoudre tout exemple de cas de test en moins d'une minute sur mon ordinateur (je ne testerai que les cas fermés. J'ai un PC inférieur à la moyenne.).

Exemples

Nouveaux tests ajoutés pour vérifier l'exactitude des soumissions. (Ils ne font pas partie de la règle d'exécution de moins d'une minute.)

Entrée => Sortie (avec le choix d'omettre les zéros non significatifs)

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

C'est le golf de code, donc l'entrée la plus courte gagne.

randomra
la source
1
moins d'une minute sur mon ordinateur est un peu difficile à viser si nous ne connaissons aucun détail.
Dennis
1
Est-ce que 7 5 3"013" ou "13" serait produit
Claudiu
1
@Claudiu basé sur le 7 10 4cas de test, je dirais13
Maltysen
2
@Claudiu "Les zéros non significatifs sont facultatifs." donc les deux versions sont correctes.
randomra
1
Doit-on accepter un entier positif pour nou k? Ou peut-on les limiter à la plage du type entier du langage?
Toby Speight

Réponses:

1

Dyalog APL , 23 octets

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

Ce programme fonctionne tant que la factorielle ne dépasse pas la limite de représentation interne. Dans Dyalog APL, la limite peut être augmentée de ⎕FR←1287.

Suppose que les variables n, b et k ont ​​été définies (par exemple n b k←7 5 4), mais si vous souhaitez plutôt demander n , b et k (dans cet ordre), remplacez les trois caractères par .

Adam
la source
Chaque test que j'ai lancé a été calculé en environ 11 microsecondes sur ma machine (M540).
Adám
7

Mathematica, 57 48 octets

9 octets enregistrés grâce à @ 2012rcampion.

IntegerString[#!/#2^#!~IntegerExponent~#2,##2]&
alephalpha
la source
Je n'ai jamais vraiment utilisé mathématique, mais ne pourriez-vous pas permuter l'ordre des arguments à faire en bpremier pour économiser 2 octets?
FryAmTheEggman
@FryAmTheEggman Je suis nouveau dans la communauté du golf, l'échange d'arguments est-il "casher"?
2012rcampion
1
Vous pouvez réellement atteindre 47: IntegerString[#!#2^-#!~IntegerExponent~#2,##2]&(ceci et votre original sont assez rapides)
2012rcampion
Le demandeur a écrit: "L'ordre des entiers d'entrée peut être choisi arbitrairement." en entrée, donc dans ce cas, c'est très bien
FryAmTheEggman
@Fry Wow, on dirait que je n'ai pas lu assez attentivement. Cependant, l' SlotSequenceastuce que j'ai utilisée dans mon commentaire ne fonctionne qu'avec la commande actuelle, vous ne pouvez donc plus enregistrer.
2012rcampion
7

Python, 198 192 181 181 caractères

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

C'est assez rapide, ~ 23 secondes sur le plus grand exemple. Et pas de facteur intégré (je vous regarde, Mathematica!).

Keith Randall
la source
[2,3,2,5,3,7,2,3,5][b-2]pourrait être int('232537235'[b-2])d'économiser 3 octets. [1,1,2,1,1,1,3,2,1][b-2]De même.
randomra
Pour ce dernier, une table de correspondance 111973>>2*(b-2)&3est encore plus courte. C'est le même nombre d'octets pour le premier cependant ( 90946202>>3*(b-2)&7).
Sp3000
nvm semble que vous aviez raison à propos des chiffres supérieurs
Sp3000
Je pense que vous pouvez économiser quelques octets en faisant de ce programme un programme et non une fonction.
FryAmTheEggman
6

Pyth, 26 35 octets

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

C'est une fonction de 3 arguments, nombre, base, nombre de chiffres.

Manifestation.

Le cas de test le plus lent, le dernier, prend 15 secondes sur ma machine.

isaacg
la source
@ Sp3000 J'ai ajouté un correctif qui devrait être suffisant.
isaacg
2

PARI / GP, 43 octets

La vitesse de négociation pour l'espace donne cet algorithme simple:

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

Chacun des cas de test s'exécute en moins d'une seconde sur ma machine.

Charles
la source
2

Mathematica - 48 octets

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

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

Exemple:

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

Pour les cas les plus importants, le facteur limitant ne génère pas les chiffres:

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

La correspondance des motifs semble l'être O(n^2), ce qui fait que les deux derniers cas de test dépassent largement la minute.

2012rcampion
la source
2

Bash / coreutils / dc, 60 octets

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

Utilise le dcscript de ma réponse pour trouver le factoriel , sortie en base $2, avec sedpour couper les zéros de fin et tailpour sélectionner les derniers $3chiffres.

Toby Speight
la source
Je dois admettre que c'est extrêmement lent avec le boîtier de test 40 bits base-2. J'ai essayé d'alléger le travail de sed en utilisant revpour réduire le retour en arrière, mais c'est ça dcqui mange le CPU ...
Toby Speight
2

Haskell, 111 109 octets

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

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

Prend environ 8 secondes pour f 359221 2 40mon ordinateur portable de 4 ans.

Comment ça marche: pliez la multiplication ( *) dans la liste [1..n]. Convertissez chaque résultat intermédiaire en base bsous la forme d'une liste de chiffres (le moins significatif en premier), supprimez les zéros non significatifs, puis prenez les premiers kchiffres et convertissez à nouveau en base 10. Enfin, convertissez à bnouveau en base , mais avec le chiffre le plus significatif en premier.

nimi
la source
vous aviez l'idée dans mon esprit, que je l'interprétais en utilisant matlab, quelle coïncidence: D
Abr001am
1

Python 3, 146 octets

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

Je ne suis pas sûr que les cas de test fonctionneront tous assez rapidement - les plus grands sont très lents (car ils parcourent le nombre).

Essayez-le en ligne ici (mais soyez prudent).

Tim
la source
1

Java, 303 299 296 octets

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

Sur mon ordinateur, cela fait en moyenne un peu moins d'un tiers de seconde sur le 359221 2 40boîtier de test. Prend des entrées via des arguments de ligne de commande.

SuperJedi224
la source
1

bc, 75 octets

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

Cela utilise certaines extensions GNU pour réduire la taille du code; un équivalent conforme à POSIX pèse 80 octets:

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

Pour garder les temps d'exécution raisonnables, nous coupons les zéros de fin ( while(!x%b)x/=b) et tronquons aux derniers kchiffres ( x%=b^k) lorsque nous calculons le factoriel ( for(x=1;n;)x*=n--).

Programme de test:

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

L'autonomie de la suite de tests complète est d'environ 4¼ secondes sur mon poste de travail de 2006.

Toby Speight
la source
C'est mon tout premier bcprogramme (golf ou pas), donc tous les conseils sont particulièrement les bienvenus ...
Toby Speight
0

PHP, 80 octets

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

Utilisé comme f(359221,2,40)pour le dernier cas de test. Fonctionne assez bien pour tous les cas de test.

Essayez ici!

Paul Picard
la source