Beeler, M., Gosper, R.W., and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb. 29, 1972. Retyped and converted to html ('Web browser format) by Henry Baker, April, 1995.

NUMBER THEORY, PRIMES, PROBABILITY

Previous Up Next

ITEM 28 (Schroeppel):

After about 40 minutes of run time to verify the absence of any non-trivial factors less than 235, the 125th Mersenne number, 
 125
2    - 1,
was factored on Tuesday, January 5, 1971, in 371 seconds run time as follows: 
 125
2    - 1 = 31 * 601 * 1801 * 269,089,806,001 * 4,710,883,168,879,506,001.
John Brillhart at the University of Arizona had already done this. M137 was factored on Friday, July 9, 1971 in about 50 hours of computer time: 
 137
2    - 1 = 32,032,215,596,496,435,569 * 5,439,042,183,600,204,290,159.
[Current prime records -- H.B.]

ITEM 29 (Schroeppel):

For a random number X, the probability of its largest prime factor being
  1. greater than sqrt(X)=X^(1/2) is ln 2.
  2. less than X^(1/3) is about 4.86%.
This suggests that similar probabilities are independent of X; for instance, the probability that the largest prime factor of X is less than X^(1/20) may be a fraction independent of the size of X.

RELEVANT DATA: ([] denote the expected value of adjacent entries.) 

RANGE            COUNT          CUMULATIVE SUM OF COUNT
10^12 to 10^6    7198 [6944]    10018
10^6 to 10^4     2466           2820
10^4 to 10^3     354            402 [487]
10^3 to 252      40             48      ;252 = 10^2.4
252 to 100       7              8
100 to 52        1              1       ;52 = 10^1.7
51 to 1          0              0
where:

"COUNT" is the number of numbers between 10^12 + 1 and 10^12 + 10018 whose largest prime factor is in "RANGE". The number of primes in 10^12 + 1 to 10^12 + 10018 is 335; the prime number theorem predicts 363 in this range. This is relevant to Knuth's discussion of Legendre's factoring method, vol. 2, p. 351-354.

ITEM 30 (Schroeppel):

Twin primes: The number 166,666,666,666,667 is prime, but 166,666,666,666,669 is not.

The primes which bracket 10^12 are 10^12 + 39 and 10^12 - 11.

The primes which bracket 10^15 are 10^15 + 37 and 10^15 - 11.

The number 23,333,333,333 is prime.

Various primes, using T = 10^12, are:

40 T + 1, 62.5 T + 1, 200 T - 3, 500 T - 1, 500 T - 7.

ITEM 31 (Schroeppel):

Ramanujan's problem of solutions to 
 N        2
2  - 7 = X
was searched to about N = 10^40; only his solutions (N = 3, 4, 5, 7, 15) were found. It has recently been proven that these are the only ones. Another Ramanujan problem: Find all solutions of n! + 1 = x^2.

ITEM 32 (Schroeppel):

Take a random real number and raise it to large powers; we expect the fraction part to be uniformly distributed. Some exceptions:
  1. phi = (1 + sqrt(5))/2
  2. all - 1 < X < 1
  3. sqrt(2) (half are integers, other half are probably uniformly distributed)
  4. 1 + sqrt(2) -- Proof: 
                 N                N
(1 + sqrt(2))  + (1 - sqrt(2))  = integer (by induction);

                 N
the (1 - sqrt(2))  goes to zero.
  5. 2 + sqrt(2) -- similar to 1 + sqrt(2)
  6. any algebraic number whose conjugates are all inside the unit circle
Now, 3 + sqrt(2) is suspicious; it looks non-uniform, and seems to have a cluster point at zero. PROBLEM: Is it non-uniform?

ITEM 33 (Schroeppel):

Numbers whose right digit can be repeatedly removed and they are still prime: CONJECTURE: There are a finite number of them in any radix. In decimal there are 51, the longest being 1,979,339,333 and 1,979,339,339.

ITEM 34 (Schroeppel):

PROBLEM: Can every positive integer be expressed in terms of 3 and the operations factorial and integer square root? E.g., 5 = sqrt(sqrt(3!!)).

ITEM 35 (Schroeppel):

Take as many numbers as possible from 1 to N such that no 3 are in arithmetic progression. CONJECTURE: As N - > infinity, the density of such sets approaches zero, probably like 
 (ln 2)/(ln 3)
N             .
Conjecture that XX.XX just keeps getting copied. If the N^[(ln 2)/(ln 3)] can be proved, it follows that there are infinitely many primes P1, P2, P3 in arithmetic progression, since primes are much more common than N^[(ln 2)/(ln 3)].

ITEM 36 (Schroeppel):

PROBLEM: How many squares have no zeros in their decimal expression? Ternary?

ITEM 37 (Gosper):

The number of n digit strings base B in which all B digits occur at least once is just the Bth forward difference at 0 of the nth powers of 0, 1, ... . E.g., for n = 4: 
  0     1     16    81   256   625
     1     15    65   175   369
        14    50   110   194
           36    60    84
              24    24
                  0
so there are 14 (= 2^4 - 2) such 4-bit strings, 36 such 4-digit ternary strings, 24 (= 4!) such quaternary, and 0 for all higher bases. 27 (= 10e?) random decimal digits are required before it is more likely than not that every digit has occurred; with 50 digits the likelihood is 95%.

ITEM 38 (Fredkin):

By the binomial theorem, the bth forward difference at 0 of the 0, 1, 2, ... powers of n is (n-1)^b. E.g., for n = 4: 
  1     4    16    64   256
     3    12    48   192
        9    36   144
          27   108
             81
In fact, any straight line with rational slope through such an array will always go through a geometric sequence with common ratio of the form n^a (n-1)^b. In the above, east by southeast knight's moves give the powers of 12: 1, 12, 144, ... .

ITEM 39 (Schutzenberger):

PROBLEM: Using N digits, construct a string of digits which at no time has any segment appearing consecutively twice. Determine maximum string length for N = 3.

SUB-PROBLEM: How many sequence exist for any particular length?

ITEM 40 (Gosper):

The variance of a pseudo-Gaussian distributed random variable made by adding T independent, uniformly distributed random integer variables which range from 0 to N-1, inclusive, is T((N^2 - 1)/12).

ITEM 41 (Salamin):

There are exactly 23000 primes less than 2^18.

ITEM 42 (Gosper):

To show that 
   N
  ====
  \                                L  N + 1          N + 1  L
   >    BINOMIAL(N + L, L) ((1 - X)  X      + (1 - X)      X ) = 1
  /
  ====
  L = 0
set N to 20 and observe that it is the probability that one or the other player wins at pingpong. (X = probability of first player gaining one point, L = loser's score, deuce rule irrelevant.) If this seems silly, try more conventional methods.

PROBLEM: If somehow you determine A should spot B 6 points for their probabilities of winning to be equal, and B should spot C 9 points, how much should A give C?

ITEM 43 (Schroeppel):

Let (A, B, C, ...) be the multinomial coefficient 
(A + B + C....)!
----------------
  A! B! C! ...
This is equal modulo the prime p to 
(A0, B0, C0...) (A1, B1, C1...) (A2, B2, C2...)...
where AJ is the Jth from the right digit of A base p.

Thus BINOMIAL(A+B, A) mod 2 is 0 iff (AND A B) is not.

The exponent of the largest power of p which divides (A, B, C,...) is equal to the sum of all the carries when the base p expressions for A, B, C, ... are added up.

ITEM 44 (Gosper):

Recurrences for multinomial coefficients:

(A,B,C,...) = (A+B,C,...)(A,B) = (A+B+C,...)(A,B,C) = ...

PROBLEM 45 (Gosper):

For what initial heading angles is your locus bounded?

PARTIAL ANSWER (Schroeppel, Gosper): When the initial angle is a rational multiple of pi, it seems that your locus is bounded (in fact, eventually periodic) iff the denominator contains as a factor the square of an odd prime other than 1093 and 3511, which must occur at least cubed. (This is related to the fact that 1093 and 3511 are the only known primes satisfying 

 P          2
2  = 2 mod P ).
But a denominator of 171 = 9 * 19 never loops, probably because 9 divides phi(19). Similarly for 9009 and 2525. Can someone construct an irrational multiple of pi with a bounded locus? Do such angles form a set of measure zero in the reals, even though the "measure" in the rationals is about .155? About .155 = the fraction of rationals with denominators containing odd primes squared = 1 - product over odd primes of 1 - 1/P(P + 1). This product = .84533064 +- a smidgen, and is not, alas, sqrt(pi/2) ARCERF(1/4) = .84534756. This errs by 16 times the correction factor one expects for 1093 and 3511, and is not even salvaged by the hypothesis that all primes > a million satisfy the congruence. It might, however, be salvaged by quantities like 171.

ITEM 46 (Schroeppel):

The most probable suit distribution in bridge hands is 4-4-3-2, as compared to 4-3-3-3, which is the most evenly distributed. This is because the world likes to have unequal numbers: a thermodynamic effect saying things will not be in the state of lowest energy, but in the state of lowest disordered energy.

ITEM 47 (Beeler):

The Fibonacci series modulo P has been studied. This series has a cycle length L and within this cycle has sub-cycles which are bounded by zero members.

The length of powers of primes seems to be 

                             power-1
L = (length of prime) * prime       .
The length of products of powers of primes seems to be

L = least common multiple of lengths of powers of primes which are factors.
There can be only 1, 2, or 4 sub-cycles in the cycle of a prime.

Primes with 1 sub-cycle seem to have lengths 

     prime - 1
L =  --------- ,
         N
N covering all integers. Primes with 2 sub-cycles seem to have lengths 
                 M
     prime - (-1) 
L =  ------------- ,
          M
M covering all integers except of form 10 K + 5.

Primes with 4 sub-cycles seem to always be of form 4 K + 1, and seem to have lengths 

      prime + 1    prime - 1
L =   --------- or --------- ,
          R            S
R covering all integers of form 10 K + 1, 3, 7 or 9; S covering all integers.

At Schroeppel's suggestion, the primes have been separated mod 40, which usually determines their number of sub-cycles: 

PRIME mod 40    SUB-CYCLES
1, 9    usually 2, occasionally 1 or 4 (about equally)
3, 7, 23, 27    2
11, 19, 31, 39  1
13, 17, 33, 37  4
21, 29          1 or 4 (about equally)
2 (only 2)      1
5 (only 5)      4
Attention was directed to primes which are 1 or 9 mod 40 but have 1 or 4 subcycles. 
    2       2
25 X  + 16 Y
seems to express those which are 9 mod 40; 
           2        2
(10 X +- 1)  + 400 Y
seems to express those which are 1 mod 40.

PROBLEM: Can some of the "seems" above be proved? Also, can a general test be made which will predict exact length for any number?

ITEM 48 (Gosper, Schroeppel):

A point of the 2 dimensional lattice is called visible iff its coordinates are relatively prime. The invisible 2 by 2 square with smallest X has its near corner on (14,20). (I.e., (14,20), (15,20), (14,21), and (15,21) are all invisible.) The corresponding 3 by 3 is at (104,6200). By the chines remainder theorem, there exist invisible sets of every finite shape. Excellent reference: Amer. Math. Monthly, May '71, p487.

ITEM 49:

There is a unique "magic hexagon" of side 3: 
     3  17  18
  19   7   1  11
16   2   5   6   9
  12   4   8  14
    10  13  15
First discovered by Clifford W. Adams, who worked on the problem from 1910. In 1957, he found a solution. (See Aug. 1963 Sci. Am., Math. Games.) Other length sides are impossible.

ITEM 50 (Schroeppel):

There is no magic cube of order 4.

Proof: Let K (= 130) be the sum of a row.

Lemma 1: In a magic square of order four, the sum of the corners is K.

Proof: Add together each edge of the square and the two diagonals. This covers the square entirely, and each corner twice again. This adds to 6 K, so twice the corner sum is 2 K.

Lemma 2: In a magic cube of order 4, the sum of any two corners connected by an edge of the cube is K/2.

Proof: Call the corners a and b. Let c, d and e, f be the corners of any two edges of the cube parallel to ab. Then abcd, abef, and cdef are all the corners of magic squares. So a+b+c+d + a+b+e+f + c+d+e+f = 3K; a+b+c+d+e = 3K/2; a+b = K/2.

Proof of magic cube impossibility: Consider a corner x. There are three corners connected by an edge to x.

Each must have value K/2 - x. QED

ITEM 51 (Schroeppel):

By similar reasoning, the center of an order 5 magic cube must be 63 = K/5.

COROLLARY: There is no magic tesseract of order 5.

ITEM 52 (Salamin):

The probability that two random integers are relatively prime is 6/pi^2.

PSEUDO-PROOF: Let X be the probability. Let S be the set of points in the integer lattice whose coordinates are relatively prime, so that S occupies a fraction X of the lattice points. Let S(D) be the set of points whose coordinates have a GCD of D. S(D) is S expanded by a factor of D from the origin. So S(D) occupies a fraction X/D^2 of the lattice, or the probability that two random integers have a GCD of D is X/D^2. If D unequals D', then S(D) intersect S(D') is empty, and union of all S(D) is the entire lattice. Therefore X*(1/1^2+1/2^2+1/3^2+...) = 1, so X = 6/pi^2. This argument is not rigorous, but can be made so.

ITEM 53 (Salamin):

The probability that N numbers will lack a Pth power common divisor is 1/zeta(NP).

ITEM 54 (Salamin & Gosper):

The probability that a random rational number has an even denominator is 1/3.

ITEM 55 (Schroeppel): GAUSSIAN INTEGERS

See following illustrations; also PI section.

Figure 1(a). This diagram is to substantiate the claim that every Gaussian integer has a unique bit combination. Running through bit combinations 0, 1, 10, 11, ..., the diagram is a map of values, radix i-1. The origin is circled; the dot is at the 127th combination (1111111 = 2 + 5i), which is merely the last point drawn.

Figure 1(b). As 1(a), but radix i+1. Large circle is origin. Dashes indicate continuity of curve at confusing places. Dotted curve is with an infinity of ones to the left (big dot = ...1111 = i). The solid and dotted curves are symmetrical about the point marked with a small circle.

Figure 2. Similar to 1(a), but showing fraction parts as well. Reprinted by special permission from Knuth, The Art of Computer Programming, Volume 2, Seminumerical Algorithms, 1969, Addison-Wesley, Reading, Mass.

ITEM 56 (Beeler):

The "length" of an N-digit decimal number is defined as the number of times one must iteratively form the product of its digits until one obtains a one-digit product (see Technology Review Puzzle Corner, December 1969 and April 1970). For various N, the following shows the maximum "length", as well as how many distinct numbers (permutation groups of N digits) there are: 
 N     MAX L     DISTINCT
 2       4           54
 3       5          219
 4       6          714
 5       7        2,001
 6       7        5,004
 7       8       11,439
 8       9       24,309
 9       9       48,619
10      10       92,377
11      10      167.959
12      10      293,929
Also, for N = 10, 11 and 12, a tendency for there to be many fewer numbers of "length" = 7 is noted. Other than this, the frequency of numbers of any given N, through N = 12, decreases with increasing "length", CONJECTURE (Schroeppel): No L > 10.

ITEM 57 (Beeler, Gosper):

There is at least one zero in the decimal expression of each power of 2 between 
 86                                           30739014
2   = 77,371,252,455,336,267,181,195,264 and 2        ,
where the program was stopped. If digits of such powers were random, the probability that there is another zeroless power would be about 1/10^411816. Assuming there aren't any raises the question:

How many final nonzero digits can a power of two have?

ANSWER (Schroeppel): Arbitrarily many. If we look at the last n digits of consecutive powers of 2, we see:

  1. None end in zero.
  2. After the nth, they are all multiples of 2^n.
  3. They get into a loop of length 4 * 5^(n-1). (Because 2 is a primitive root of powers of 5.)
But there are only 4 * 5(n-1) multiples of 2^n which don't end with zero and are < 10^n, so we will see them all. In particular, we will see the one composed entirely of 1's and 2's, which ends ...11112111211111212122112.

ITEM 58 (Fredkin):

 3    3    3    3
3  + 4  + 5  = 6 .

ITEM 59 (Schroeppel):

                                               2
91038 90995 89338 00226 07743 74008 17871 09376  =

82880 83126 51085 58711 66119 71699 91017 17324
91038 90995 89338 00226 07743 74008 17871 09376

ITEM 60 (Beeler):

If S = the sum of all integers which exactly divide N, including 1 and N, then "perfect numbers" are S = 2 N; the first three numbers which are S = 3 N are: 
           3
    120 = 2  * 3 * 5 = 1111000 base 2

           5
    672 = 2  * 3 * 7 = 1010100000 base 2

           9
523,776 = 2  * 3 * 11 * 31 = 1111111111000000000 base 2

ITEM 61 (Root):

Consider iteratively forming the sum of the factors (including 1 but not N) of a number N. This process may loop; "perfect numbers" are those whose loop is one member, N. For example, N = 28 = 1 + 2 + 4 + 7 + 14. An example of a two-member loop is: Two-member loops are called "amicable pairs."

A program to search for loops of length > 2, all of whose members are < 6,600,000,000 found the known loops of length 5 (lowest member is 12496) and 28 (lowest member is 14316), but also 13 loops of 4 members (lowest member is given): 

  1,264,460 = 2^2 * 5 * 17 * 3,719
  2,115,324 = 2^2 * 3^2 * 67 * 877
  2,784,580 = 2^2 * 5 * 29 * 4,801
  4,938,136 = 2^3 * 7 * 109 * 809
  7,169,104 = 2^4 * 17 * 26,357
 18,048,976 = 2^4 * 11 * 102,551
 18,656,380 = 2^2 * 5 * 932,819
 46,722,700 = 2^2 * 5^2 * 47 * 9,941
 81,128,632 = 2^3 * 13 * 19 * 41,057
174,277,820 = 2^2 * 5 * 29 * 487 * 617
209,524,210 = 2 * 5 * 7 * 19 * 263 * 599
330,003,580 = 2^2 * 5 * 16,500,179
498,215,416 = 2^3 * 19 * 47 * 69,739

ITEM 62 (Speciner):

The first four perfect numbers are 6, 28, 496, 8128.

Two-member loops (amicable pairs) are: 

   220 <-> 284
  1184 <-> 1210
  2620 <-> 2924
  5020 <-> 5564
  6232 <-> 6368
 10744 <-> 10856
 12285 <-> 14595
 17296 <-> 18416
 63020 <-> 76084
 66928 <-> 66992
 67095 <-> 71145
 69615 <-> 87633
 79750 <-> 88730
100485 <-> 124155
122265 <-> 139815
122368 <-> 123152
141644 <-> 153176
142310 <-> 168730
171856 <-> 176336
176272 <-> 180848
185368 <-> 203432
196724 <-> 202444
(Exhaustive to smaller member <= 196724 and larger member < 2^35.)

A prime decade is where N+1, N+3, N+7 and N+9 are all prime. The first occurrence of two prime decades with the theoretical minimum separation is N = 1006300 and N = 1006330. The 335th prime decade is N = 2342770. There are 172400 primes < 2342770.

ITEM 63 (Schroeppel, etc.):

The joys of 239 are as follows:

# Actually, this statement was not correct, even in 1972. Many thanks to these sharp-eyed Netizens of sci.math -- kfoster@rainbow.rmii.com (Kurt Foster) 4-Nov-1996, rawling@erols.com (Mark Rawlings) 4-Nov-1996, Dan Shanks ~1972 [according to rcs@cs.arizona.edu (Richard Schroeppel)] -- for pointing out that 

M239 = 2^239 - 1
     = 479 * 1913 * 5737 * 176383 * 134000609
           * 7110008717824458123105014279253754096863768062879.
The "factor()" command of the incredible "PARI-GP" program reproduced the above factorization in 50 seconds on a lowly 68030 processor without a floating point unit. The PARI-GP program is by C. Batut, D. Bernardi, H. Cohen, and M. Olivier of 
Laboratoire A2X, Universite Bordeaux I
351 Cours de la Liberation
33405 TALENCE Cedex, FRANCE
pari@math.u-bordeaux.fr
ftp://megrez.math.u-bordeaux.fr/pub/pari/

Previous Up Next