Zéros à la fin d'une factorielle

35

Ecrivez un programme ou une fonction qui trouve le nombre de zéros à la fin de la n!base 10, où nest un nombre entré (dans le format de votre choix).

On peut supposer qu'il ns'agit d'un entier positif, ce qui signifie n!également un entier. Il n'y a pas de zéros après une décimale dans n!. En outre, on peut supposer que votre langage de programmation peut gérer la valeur de net n!.


Cas de test

1
==> 0

5
==> 1

100
==> 24

666
==> 165

2016
==> 502

1234567891011121314151617181920
==> 308641972752780328537904295461

C'est du code golf. Les règles standard s'appliquent. Le code le plus court en octets gagne.

Les soumissions

Pour vous assurer que votre réponse apparaît, commencez votre réponse par un titre, en utilisant le modèle Markdown suivant:

# Language Name, N bytes

Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores en les effaçant. Par exemple:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Si vous souhaitez inclure plusieurs numéros dans votre en-tête (par exemple, parce que votre score est la somme de deux fichiers ou si vous souhaitez répertorier séparément les pénalités d'indicateur d'interprétation), assurez-vous que le score réel est le dernier numéro de l'en-tête:

# Perl, 43 + 2 (-p flag) = 45 bytes

Vous pouvez également faire du nom de la langue un lien qui apparaîtra ensuite dans l'extrait de classement:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

Classement

Voici un extrait de pile permettant de générer un classement régulier et un aperçu des gagnants par langue.

Arcturus
la source
Peut-on supposer que n! s'intégrera dans le type entier natif de nos langues?
Alex A.
@Alexa. Oui, vous pouvez.
Arcturus
Peut- nêtre une chaîne d'entrée?
Conor O'Brien
15
Je pense que ce serait une meilleure question si vous n'étiez pas autorisé à supposer qu'il n!tiendrait dans votre type entier! Eh bien, peut-être une autre fois.
Un Simmons

Réponses:

43

Python 2, 27 octets

f=lambda n:n and n/5+f(n/5)

Les zéros de fin sont limités par des facteurs de 5. Le nombre de multiples de ce 5qui est au plus nest n/5(avec division des étages), mais cela ne compte pas les facteurs répétés dans des multiples de 25, 125, .... Pour les obtenir, divisez npar 5 et recurse.

Xnor
la source
19

Gelée , 5 octets

!Æfċ5

Utilise l’approche contre-productive de trouver la factorielle, puis de la factoriser à nouveau, en vérifiant l’exposant de 5 dans la factorisation première.

Essayez-le en ligne!

!              Factorial
 Æf            List of prime factors, e.g. 120 -> [2, 2, 2, 3, 5]
   ċ5          Count number of 5s
Sp3000
la source
4
beurk. Parlez de compromis! Pour réduire le code à 5 octets, augmentez la mémoire et le temps d'absurdité.
Ross Presser
19

Croissant Mornington, 1949 1909 octets

Take Northern Line to Bank
Take Circle Line to Bank
Take District Line to Parsons Green
Take District Line to Cannon Street
Take Circle Line to Victoria
Take Victoria Line to Seven Sisters
Take Victoria Line to Victoria
Take Circle Line to Victoria
Take Circle Line to Bank
Take Circle Line to Hammersmith
Take District Line to Turnham Green
Take District Line to Hammersmith
Take District Line to Upminster
Take District Line to Hammersmith
Take District Line to Turnham Green
Take District Line to Bank
Take Circle Line to Hammersmith
Take Circle Line to Blackfriars
Take Circle Line to Hammersmith
Take Circle Line to Notting Hill Gate
Take Circle Line to Notting Hill Gate
Take Circle Line to Bank
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Becontree
Take District Line to Upminster
Take District Line to Becontree
Take District Line to Upminster
Take District Line to Becontree
Take District Line to Upminster
Take District Line to Bank
Take Circle Line to Blackfriars
Take District Line to Upminster
Take District Line to Temple
Take Circle Line to Hammersmith
Take Circle Line to Cannon Street
Take Circle Line to Bank
Take Circle Line to Blackfriars
Take Circle Line to Hammersmith
Take District Line to Becontree
Take District Line to Cannon Street
Take District Line to Becontree
Take District Line to Cannon Street
Take District Line to Becontree
Take District Line to Blackfriars
Take Circle Line to Bank
Take District Line to Upminster
Take District Line to Becontree
Take District Line to Upminster
Take District Line to Becontree
Take District Line to Upminster
Take District Line to Becontree
Take District Line to Bank
Take Circle Line to Bank
Take Northern Line to Angel
Take Northern Line to Bank
Take Circle Line to Bank
Take District Line to Upminster
Take District Line to Bank
Take Circle Line to Bank
Take Northern Line to Mornington Crescent

