|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |