84 arithmetic/digits/zeros/trailing.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
84 arithmetic/digits/zeros/trailing.p
How many trailing zeros are in the decimal expansion of n!?
arithmetic/digits/zeros/trailing.s
The general answer to the question
"what power of p divides x!" where p is prime
is (x-d)/(p-1) where d is the sum of the digits of (x written in base p).
So where p=5, 10 is written as 20 and is divisible by 5^2 (2 = (10-2)/4);
x to base 10: 100 1000 10000 100000 1000000 x to base 5: 400 13000 310000 11200000 224000000 d : 4 4 4 4 8 trailing 0s in x! 24 249 2499 24999 249998
arithmetic/magic.squares.p
Are there large squares, containing only consecutive integers, all of whose
rows, columns and diagonals have the same sum? How about cubes?
arithmetic/magic.squares.s
These are called magic squares. A magic square of order n (integers
from 1 to n*n) has only one possible sum: (n*n+1)*n/2.
Odd and even order squares must be constructed by different approaches.
For odd orders, the most common algorithm is a recursive scheme
devised by de la Loubere about 300 years ago. For even orders, one
procedure is the Devedec algorithm, which treats even orders not
divisible by 4 slightly differently from those which are divisible by
4 (doubly even).
For squares with odd-length sides, the following algorithm builds a magic
square:
Put 1 in the middle box in the upper row. From then on, if it's
possible to put the next number one box diagonally up and to the right
(wrapping around if the edge of the grid is reached), do so, otherwise,
put it directly below the last one.
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
...or even
47 58 69 80 1 12 23 34 45
57 68 79 9 11 22 33 44 46
67 78 8 10 21 32 43 54 56
77 7 18 20 31 42 53 55 66
6 17 19 30 41 52 63 65 76
16 27 29 40 51 62 64 75 5
26 28 39 50 61 72 74 4 15
36 38 49 60 71 73 3 14 25
37 48 59 70 81 2 13 24 35
See archive entry knight.tour for magic squares that are knight's tours.
To get a 4x4 square, write the numbers in order across each row, filling
the square...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
then use the following pattern as a mask:
. X X . X . . X X . . X . X X .
Everywhere there is an X, complement the number (subtract it from
n*n+1). For the 4x4 you get:
1 15 14 4 12 6 7 9 8 10 11 5 13 3 2 16
For n even (n>4):
Make an initial magic square by writing an n/2 magic square four times
(the same one each time). Now, although this square adds up right we
have the numbers 1 to n*n/4 written four times each. To fix this,
simply add to it n*n/4 times one of the following magic squares:
if n/2 is odd (example: n/2=7),
3 3 3 0 0 0 0 2 2 2 2 2 1 1 (there are int(n/4) 3s, int(n/4-1) 1s on each 3 3 3 0 0 0 0 2 2 2 2 2 1 1 row) 3 3 3 0 0 0 0 2 2 2 2 2 1 1 0 3 3 3 0 0 0 2 2 2 2 2 1 1 (this is row int(n/4)+1. It starts with just 3 3 3 0 0 0 0 2 2 2 2 2 1 1 the one 0) 3 3 3 0 0 0 0 2 2 2 2 2 1 1 3 3 3 0 0 0 0 2 2 2 2 2 1 1 0 0 0 3 3 3 3 1 1 1 1 1 2 2 (the lower half is the same as the upper half 0 0 0 3 3 3 3 1 1 1 1 1 2 2 with 3<->0 and 1<->2 swapped. This guarantees 0 0 0 3 3 3 3 1 1 1 1 1 2 2 that each number 1-n*n will appear in the 3 0 0 0 3 3 3 1 1 1 1 1 2 2 completed square) 0 0 0 3 3 3 3 1 1 1 1 1 2 2 0 0 0 3 3 3 3 1 1 1 1 1 2 2 0 0 0 3 3 3 3 1 1 1 1 1 2 2
if n/2 is even (example: n/2=4),
0 0 3 3 2 2 1 1 (there are n/4 of each number on each row) 0 0 3 3 2 2 1 1 0 0 3 3 2 2 1 1 0 0 3 3 2 2 1 1 3 3 0 0 1 1 2 2 3 3 0 0 1 1 2 2 3 3 0 0 1 1 2 2 3 3 0 0 1 1 2 2
References:
"Magic Squares and Cubes"
W.S. Andrews
The Open Court Publishing Co.
Chicago, 1908
"Mathematical Recreations"
M. Kraitchik
Dover
New York, 1953
Continue to:
My Books