-40 octets grâce à NieDzejkob

poivré
la source
Et c'est maintenant ma réponse la plus votée.
pppery
3
Une brève explication pour ceux d’entre nous qui sommes Mornington Crescentcontestés serait bien. :)
Robert Benson
-40 octets en utilisant des noms de lignes plus courts dans la mesure du possible.
NieDzejkob
18

Pyth, 6 octets

/P.!Q5

Essayez ici.

/    5   Count 5's in
 P        the prime factorization of
  .!Q      the factorial of the input.

Alternative 7 octets :

st.u/N5

La réduction cumulative du .u/N5plancher divisée de manière répétée 5jusqu'à obtenir une répétition, ce qui dans ce cas se produit après avoir atteint 0.

34 -> [34, 6, 1, 0]

Le premier élément est ensuite supprimé ( t) et le reste est ajouté ( s).

Xnor
la source
13

En fait, 10 octets

!$R;≈$l@l-

Essayez-le en ligne!

Notez que le dernier cas de test échoue lors de l’exécution sérieuse de CPython car math.factorial utilise une extension C (limitée aux entiers 64 bits). Courir sérieusement sur PyPy fonctionne bien, cependant.

Explication:

!$R;≈$l@l-
!           factorial of input
 $R         stringify, reverse
   ;≈$      make a copy, cast to int, then back to string (removes leading zeroes)
      l@l-  difference in lengths (the number of leading zeroes removed by the int conversion)
Mego
la source
3
Oh wow, j'aime comment cette méthode n'utilise pas le truc de la division par 5.
Arcturus
Je compte 12 octets sur celui-ci
Score_Under
1
@Score_Under Utilise en réalité la page de code CP437, pas UTF-8. Chaque caractère est un octet.
Mego
9

Haskell, 26 octets

f 0=0
f n=(+)=<<f$div n 5

Floor divise l’entrée par 5, puis ajoute le résultat à la fonction appelée. L'expression (+)=<<fprend une entrée xet des sorties x+(f x).

Raccourci de:

f 0=0
f n=div n 5+f(div n 5)

f 0=0
f n|k<-div n 5=k+f k

Une expression non récursive a donné 28 octets:

f n=sum[n`div`5^i|i<-[1..n]]
Xnor
la source
Est-ce iqu'un compteur 1..n?
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Oui, bien que ce ne soit que log_5(n)question, le reste donne 0.
xnor
8

MATL , 9 octets

:"@Yf5=vs

Essayez-le en ligne!

Cela fonctionne pour de très grands nombres, car cela évite de calculer la factorielle.

Comme d’autres réponses, cela exploite le fait que le nombre de fois 2indiqué comme diviseur de la factorielle est supérieur ou égal au nombre de fois où il 5apparaît.

:     % Implicit input. Inclusive range from 1 to that
"     % For each
  @   %   Push that value
  Yf  %   Array of prime factors
  5=  %   True for 5, false otherwise
  v   %   Concatenate vertically all stack contents
  s   %   Sum
Luis Mendo
la source
6

