22
\$\begingroup\$

You should write a program or function which given three positive integers n b k as input outputs or returns the last k digits before the trailing zeros in the base b representation of n!.

Example

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

Input

  • 3 positive integers n b k where 2 <= b <= 10.
  • The order of the input integers can be chosen arbitrarily.

Output

  • A list of digits returned or outputted as an integer or integer list.
  • Leading zeros are optional.
  • Your solution has to solve any example test case under a minute on my computer (I will only test close cases. I have a below-average PC.).

Examples

New tests added to check correctness of submissions. (They are not part of the under 1 minute runtime rule.)

Input => Output (with the choice of omitting leading zeros)

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

This is code-golf, so the shortest entry wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ under a minute on my computer is a little difficult to aim for if we don't know any specifics. \$\endgroup\$ – Dennis Apr 30 '15 at 17:04
  • 1
    \$\begingroup\$ Would 7 5 3 output "013" or "13"? \$\endgroup\$ – Claudiu Apr 30 '15 at 17:06
  • 1
    \$\begingroup\$ @Claudiu based on the 7 10 4 test case I would say 13 \$\endgroup\$ – Maltysen Apr 30 '15 at 17:07
  • 2
    \$\begingroup\$ @Claudiu "Leading zeros are optional." so both version is correct. \$\endgroup\$ – randomra Apr 30 '15 at 17:12
  • 1
    \$\begingroup\$ Must we accept any positive integer for n or k? Or can we limit them to the range of the language's integer type? \$\endgroup\$ – Toby Speight Jan 19 '16 at 21:06

12 Answers 12

1
\$\begingroup\$

Dyalog APL, 23 bytes

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

This program works as long as the factorial does not exceed internal representation limit. In Dyalog APL, the limit can be raised by ⎕FR←1287.

Assumes the variables n, b, and k have been set (e.g. n b k←7 5 4), but if you rather want prompting for n, b, and k (in that order) then replace the three characters with .

\$\endgroup\$
  • \$\begingroup\$ Every test case I threw at it was computed in about 11 microseconds on my machine (M540). \$\endgroup\$ – Adám Jan 20 '16 at 15:20
7
\$\begingroup\$

Mathematica, 57 48 bytes

Saved 9 bytes thanks to @2012rcampion .

IntegerString[#!/#2^#!~IntegerExponent~#2,##2]&
\$\endgroup\$
  • \$\begingroup\$ I've never really used mathematica, but couldn't you swap the order of the arguments to make b first to save 2 bytes? \$\endgroup\$ – FryAmTheEggman Apr 30 '15 at 18:06
  • \$\begingroup\$ @FryAmTheEggman I'm new to the golfing community, is swapping argument order "kosher"? \$\endgroup\$ – 2012rcampion Apr 30 '15 at 18:34
  • 1
    \$\begingroup\$ You can actually get to 47: IntegerString[#!#2^-#!~IntegerExponent~#2,##2]& (both this and your original are quite fast) \$\endgroup\$ – 2012rcampion Apr 30 '15 at 18:44
  • \$\begingroup\$ The asker wrote: "The order of the input integers can be chosen arbitrarily." under input, so in this case it's definitely fine \$\endgroup\$ – FryAmTheEggman Apr 30 '15 at 18:46
  • \$\begingroup\$ @Fry Wow, looks like I didn't read closely enough. However, the SlotSequence trick I used in my comment only works with the current order, so you couldn't save any more. \$\endgroup\$ – 2012rcampion Apr 30 '15 at 23:50
2
\$\begingroup\$

PARI/GP, 43 bytes

Trading speed for space yields this straightforward algorithm:

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

Each of the test cases runs in less than a second on my machine.

\$\endgroup\$
1
\$\begingroup\$

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

I'm not sure the test cases will all run fast enough - the larger ones are very slow (as it is looping through the number).

Try it online here (but be careful).

\$\endgroup\$
2
\$\begingroup\$

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

Example:

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

For the largest cases, the limiting factor is not generating the digits:

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

The pattern matching seems to be O(n^2), causing the last two test cases to go far over the one-minute mark.

\$\endgroup\$
7
\$\begingroup\$

Python, 198 192 181 chars

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

It's fast enough, ~23 seconds on the biggest example. And no factorial builtin (I'm looking at you, Mathematica!).

\$\endgroup\$
  • \$\begingroup\$ [2,3,2,5,3,7,2,3,5][b-2] could be int('232537235'[b-2]) to save 3 bytes. [1,1,2,1,1,1,3,2,1][b-2] similarly. \$\endgroup\$ – randomra May 1 '15 at 1:10
  • \$\begingroup\$ For the latter, a lookup table 111973>>2*(b-2)&3 is even shorter. It's the same number of bytes for the former though (90946202>>3*(b-2)&7). \$\endgroup\$ – Sp3000 May 1 '15 at 2:51
  • \$\begingroup\$ nvm looks like you were right about the higher digits thing \$\endgroup\$ – Sp3000 May 1 '15 at 3:17
  • \$\begingroup\$ I believe you can save a few bytes by making this a program and not a function. \$\endgroup\$ – FryAmTheEggman May 3 '15 at 17:21
6
\$\begingroup\$

Pyth, 26 35 bytes

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

This is a function of 3 arguments, number, base, number of digits.

Demonstration.

The slowest test case, the final one, takes 15 seconds on my machine.

\$\endgroup\$
  • \$\begingroup\$ @Sp3000 I added a fix which I think should be sufficient. \$\endgroup\$ – isaacg May 1 '15 at 5:31
2
\$\begingroup\$

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]

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

Takes about 8 seconds for f 359221 2 40 on my 4 year old laptop.

How it works: fold the multiplication (*) into the list [1..n]. Convert every intermediate result to base b as a list of digits (least significant first), strip leading zeros, then take the first k digits and convert to base 10 again. Finally convert to base b again, but with most significant digit first.

\$\endgroup\$
  • \$\begingroup\$ you had the idea in my mind , that i was interpreting it using matlab , what a coincidende :D \$\endgroup\$ – Abr001am May 1 '15 at 16:52
2
\$\begingroup\$

Bash/coreutils/dc, 60 bytes

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

Uses the dc script from my answer to Find the Factorial, outputting in base $2, with sed to trim trailing zeros and tail to select the last $3 digits.

\$\endgroup\$
  • \$\begingroup\$ I have to admit that it's extremely slow with the 40-bit base-2 testcase. I tried easing sed's work using rev to reduce backtracking, but it's dc that's eating the CPU... \$\endgroup\$ – Toby Speight Jan 20 '16 at 22:44
1
\$\begingroup\$

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

On my computer, this averages a little under a third of a second on the 359221 2 40 testcase. Takes input via command line arguments.

\$\endgroup\$
1
\$\begingroup\$

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}

This uses some GNU extensions to reduce code size; a POSIX-conforming equivalent weighs in at 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)}

To keep run times reasonable, we trim the trailing zeros (while(!x%b)x/=b) and truncate to the final k digits (x%=b^k) as we compute the factorial (for(x=1;n;)x*=n--).

Test program:

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 of the full test suite is approx 4¼ seconds on my 2006-vintage workstation.

\$\endgroup\$
  • \$\begingroup\$ This is my first ever bc program (golf or not), so any tips are especially welcome... \$\endgroup\$ – Toby Speight Jan 20 '16 at 11:17
0
\$\begingroup\$

PHP, 80 bytes

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

Used as f(359221,2,40) for the last test case. Runs pretty smoothly for all test cases.

Try here !

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.