You can find primes with really short Fibonacci periods by factoring Fibonacci numbers. Fib25 = 75025 = 5 * 5 * 3001 Fib26 = 121393 == 1353 (mod 3001) == I == sqrt(-1) (mod 3001) so the full period for P=3001 is 4*25 = 100. There's a fairly strong analogy between Fibonaccis and Mersennes, so there's likely a Wieferich phenomenon for Fibonaccis. (1093^2 | M1092, and 3511^2 | M3510, and 11^2 | 3^10-1.) ---- I recently read about a new test for AIDS. It detects something about the actual virus -- its DNA or proteins -- whereas older tests detect antibodies. The new test detects an infection earlier than the antibody tests. The drawback is that the new test is expensive. One use of the test is confirm negative results from the older tests: A group of samples, from people who are older-test-negative, is mixed together for a run of the new expensive test. If the new test reports negative, all is well; if positive, then a series of retests & eliminations follows to locate the true positives. I've oversimplified this into a math problem. Even listing the oversimplifications would take a page, so I won't. Here's the "ORed Testing Problem": Assume you have some number of people, each independently likely to have property A with probability P. Property A does not change with time. A perfectly accurate test is available for property A, and it can operate on any set of one or more combined samples, and report either Negative (none of the samples in the test run has property A) or Positive (at least one sample has property A). Each run of the test costs $1, no matter how many samples are pooled for the run. Each person will provide however many samples are needed, and all samples from the same person produce the same result. There is no other test for property A. The goal is to determine each person's property A status, with an (expected) minimum total cost. The best strategy depends on P. If P is near 1, there's no point in doing any combined tests, since they will almost always be positive. Each person must be tested individually. But if P is small, there's an advantage to combining samples. An entire group can be tested at once, and there's a good chance they are all negative. In this case we get a total cost of only $1, saving $N-1 over the cost of individual tests. For two people, it turns out that a merged test is optimal when P < .382 = 2-phi = phi^-2. I started working on the three-person case, but it turned into an algebra morass. The best strategy needs to be calculated for the situations where you know that 1) the merged group XYZ is positive; 2) the merged pair XY is positive, and nothing is known about Z; 3) the merged pairs XY and XZ are positive; 4) the merged pairs XY, XZ, and YZ are positive; 5) nothing is known; 6) the merged pair XY is positive and Z's status is settled. The available inferences are pretty simple. A negative test applies to everyone in the merged sample, and deletes them from any positive groups. An individual may be determined positive if they are they only one left in a positive group test, or in the limiting case of an individual test. A positive test for a group G superannuates any previous test for a supergroup of G, including the case where G is a singleton. Hilarie suggested a first cut at a strategy for small P and a large group: Calculate the number of samples to merge so as to make the probability for a positive test about 50:50, and test subgroups of that size. Anyone in a positive group has his probability adjusted upward for the next round. Randomize the positive subgroups for the next round, and retest with the smaller subgroups based on the revised probabilities. Etc. Rich rcs@cs.arizona.edu