Warp schrieb:
>   1) The classical proof that there are infinitely many primes is a proof by
> contradiction: Let's assume that there's a largest prime. If we multiply
> all the primes up to that largest prime and add 1, we get a number which
> is not divisible by any of the primes, and thus the assumption we made is
> false: There was a prime which is larger than the one we assumed was the
> largest.
> 
>   However, consider this: 2*3*5*7*11*13 + 1 = 30031, which is a composite
> number.
> 
>   Isn't this a contradiction to the proof? It clearly doesn't hold that the
> product of the first n primes plus 1 is a prime.
> 
>   How to explain this apparent contradiction?

I didn't verify whether 30031 is indeed composite - but one thing's for 
sure: It is not a multiple of 2, 3, 5, 7, 11 or 13 (I checked :-)). So 
whatever the smallest factor, that's (a) a prime by definition 
(otherwise there would obviously be a smaller factor) and (b) it's 
larger than 13, our "current largest prime". Q.e.d.


>   2) Assume you have an array of 24 integers. Each element of that array
> can get a value between 0 and 7. Thus the total amount of different contents
> for such as an array is 8^24, which is approximately 4*10^21.
> 
>   Now assume that you fill the array with some values and then calculate
> all the possible permutations of that array. The amount of permutations
> for 24 elements is 24!, which is approximately 6*10^23.
> 
>   Now here's the apparent paradox: The total amount of different contents is
> about 4*10^21, and naturally all those permutations should be among them as
> well. How come the total amount of permutations, 6*10^23, is way larger
> than the total amount of possible different array contents?

You used the wrong formula for your permutations, as the one you used 
presumes that all elements are unique.


>   3) Assume two people, person A and person B, who want to decide who gets
> a price by tossing a coin.
> 
>   Person A is a bad loser and a bully, so if he loses he says "I said it's
> two out of three". So they play it like that. If A loses again, he says
> "I said it's three out of five", and so on, until he wins.
> 
>   How many tosses is this game expected to last, in average?

I think that very much depends on whether the sequence is

   1 - 3 - 5 - 7 -  9 - ...

or

   1 - 3 - 5 - 9 - 17 - ...


>   4) By their nature, factorials tend to accumulate trailing zeroes. For
> example, 5! (120) has one trailing zero, 10! (3628800) has two trailing
> zeroes, 25! (15511210043330985984000000) has six trailing zeroes, etc.
> 
>   Give a (non-recursive) mathematical function which, for an integer n,
> gives the number of trailing zeroes in n!.

Obviously, trailing zeros are due to the presence of prime factors 2 and 
5 in the factorial term. As that term is defined recursively as n! = 
(n-1)!*n, n! "inherits" all the prime factors from (n-1)!, additionally 
"injecting" its own prime factors.

We can ignore the factor 2 here, as the prime factor 2 is much more 
frequent than the factor 5, so for every factor of 5 we have ample 
factors of 2 to complement for a factor of 10, and thus a digit.

Any multiple of 5 will therefore "inject" at least one trailing zero.
Any multiple of 5^2 will "inject" an additional trailing zero.
Any multiple of 5^3 will "inject" an additional third trailing zeros.
And so forth.

Thus, the number of trailing zeros can be expressed as:

   floor(n/5) + floor (n/(5^2)) + floor(n/(5^3)) + ...

which is a perfectly valid, non-recursive (albeit infinite) mathematical 
formula for the desired thing. (Unfortunately the floor() function 
complicates matters, otherwise this would be a nice straightforward 
geometric series, and we'd end up with the number of trailing zeros 
being equal to n/4, which is apparently not /quite/ right :-P

Post a reply to this message