15
\$\begingroup\$

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
\$\endgroup\$
3
  • 5
    \$\begingroup\$ Suggest not including \$0^0\$ as it's undefined somewhere \$\endgroup\$
    – l4m2
    Commented Aug 1, 2023 at 7:28
  • 1
    \$\begingroup\$ Okay, but H(0) is still 1, just like 0! is 1. \$\endgroup\$ Commented Aug 1, 2023 at 8:33
  • 3
    \$\begingroup\$ 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 \$\endgroup\$ Commented Aug 1, 2023 at 18:03

14 Answers 14

20
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ Great description - thank you! \$\endgroup\$ Commented Aug 1, 2023 at 12:32
  • 1
    \$\begingroup\$ Is there not a released 3.8 yet? Or is the pre-release somehow more capable? \$\endgroup\$ Commented Aug 1, 2023 at 12:33
  • 5
    \$\begingroup\$ @TobySpeight Neither I believe, TIO just happens to be stuck on that version. Python official is at 3.11 or so. \$\endgroup\$
    – loopy walt
    Commented Aug 1, 2023 at 12:38
5
\$\begingroup\$

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

\$\endgroup\$
0
4
\$\begingroup\$

Charcoal, 16 bytes

IΣE⊕N×ι⌕⮌X⁰↨ι⁵¦⁰

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

    N               Input integer
   ⊕                Incremented
  E                 Map over implicit (inclusive) range
      ι             Current value
     ×              Times
          ⁰         Literal integer `0`
         X          Vectorised raise to power
            ι       Current value
           ↨        Converted to base
             ⁵      Literal integer `5`
        ⮌           Reversed
       ⌕            Find index of
               ⁰    Literal integer `0`
 Σ                  Take the sum
I                   Cast to string
                    Implicitly print
\$\endgroup\$
3
  • \$\begingroup\$ Does this work with the full range of positive integers? \$\endgroup\$ Commented Aug 1, 2023 at 8:48
  • \$\begingroup\$ @TobySpeight Probably only up to python's sys.maxsize as Charcoal doesn't use generators. \$\endgroup\$
    – Neil
    Commented Aug 1, 2023 at 8:54
  • \$\begingroup\$ That's reasonable - at first I thought this computed H(n), which would make the full range too expensive. \$\endgroup\$ Commented Aug 1, 2023 at 10:52
4
\$\begingroup\$

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

\$\endgroup\$
0
4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ This seems to struggle with the medium-sized test cases I've recently added. Remember that input is any valid non-negative! \$\endgroup\$ Commented Aug 1, 2023 at 8:39
  • \$\begingroup\$ @TobySpeight that was just the recursion limit - I've updated the link. \$\endgroup\$
    – The Thonnu
    Commented Aug 1, 2023 at 9:38
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

Vyxal s, 34 bitsv2, 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.

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

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
\$\endgroup\$
2
  • \$\begingroup\$ I guess Rọ5ḋƊ also works? \$\endgroup\$
    – Neil
    Commented Aug 1, 2023 at 17:42
  • \$\begingroup\$ Yep, or even the no hyper (€ⱮÞ"...), no quick ($Ɗ¥?Ƈ...) Rọ5ḋR \$\endgroup\$ Commented Aug 1, 2023 at 20:27
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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 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.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Try it online! for 12 bytes using a different approach (group by) \$\endgroup\$
    – lyxal
    Commented Aug 2, 2023 at 8:17
  • \$\begingroup\$ @lyxal 10 bytes actually, since .γ} is basically builtin γ. :) Thanks! \$\endgroup\$ Commented Aug 2, 2023 at 8:42
  • 1
    \$\begingroup\$ Doesn’t Python use arbitrary large integers? \$\endgroup\$ Commented Aug 2, 2023 at 18:35
  • 1
    \$\begingroup\$ 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! \$\endgroup\$
    – Aiden Chow
    Commented Aug 2, 2023 at 20:01
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Aiden Chow
    Commented Aug 2, 2023 at 20:04
2
\$\begingroup\$

Excel, 68 bytes

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

Input in cell A1. Fails for A1>7.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 1, 2023 at 8:52
  • \$\begingroup\$ 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? \$\endgroup\$ Commented Aug 1, 2023 at 8:56
  • \$\begingroup\$ Up to 2³² if that's a number in your language. \$\endgroup\$ Commented Aug 1, 2023 at 10:48
  • 1
    \$\begingroup\$ AFAIK, Excel only has 15-bit precision floating-point numbers. Here's a link to the specs: support.microsoft.com/en-us/office/… \$\endgroup\$
    – Someone
    Commented Aug 1, 2023 at 21:46
2
\$\begingroup\$

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.

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

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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