 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> 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?
The answer lies (as I look at that bit of the wikipedia article on
primes) in that there exists a prime smaller than 30031 by which it's
divisible that's also larger than 13, so 13 isn't the largest prime.
> 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?
The total amount of permutations doesn't consider duplicate cell values.
It treats 77 and 77 (with the 7s being swapped) as two different numbers.
--
Tim Cook
http://empyrean.freesitespace.net
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I got 1, but I had to factor 30,031 before I got it.
Permutations and combinations make my eyes go wonky, so I have pass on 2.
I quite know what's meant in 3 by an "average", unless it's the convergence
of a series; not sure if I have that one or not.
As for 4, I'm stumped. :)
Thanks for the fun though... must get back to work now.
"Warp" <war### [at] tag povrayorg> wrote in message
news:4ab90520@news.povray.org...
> Some relatively easy math problems for your consideration and enjoyment:
>
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 22-9-2009 19:10, Warp wrote:
> Some relatively easy math problems for your consideration and enjoyment:
>
>
> 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?
The claim is not that the products of primes plus one is a prime, just
that it has a prime divisor that is not one in the product.
> 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?
8 is less than 24
> 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?
same answer as: what will the average number if boys be if every pair of
parents continues getting children untill they get a boy. (assuming 50%
chance of a boy, which is not exactly correct, and that every pair that
gets one child can in principle get an infinite number)
> 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!.
just count the number of 5s, 25s, 125s etc
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 22-9-2009 21:20, andrel wrote:
>> 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!.
>
> just count the number of 5s, 25s, 125s etc
BTW I did write a quick and dirty arbitrary precision integer thing to
compute some factorials. I saw the answer before actually having to use
it, but here is 100!:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
in case you wanted to know.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
andrel <a_l### [at] hotmailcom> wrote:
> > 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?
> 8 is less than 24
So? How does that answer the question?
> > 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?
> same answer as: what will the average number if boys be if every pair of
> parents continues getting children untill they get a boy.
It isn't. It would be if the game would have been "we throw the coin
until it gives heads". However, that's not how the game goes.
> > 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!.
> just count the number of 5s, 25s, 125s etc
Firstly, the question didn't ask for an algorithm to calculate the number
of zeros (which is what the "non-recursive" part more or less rules out).
It asked for a closed-form function which tells the number of zeros.
Secondly, your algorithm is flawed. 10! has two zeros and only one 5 as
a factor.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 09/22/09 12:10, Warp wrote:
> 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!.
For a tougher problem, estimate the number of digits in n!
(Well, easy if you know one certain piece of information...).
--
I think animal testing is a terrible idea. They get all nervous and give
the wrong answers.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 22-9-2009 21:58, Warp wrote:
> andrel <a_l### [at] hotmailcom> wrote:
>>> 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?
>
>> 8 is less than 24
>
> So? How does that answer the question?
that is obvious, I would think.
>>> 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?
>
>> same answer as: what will the average number if boys be if every pair of
>> parents continues getting children until they get a boy.
>
> It isn't. It would be if the game would have been "we throw the coin
> until it gives heads". However, that's not how the game goes.
Ok I read that wrong. Can you give an algorithm for 'and so on'?
1 2 3 4 5..
- - - - -
2 3 5 8 13...
or
1 2 3 4 5 ..
- - - - -
2 3 5 7 11...
or
?
>>> 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!.
>
>> just count the number of 5s, 25s, 125s etc
>
> Firstly, the question didn't ask for an algorithm to calculate the number
> of zeros (which is what the "non-recursive" part more or less rules out).
> It asked for a closed-form function which tells the number of zeros.
>
> Secondly, your algorithm is flawed. 10! has two zeros and only one 5 as
> a factor.
No it has 2 both 10 and 5 have a factor of 5. So if you want your
algorithm:
sum_k floor(x/(5^k)) over all k from 1 till 5^k<=x
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka wrote:
> Warp schrieb:
>> 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 - ...
>
>
I didn't look at the other puzzles, but this one sounds easy enough to
work with before sleep.
First round, A claims 'heads I win' so could win 50% of the time.
Each time B gets a tail flip, A increments how many are needed to win.
Best N out of 2N-1.
Okay, A stands to win first round 50% of the time.
Second round, A can not win because he obviously lost first round.
Third round, A has a remaining 50% chance to win if he won either
previous, a 0 if not.
Just going on brain alone, and barely any of that since it is late here.
But it seems that if the game progresses past the first round, it has a
high chance of going on forever. Same for any of the loss points after
that. Average of 1 + infinity is somewhat closer to infinity than to
one. I would say the game in unwinnable.
The other option is that Player B just needs to punch A, take the coin
and walk away. At least he wins a coin, this way.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> 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!.
>
I think I have a numerical solution, but I do not have the formulas to
write the equation. Yet. . .
What you are interested in is the number of numbers, less than n, that
end in 5, or 0. Five times any even number will result in a multiple of
10 and have add zero at the end. All factorials after 2! are even, given
that 2 is even and they are all multiplied by 2 by recursion.
So, to solve for the number of integers that are multiples of 10, X =
floor(N/10), but save the remainder of N/10 as R. Y, the number of
integers <N ending in 5s, can be gotten via R. Y = floor(R/5)+X. Number
of zeros would be X + Y.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
