(49g 50g) Number of Trailing Zeros in N!

[John Keith]

Inspired by this program and others by member GeraldH, this program will return A027868(n), the number of trailing zeros in n!.

Using ListExt 1.3, it is reasonably small and very fast, even for numbers with over 100 digits. The program is based on the third comment in the OEIS link above.

Code:


\<< DUP I\->R 5. \>=        @ Check that n >= 5
    { 5 I\->BL REV TAIL     @ Base 5 digits of n
      1 5 PICK3 SIZE LMSEQ  @ List of powers of 5
      :: + LSCAN            @ A003463
      * LSUM }              @ Sum of products
    { DROP 0 } IFTE         @ Return 0 for n<5
\>>

[Thomas Klemm]

We can also use the recurrence:

a(n) = floor(n/5) + a(floor(n/5));

This program is for the HP-42S but should work with most other models as well:

Code:

00 { 14-Byte Prgm }
01 0
02 X<>Y
03▸LBL 00
04 5
05 ÷
06 IP
07 +
08 LASTX
09 X>0?
10 GTO 00
11 R↓
12 END

This program is for the HP-48:

Code:

\<< 0
    WHILE SWAP DUP
    REPEAT
        5 / IP
        DUP ROT +
    END
    DROP
\>>

Example

\(
\begin{align}
n &= 7392 \\
\\
a(n) &= 1478 + 295 + 59 + 11 + 2 \\
&= 1845 \\
\end{align}
\)

References

Quote:Gardner, M. "Factorial Oddities." Ch. 4 in Mathematical Magic Show: More Puzzles, Games, Diversions, Illusions and Other Mathematical Sleight-of-Mind from Scientific American. New York: Vintage, pp. 50-65, 1978

Thank you for reminding me of this book.
I got the German translation "Mathematische Hexereien" as a teenager.

[John Keith]

Thanks for posting this, Thomas. Your program is certainly simpler, although it is limited to numbers < 10^12.

The reason for my rather brute-force approach is to allow number sizes limited only by the calculator's memory while avoiding the slowness of the HP50 IQUOT function. I am working on a revised version that should allow numbers with several thousand digits (that is the number n itself, not n!).

As shown in this paper from the OEIS link above, this method can be extended to numbers with arbitrary base. Doing so is not entirely straightforward because the details seem to depend on whether the base b is a prime, semiprime, prime power, etc. As they say, further research is needed.

[Thomas Klemm]

In the same chapter Martin Gardner talks about printing a factorial as a tree.

This Python program produces one of the examples:

Code:

from math import factorial

p = str(factorial(508))

n = 0
for j in range(34):
    k = 2*j + 1
    print(" " * (35 - j), p[n:n+k])
    n += k

                                  5
                                 119
                                90692
                               7755879
                              266003615
                             25819185379
                            7984360677298
                           470133958906714
                          46011174633964398
                         5839112233165772956
                        548496166254935516795
                       14565079522588677608012
                      6423489045662147453126349
                     825790036437158643266482002
                    88113505694916924243929121639
                   7995123320680205388149829536720
                  697546589338105120020005674705145
                 28641409978978956631664608452253922
                2182139322091260889711710217500934598
               659546487929459214735007200769105667735
              54074289548655659977226200540160335058131
             8365384235510714071491098835812736588922795
            511456461421254773804907853073384484888784090
           75030962875912509521999525292598359880846423952
          3931204111818280979213544777644751538435208774603
         088477116032223651164439419220002073567325180151958
        35354728897604905269289015307797618984464654042934912
       7882733479825616955531216107050271401259459875249508169
      440013327395316887000833911764483284987619075088343797786
     47371945157918046252226969546616811434035461815792968273198
    2545625613705049834238544557702694536385292145346080336071424
   289160111720849018903249047529128422886467764267877861568498090
  42964480000000000000000000000000000000000000000000000000000000000
 0000000000000000000000000000000000000000000000000000000000000000000

Also he mentions:

Quote:If someone had predicted fifty years ago that before the century
ended this factorial would be written out in full, digit by digit,
most mathematicians would have laughed at so preposterous a
prophecy.

And now, another 50 years later, we can do this with our smartphones.

---

Mathematical Magic Show

[John Keith]

That's pretty neat, especially considering the year that book was published. Very few people at that time had access to computers that could calculate and print such a large number.

Here is an experimental program that hits both points in my previous post. It works with very large numbers, and calculates the number of zeros in almost any base. The "almost" is the issue here- in particular, the base cannot be a prime power or a composite number whose largest prime factor occurs more than once. For example, bases 4, 8, 9, 16, 18 etc. will not return correct answers.

To use the program, first enter the number n. Note: n must be greater than the square of the base or the program will quit with an error. Then for the base, enter the largest prime factor for q. For example, q = 5 will return the correct answer for base 5, 10, 15 and 20 but not 25.

Code:


\<< SWAP OVER I\->BL SWAP \-> q
  \<< SLST\-> 1. - NIP 1 SWAP 2. SWAP
    START q * 1 + ROT OVER * ROT + SWAP
    NEXT DROP
  \>>
\>>

Some notes about the program:

The ListExt command SLST-> is a modified version of OBJ-> for lists which effectively applies NEWOB to every element of the list.

The heart of the program is the phrase q * 1 + which generates successive q-integers (partial sums of the powers of q). This obviates the need to maintain a large list of large integers on the stack.

This program is just as fast as the previous one but still takes over a minute on the physical calculator for 10^1000. EMU48 is your friend here- about 1.5 seconds on my phone.

[John Keith]

Just for laughs, a couple of programs to print large integers as triangles. They are most useful on a PC-based emulator where the resulting string can be pasted into a text file and printed.

The first program makes a triangle where row n has 2n-1 digits, similar to Thomas' Python program if not as elegant. Input is an integer, output is a string centered at the 40th column. Maximum integer size is 1521 digits (39 rows). If the number of digits is not a square, the last row will be incomplete.

Code:


\<< \->STR -1. 40. 13. CHR 10. CHR + \-> k sp crlf
  \<< ""
    WHILE OVER SIZE
    REPEAT 'k' 2. STO+ 'sp' 1. STO-
      SWAP k SPLIT UNROT
      crlf + " " sp RPTCHR SWAP + +
    END NIP
  \>>
\>>

The next version makes a triangle where row n has n digits (like Pascal's triangle). The string is left justified. There is no maximum size but very large integers will make rows longer than 80 characters. If the number of digits is not a triangular number, the last row will be incomplete.

Code:


\<< \->STR 0. 13. CHR 10. CHR + \-> k crlf
  \<< "" SWAP
    WHILE DUP SIZE
    REPEAT 'k' 1. STO+
      k SPLIT UNROT crlf + + SWAP
    END DROP
  \>>
\>>

As an example, this is 570!:


1
19
647
5758
26679
992521
3150971
60611198
503056621
9007683399
48400991237
661587270341
8103894782133
53453090699254
154454320719614
5487509118626349
08696686820305004
379306247797103488
6790434213832213245
94841498332690282044
085187027223617659230
9518428094945979214940
56709685270263887874435
753547709167084262926620
3332741387705148411462271
23095175757304448772093194
373279490301207089965787664
8575127566724513575715482702
70788565544870146828024429021
833502813292623326287501458026
9161119577367392188068125282549
20234801893594111768456673065490
279986528074506746792875128696146
7862034450599336508683729157632623
68712749711136718818742496831196746
909912133660990822097617434066349471
5222497263330885513955829086147220454
59821787316263806805289352977171927611
915931808505004008935038815697112288240
3089565859840019822465218311419147832147
74003130942944407137531510505316475042841
159819848160593032726584717409062104550132
5700007860560251989608104718347968735642475
43983373049782988651222694742053310200491418
863588405480343023964791498461218898945580264
8406113303807150001581953263761718561315680021
38450168036268440168979166079893774258519311891
845963565722703706788257300598498708086057505863
1759757312000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000