05AB1E, 5 octets

Serait 4 octets si nous pouvions garantir n> 4

Code:

Î!Ó7è

Explication:

Î        # push 0 then input
  !      # factorial of n: 10 -> 2628800
   Ó     # get primefactor exponents -> [8, 4, 2, 1]
    7è   # get list[7] (list is indexed as string) -> 2
         # implicit output of number of 5s or 0 if n < 5

Solution alternative, beaucoup plus rapide, à 6 octets: Inspirée de la réponse MATL de Luis Mendo

LÒ€`5QO

Explication:

L         # push range(1,n) inclusive, n=10 -> [1,2,3,4,5,6,7,8,9,10]
 Ò        # push prime factors of each number in list -> [[], [2], [3], [2, 2], [5], [2, 3], [7], [2, 2, 2], [3, 3], [2, 5]]
  €`      # flatten list of lists to list [2, 3, 2, 2, 5, 2, 3, 7, 2, 2, 2, 3, 3, 2, 5]
    5Q    # and compare each number to 5 -> [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
      O   # sum -> 2

Edit: solutions supprimées en utilisant ¢ (nombre), car tous les nombres premiers contenant 5 seraient comptés comme 5, par exemple 53.

Edit 2: ajout d'une solution plus efficace pour une entrée plus élevée à titre de comparaison.

Emigna
la source
Ouais, au lieu de , 5Qça devrait marcher. Bonne réponse cependant! :)
Adnan
J'allais tester sur des entrées plus volumineuses avec le commentaire "cela ne va pas échouer si la sortie est> 9", mais la mise en oeuvre du garçon 05AB1E Óest lente
Sp3000
Btw, le premier code peut aussi être Î!Ó2é. Le bug a été corrigé hier .
Adnan
Si vous utilisez utf-8, utilisez Î!Ó7è8 octets et la solution "6 octets" 10 octets
Score_Under
@Score_Under Oui, c'est correct. Cependant, 05AB1E utilise le codage CP-1252.
Adnan,
6

Matlab (59) (54)(39)

Salut papa !!!! nous vous avons entendu comme maths ....

  @(n)sum(fix(n./5.^(1:fix(log(n)/1.6))))
  • Ceci est basé sur ma réponse créée dans la révision du code .

  • plus loin que ce qui est mentionné dans ma réponse dans la révision du code, la formule du nombre de zéros dans factorielle (n) est Sum (n / (5 ^ k)) où k varie entre 1 et log_5 (n)

  • La seule raison triviale pour laquelle il ne peut pas jouer au golf est que ce log5n’est pas disponible dans Matlab en tant que fonction intégrée, c’est pourquoi j’ai remplacé log (5) par 1,6, n’importe pas parce qu’il sera de toute façon recouvert.

Essaie

Abr001am
la source
Quelques questions. 1. Comment gérez-vous cela dans Matlab? 2. Quel est le résultat pour n = 1?
Stuart Bruff
@StuartBruff pour exécuter ce type ans (1) et il renvoie 0.
1er
D'ACCORD. Merci. Intéressant. Je n'ai pas beaucoup utilisé de poignées de fonction dans Matlab, donc j'étais un peu perplexe quant à la manière de l'exécuter ... pourquoi l'ans () ne compte-t-il pas dans le total? Réponse soignée cependant, je l’ai essayé dans Mathcad, mais j’ai dû modifier la limite supérieure de la somme car Mathcad décrivait automatiquement la variable de somme si la valeur "supérieure" était inférieure à la limite "inférieure" (et par conséquent ma question sur 0).
Stuart Bruff,
5

Mathematica, 20 octets

