I draw numbers 1 through k (k≤10) out of a hat ten times at random, replacing the numbers after drawing them. If I disregard the case where I draw "1" all ten times, explain why the number of possible sequences is divisible by 11. (Result by a calculator is insufficient because anyone can do that easily.)
Now if I change the number '10' to another integer n in the above paragraph, can I still have a similar result; i.e., the total possible number of configurations is divisible by n+1? Does this work for all integers n? If so, prove it; if not, find all integers n it works for.
(In reply to
almost solution by Charlie)
It seems like we can then test for primality using the basic algorithm
of your program. Your program will say that n+1=561 (the smallest
Carmichael number) doesn't work. And raising to the nth power
can be speeded up by expressing n in binary and doing repeated
squaring. This will still be a very "slow" algorithm, however, but
would seem to be 100% accurate. (There is a recently discovered
fast algorithm for primality testing that has been in the news, as many
readers realize, no doubt.)
Edited on September 4, 2006, 3:32 pm

Posted by Richard
on 20060904 13:25:54 