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
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\$

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\$
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\$
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
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
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\$
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\$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .