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 (when written in decimal).

As a recap, the hyperfactorial of a number, H(n) is simply Πii, that is, 11·22·33·44·55·...·nn. It can be defined recursively as H(n) = nnH(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 232 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

• l4m2: Suggest not including \0ドル^0\$ as it's undefined somewhere
• Toby Speight: Okay, but H(0) is still 1, just like 0! is 1.
• Peter Cordes: After having just looked at Number of bits needed to represent the product of the first primes, it took me several minutes to realize this question was about base-10 trailing zeros, not __builtin_ctz( h ), the number of trailing zero bits. (Which would be the sum of the ctz of each input times its power, I think.) Base 10 explains all the 5s in the answers! :P

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

• Toby Speight: Great description - thank you!
• Toby Speight: Is there not a released 3.8 yet? Or is the pre-release somehow more capable?
• loopy walt: @TobySpeight Neither I believe, TIO just happens to be stuck on that version. Python official is at 3.11 or so.

Answer 2

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 3

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 4

Charcoal, 16 bytes

×ばつι⌕⮌X0↨ι5¦0

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

 N Input integer
 ⊕ Incremented
 E Map over implicit (inclusive) range
 ι Current value
 ×ばつ Times
 0 Literal integer `0`
 X Vectorised raise to power
 ι Current value
 ↨ Converted to base
 5 Literal integer `5`
 ⮌ Reversed
 ⌕ Find index of
 0 Literal integer `0`
 Σ Take the sum
I Cast to string
 Implicitly print

• Toby Speight: Does this work with the full range of positive integers?
• Neil: @TobySpeight Probably only up to python's sys.maxsize as Charcoal doesn't use generators.
• Toby Speight: That's reasonable - at first I thought this computed H(n), which would make the full range too expensive.

Answer 5

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 6

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.

• Toby Speight: This seems to struggle with the medium-sized test cases I've recently added. Remember that input is any valid non-negative!
• The Thonnu: @TobySpeight that was just the recursion limit - I've updated the link.

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.

• emanresu A: 39 bits and O(n)

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

• Neil: I guess Rọ5ḋƊ also works?
• Jonathan Allan: Yep, or even the no hyper (€ⱮÞ"...), no quick ($Ɗ¥?Ƈ...) Rọ5ḋR

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

LDmTaPγθ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,...]
 Ta # 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 Ta 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.

• lyxal: Try it online! for 12 bytes using a different approach (group by)
• Kevin Cruijssen: @lyxal 10 bytes actually, since .γ} is basically builtin γ. :) Thanks!
• The Empty String Photographer: Doesn’t Python use arbitrary large integers?
• Aiden Chow: Heh I think this is like the first time someone has ported one of my Desmos answers, and I certainly didn’t expect it from a golfing lang. Cool!
• Aiden Chow: Just a note, in my desmos answer, I had to do 5^{ceil(log_5n)} because of some floating point inaccuracies, but I think if your lang has arbitrary precision then you can simply do 5^n. Not that it changes much now that you are using another strategy.

Answer 12

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!

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

Wolfram Language (Mathematica), 54 bytes

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

---

Golfed version. Try it online!

f=If[#<1,0,With[{m=#~Quotient~5},(f[m]+m*(m+1)/2)*5]]&

Ungolfed version. Try it online!

(* Define the recursive function f *)
f[n_Integer] := If[n < 1, 0, 
 Module[{m = Quotient[n, 5]}, 
 (f[m] + m*(m + 1)/2)*5
 ]
]

Answer 15

Excel, 68 bytes

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

Input in cell A1. Fails for A1>7.

• Toby Speight: 8 is a valid input, so this isn't a correct answer. I've edited the question to make it clearer that it has to work for all valid inputs.
• Jos Woolley: Ah, so there is no tolerance for IEEE 754 precision errors? You expect a solution to handle all inputs up to and including 10,000?
• Toby Speight: Up to 2³² if that's a number in your language.
• Someone: AFAIK, Excel only has 15-bit precision floating-point numbers. Here's a link to the specs: support.microsoft.com/en-us/office/…

Answer 16

APL(NARS), 21 chars

×ばつ+/(∇,⍳)⌊⍵÷5}

It would apply the formula of "loopy walt" post. It apply the formula below too.

(2÷⍨k×ばつ1+k)=+/⍳k

test:

 ×ばつ+/(∇,⍳)⌊⍵÷5}
 f 0
0
 f 4
0
 f 5
5
 f 250
8125
 f 10000
12518750
 f 10000000000x
WS FULL
 f 10000000000x
 ∧

probably it because there are problem in doing ⍳⌊10000000000x÷5 but here no problem:

 ×ばつ(∇k)+2÷⍨k×ばつ1+k←⌊⍵÷5}10000000000x
12500000041240234375 

Answer 17

AWK, 50 bytes

{for(x=1;0ドル;match(x,/0+$/))x*=0ドル^0ドル--}1,0ドル=RLENGTH

Attempt This Online!

Doesn't work in ATO with large numbers, but should work locally if you try:

awk -M '{for(x=1;0ドル;match(x,/0+$/))x*=0ドル^0ドル--}1,0ドル=RLENGTH' <<< 10

Replace the 10 with your input number. Works up to at least 250, but it's slow (I tried 10000 and it's been running for a minute...).