How many trailing zeros in the hyperfactorial?

Question

We have a challenge to calculate the hyperfactorial and one to count the trailing zeros of the factorial, so it seems logical to put them together and count the trailing zeros in the hyperfactorial.

As a recap, the hyperfactorial of a number, H(n) is simply Πiⁱ, that is, 1¹·2²·3³·4⁴·5⁵·…·nⁿ. It can be defined recursively as H(n) = nⁿH(n-1) with H(0) = 1. This is integer sequence A002109.

Your task is to write the shortest program or function that accepts a non-negative integer n and returns or prints the number of trailing zeros in H(n) when represented as a decimal number (i.e. the corresponding entry from sequence A246839).

n will be in the range of integers in your language; H(n) might not be. That means your program must terminate given any non-negative n that's valid in your language (or 2³² if that's smaller).

Some test cases:

input	output
0	0
4	0
5	5
10	15
24	50
25	100
250	8125
10000	12518750

Answer 1

Python 3.8 (pre-release), 38 bytes

f=lambda n:n and(f(m:=n//5)-m*~m//2)*5

Try it online!

How?

Calculates the number almost directly only recursing to correct for higher powers of 5 in the base:

$$\begin{align} f(n) & =\sum_{i=5,10,...,n} i+\sum_{i=25,50,...,n}i+\sum_{i=125,250,...,n}i+... \\ & =5 \sum_{i=1}^\left\lfloor\frac n 5 \right\rfloor i + 25 \sum_{i=1}^\left\lfloor\frac n {25} \right\rfloor i + 125 \sum_{i=1}^\left\lfloor\frac n {125} \right\rfloor i + ... \\ & = 5 \sum_{i=1}^\left\lfloor\frac n 5 \right\rfloor i + 5 f\left(\left\lfloor\frac n 5 \right\rfloor\right) \\ & = 5 \frac{\left\lfloor\frac n 5 \right\rfloor\left(\left\lfloor\frac n 5 \right\rfloor+1\right)}2 + 5 f\left(\left\lfloor\frac n 5 \right\rfloor\right)\end{align}$$

Answer 2

JavaScript (Node.js), 41 bytes

f=n=>n&&f(~-n)+g(n)*n
g=n=>n%5?0:-~g(n/5)

Try it online!

-3 bytes from Arnauld

JavaScript (Node.js), 29 bytes

f=n=>n&&f(n=n/5|0)*5-n*~n/2*5

Try it online!

Port of loopy walt's

Answer 3

Charcoal, 16 bytes

ＩΣＥ⊕Ｎ×ι⌕⮌Ｘ⁰↨ι⁵¦⁰

Try it online! Link is to verbose version of code. Explanation:

    Ｎ               Input integer
   ⊕                Incremented
  Ｅ                 Map over implicit (inclusive) range
      ι             Current value
     ×              Times
          ⁰         Literal integer `0`
         Ｘ          Vectorised raise to power
            ι       Current value
           ↨        Converted to base
             ⁵      Literal integer `5`
        ⮌           Reversed
       ⌕            Find index of
               ⁰    Literal integer `0`
 Σ                  Take the sum
Ｉ                   Cast to string
                    Implicitly print

Answer 4

C (gcc), 49 bytes

g(n){n=n%5?0:-~g(n/5);}f(n){n=n?f(~-n)+g(n)*n:0;}

Try it online!

Port of l4m2 JavaScript answer

Answer 5

Python 2, 58 bytes

f=lambda n:n and f(n-1)+g(n)*n
g=lambda i:i%5<1and-~g(i/5)

Try it online!

Python 2, 39 bytes

f=lambda n:n and(f(n/5)-n/5*~(n/5)/2)*5

Try it online!

Port of loopy walt's Python answer.

Answer 6

PARI/GP, 30 bytes

n->sum(i=1,n,i*valuation(i,5))

Attempt This Online!

Based on Michel Marcus's code on the OEIS page.

Answer 7

C (gcc), 31 bytes

port of loopy walt's Python answer.

f(n){n=n?(f(n/=5)-n*~n/2)*5:0;}

Try it online!

Answer 8

Vyxal s, 34 bits^v2, 4.25 bytes

ɾ:5Ǒ*

Try it Online!

-7 bits thanks to emanresu

Explained

ɾ:5Ǒ*­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏⁠⁠‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁢⁡​‎‏​⁢⁠⁡‌­
ɾ      # ‎⁡The range [1, input]
 :     # ‎⁢Duplicated
  5Ǒ   # ‎⁣With the multiplicity of 5 of each number
    *  # ‎⁤Multiply that by the original list
# ‎⁢⁡The s flag sums the list
💎

Created with the help of Luminespire.

Answer 9

Jelly, 5 bytes

ọ€5ḋR

A monadic Link that accepts a non-negative integer, \$n\$, and yields the number of trailing zeros of the hyperfactorial, \$H(n)\$.

Try it online!

How?

As the hyperfactorial's input increases, each time \$n\$ reaches a multiple of five \$n\nu_5(n)\$ more zeros are added.

ọ€5ḋR - Link: non-negative integer, n
 €    - for each {i in [1..n]}:
ọ 5   -   {i} order of multiplicity of {5}
    R - range {n} -> [1..n]
   ḋ  - dot-product

Answer 10

Desmos, 47 bytes

f(k)=∑_{n=1}^knlog_5(gcd(n,5^{ceil(log_5n)}))

Try It On Desmos!

Try It On Desmos! - Prettified

It can be f(k)=∑_{n=1}^knlog_5(gcd(n,5^n)) but that quickly runs into inaccuracies even for smaller inputs.

Answer 11

05AB1E, 16 10 bytes

LDmTªPγθg<

-6 bytes thanks to @lyxal.

Actually calculates \$H(n)\$ and counts the amount of trailing 0s, so this is a much slower approach. Still valid though, since the new 05AB1E is built in Elixir, which has an infinitely large integer and is only limited by memory (in the legacy version of 05AB1E, built in Python, it would be valid as well for the same reason).

Try it online or verify (almost) all test cases.

Explanation:

L           # Push a list in the range [1, (implicit) input-integer]
 D          # Duplicate it
  m         # Take the power of the values at the same positions: [1**1,2**2,3**3,...]
   Tª       # Append a 10 to this list
     P      # Take the product
      γ     # Group adjacent equal digits together in substrings
       θ    # Pop and keep the trailing part of 0s
        g   # Pop and push its length
         <  # And decrease it by 1
            # (after which the result is output implicitly)

The Tª and < are only there for inputs in the range \$0\leq n<4\$. For \$n\geq5\$ it works fine without it. These three bytes also have loads of alternatives (i.e. LDmP0«γθ¦g; LDmPγθgDi0; LDmPγθgD≠*; etc.), but I've been unable to find anything shorter thus far.

Original 16 12 bytes approach:

ƒNÐ5sm¿5.n*O

Port of AidenChow's Desmos answer, so make sure to upvote that answer as well!

Try it online or verify all test cases.

Explanation:

ƒ             # Loop `N` in the range [0, (implicit) input-integer]:
 NÐ           #  Push three copies of `N` to the stack
 N 5sm        #  Pop one, and push 5 to the power `N`
 N    ¿       #  Pop this and another `N`, and push their Greatest Common Divisor
       5.n    #  Take log_5 of that value
 N        *   #  Multiply it by the remaining `N`
           O  #  Sum all values on the stack together
              # (after which the result is output implicitly)

05AB1E lacks the convenient multiplicity-builtin that the Jelly and Vyxal answers have, although I still have the feeling this can be shorter with another approach, since the 5sm and 5.n are rather verbose. EDIT: which was indeed correct.

Answer 12

Excel, 68 bytes

=LET(a,SEQUENCE(A1),IFERROR(SUM(N(TEXTSPLIT(PRODUCT(a^a),,0)="")),))

Input in cell A1. Fails for A1>7.

Answer 13

Retina 0.8.2, 47 bytes

.+
$*¶

$.`$*#$.`$*
+%`^(#+)\1{4}\b
$'¶$1
A`#
1

Try it online! Link includes Link includes faster test cases (since it calculates in unary internally, it times out TIO after about 3000 and probably runs out of memory anyway after about 30000). Explanation:

.+
$*¶

$.`$*#$.`$*

Generate a range from 0 up to and including the input, in duplicated unary, once using # and once using 1.

%`^(#+)\1{4}\b
$'¶$1

For each entry that has a multiple of 5 #s, remove them leaving the 1s, and then append an entry with the number of #s divided by 5, but with the original number of 1s.

+`

Repeatedly process any new entries that have a multiple of 5 #s.

A`#

Remove all entries that weren't a multiple of 5 #s. (If they were, the #s would have been removed.)

1

Count the number of trailing zeros.

Retina 1 can do the whole calculation in decimal, allowing it to quickly compute the result for 10000, although it does take 65 bytes:

.+
*¶

$.`
+%`.*50*$
$.(*2*
~["L$`^¶$.("|""L$rm`0*$
$.($:&*$&)$*_

Try it online! Link includes test cases. Explanation:

.+
*¶

$.`,$.`

Generate a range from 0 up to and including the input.

+%`.*50*$
$.(*2*

Double any value that ends in 5, 50, 500 etc. as many times as necessary so that it does not.

["L$`^¶$.("|""L$rm`0*$
$.($:&*$&)$*_

Multiply each original value by the number of trailing zeros, then generate a command that calculates the sum of those products. The intermediate multiplication allows use of a capture on the right which would otherwise have to be wrapped. The match is performed right-to-left so that values with trailing zeros are only matched once but matches without trailing zeros are also matched so that the match index will give the original value.

~`

Execute that command.

Answer 14

Scala 3, 48 bytes

Port of @loopy walt's Python answer in Scala.

n=>{if(n<1)0 else{val m=n/5;(f(m)+m*(m+1)/2)*5}}

Attempt This Online!