IntegerExponent[#!]&

IntegerExponentcompte les zéros. Pour le plaisir, voici une version qui ne calcule pas la factorielle:

Tr[#~IntegerExponent~5&~Array~#]&
LegionMammal978
la source
Je pense Arrayenregistre un octet sur la deuxième solution.
Martin Ender
5

C, 28 octets

f(n){return(n/=5)?n+f(n):n;}

Explication

Le nombre de zéros à la fin est égal au nombre de cinq composant la factorielle. De ce nombre 1..n, un cinquième contribue 5, nous allons donc commencer par n/5. Parmi ceux-ci n/5, un cinquième est un multiple de 25, alors contribuez-en cinq, et ainsi de suite. Nous nous retrouvons avec f(n) = n/5 + n/25 + n/125 + ..., ce qui est f(n) = n/5 + f(n/5). Nous devons mettre fin à la récursion lorsque nzéro est atteint; nous profitons également du point de séquence à ?:pour diviser navant l’addition.

En prime, ce code est beaucoup plus rapide que celui qui visite chaque 1..n (and much, much faster than computing the factorial).

Programme de test

#include<stdio.h>
#include<stdlib.h>
int main(int argc, char **argv) {
    while(*++argv) {
        int i = atoi(*argv);
        printf("%d: %d\n",i,f(i));
    }
}

Test de sortie

1: 0
4: 0
5: 1
24: 4
25: 6
124: 28
125: 31
666: 165
2016: 502
2147483644: 536870901
2147483647: 536870902

Toby Speight
la source
+1 for an excellent explanation
Titus
4

JavaScript ES6, 20 bytes

f=x=>x&&x/5+f(x/5)|0

Same tactic as in xnor's answer, but shorter.

Conor O'Brien
la source
4

Julia, 34 31 30 bytes

n->find(digits(prod(1:n)))[]-1

This is an anonymous function that accepts any signed integer type and returns an integer. To call it, assign it to a variable. The larger test cases require passing n as a larger type, such as a BigInt.

We compute the factorial of n (manually using prod is shorter than the built-in factorial), get an array of its digits in reverse order, find the indices of the nonzero elements, get the first such index, and subtract 1.

Try it online! (includes all but the last test case because the last takes too long)

Saved a byte thanks to Dennis!

Alex A.
la source
3

C, 36

r;f(n){for(r=0;n/=5;)r+=n;return r;}

Same method as @xnor's answer of counting 5s, but just using a simple for loop instead of recursion.

Ideone.

Digital Trauma
la source
@TobySpeight there you go.
Digital Trauma
3

Retina, 33 bytes

Takes input in unary.

Returns output in unary.

+`^(?=1)(1{5})*1*
$#1$*1;$#1$*
;

(Note the trailing linefeed.)

Try it online!

How it works:

The first stage:

+`^(?=1)(1{5})*1*
$#1$*1;$#1$*

Slightly ungolfed:

+`^(?=1)(11111)*1*\b
$#1$*1;$#1$*1

What it does:

  • Firstly, find the greatest number of 11111 that can be matched.
  • Replace by that number
  • Effectively floor-divides by 5.
  • The lookahead (?=1) assures that the number is positive.
  • The +` means repeat until idempotent.
  • So, the first stage is "repeated floor-division by 5"

If the input is 100 (in unary), then the text is now:

;;1111;11111111111111111111

Second stage:

;

Just removes all semi-colons.

Leaky Nun
la source
2

Ruby, 22 bytes

One of the few times where the Ruby 0 being truthy is a problem for byte count.

f=->n{n>0?f[n/=5]+n:0}
Value Ink
la source
wait why is 0 truthy?
Conor O'Brien
2
@CᴏɴᴏʀO'Bʀɪᴇɴ In Ruby, nil and false are falsey, and nothing else is. There are a lot of cases where helps out in golf, since having 0 be truthy means the index and regex index functions in Ruby return nil if there is no match instead of -1, and some where it is a problem, like empty strings still being truthy.
Value Ink
@KevinLau-notKenny That does make sense.
Conor O'Brien
2

Perl 6, 23 bytes

{[+] -$_,$_,*div 50}
{sum -$_,$_,*div 5...0}

I could get it shorter if ^... was added to Perl 6 {sum $_,*div 5^...0}.
It should be more memory efficient for larger numbers if you added a lazy modifier between sum and the sequence generator.

Explanation:

{ # implicitly uses $_ as its parameter
  sum

    # produce a sequence
    -$_,     # negate the next value
     $_,     # start of the sequence

     * div 5 # Whatever lambda that floor divides its input by 5

             # the input being the previous value in the sequence,
             # and the result gets appended to the sequence

     ...     # continue to do that until:

     0       # it reaches 0
}

Test:

#! /usr/bin/env perl6

use v6.c;
use Test;

my @test = (
     1,   0,
     5,   1,
   100,  24,
   666, 165,
  2016, 502,
  1234567891011121314151617181920,
        308641972752780328537904295461,

  # [*] 5 xx 100
  7888609052210118054117285652827862296732064351090230047702789306640625,
        1972152263052529513529321413206965574183016087772557511925697326660156,
);

plan @test / 2;

# make it a postfix operator, because why not
my &postfix:<!0> = {[+] -$_,$_,*div 5...0}

for @test -> $input, $expected {
  is $input!0, $expected, "$input => $expected"
}

diag "runs in {now - INIT now} seconds"
1..7
ok 1 - 1 => 0
ok 2 - 5 => 1
ok 3 - 100 => 24
ok 4 - 666 => 165
ok 5 - 2016 => 502
ok 6 - 1234567891011121314151617181920 => 308641972752780328537904295461
ok 7 - 7888609052210118054117285652827862296732064351090230047702789306640625 => 1972152263052529513529321413206965574183016087772557511925697326660156
# runs in 0.0252692 seconds

( That last line is slightly misleading, as MoarVM has to start, load the Perl 6 compiler and runtime, compile the code, and run it. So it actually takes about a second and a half in total.
That is still significantly faster than it was to check the result of the last test with WolframAlpha.com )

Brad Gilbert b2gills
la source
2

Mathcad, [tbd] bytes

enter image description here

Mathcad is sort of mathematical "whiteboard" that allows 2D entry of expressions, text and plots. It uses mathematical symbols for many operations, such as summation, differentiation and integration. Programming operators are special symbols, usually entered as single keyboard combinations of control and/or shift on a standard key.

What you see above is exactly how the Mathcad worksheet looks as it is typed in and as Mathcad evaluates it. For example, changing n from 2016 to any other value will cause Mathcad to update the result from 502 to whatever the new value is.

http://www.ptc.com/engineering-math-software/mathcad/free-download


Mathcad's byte equivalence scoring method is yet to be determined. Taking a symbol equivalence, the solution takes about 24 "bytes" (the while operator can only be entered using the "ctl-]" key combination (or from a toolbar)). Agawa001's Matlab method takes about 37 bytes when translated into Mathcad (the summation operator is entered by ctl-shft-$).

Stuart Bruff
la source
Sounds a stunning tool to handle, I wont spare a second downloading it !
Abr001am
2

dc, 12 bytes

[5/dd0<f+]sf

This defines a function f which consumes its input from top of stack, and leaves its output at top of stack. See my C answer for the mathematical basis. We repeatedly divide by 5, accumulating the values on the stack, then add all the results:

5/d   # divide by 5, and leave a copy behind
d0<   # still greater than zero?
f+    # if so, apply f to the new value and add

Test program

# read input values
?
# print prefix
[  # for each value
    # print prefix
    [> ]ndn[ ==> ]n
    # call f(n)
    lfx
    # print suffix
    n[  
]n
    # repeat for each value on stack
    z0<t
]
# define and run test function 't'
dstx

Test output

./79762.dc <<<'1234567891011121314151617181920 2016 666 125 124 25 24 5 4 1'
1 ==> 0  
4 ==> 0  
5 ==> 1  
24 ==> 4  
25 ==> 6  
124 ==> 28  
125 ==> 31  
666 ==> 165  
2016 ==> 502  
1234567891011121314151617181920 ==> 308641972752780328537904295461  
Toby Speight
la source
1

Jolf, 13 bytes

Ώmf?H+γ/H5ΏγH

Defines a recursive function which is called on the input. Try it here!

Ώmf?H+γ/H5ΏγH  Ώ(H) = floor(H ? (γ = H/5) + Ώ(γ) : H)
Ώ              Ώ(H) =
       /H5                           H/5
      γ                         (γ =    )
     +    Ώγ                              + Ώ(γ)
   ?H       H               H ?                  : H
 mf                   floor(                        )
               // called implicitly with input
Conor O'Brien
la source
1

J, 28 17 16 bytes

<.@+/@(%5^>:@i.)

Pretty much the same as the non-recursive technique from xnor's answer.


Here's an older version I have kept here because I personally like it more, clocking in at 28 bytes:

+/@>@{:@(0<;._1@,'0'&=@":@!)

Whilst not needed, I have included x: in the test cases for extended precision.

   tf0 =: +/@>@{:@(0<;._1@,'0'&=@":@!@x:)
   tf0 5
1
   tf0 100
24

   tf0g =: tf0"0
   tf0g 1 5 100 666 2016
0 1 24 165 502

The last number doesn't work with this function.

Explanation

This works by calculating n!, converting it to a string, and checking each member for equality with '0'. For n = 15, this process would be:

15
15! => 1307674368000
": 1307674368000 => '1307674368000'
'0' = '1307674368000' => 0 0 1 0 0 0 0 0 0 0 1 1 1

Now, we use ;._1 to split the list on its first element (zero), boxing each split result, yielding a box filled with aces (a:) or runs of 1s, like so:

┌┬─┬┬┬┬┬┬┬─────┐
││1│││││││1 1 1│
└┴─┴┴┴┴┴┴┴─────┘

We simple obtain the last member ({:), unbox it (>), and perform a summation over it +/, yielding the number of zeroes.

Here is the more readable version:

split =: <;._1@,
tostr =: ":
is =: =
last =: {:
unbox =: >
sum =: +/
precision =: x:
n =: 15

NB. the function itself
tf0 =: sum unbox last 0 split '0' is tostr ! precision n
tf0 =: sum @ unbox @ last @ (0 split '0'&is @ tostr @ ! @ precision)
tf0 =: +/ @ > @ {: @ (0 <;._1@, '0'&= @ ": @ ! )
Conor O'Brien
la source
>:@i. can be written 1+i. to save a byte.
algorithmshark
Your older version can be made into [:#.~'0'=":@! for 13 bytes by changing the method of counting the trailing 1s.
cole
1

Python 3, 52 bytes

g=lambda x,y=1,z=0:z-x if y>x else g(x,y*5,z+x//y)
Magenta
la source
This doesn't work, try the test cases.
xnor
It should work now.
Magenta
1

Pyke, 5 bytes

SBP5/

Try it here!

S     -    range(1,input()+1)
 B    -   product(^)
  P   -  prime_factors(^)
   5/ - count(^, 5)
Blue
la source
1

RETURN, 17 bytes

[$[5÷\%$F+][]?]=F

Try it here.

Recursive operator lambda. Usage:

[$[5÷\%$F+][]?]=F666F

Explanation

[             ]=F  Lambda -> Operator F
 $                 Check if top of stack is truthy
  [       ][]?     Conditional
   5÷\%$F+         If so, do x/5+F(x/5)
Mama Fun Roll
la source
1

Perl, 24 22 + 1 (-p flag) = 23 bytes

$\+=$_=$_/5|0while$_}{

Using:

> echo 2016 | perl -pe '$\+=$_=$_/5|0while$_}{'

Full program:

while (<>) {
# code above added by -p
    while ($_) {
        $\ += $_ = int($_ / 5);
    }
} {
# code below added by -p
    print;  # prints $_ (undef here) and $\
}
Denis Ibaev
la source
1

Java, 38 bytes

int z(int n){return n>0?n/5+z(n/5):0;}

Full program, with ungolfed method:

import java.util.Scanner;

public class Q79762{
    int zero_ungolfed(int number){
        if(number == 0){
            return 0;
        }
        return number/5 + zero_ungolfed(number/5);
    }
    int z(int n){return n>0?n/5+z(n/5):0;}
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();
        System.out.println(new Q79762().zero_ungolfed(n));
        System.out.println(new Q79762().z(n));
    }
}
Leaky Nun
la source
1

J, 7 bytes

Monadic function, taking argument on the right.

3{:@q:!

If x is positive, x q: y returns the exponents in a prime factorization of y, for only the first x primes. The 3-rd prime is 5 and {: takes the tail of a list.

Note that you have to input integers with an x at the end, or else J will treat them as floats.

   3{:@q:! 100x
24
   3{:@q:! 666x
165
   3{:@q:! 2016x
502

Try it yourself at tryj.tk, though be warned that this online interpreter will complain if you try anything larger than 1343.

If you want something that doesn't compute n! and hence doesn't require it fit in an integer, use the recursive solution <.@%&5(+$:@)^:*. (tryj.tk is still whiny on large inputs.)

algorithmshark
la source
1

Ruby, 70 61 51 49 bytes

Version 3 with thanks to Kenny Lau and daniero

->n{(n-n.to_s(5).chars.map(&:to_i).reduce(:+))/4}

Edit: Turns out you can save two bytes by mapping to_i before you reduce. Weird :P

This function subtracts the sum of n's base 5 digits from n and then divides that result by 4. This is related to the sum of the geometric series 1+5+25+..+5**n = (5**n+1)/4.

As an example (again, with thanks to Kenny Lau), consider 358 (2413 in base 5) minus its base 5 digits.

2413-2-4-1-3 
= (2000-2) + (400-4) + (10-1) + (3-3)
# consider that 1000-1=444 and you'll see why every 5**n is multiplied by 4
= 2*444 + 4*44 + 1*4 + 3*0
= 2*(4*5**0+4*5**1+4*5**2) + 4*(4*5**0+4*5**1) + 1*(4*5**0) + 3*()
= 348

Divide 348 by 4 and you get f(358) = 87.

Version 2 with thanks to Kenny Lau

->n{s=(1..n).reduce(:*).to_s;s.size-s.reverse.to_i.to_s.size}

This function calculates n! then subtracts the size of n! from the size of (n!).reverse.to_i.to_s, which removes all the zeroes, thus, returning the size of the zeroes themselves.

Version 1

->n{s=n.to_s(5).chars;(0...s.size).reduce{|a,b|a+(s[0,b]*'').to_i(5)}}

This a variation of the "How many 5s are there in the prime factorization of n!?" trick that uses Ruby's simple base conversion builtins.

The golfing is a bit of a pain though, with converting from Integer to String to Array, grabbing part of the Array and converting that to String to Integer again for the reduce. Any golfing suggestions are welcome.

Sherlock9
la source
It's slightly shorter to map to_i before reducing: ->n{(n-n.to_s(5).chars.map(&:to_i).reduce(:+))/4} (saves two bytes)
daniero
@daniero I would not have expected that. Thanks :D
Sherlock9
1

Dyalog APL, 9 bytes

⊥⍨'0'=⍕!⎕

prompt for number

! factorialize

stringify

'0'= check equality to character zero

⊥⍨ count trailing trues*


*Literally it is a mixed-base to base-10 conversion, using the boolean list as both number and base:

⊥⍨0 1 0 1 1 is the same as 0 1 0 1 1⊥⍨0 1 0 1 1 which is 0×(0×1×0×1×1) 1×(1×0×1×1) 0×(0×1×1) 1×(1×1) + 1×(1) which again is two (the number of trailing 1s).

Adám
la source