home *** CD-ROM | disk | FTP | other *** search
/ Otherware / Otherware_1_SB_Development.iso / mac / misc / math / lifelb21.sit / Hmmm... next >
Encoding:
Text File  |  1990-01-12  |  5.6 KB  |  139 lines
  1.  
  2.             1                                                     rows
  3.       _____________                                           _____________
  4.      |           1 |                                         |       total |
  5.   1  |100        1 |      2                             cols | %    unique |
  6.      |_____________|_____________                            |_____________|
  7.      |           3 |          15 |
  8.   2  | 67        2 | 33        5 |      3
  9.      |_____________|_____________|_____________
  10.      |           7 |          63 |         511 |
  11.   3  | 57        4 | 30       19 | 17       85 |      4
  12.      |_____________|_____________|_____________|_____________
  13.      |          15 |         255 |        4095 |       65535 |
  14.   4  | 47        7 | 24       62 | 22      898 | 12     7625 |      5
  15.      |_____________|_____________|_____________|_____________|_____________
  16.      |          31 |        1023 |       31267 |     1048575 |    33554431 |
  17.   5  | 42       13 | 22      226 | 23     7334 | 22   233185 | 12  3956995 |
  18.      |_____________|_____________|_____________|_____________|_____________|
  19.      |          63 |        4095 |      262143 |             |
  20.   6  | 37       23 | 20      830 | 22    57738 |             |
  21.      |_____________|_____________|_____________|_____________|
  22.      |         127 |       16383 |     2097151 |
  23.   7  | 34       43 | 20     3214 | 22   460474 |
  24.      |_____________|_____________|_____________|
  25.      |         255 |       65535 |             |
  26.   8  | 31       79 | 19    12542 |             |
  27.      |_____________|_____________|_____________|
  28.      |         511 |      262143 |
  29.   9  | 30      151 | 19    49726 |
  30.      |_____________|_____________|
  31.      |        1023 |
  32.  10  | 28      287 |
  33.      |_____________|
  34.      |        2047 |
  35.  11  | 27      559 |
  36.      |_____________|
  37.      |        4095 |
  38.  12  | 27     1087 |
  39.      |_____________|
  40.      |        8191 |
  41.  13  | 26     2143 |
  42.      |_____________|
  43.      |       16383 |
  44.  14  | 26     4223 |
  45.      |_____________|
  46.      |       32767 |
  47.  15  | 26     8383 |
  48.      |_____________|
  49.      |       65535 |
  50.  16  | 25    16639 |
  51.      |_____________|
  52.      |      131071 |
  53.  17  | 25    33151 |
  54.      |_____________|
  55.      |      262143 |
  56.  18  | 25    66047 |
  57.      |_____________|
  58.  
  59. Let U equal the number of unique patterns in a 1*n rectangle.
  60. By representing patterns as binary numbers we can eliminate translations
  61. (they are simply all the even numbers) and reflections (half the asymmetric
  62. odd numbers) and so derive:
  63.  
  64.    U = 2^(n-2) + 2^(n/2) - 1         for even n >= 2
  65.      = 2^(n-2) + 3*2^((n-3)/2) - 1   for odd n >= 1
  66.  
  67. For a 1*n rectangle the unique/total ratio approaches 25% as n increases.
  68. Proof: 2^(n-2) = 1/4 of 2^n, and since the total number of patterns = (2^n)-1
  69. then U/total approaches 1/4 because 2^n grows more rapidly than the other terms.
  70.  
  71. The above expressions for U have been verified by LifeLab for n = 1 to 18.
  72. Conjecture: U is either prime or the product of two primes!?
  73. NO; see n = 28 and 29.
  74.  
  75.     n           U
  76.     1           1   prime
  77.     2           2   prime
  78.     3           4   2 * 2
  79.     4           7   prime
  80.     5          13   prime
  81.     6          23   prime
  82.     7          43   prime
  83.     8          79   prime
  84.     9         151   prime
  85.    10         287   7 * 41
  86.    11         559   13 * 43
  87.    12        1087   prime
  88.    13        2143   prime
  89.    14        4223   41 * 103
  90.    15        8383   83 * 101
  91.    16       16639   7 * 2377
  92.    17       33151   prime
  93.    18       66047   prime
  94.    19      131839   prime
  95.    20      263167   prime
  96.    21      525823   191 * 2753
  97.    22     1050623   7 * 150089
  98.    23     2100223   59 * 35597
  99.    24     4198399   1399 * 3001
  100.    25     8394751   19 * 441829
  101.    26    16785407   prime
  102.    27    33566719   prime
  103.    28    67125247   7 * 7 * 23 * 59561
  104.    29   134242303   13 * 179 * 57689
  105.    30   268468223   15913 * 16871
  106.    31   536920063   2371 * 226453
  107.    32  1073807359   prime
  108.  
  109. Dean Hickerson came up with the explanation for why primes occur
  110. so frequently in the above table:
  111.  
  112. By the prime number theorem, the probability
  113. that a number near U(1x32)  (about 10^9) is prime is about 1/ln(10^9),
  114. which is about 1/20.  But it's easy to see that U(1xn) is never divisible
  115. by 2, 3, or 5 for n>3.  That raises the probability of its being prime by a
  116. factor of 2/1 * 3/2 * 5/4 = 15/4, so the probability is now about 1/5.  For
  117. smaller numbers, the probability is even higher, so the large number of
  118. primes in your list isn't surprising.
  119.  
  120. In fact we can go even further.  Consider the case when n is even.  Then
  121. U(1xn) = x^2 - 2, where x = 1 + 2^(n/2 - 1).  So if p is a prime divisor
  122. of U(1xn), then 2 must be a quadratic residue of n, which means that
  123. p is congruent to 1 or 7 mod 8.  And not even all such primes can occur;
  124. e.g. 17 does not, since if x^2 is congruent to 2 mod 17 then x is 6 or 11
  125. mod 17 and x - 1 = 2^(n/2 - 1) is 5 or 10 mod 17.  But the residues mod 17
  126. of powers of 2 run through the cycle 1, 2, 4, 8, 16, 15, 13, 9, 1, 2, ...
  127. So with so many possible prime divisors excluded, the probability of
  128. primality for U(1xn) must be much larger than for a random integer about
  129. the same size.  I don't see how to estimate what percentage of primes are
  130. excluded from being divisors, so I don't know how to give even a heuristic
  131. asymptotic formula for the number of primes among U(1x2), U(1x4), ...,
  132. U(1 x 2n).
  133.  
  134. Similarly, if n is odd, then 8 * U(1xn) = x^2 - 17, where
  135. x = 3 + 2^((n+1)/2).  So if p is a prime divisor then 17 is a quadratic
  136. residue of p; hence p is congruent to 1, 9, 13, 15, 19, 21, 25, or 33
  137. mod 34.  So again half of all primes are excluded immediately and even
  138. more when we use the fact that x-3 is a power of 2.
  139.