View source for John Selfridge

{{Infobox scientist
|name              = John Selfridge
|birth_date        = {{birth date|1927|2|17}}
|death_date        = {{death date and age|2010|10|31|1927|2|17}} <ref name="obit">{{cite web |url=http://www.legacy.com/obituaries/daily-chronicle/obituary.aspx?n=john-selfridge&pid=146547346&fhid=6514 |title=John Selfridge (1927–2010) |date= November 11, 2010 |newspaper=DeKalb Daily Chronicle |accessdate=November 13, 2010}}</ref>
|birth_place       = [[Ketchikan, Alaska]], United States
|nationality       = American
|fields            = [[Analytic number theory]]
|workplaces        = [[University of Illinois at Urbana-Champaign]]<br />[[Northern Illinois University]]
|alma_mater        = [[University of California, Los Angeles]]
|doctoral_advisor  = [[Theodore Motzkin]]
}}
'''John Lewis Selfridge''' (February 17, 1927 in [[Ketchikan, Alaska]] &ndash; October 31, 2010 in [[DeKalb, Illinois]]<ref name="obit" />), was an American [[mathematician]] who contributed to the fields of [[analytic number theory]], [[computational number theory]], and [[combinatorics]].  He co-authored 14 papers with [[Paul Erdős]] (giving him an [[Erdős number]] of 1).

Selfridge received his [[Ph.D.]] in 1958 from the [[University of California, Los Angeles]] under the supervision of [[Theodore Motzkin]].<ref>{{MathGenealogy|id=4827}}</ref>

In 1962, he proved that 78,557 is a [[Sierpinski number]]; he showed that, when ''k''=78,557, all numbers of the form ''k''2<sup>''n''</sup>&nbsp;+&nbsp;1 have a [[factorization|factor]] in the [[covering set]] {3, 5, 7, 13, 19, 37, 73}. Five years later, he and [[Wacław Sierpiński|Sierpiński]] proposed the conjecture that 78,557 is the smallest Sierpinski number, and thus the answer to the Sierpinski problem. A [[distributed computing]] project called [[Seventeen or Bust]] is currently trying to prove this statement, {{as of|2016|04|alt=as of April 2017}} only five of the original seventeen possibilities remain.

In 1964, Selfridge and Alexander Hurwitz proved that the 14th [[Fermat number]] <math>2^{2^{14}} + 1</math> was composite.
<ref>{{cite journal |author1 = J. L. Selfridge |author2 = A. Hurwitz |title=Fermat numbers and Mersenne numbers |journal=Math. Comput. |date=January 1964 |volume=18 |issue=85 |pages=146–148 |jstor=2003419 |doi=10.2307/2003419  }}</ref>
However, their proof did not provide a factor. It was not until 2010 that the first factor of the 14th Fermat number was found.
<ref>{{cite web |title=GIMPS' second Fermat factor! |last=Rajala |first=Tapio
 |url=http://www.mersenneforum.org/showthread.php?t=13051 |date = 3 February 2010 |accessdate=9 April 2017
}}</ref>
<ref>{{cite web |title=Fermat factoring status |last=Keller |first=Wilfrid
 |url=http://www.prothsearch.com/fermat.html#Incomplete |accessdate=11 April 2017
}}</ref>

In 1975 [[John Brillhart]], [[Derrick Henry Lehmer]] and Selfridge developed a method of proving the primality of p given only partial factorizations of ''p''&nbsp;&minus;&nbsp;1 and ''p''&nbsp;+&nbsp;1.
<ref>{{ cite journal|author1=John Brillhart |author-link1 = John Brillhart |author2=D. H. Lehmer |author-link2 = Derrick Henry Lehmer |author3=J. L. Selfridge |author-link3 = John Selfridge |title=New Primality Criteria and Factorizations of 2<sup>m</sup> ± 1|journal=Math. Comput. |volume=29|number=130|date=April 1975|pages=620–647|jstor=2005583|doi=10.1090/S0025-5718-1975-0384673-1}}</ref>
Together with [[Samuel Wagstaff]] they also all participated in the [[Cunningham project]].

Together with Paul Erdős, Selfridge solved a 250-year-old problem, proving that the product of consecutive numbers is never a power. It took them many years to find the proof and John made extensive use of computers, but the final version of the proof requires only a modest amount of computation, namely evaluating an easily computed function f(n) for 30,000 consecutive values of&nbsp;''n''. Selfridge suffered from [[writer's block]] and paid a former student to write up the result, even though it is only two pages long.

As a mathematician, Selfridge was one of the most effective number theorists with a computer. He also had a way with words. On the occasion that another computational number theorist, [[Samuel Wagstaff]], was lecturing at the semiannual Bloomington Illinois Number Theory Conference on his computer investigations into Fermat's Last Theorem, someone a little too pointedly asked him what methods he was using and kept insisting on an answer. Wagstaff stood there like a deer blinded in headlights, totally at a loss what to say, until Selfridge helped him out. "He used the principle of computer fooling-aroundedness." Wagstaff said later that you probably wouldn't want to use that phrase in a research proposal asking for funding, such as an NSF proposal.

Selfridge also developed the [[Selfridge–Conway discrete procedure]] for creating an [[envy-free cake-cutting]] among three people. Selfridge developed this in 1960,  and [[John Horton Conway|John Conway]] independently discovered it in 1993. Neither of them ever published the result, but [[Richard K. Guy|Richard Guy]] told many people Selfridge's solution in the 1960s, and it was eventually attributed to the two of them in a number of books and articles.

Selfridge served on the faculties of the [[University of Illinois at Urbana-Champaign]] and [[Northern Illinois University]] from 1971 to 1991 (retirement), chairing the Department of Mathematical Sciences 1972–1976 and 1986–1990.
He was executive editor of [[Mathematical Reviews]] from 1978 to 1986, overseeing the computerization of its operations [http://www.ams.org/notices/199703/comm-mr.pdf].  He was a founder of the [[Number Theory Foundation]] [https://web.archive.org/web/20110605043000/http://www.math.uiuc.edu/mathtimes/Fall2007/mathtimes_fall07.htm], which has named its [[Selfridge prize]] in his honour.

==Selfridge's Conjecture about Fermat Numbers==
Selfridge made the following conjecture about the [[Fermat numbers]] ''F<sub>n</sub>'' = 2<sup>2<sup>n</sup></sup> + 1 . Let ''g''(''n'') be the number of distinct prime factors of ''F<sub>n</sub>'' {{OEIS|id=A046052}}. As to 2016, ''g''(''n'') is known only up to ''n'' = 11, and it is monotonic. Selfridge conjectured that contrary to appearances, ''g''(''n'') is NOT monotonic. In support of his conjecture he showed: a sufficient (but not necessary) condition for its truth is the existence of another Fermat ''prime'' beyond the five known (3, 5, 17, 257, 65537).<ref>''Prime Numbers: A Computational Perspective'', Richard Crandall and Carl Pomerance, Second edition, Springer, 2011 Look up ''Selfridge's Conjecture'' in the Index.</ref>

==Selfridge's Conjecture about Primality Testing==
This conjecture is also called the PSW conjecture, after Selfridge, [[Carl Pomerance]], and [[Samuel Wagstaff]].

Let p be an odd number, with p ≡ ± 2 (mod 5). Selfridge conjectured that if

* 2<sup>p-1</sup> ≡ 1 (mod p) and at the same time
* f<sub>p+1</sub> ≡ 0 (mod p),
where f<sub>k</sub> is the kth [[Fibonacci number]], then p is a prime number, and he offered $500 for an example disproving this. He also offered $20 for a proof that the conjecture was true. The Number Theory Foundation will now cover this prize. An example will actually yield you $620 because [[Samuel Wagstaff]] offers $100 for an example or a proof, and [[Carl Pomerance]] offers $20 for an example and $500 for a proof. Selfridge requires that a factorization be supplied, but Pomerance does not. The conjecture was still open August 23, 2015. The related test that f<sub>p-1</sub> ≡ 0 (mod p) for p ≡ ±1 (mod 5) is false and has e.g. a 6-digit counterexample.<ref>According to an email from Pomerance.</ref><ref>Carl Pomerance, Richard Crandall, ''Prime Numbers: A Computational Perspective'', Second Edition, p.&nbsp;168, Springer Verlag, 2005.</ref> The smallest counter example for +1 (mod 5) is 6601 = 7 × 23 × 41 and the smallest for -1 (mod 5) is 30889 = 17 × 23 × 79.

==In the Media==

Selfridge is a major figure in <i>Never Split Tens!</i>, a novel based on the life of pioneering blackjack probability theorist [[Edward O. Thorp]], by gambling writer Les Golden published in 2017 by Springer.  Selfridge had been a graduate student with Thorp at [[UCLA]] and later, as a committee member  for the [[American Mathematical Society]], persuaded the committee to allow Thorp’s seminal paper on blackjack strategy to be presented at their 1961 meeting.

== See also ==
* [[Sierpinski number]]
* [[New Mersenne conjecture]]
* [[Lander, Parkin, and Selfridge conjecture]]
* [http://mathworld.wolfram.com/Erdos-SelfridgeFunction.html Erdős–Selfridge function at Wolfram MathWorld]

==References==
{{Reflist}}

==Publications==
*{{cite journal
|first1=F. A. E.
|last1=Pirani
|first2=Leo
|last2=Moser,
|first3=John
|last3=Selfridge
|title=Elementary Problems and Solutions: Solutions: E903
|journal=Am. Math. Mon.
|volume=57
|year=1950
|issue=8
|pages=561–562
|mr=1527674
|doi=10.2307/2307953
}}

*{{cite journal |author1 = Carl Pomerance |author-link1 = Carl Pomerance |author2 = John L. Selfridge |author-link2 = John L. Selfridge |author3 = Samuel S. Wagstaff, Jr. |author-link3 = Samuel S. Wagstaff, Jr. |title=The pseudoprimes to 25·10<sup>9</sup> |journal=Math. Comput. |date=July 1980 |volume=35 |issue=151 |pages=1003–1026 |url=//math.dartmouth.edu/~carlp/PDF/paper25.pdf |jstor=2006210 |doi=10.1090/S0025-5718-1980-0572872-7 }}
*{{cite journal
|first1=L. C.
|last1=Eggan
|first2=Peter C.
|last2=Eggan
|first3=J. L.
|last3=Selfridge
|title=Polygonal products of polygonal numbers and the Pell equation
|journal=[[Fibonacci Q.]]
|volume=20
|year=1982
|issue=1
|pages=24–28
|mr=0660755
}}
*{{cite journal
|first1=P
|last1=Erdos
|first2=J. L.
|last2=Selfridge
|title=Another property of 239 and some related questions
|year=1982
|journal=Congr. Numer.
|pages=243–257
|mr=0681710
}}
*{{cite journal
|first1=C. B.
|last1=Lacampagne
|authorlink1=Carole Lacampagne
|first2=J. L.
|last2=Selfridge
|title=Large highly powerful numbers are cubeful
|journal=[[Rocky Mt. J. Math.]]
|volume=15
|year=1985
|issue=2
|page=459
|mr=0823257
|doi=10.1216/rmj-1985-15-2-459
}}
*{{cite journal
|first1=C. B.
|last1=Lacampagne
|authorlink1=Carole Lacampagne
|first2=J. L.
|last2=Selfridge
|title=Pairs of squares with consecutive digits
|journal=Math. Mag.
|volume=59
|year=1986
|issue=5
|pages=270–275
|mr=0868804
|doi=10.2307/2689401
}}
*{{cite journal
|first1=W. D.
|last1=Blair
|first2=C. B.
|last2=Lacampagne
|authorlink2=Carole Lacampagne
|first3=J. L.
|last3=Selfridge
|title=Notes: Factoring Large Numbers on a Pocket Calculator
|journal=Am. Math. Mon.
|volume=93
|year=1986
|issue=10
|pages=802–808
|mr=1540993
|doi=10.2307/2322936
}}
*{{cite journal
|first1=R. K.
|last1=Guy
|first2=C. B. 
|last2=Lacampagne
|first3=J. L.
|last3=Selfridge
|title=Primes at a glance
|journal=Math. Comput.
|volume=48
|issue=177
|year=1987
|pages=183–202
|mr=0866108
|doi=10.1090/s0025-5718-1987-0866108-3
}}
*{{cite journal
|first1=William F.
|last1=Trench
|first2=R. S.
|last2=Rodriguez
|first3=H.
|last3=Sherwood
|first4=Bruce A.
|last4=Reznick
|first5=Lee A.
|last5=Rubel
|first6=Solomon W.
|last6=Golomb
|first7=Nick M.
|last7=Kinnon
|first8=Paul
|last8=Erdos
|first9=John
|last9=Selfridge
|title=Problems and Solutions: Elementary Problems: E3243–E3248
|journal=Am. Math. Mon.
|volume=95
|year=1988
|pages=50–51
|mr=1541238

|doi=10.2307/2323449
}}
*{{cite journal
|first1=P.
|last1=Erdos
|first2=C. B.
|last2=Lacampagne
|first3=J. L.
|last3=Selfridge
|title=Prime factors of binomial coefficients and related problems
|journal=Acta Arith.
|volume=49
|issue=5
|year=1988
|pages=507–523
|mr=0967334
}}
*{{cite journal
|first1=P. T.
|last1=Bateman
|first2=J. L.
|last2=Selfridge
|first3=S. S.
|last3=Wagstaff
|title =The New Mersenne conjecture
|journal=Am. Math. Mon.
|volume=96
|year=1989
|issue=2
|pages=125–128
|mr=0992073
|doi=10.2307/2323195
}}
*{{Cite conference |first1=C. B.
|last1=Lacampagne
|first2=C. A.
|last2=Nicol
|first3=J. L.
|last3=Selfridge
|title=Sets with nonsquarefree sums
|booktitle=Number Theory
|year=1990
|pages=299–311
|publisher=de Gruyter
}}
*{{cite journal
|first1=John M.
|last1=Howie
|first2=J. L.
|last2=Selfridge
|title=A semigroup embedding problem and an arithmetical function
|journal=Math. Proc. Camb. Philos. Soc.
|volume=109
|year=1991
|issue=2
|pages=277–286
|mr=1085395
|doi=10.1017/s0305004100069747
}}
*{{cite journal
|mr=1191702
|last1=Eggleton
|first1=R. B.
|last2=Lacampagne
|first2=C. B.
|last3=Selfridge
|first3=J. L.
|title=Eulidean quadratic fields
|journal=Am. Math. Mon.
|volume=99
|year=1992
|issue=9
|pages=829–837
|doi= 10.2307/2324118
}}
*{{cite journal
|mr=1199990
|last1=Erdos
|first1= P.
|last2=Lacampagne
|first2=C. B.
|last3=Selfridge
|first3=J. L.
|title=Estimates of the least prime factor of a binomial coefficient
|journal=Math. Comput.
|volume=61
|year=1993
|issue=203
|pages=215–224
|doi=10.1090/s0025-5718-1993-1199990-6
}}
*{{cite journal
|first1=Cantian
|last1=Lin
|first2=J. L.
|last2=Selfridge
|first3=Peter Jau-shyong
|last3=Shiue
|title=A note on periodic complementary binary sequences
|journal=J. Comb. Math. Comb. Comput.
|volume=19
|year=1995
|pages=225–29
|mr=1358509
}}
*{{cite journal
|first1=Richard
|last1=Blecksmith
|first2=Michael
|last2=McCallum
|first3=J. L.
|last3=Selfridge
|title=3-smooth representations of integers
|journal=Am. Math. Mon.
|year=1998
|volume=105
|issue=6
|pages=529–543
|mr=1626189
|doi=10.2307/2589404
}}
*{{cite journal
|first1=Richard
|last1=Blecksmith
|first2=Paul
|last2=Erdos
|first3=J. L.
|last3=Selfridge
|title=cluster primes
|journal=Am. Math. Mon.
|year=1999
|volume=106
|issue=1
|pages=43–48
|mr=1674129
|doi=10.2307/2589585
}}
*{{cite journal
|first1=Paul
|last1=Erdos
|first2=Janice L.
|last2=Malouf,
|first3=J. L.
|last3=Selfridge
|first4=Esther
|last4=Szekeres
|title=Subsets of an interval whose product is a power
|journal=Discrete Math.
|volume=200
|year=1999
|issue=1–3
|pages=137–147
|mr=1692286
|doi=10.1016/s0012-365x(98)00332-x
}}
*{{cite journal
|first1=Andrew
|last1=Granville
|first2=J. L.
|last2=Selfridge
|title=Product of integers in an interval, modulo squares
|journal=Electron. J. Comb.
|volume=8
|year=2001
|issue=1
|pages=#R5
|mr=1814512
}}

{{Authority control}}

{{DEFAULTSORT:Selfridge, John}}
[[Category:1927 births]]
[[Category:2010 deaths]]
[[Category:20th-century mathematicians]]
[[Category:Number theorists]]
[[Category:University of California, Los Angeles alumni]]
[[Category:People from Ketchikan Gateway Borough, Alaska]]
[[Category:People from DeKalb, Illinois]]