8. Repeat A Question - Power of the Internet

A number growing in size (placing one grain on the first square of a chessboard, doubling the grains on each sucessive square) is a concept that over centuries formed some key mathematical ideas (infinity, infinite series). Today the Internet fosters rapid communication. People can jointly discuss an issue using the world's computers. This has been going on since a visit to UCLA by UCSD Prof. R. Graham May 21, 1999. Here is a general view of that discussion.

There was an open problem when this was initiated on June 24, 1999. It was to find n, a second integer greater than one, with the property (8.1) that when 2 is raised to it and 3 is taken away from the result, the answer is evenly divisible by the n value. What was known is that the value 4700063497 does this. In other words 24700063497-3 is an integer times 4700063497.

Electronic mail (email) communication put this problem to this page's author. Inquiry by email led a correspondent suggesting listing the problem. Posting it to an email list on number theory led to at least four people sending informative messages in hours. This note continues the fact-seeking process through the Internet. (Informative email continues to arrive.) A recent message included: "D.H. Lehmer found such an n. Look at Mathematics of Computation about 10 years ago. ..." Since then more has been done.

Computer-communications stimulate learning about individuals involved in such work. [Related items are in mathematical books.]

Any n satisfying the property (8.1) must be odd. (Since the minus three causes the expression to be odd. No even number can exactly divide an odd.) That a solution can't be a multiple of three (substitute n=3k, find that for the property to be satisfied 3 has to evenly divide a power of 2 ... which is impossible), nor in several other families of integers is also known. UCLA Prof. E. Koutsoupias pointed out July 1, 1999 that Fermat's Little Theorem eliminates the possibility that such an n would be a prime.

This property written concisely in mathematical notation is:

n|[(2n)-3] (8.1)

Experts: Peter Montgomery wrote This is problem F10 in the 1981 Edition of Richard K. Guy's Unsolved Problems in Number Theory. He gives the solution 4700063497 = 19 * 47 * 5263229.
To refer to it later we write:
4700063497 = 19 * 47 * 5263229 (8.2)
June 11, 1999 Joe Crump pointed out that Number Sequences is an available resource and (8.2) appears in List [list begins a(1) = 1].
On June 24, 1999 Dr. Montgomery conveyed this number to me by electronic mail:

63130707451134435989380140059866138830623361447484274774099906755 (8.3)

On June 29, 1999 he stated that this solves the problem. He used a computer program Prof. Noam Elkies mentioned on June 5, 1999. Using sources detailed in Computations, items others sent me by email, I was able to factor the above number to:

5 * 97 * 130166407115741105132742556824466265630151260716462422214638983 (8.4)

This used Factoris, a tool that factors integers and polynomials written by XIAO Gang (email: xiao@unice.fr). His program concluded that 130166407115741105132742556824466265630151260716462422214638983 is a prime. It is striking that both the numbers found factor into three primes with two of them small (except see below). Further it is also striking that the ratio of the two is close to the ratio of their corresponding large prime factors. (8.3) is about 6.3 * 1064; (8.2) is about 4.7 * 109. The ratio (8.3)/(8.2) is about 1.34 * 1055. The ratio of their largest factors is about 2.47 * 1055.

In Chapter 3 of G. H. Hardy's Ramanujan, Twelve Lectures on Subjects Suggested By His Life and Work, Cambridge UK: The University Press, 1940, a round number is said to be one that "is the product of a considerable number of comparatively small factors." On the second page of that chapter appears "We find, if we try numbers at random from near the end of the factor tables, that f(n) [the number of distinct prime factors of a number n] is usually not 7 or 8 but 3 or 4; ...".

On 11/13/06 Max Alekseyev pointed out that Two lists the value 8365386194032363 found by J. Crump in 2000. Alekseyev found yet another value, 3468371109448915. {He suggested use of Mathematica's PowerMod; the online documentation indicates that PowerMod[a, b, n] gives ab mod n.}

Now the questions about (8.3) begin. [On p. 275 of Guy, Richard K. and Woodrow, Robert E., Eds., The Lighter Side of Mathematics, Mathematical Association of America, Wash. DC, 1994, in Guy's article "The Strong Law of Small Numbers," there is this item: D. H. & Emma Lehmer discovered that 2^n = 3 (mod n) for n = 4700063497, but for no smaller n > 1 .]

7 December 2006 Version