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.]
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.
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.
N 2 2 - 7 = Xwas 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.
N N (1 + sqrt(2)) + (1 - sqrt(2)) = integer (by induction); N the (1 - sqrt(2)) goes to zero.
(ln 2)/(ln 3) N .
0 1 16 81 256 625 1 15 65 175 369 14 50 110 194 36 60 84 24 24 0so 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%.
1 4 16 64 256 3 12 48 192 9 36 144 27 108 81In 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, ... .
SUB-PROBLEM: How many sequence exist for any particular length?
N ==== \ L N + 1 N + 1 L > BINOMIAL(N + L, L) ((1 - X) X + (1 - X) X ) = 1 / ==== L = 0set 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?
(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.
(A,B,C,...) = (A+B,C,...)(A,B) = (A+B+C,...)(A,B,C) = ...
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.
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 = --------- , NN covering all integers. Primes with 2 sub-cycles seem to have lengths
M prime - (-1) L = ------------- , MM 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 SR 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 Yseems to express those which are 9 mod 40;
2 2 (10 X +- 1) + 400 Yseems 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?
3 17 18 19 7 1 11 16 2 5 6 9 12 4 8 14 10 13 15First 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.
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
COROLLARY: There is no magic tesseract of order 5.
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.
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.
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,929Also, 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.
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:
3 3 3 3 3 + 4 + 5 = 6 .
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
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
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
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.