SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Carl Bernard Pomerance (born 1944) is an American mathematician renowned for his work in number theory, particularly integer factorization and primality testing. He has made significant contributions to the development and analysis of prime-testing algorithms and factoring methods, including work on the Quadratic Sieve and the Multiple Polynomial Quadratic Sieve (MPQS).

Pomerance has held academic positions at institutions such as the University of Georgia and Dartmouth College. Alongside his research, he has mentored many students and collaborated with leading mathematicians in the field of computational number theory.

Ask a Question About This Mathematician

On a problem of Oppenheim concerning “factorisatio numerorum”

1983-08-01
E. Rodney Canfield , Paul Erdős , Carl Pomerance

There are Infinitely Many Carmichael Numbers

1994-05-01
W. R. Alford , Andrew Granville , Carl Pomerance

On Distinguishing Prime Numbers from Composite Numbers

1983-01-01
Leonard M. Adleman , Carl Pomerance , Robert Rumely

The Quadratic Sieve Factoring Algorithm

2007-02-28
Carl Pomerance
View PDF Chat

The Riemann Zeta-Function and the One-Dimensional Weyl-Berry Conjecture for Fractal Drums

1993-01-01
Michel L. Lapidus , Carl Pomerance
Based on his earlier work on the vibrations of 'drums with fractal boundary', the first author has refined M. V. Berry's conjecture that extended from the 'smooth' to the 'fractal' … Based on his earlier work on the vibrations of 'drums with fractal boundary', the first author has refined M. V. Berry's conjecture that extended from the 'smooth' to the 'fractal' case H. Weyl's conjecture for the asymptotics of the eigenvalues of the Laplacian on a bounded open subset of Rn (see [16]). We solve here in the one-dimensional case (that is, when n = 1) this 'modified Weyl-Berry conjecture'. We discover, in the process, some unexpected and intriguing connections between spectral geometry, fractal geometry and the Riemann zeta-function. We therefore show that one can 'hear' (that is, recover from the spectrum) not only the Minkowski fractal dimension of the boundary—as was established previously by the first author—but also, under the stronger assumptions of the conjecture, its Minkowski content (a 'fractal' analogue of its 'length'). We also prove (still in dimension one) a related conjecture of the first author, as well as its converse, which characterizes the situation when the error estimates of the aforementioned paper are sharp.
View PDF Chat

Factoring integers with the number field sieve

1993-01-01
Joe Buhler , H. W. Lenstra , Carl Pomerance

Prime Numbers

2001-01-01
Richard S. Crandall , Carl Pomerance

A search for Wieferich and Wilson primes

1997-01-01
Richard E. Crandall , Karl Dilcher , Carl Pomerance
An odd prime $p$ is called a Wieferich prime if \begin{equation*}2^{p-1} \equiv 1 \pmod {p^{2}};\end{equation*} alternatively, a Wilson prime if \begin{equation*}(p-1)! \equiv -1 \pmod { p^{2}}.\end{equation*} To date, the only … An odd prime $p$ is called a Wieferich prime if \begin{equation*}2^{p-1} \equiv 1 \pmod {p^{2}};\end{equation*} alternatively, a Wilson prime if \begin{equation*}(p-1)! \equiv -1 \pmod { p^{2}}.\end{equation*} To date, the only known Wieferich primes are $p = 1093$ and $3511$, while the only known Wilson primes are $p = 5, 13$, and $563$. We report that there exist no new Wieferich primes $p < 4 \times 10^{12}$, and no new Wilson primes $p < 5 \times 10^{8}$. It is elementary that both defining congruences above hold merely (mod $p$), and it is sometimes estimated on heuristic grounds that the "probability" that $p$ is Wieferich (independently: that $p$ is Wilson) is about $1/p$. We provide some statistical data relevant to occurrences of small values of the pertinent Fermat and Wilson quotients (mod $p$).
View PDF Chat

The pseudoprimes to 25⋅10⁹

1980-01-01
Carl Pomerance , J. L. Selfridge , Samuel S. Wagstaff
The odd composite<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n less-than-or-slanted-equals 25 dot 10 Superscript 9"><mml:semantics><mml:mrow><mml:mi>n</mml:mi><mml:mo>⩽<!-- ⩽ --></mml:mo><mml:mn>25</mml:mn><mml:mo>⋅<!-- ⋅ --></mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:msup><mml:mn>10</mml:mn><mml:mn>9</mml:mn></mml:msup></mml:mrow></mml:mrow><mml:annotation encoding="application/x-tex">n \leqslant 25 \cdot {10^9}</mml:annotation></mml:semantics></mml:math></inline-formula>such that<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 Superscript n minus 1 … The odd composite<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n less-than-or-slanted-equals 25 dot 10 Superscript 9"><mml:semantics><mml:mrow><mml:mi>n</mml:mi><mml:mo>⩽<!-- ⩽ --></mml:mo><mml:mn>25</mml:mn><mml:mo>⋅<!-- ⋅ --></mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:msup><mml:mn>10</mml:mn><mml:mn>9</mml:mn></mml:msup></mml:mrow></mml:mrow><mml:annotation encoding="application/x-tex">n \leqslant 25 \cdot {10^9}</mml:annotation></mml:semantics></mml:math></inline-formula>such that<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 Superscript n minus 1 Baseline identical-to 1 left-parenthesis mod n right-parenthesis"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:msup><mml:mn>2</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>n</mml:mi><mml:mo>−<!-- − --></mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:mrow><mml:mo>≡<!-- ≡ --></mml:mo><mml:mn>1</mml:mn><mml:mspace width="thickmathspace" /><mml:mspace width="0.667em" /><mml:mo stretchy="false">(</mml:mo><mml:mi>mod</mml:mi><mml:mspace width="0.333em" /><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">{2^{n - 1}} \equiv 1\;\pmod n</mml:annotation></mml:semantics></mml:math></inline-formula>have been determined and their distribution tabulated. We investigate the properties of three special types of pseudoprimes: Euler pseudoprimes, strong pseudoprimes, and Carmichael numbers. The theoretical upper bound and the heuristic lower bound due to Erdös for the counting function of the Carmichael numbers are both sharpened. Several new quick tests for primality are proposed, including some which combine pseudoprimes with Lucas sequences.
View PDF Chat

Carmichael's lambda function

1991-01-01
P. Erdős , Carl Pomerance , Eric Schmutz
View PDF Chat

On the distribution of pseudoprimes

1981-01-01
Carl Pomerance
Let<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper P left-parenthesis x right-parenthesis"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">P</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\mathcal {P}(x)</mml:annotation></mml:semantics></mml:math></inline-formula>denote the pseudoprime counting function. With<disp-formula content-type="math/mathml">\[<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L left-parenthesis x right-parenthesis equals exp … Let<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper P left-parenthesis x right-parenthesis"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">P</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\mathcal {P}(x)</mml:annotation></mml:semantics></mml:math></inline-formula>denote the pseudoprime counting function. With<disp-formula content-type="math/mathml">\[<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L left-parenthesis x right-parenthesis equals exp left-brace log x log log log x slash log log x right-brace comma"><mml:semantics><mml:mrow><mml:mi>L</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>exp</mml:mi><mml:mo>⁡<!-- ⁡ --></mml:mo><mml:mo fence="false" stretchy="false">{</mml:mo><mml:mi>log</mml:mi><mml:mo>⁡<!-- ⁡ --></mml:mo><mml:mi>x</mml:mi><mml:mi>log</mml:mi><mml:mo>⁡<!-- ⁡ --></mml:mo><mml:mi>log</mml:mi><mml:mo>⁡<!-- ⁡ --></mml:mo><mml:mi>log</mml:mi><mml:mo>⁡<!-- ⁡ --></mml:mo><mml:mi>x</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>log</mml:mi><mml:mo>⁡<!-- ⁡ --></mml:mo><mml:mi>log</mml:mi><mml:mo>⁡<!-- ⁡ --></mml:mo><mml:mi>x</mml:mi><mml:mo fence="false" stretchy="false">}</mml:mo><mml:mo>,</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">L(x) = \exp \{ \log x\log \log \log x/\log \log x\} ,</mml:annotation></mml:semantics></mml:math>\]</disp-formula>we prove<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper P left-parenthesis x right-parenthesis less-than-or-slanted-equals x bullet upper L left-parenthesis x right-parenthesis Superscript negative 1 slash 2"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">P</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>⩽<!-- ⩽ --></mml:mo><mml:mi>x</mml:mi><mml:mo>∙<!-- ∙ --></mml:mo><mml:mi>L</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:msup><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>−<!-- − --></mml:mo><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msup></mml:mrow></mml:mrow><mml:annotation encoding="application/x-tex">\mathcal {P}(x) \leqslant x \bullet L{(x)^{ - 1/2}}</mml:annotation></mml:semantics></mml:math></inline-formula>for large<italic>x</italic>, an improvement on the 1956 work of Erdös. We conjecture that<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper P left-parenthesis x right-parenthesis equals x bullet upper L left-parenthesis x right-parenthesis Superscript negative 1 plus o left-parenthesis 1 right-parenthesis"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">P</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>x</mml:mi><mml:mo>∙<!-- ∙ --></mml:mo><mml:mi>L</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:msup><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>−<!-- − --></mml:mo><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msup></mml:mrow></mml:mrow><mml:annotation encoding="application/x-tex">\mathcal {P}(x) = x \bullet L{(x)^{ - 1 + o(1)}}</mml:annotation></mml:semantics></mml:math></inline-formula>.
View PDF Chat

The Search for Prime Numbers

1982-12-01
Carl Pomerance

Popular values of Euler's function

1980-06-01
Carl Pomerance

Average case error estimates for the strong probable prime test

1993-01-01
Ivan Damgård , Peter Landrock , Carl Pomerance
Consider a procedure that chooses <italic>k</italic>-bit odd numbers independently and from the uniform distribution, subjects each number to <italic>t</italic> independent iterations of the strong probable prime test (Miller-Rabin test) with … Consider a procedure that chooses <italic>k</italic>-bit odd numbers independently and from the uniform distribution, subjects each number to <italic>t</italic> independent iterations of the strong probable prime test (Miller-Rabin test) with randomly chosen bases, and outputs the first number found that passes all <italic>t</italic> tests. Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p Subscript k comma t"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>p</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>,</mml:mo> <mml:mi>t</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{p_{k,t}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> denote the probability that this procedure returns a composite number. We obtain numerical upper bounds for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p Subscript k comma t"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>p</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>,</mml:mo> <mml:mi>t</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{p_{k,t}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for various choices of <italic>k, t</italic> and obtain clean explicit functions that bound <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p Subscript k comma t"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>p</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>,</mml:mo> <mml:mi>t</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{p_{k,t}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for certain infinite classes of <italic>k, t</italic>. For example, we show <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p Subscript 100 comma 10 Baseline less-than-or-equal-to 2 Superscript negative 44 Baseline comma p Subscript 300 comma 5 Baseline less-than-or-equal-to 2 Superscript negative 60 Baseline comma p Subscript 600 comma 1 Baseline less-than-or-equal-to 2 Superscript negative 75"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>p</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>100</mml:mn> <mml:mo>,</mml:mo> <mml:mn>10</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:mo>≤<!-- ≤ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−<!-- − --></mml:mo> <mml:mn>44</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:mo>,</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>p</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>300</mml:mn> <mml:mo>,</mml:mo> <mml:mn>5</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:mo>≤<!-- ≤ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−<!-- − --></mml:mo> <mml:mn>60</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:mo>,</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>p</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>600</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:mo>≤<!-- ≤ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−<!-- − --></mml:mo> <mml:mn>75</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{p_{100,10}} \leq {2^{ - 44}},{p_{300,5}} \leq {2^{ - 60}},{p_{600,1}} \leq {2^{ - 75}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p Subscript k comma 1 Baseline less-than-or-equal-to k squared 4 Superscript 2 minus StartRoot k EndRoot"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>p</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:mo>≤<!-- ≤ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>4</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> <mml:mo>−<!-- − --></mml:mo> <mml:msqrt> <mml:mi>k</mml:mi> </mml:msqrt> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{p_{k,1}} \leq {k^2}{4^{2 - \sqrt k }}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for all <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k greater-than-or-equal-to 2"> <mml:semantics> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>≥<!-- ≥ --></mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">k \geq 2</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. In addition, we characterize the worst-case numbers with unusually many "false witnesses" and give an upper bound on their distribution that is probably close to best possible.
View PDF Chat

Counterexamples to the modified Weyl–Berry conjecture on fractal drums

1996-01-01
Michel L. Lapidus , Carl Pomerance
Let Ω be a non-empty open set in ℝ n with finite ‘volume’ ( n -dimensional Lebesgue measure). Let be the Laplacian operator. Consider the eigenvalue problem (with Dirichlet boundary … Let Ω be a non-empty open set in ℝ n with finite ‘volume’ ( n -dimensional Lebesgue measure). Let be the Laplacian operator. Consider the eigenvalue problem (with Dirichlet boundary conditions): where λ ∈ ℝ and u is a non-zero member of (the closure in the Sobolev space H 1 (Ω) of the set of smooth functions with compact support contained in Ω). It is well known that the values of λ∈ℝ for which (1·1) has a non-zero solution are positive and form a discrete set. Moreover, for each λ, the associated eigenspace is finite dimensional. Let the spectrum of (1·1) be denoted where 0 &lt; λ 1 ≤ λ 2 ≤ … and where the multiplicity of each λ in the sequence is the dimension of the associated eigenspace. Let

On the distribution of amicable numbers. II.

1981-06-01
Carl Pomerance

Unusually large gaps between consecutive primes

1990-01-01
Helmut Maier , Carl Pomerance
Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G left-parenthesis x right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">G(x)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> denote the largest gap between consecutive … Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G left-parenthesis x right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">G(x)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> denote the largest gap between consecutive primes below <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="x"> <mml:semantics> <mml:mi>x</mml:mi> <mml:annotation encoding="application/x-tex">x</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. In a series of papers from 1935 to 1963, Erdàs, Rankin, and Schànhage showed that <disp-formula content-type="math/mathml"> \[ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G left-parenthesis x right-parenthesis greater-than-or-equal-to left-parenthesis c plus o left-parenthesis 1 right-parenthesis right-parenthesis log x l o g l o g x l o g l o g l o g l o g x left-parenthesis l o g l o g l o g x right-parenthesis Superscript negative 2"> <mml:semantics> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>≥<!-- ≥ --></mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>c</mml:mi> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>log</mml:mi> </mml:mrow> <mml:mi>x</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>loglog</mml:mi> </mml:mrow> <mml:mi>x</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>loglogloglog</mml:mi> </mml:mrow> <mml:mi>x</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>logloglog</mml:mi> </mml:mrow> <mml:mi>x</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−<!-- − --></mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">G(x) \geq (c + o(1)){\operatorname {log}}x{\operatorname {loglog}}x{\operatorname {loglogloglog}}x{({\operatorname {logloglog}}x)^{ - 2}}</mml:annotation> </mml:semantics> </mml:math> \] </disp-formula>, where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="c equals e Superscript gamma"> <mml:semantics> <mml:mrow> <mml:mi>c</mml:mi> <mml:mo>=</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>e</mml:mi> <mml:mi>γ<!-- γ --></mml:mi> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">c = {e^\gamma }</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="gamma"> <mml:semantics> <mml:mi>γ<!-- γ --></mml:mi> <mml:annotation encoding="application/x-tex">\gamma</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is Euler’s constant. Here, this result is shown with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="c equals c 0 e Superscript gamma"> <mml:semantics> <mml:mrow> <mml:mi>c</mml:mi> <mml:mo>=</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>c</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>e</mml:mi> <mml:mi>γ<!-- γ --></mml:mi> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">c = {c_0}{e^\gamma }</mml:annotation> </mml:semantics> </mml:math> </inline-formula> where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="c 0 equals 1.31256 ellipsis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>c</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mn>1.31256</mml:mn> <mml:mo>…<!-- … --></mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">{c_0} = 1.31256 \ldots</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the solution of the equation <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="4 slash c 0 minus e Superscript negative 4 slash c 0 Baseline equals 3"> <mml:semantics> <mml:mrow> <mml:mn>4</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>c</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:mrow> <mml:mo>−<!-- − --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>e</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−<!-- − --></mml:mo> <mml:mn>4</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>c</mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:mrow> </mml:mrow> </mml:msup> </mml:mrow> <mml:mo>=</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">4/{c_0} - {e^{ - 4/{c_0}}} = 3</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. The principal new tool used is a result of independent interest, namely, a mean value theorem for generalized twin primes lying in a residue class with a large modulus.
View PDF Chat

On the Normal Behavior of the Iterates Of some Arithmetic Functions

1990-01-01
Paul Erdős , Andew Granvilie , Carl Pomerance +1 more

Some new results on odd perfect numbers

1975-04-01
G. G. Dandapat , John Hunsucker , Carl Pomerance
If ra is a multiply perfect number (σ(m) = tm for some integer ί), we ask if there is a prime p with m = pan, (pa, n) = 1, … If ra is a multiply perfect number (σ(m) = tm for some integer ί), we ask if there is a prime p with m = pan, (pa, n) = 1, σ(n) = pα, and σ(pa) = tn. We prove that the only multiply perfect numbers with this property are the even perfect numbers and 672. Hence we settle a problem raised by Suryanarayana who asked if odd perfect numbers necessarily had such a prime factor. The methods of the proof allow us also to say something about odd solutions to the equation σ(σ(n)) ~ 2n.
View PDF Chat

Timed Fair Exchange of Standard Signatures

2003-01-01
Juan A. Garay , Carl Pomerance

On composite<i>n</i>for which<i>φ</i>(<i>n</i>)<i>∣</i><i>n</i>− 1. II

1977-03-01
Carl Pomerance
The problem of whether there exists a composite n for which φ(n) n — 1 (φ is Euler's function) was first posed by D. H. Lehmer in 1932 and still … The problem of whether there exists a composite n for which φ(n) n — 1 (φ is Euler's function) was first posed by D. H. Lehmer in 1932 and still remains unsolved. In this paper we prove that the number of such n not exceeding x is O(x(logx)). We also prove that any such n with precisely K distinct prime factors is necessarily less than K. There are appropriate generalizations of these results to integers n for which φ{n) n — a, a an arbitrary integer.
View PDF Chat

A note on the least prime in an arithmetic progression

1980-05-01
Carl Pomerance

On the normal number of prime factors of $\phi(n)$

1985-06-01
Paul Erdős , Carl Pomerance
View PDF Chat

Combinatorial Number Theory

2013-08-27
Carl Pomerance , Andràs Sárközy

On the binary expansions of algebraic numbers

2004-01-01
David H. Bailey , Jonathan M. Borwein , Richard E. Crandall +1 more
Employing concepts from additive number theory, together with results on binary evaluations and partial series, we establish bounds on the density of 1’s in the binary expansions of real algebraic … Employing concepts from additive number theory, together with results on binary evaluations and partial series, we establish bounds on the density of 1’s in the binary expansions of real algebraic numbers. A central result is that if a real y has algebraic degree D>1, then the number #(|y|,N) of 1-bits in the expansion of |y| through bit position N satisfies
View PDF Chat

A hyperelliptic smoothness test. I

1993-11-15
H. W. Lenstra , Jonathan Pila , Carl Pomerance
This series of papers is concerned with a probabilistic algorithm for finding small prime factors of an integer. While the algorithm is not practical, it yields an improvement over previous … This series of papers is concerned with a probabilistic algorithm for finding small prime factors of an integer. While the algorithm is not practical, it yields an improvement over previous complexity results. The algorithm uses the jacobian varieties of curves of genus 2 in the same way that the elliptic curve method uses elliptic curves. In this first paper in the series a new density theorem is presented for smooth numbers in short intervals. It is a key ingredient of the analysis of the algorithm.
View PDF Chat

On the periods of the linear congruential and power generators

2005-01-01
Pär Kurlberg , Carl Pomerance
We consider the periods of the linear congruential and the power generators modulo $n$ and, for fixed choices of initial parameters, give lower bounds that hold for ``most'' $n$ when … We consider the periods of the linear congruential and the power generators modulo $n$ and, for fixed choices of initial parameters, give lower bounds that hold for ``most'' $n$ when $n$ ranges over three different sets: the set of primes, the set of products of two primes (of similar size), and the set of all integers. For most $n$ in these sets, the period is at least $n^{1/2+\epsilon(n)}$ for any monotone function $\epsilon(n)$ tending to zero as $n$ tends to infinity. Assuming the Generalized Riemann Hypothesis, for most $n$ in these sets the period is greater than $n^{1-\epsilon}$ for any $\epsilon >0$. Moreover, the period is unconditionally greater than $n^{1/2+\delta}$, for some fixed $\delta>0$, for a positive proportion of $n$ in the above mentioned sets. These bounds are related to lower bounds on the multiplicative order of an integer $e$ modulo $p-1$, modulo $\lambda(pl)$, and modulo $\lambda(m)$ where $p,l$ range over the primes, $m$ ranges over the integers, and where $\lambda(n)$ is the order of the largest cyclic subgroup of $(\Z/n\Z)^\times$.
View PDF Chat

On generalizing Artins conjecture on primitive roots to composite moduli

2003-01-18
Shuguang Li , Carl Pomerance
Article On generalizing Artins conjecture on primitive roots to composite moduli was published on March 18, 2003 in the journal Journal für die reine und angewandte Mathematik (volume 2003, issue … Article On generalizing Artins conjecture on primitive roots to composite moduli was published on March 18, 2003 in the journal Journal für die reine und angewandte Mathematik (volume 2003, issue 556).

Two contradictory conjectures concerning Carmichael numbers

2001-10-04
Andrew Granville , Carl Pomerance
Erdős conjectured that there are $x^{1-o(1)}$ Carmichael numbers up to $x$, whereas Shanks was skeptical as to whether one might even find an $x$ up to which there are more … Erdős conjectured that there are $x^{1-o(1)}$ Carmichael numbers up to $x$, whereas Shanks was skeptical as to whether one might even find an $x$ up to which there are more than $\sqrt {x}$ Carmichael numbers. Alford, Granville and Pomerance showed that there are more than $x^{2/7}$ Carmichael numbers up to $x$, and gave arguments which even convinced Shanks (in person-to-person discussions) that Erdős must be correct. Nonetheless, Shanks's skepticism stemmed from an appropriate analysis of the data available to him (and his reasoning is still borne out by Pinch's extended new data), and so we herein derive conjectures that are consistent with Shanks's observations, while fitting in with the viewpoint of Erdős and the results of Alford, Granville and Pomerance.
View PDF Chat

Multiply perfect numbers, mersenne primes, and effective computability

1977-10-01
Carl Pomerance

The generation of random numbers that are probably prime

1988-01-01
Pierre Beauchemin , Gilles Brassard , Claude Crépeau +2 more
View PDF Chat

On multiply perfect numbers with a special property

1975-04-01
Carl Pomerance
Note that in [2] all solutions of (1.1) with p = σ(n) are enumerated: they are (1.2) and (1.5). Hence in the proof of Theorem 1.1, we may assume p … Note that in [2] all solutions of (1.1) with p = σ(n) are enumerated: they are (1.2) and (1.5). Hence in the proof of Theorem 1.1, we may assume p < σ(n). We recall that a natural number n is said to be super perfect it σ(σ(n)) = 2n. In [2] and Suryanarayana [8] it is shown that if n is super perfect and if either n or σ(n) is a prime power, then n = 2~ for keM. Here we will say n is swper multiply perfect if σ(σ(n))jn is an integer.
View PDF Chat

The Role of Smooth Numbers in Number Theoretic Algorithms

1995-01-01
Carl Pomerance
A smooth number is a number with only small prime factors. In particular, a positive integer is y-smooth if it has no prime factor exceeding y. Smooth numbers are a … A smooth number is a number with only small prime factors. In particular, a positive integer is y-smooth if it has no prime factor exceeding y. Smooth numbers are a useful tool in number theory because they not only have a simple multiplicative structure, but are also fairly numerous. These twin properties of smooth numbers are the main reason they play a key role in almost every moder integer factorization algorithm. Smooth numbers play a similar essential role in discrete logarithm algorithms (methods to represent some group element as a power of another), and a lesser, but still important, role in primality tests.

On the number of distinct values of Euler's φ-function

1988-01-01
Helmut Maier , Carl Pomerance
View PDF Chat

On divisors of sums of integers. III

1988-06-01
Carl Pomerance , Andràs Sárközy , C. L. Stewart
are "dense" sets of integers, then there is a sum a,\ + #2 H V &k w are "dense" sets of integers, then there is a sum a,\ + #2 H V &k w
View PDF Chat

On locally repeated values of certain arithmetic functions. II

1987-03-01
Paul Erdős , Carl Pomerance , Andràs Sárközy
View PDF Chat

On Primes Recognizable in Deterministic Polynomial Time

2013-01-01
Sergeĭ Konyagin , Carl Pomerance

The Pseudoprimes to 25 ⋅10 9

1980-07-01
Carl Pomerance , J. L. Selfridge , Samuel S. Wagstaff

Combinatorial Number Theory

2007-12-31
Bruce Landman , Melvyn B. Nathanson , Jaroslav Nesetril +2 more
This carefully edited volume contains selected refereed papers based on lectures presented by many distinguished speakers at the "Integers Conference 2005", an international conference in combinatorial number theory. The conference … This carefully edited volume contains selected refereed papers based on lectures presented by many distinguished speakers at the "Integers Conference 2005", an international conference in combinatorial number theory. The conference was held in celebration of the 70th birthday of Ronald Graham, a leader in several fields of mathematics.

Odd perfect numbers are divisible by at least seven distinct primes

1974-01-01
Carl Pomerance
View PDF Chat

A new lower bound for the pseudoprime counting function

1982-03-01
Carl Pomerance

The distribution of smooth numbers in arithmetic progressions

1992-01-01
Antal Balog , Carl Pomerance
We estimate the number of integers <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> up to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="x"> <mml:semantics> <mml:mi>x</mml:mi> <mml:annotation encoding="application/x-tex">x</mml:annotation> </mml:semantics> … We estimate the number of integers <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> up to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="x"> <mml:semantics> <mml:mi>x</mml:mi> <mml:annotation encoding="application/x-tex">x</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in the arithmetic progression <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a left-parenthesis mod q right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>a</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mo lspace="thickmathspace" rspace="thickmathspace">mod</mml:mo> <mml:mi>q</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">a(\bmod q)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> free of prime factors exceeding <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="y"> <mml:semantics> <mml:mi>y</mml:mi> <mml:annotation encoding="application/x-tex">y</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. For a wide range of the variables <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="x comma y comma q"> <mml:semantics> <mml:mrow> <mml:mi>x</mml:mi> <mml:mo>,</mml:mo> <mml:mi>y</mml:mi> <mml:mo>,</mml:mo> <mml:mi>q</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">x,y,q</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a"> <mml:semantics> <mml:mi>a</mml:mi> <mml:annotation encoding="application/x-tex">a</mml:annotation> </mml:semantics> </mml:math> </inline-formula> we show that this number is about <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="x slash left-parenthesis q u Superscript u Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>x</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>q</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>u</mml:mi> <mml:mi>u</mml:mi> </mml:msup> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">x/(q{u^u})</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="u equals log x slash log y"> <mml:semantics> <mml:mrow> <mml:mi>u</mml:mi> <mml:mo>=</mml:mo> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>x</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>y</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">u = \log x/\log y</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.
View PDF Chat

Remarks on the Pólya–Vinogradov Inequality

2011-01-01
Carl Pomerance
Abstract We establish a numerically explicit version of the Pólya–Vinogradov inequality for the sum of values of a Dirichlet character on an interval. While the technique of proof is essentially … Abstract We establish a numerically explicit version of the Pólya–Vinogradov inequality for the sum of values of a Dirichlet character on an interval. While the technique of proof is essentially that of Landau from 1918, the result we obtain has better constants than in other numerically explicit versions that have been found more recently.
View PDF Chat

Multiplicative structure of values of the Euler function

2004-05-25
William D. Banks , John Friedlander , Carl Pomerance +1 more
We establish upper bounds for the number of smooth values of the Euler function.In particular, although the Euler function has a certain "smoothing" effect on its integer arguments, our results … We establish upper bounds for the number of smooth values of the Euler function.In particular, although the Euler function has a certain "smoothing" effect on its integer arguments, our results show that, in fact, most values produced by the Euler function are not smooth.We apply our results to study the distribution of "strong primes", which are commonly encountered in cryptography.We also consider the problem of obtaining upper and lower bounds for the number of positive integers n ≤ x for which the value of the Euler function ϕ(n) is a perfect square and also for the number of n ≤ x such that ϕ(n) is squarefull.We give similar bounds for the Carmichael function λ(n).
View PDF Chat

Sieving by large integers and covering systems of congruences

2006-09-19
Michael Filaseta , Kevin Ford , Sergeĭ Konyagin +2 more
An old question of Erdős asks if there exists, for each number <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"> <mml:semantics> <mml:mi>N</mml:mi> <mml:annotation encoding="application/x-tex">N</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, a finite set <inline-formula content-type="math/mathml"> … An old question of Erdős asks if there exists, for each number <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"> <mml:semantics> <mml:mi>N</mml:mi> <mml:annotation encoding="application/x-tex">N</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, a finite set <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of integers greater than <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"> <mml:semantics> <mml:mi>N</mml:mi> <mml:annotation encoding="application/x-tex">N</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and residue classes <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r left-parenthesis n right-parenthesis left-parenthesis mod n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mtext> </mml:mtext> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext>mod</mml:mtext> </mml:mrow> <mml:mtext> </mml:mtext> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">r(n)~(\textrm {mod}~n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n element-of upper S"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mi>S</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n\in S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> whose union is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper Z"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">Z</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbb Z</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We prove that if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="sigma-summation Underscript n element-of upper S Endscripts 1 slash n"> <mml:semantics> <mml:mrow> <mml:munder> <mml:mo>∑<!-- ∑ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mi>S</mml:mi> </mml:mrow> </mml:munder> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\sum _{n\in S}1/n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is bounded for such a covering of the integers, then the least member of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is also bounded, thus confirming a conjecture of Erdős and Selfridge. We also prove a conjecture of Erdős and Graham, that, for each fixed number <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K greater-than 1"> <mml:semantics> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">K&gt;1</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, the complement in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper Z"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">Z</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbb Z</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of any union of residue classes <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r left-parenthesis n right-parenthesis left-parenthesis mod n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mtext> </mml:mtext> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext>mod</mml:mtext> </mml:mrow> <mml:mtext> </mml:mtext> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">r(n)~(\textrm {mod}~n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, for distinct <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n element-of left-parenthesis upper N comma upper K upper N right-bracket"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>N</mml:mi> <mml:mo>,</mml:mo> <mml:mi>K</mml:mi> <mml:mi>N</mml:mi> <mml:mo stretchy="false">]</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">n\in (N,KN]</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, has density at least <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d Subscript upper K"> <mml:semantics> <mml:msub> <mml:mi>d</mml:mi> <mml:mi>K</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">d_K</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"> <mml:semantics> <mml:mi>N</mml:mi> <mml:annotation encoding="application/x-tex">N</mml:annotation> </mml:semantics> </mml:math> </inline-formula> sufficiently large. Here <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d Subscript upper K"> <mml:semantics> <mml:msub> <mml:mi>d</mml:mi> <mml:mi>K</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">d_K</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a positive number depending only on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K"> <mml:semantics> <mml:mi>K</mml:mi> <mml:annotation encoding="application/x-tex">K</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Either of these new results implies another conjecture of Erdős and Graham, that if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a finite set of moduli greater than <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"> <mml:semantics> <mml:mi>N</mml:mi> <mml:annotation encoding="application/x-tex">N</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, with a choice for residue classes <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r left-parenthesis n right-parenthesis left-parenthesis mod n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mtext> </mml:mtext> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext>mod</mml:mtext> </mml:mrow> <mml:mtext> </mml:mtext> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">r(n)~(\textrm {mod}~n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n element-of upper S"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mi>S</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n\in S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> which covers <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper Z"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">Z</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbb Z</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, then the largest member of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> cannot be <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis upper N right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(N)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We further obtain stronger forms of these results and establish other information, including an improvement of a related theorem of Haight.

On the difficulty of finding reliable witnesses

1994-01-01
W. R. Alford , Andrew Granville , Carl Pomerance

Very short primality proofs

1987-01-01
Carl Pomerance
It is shown that every prime <italic>p</italic> has a proof of its primality of length <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis log p right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> … It is shown that every prime <italic>p</italic> has a proof of its primality of length <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis log p right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>p</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(\log p)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> multiplications modulo <italic>p</italic>.
View PDF Chat

The distribution of Lucas and elliptic pseudoprimes

1991-01-01
Daniel M. Gordon , Carl Pomerance
Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper L left-parenthesis x right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">L</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {L}(x)</mml:annotation> </mml:semantics> </mml:math> … Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper L left-parenthesis x right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">L</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {L}(x)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> denote the counting function for Lucas pseudoprimes, and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper E left-parenthesis x right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">E</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {E}(x)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> denote the elliptic pseudoprime counting function. We prove that, for large <italic>x</italic>, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper L left-parenthesis x right-parenthesis less-than-or-equal-to x upper L left-parenthesis x right-parenthesis Superscript negative 1 slash 2"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">L</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>≤<!-- ≤ --></mml:mo> <mml:mi>x</mml:mi> <mml:mi>L</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {L}(x) \leq xL{(x)^{ - 1/2}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper E left-parenthesis x right-parenthesis less-than-or-equal-to x upper L left-parenthesis x right-parenthesis Superscript negative 1 slash 3"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">E</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>≤<!-- ≤ --></mml:mo> <mml:mi>x</mml:mi> <mml:mi>L</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {E}(x) \leq xL{(x)^{ - 1/3}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, where <disp-formula content-type="math/mathml"> \[ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L left-parenthesis x right-parenthesis equals exp left-parenthesis log x log log log x slash log log x right-parenthesis period"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>exp</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>x</mml:mi> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>x</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>.</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">L(x) = \exp (\log x\log \log \log x/\log \log x).</mml:annotation> </mml:semantics> </mml:math> \] </disp-formula>
View PDF Chat

On the Least Prime in Certain Arithmetic Progressions

1990-04-01
Andrew Granville , Carl Pomerance
We find infinitely many pairs of coprime integers, a and q, such that the least prime congruent to a (modulo q) is unusually large. In so doing we also consider … We find infinitely many pairs of coprime integers, a and q, such that the least prime congruent to a (modulo q) is unusually large. In so doing we also consider the question of approximating rationals by other rationals with smaller and coprime denominators.

Error estimates for the Davenport-Heilbronn theorems

2010-04-28
Karim Belabas , Manjul Bhargava , Carl Pomerance
We obtain the first known power-saving remainder terms for the theorems of Davenport and Heilbronn on the density of discriminants of cubic fields and the mean number of 3-torsion elements … We obtain the first known power-saving remainder terms for the theorems of Davenport and Heilbronn on the density of discriminants of cubic fields and the mean number of 3-torsion elements in the class groups of quadratic fields. In addition, we prove analogous error terms for the density of discriminants of quartic fields and the mean number of 2-torsion elements in the class groups of cubic fields. These results prove analytic continuation of the related Dirichlet series to the left of the line R(s)=1.
View PDF Chat

Cyclotomic primes

2025-05-01
Carl Pomerance

Cyclotomic primes

2024-11-06
Carl Pomerance
Mersenne primes and Fermat primes may be thought of as primes of the form $\Phi_m(2)$, where $\Phi_m(x)$ is the $m$th cyclotomic polynomial. This paper discusses the more general problem of … Mersenne primes and Fermat primes may be thought of as primes of the form $\Phi_m(2)$, where $\Phi_m(x)$ is the $m$th cyclotomic polynomial. This paper discusses the more general problem of primes and composites of this form.
View PDF Chat

Shifted-prime divisors

2024-01-01
Steve Fan , Carl Pomerance
Let $\omega^*(n)$ denote the number of divisors of $n$ that are shifted primes, that is, the number of divisors of $n$ of the form $p-1$, with $p$ prime. Studied by … Let $\omega^*(n)$ denote the number of divisors of $n$ that are shifted primes, that is, the number of divisors of $n$ of the form $p-1$, with $p$ prime. Studied by Prachar in an influential paper from 70 years ago, the higher moments of $\omega^*(n)$ are still somewhat a mystery. This paper addresses these higher moments and considers other related problems.

An inequality related to the sieve of Eratosthenes

2023-08-22
Kai Fan , Carl Pomerance
View PDF Chat

An inequality related to the sieve of Eratosthenes

2023-01-01
Steve Fan , Carl Pomerance
Let $\Phi(x,y)$ denote the number of integers $n\in[1,x]$ free of prime factors $\le y$. We show that but for a few small cases, $\Phi(x,y)<.6x/\log y$ when $y\le\sqrt{x}$. Let $\Phi(x,y)$ denote the number of integers $n\in[1,x]$ free of prime factors $\le y$. We show that but for a few small cases, $\Phi(x,y)<.6x/\log y$ when $y\le\sqrt{x}$.
View PDF Chat

Permutations with Arithmetic Constraints

2023-01-01
Carl Pomerance

On a problem of Evelyn--Linfoot and Page in additive number theory

2022-07-01
Carl Pomerance , D. Suryanarayana

A note on Carmichael numbers in residue classes

2022-04-19
Carl Pomerance
Improving on some recent results of Matomäki and of Wright, we show that the number of Carmichael numbers to X in a coprime residue class exceeds X1/(6 log log log … Improving on some recent results of Matomäki and of Wright, we show that the number of Carmichael numbers to X in a coprime residue class exceeds X1/(6 log log log X) for all sufficiently large X depending on the modulus of the residue class.
View PDF Chat

The denominators of the Bernoulli numbers

2022-03-17
Carl Pomerance , Samuel S. Wagstaff
We study the asymptotic density of the set of subscripts of the Bernoulli numbers having a given denominator. We also study the distribution of distinct Bernoulli denominators and some related … We study the asymptotic density of the set of subscripts of the Bernoulli numbers having a given denominator. We also study the distribution of distinct Bernoulli denominators and some related problems.
View PDF Chat

Permutations with arithmetic constraints

2022-01-01
Carl Pomerance
Let $S_{\rm lcm}(n)$ denote the set of permutations $\pi$ of $[n]=\{1,2,\dots,n\}$ such that ${\rm lcm}[j,\pi(j)]\le n$ for each $j\in[n]$. Further, let $S_{\rm div}(n)$ denote the number of permutations $\pi$ of … Let $S_{\rm lcm}(n)$ denote the set of permutations $\pi$ of $[n]=\{1,2,\dots,n\}$ such that ${\rm lcm}[j,\pi(j)]\le n$ for each $j\in[n]$. Further, let $S_{\rm div}(n)$ denote the number of permutations $\pi$ of $[n]$ such that $j\mid\pi(j)$ or $\pi(j)\mid j$ for each $j\in[n]$. Clearly $S_{\rm div}(n)\subset S_{\rm lcm}(n)$. We get upper and lower bounds for the counts of these sets, showing they grow geometrically. We also prove a conjecture from a recent paper on the number of "anti-coprime" permutations of $[n]$, meaning that each $\gcd(j,\pi(j))>1$ except when $j=1$.
View PDF Chat

Coprime permutations

2022-01-01
Carl Pomerance
Let $C(n)$ denote the number of permutations $\sigma$ of $[n]=\{1,2,\dots,n\}$ such that $\gcd(j,\sigma(j))=1$ for each $j\in[n]$. We prove that for $n$ sufficiently large, $n!/3.73^n < C(n) < n!/2.5^n$. Let $C(n)$ denote the number of permutations $\sigma$ of $[n]=\{1,2,\dots,n\}$ such that $\gcd(j,\sigma(j))=1$ for each $j\in[n]$. We prove that for $n$ sufficiently large, $n!/3.73^n < C(n) < n!/2.5^n$.
View PDF Chat

On the Critical Exponent for k-Primitive Sets

2021-11-25
Tsz Ho Chan , Jared Duker Lichtman , Carl Pomerance
View PDF Chat

Coprime matchings.

2021-11-15
Carl Pomerance
We prove that there is a matching between 2 intervals of positive integers of the same even length, with corresponding pairs coprime, provided the intervals are in $[n]$ and their … We prove that there is a matching between 2 intervals of positive integers of the same even length, with corresponding pairs coprime, provided the intervals are in $[n]$ and their lengths are $>c(\log n)^2$, for a positive constant $c$. This improves on a recent result of Bohman and Peng. As in their paper, the result has an application to the lonely runner conjecture.

On a nonintegrality conjecture

2021-10-12
Florian Luca , Carl Pomerance
View PDF Chat

On a nonintegrality conjecture

2021-06-15
Florian Luca , Carl Pomerance
It is conjectured that the sum $$ S_r(n)=\sum_{k=1}^{n} \frac{k}{k+r}\binom{n}{k} $$ for positive integers $r,n$ is never integral. This has been shown for $r\le 22$. In this note we study the … It is conjectured that the sum $$ S_r(n)=\sum_{k=1}^{n} \frac{k}{k+r}\binom{n}{k} $$ for positive integers $r,n$ is never integral. This has been shown for $r\le 22$. In this note we study the problem in the ``$n$ aspect showing that the set of $n$ such that $S_r(n)\in {\mathbb Z}$ for some $r\ge 1$ has asymptotic density $0$. Our principal tools are some deep results on the distribution of primes in short intervals.

Elliptic curves with Galois-stable cyclic subgroups of order 4

2021-04-30
Carl Pomerance , Edward F. Schaefer
View PDF Chat

Some thoughts on pseudoprimes

2021-03-01
Carl Pomerance , Samuel S. Wagstaff
We consider several problems about pseudoprimes. First, we look at the issue of their distribution in residue classes. There is a literature on this topic in the case that the … We consider several problems about pseudoprimes. First, we look at the issue of their distribution in residue classes. There is a literature on this topic in the case that the residue class is coprime to the modulus. Here we provide some robust statistics in both these cases and the general case. In particular we tabulate all even pseudoprimes to $10^{16}$. Second, we prove a recent conjecture of Ordowski: the set of integers $n$ which are a pseudoprime to some base which is a proper divisor of $n$ has an asymptotic density.

On primes and practical numbers

2021-02-15
Carl Pomerance , Andreas Weingartner
View PDF Chat

On a nonintegrality conjecture

2021-01-01
Florian Luca , Carl Pomerance
It is conjectured that the sum $$ S_r(n)=\sum_{k=1}^{n} \frac{k}{k+r}\binom{n}{k} $$ for positive integers $r,n$ is never integral. This has been shown for $r\le 22$. In this note we study the … It is conjectured that the sum $$ S_r(n)=\sum_{k=1}^{n} \frac{k}{k+r}\binom{n}{k} $$ for positive integers $r,n$ is never integral. This has been shown for $r\le 22$. In this note we study the problem in the ``$n$ aspect" showing that the set of $n$ such that $S_r(n)\in {\mathbb Z}$ for some $r\ge 1$ has asymptotic density $0$. Our principal tools are some deep results on the distribution of primes in short intervals.
View PDF Chat

The denominators of the Bernoulli numbers

2021-01-01
Carl Pomerance , Samuel S. Wagstaff
We study the asymptotic density of the set of subscripts of the Bernoulli numbers having a given denominator. We also study the distribution of distinct Bernoulli denominators and some related … We study the asymptotic density of the set of subscripts of the Bernoulli numbers having a given denominator. We also study the distribution of distinct Bernoulli denominators and some related problems.
View PDF Chat

Some thoughts on pseudoprimes

2021-01-01
Carl Pomerance , Samuel S. Wagstaff
We consider several problems about pseudoprimes. First, we look at the issue of their distribution in residue classes. There is a literature on this topic in the case that the … We consider several problems about pseudoprimes. First, we look at the issue of their distribution in residue classes. There is a literature on this topic in the case that the residue class is coprime to the modulus. Here we provide some robust statistics in both these cases and the general case. In particular we tabulate all even pseudoprimes to $10^{16}$. Second, we prove a recent conjecture of Ordowski: the set of integers $n$ which are a pseudoprime to some base which is a proper divisor of $n$ has an asymptotic density.

A note on Carmichael numbers in residue classes

2021-01-01
Carl Pomerance
Improving on some recent results of Matom\"aki and of Wright, we show that the number of Carmichael numbers to $X$ in a coprime residue class exceeds $X^{1/(6\log\log\log X)}$ for all … Improving on some recent results of Matom\"aki and of Wright, we show that the number of Carmichael numbers to $X$ in a coprime residue class exceeds $X^{1/(6\log\log\log X)}$ for all sufficiently large $X$ depending on the modulus of the residue class.
View PDF Chat

Coprime matchings

2021-01-01
Carl Pomerance
We prove that there is a matching between 2 intervals of positive integers of the same even length, with corresponding pairs coprime, provided the intervals are in $[n]$ and their … We prove that there is a matching between 2 intervals of positive integers of the same even length, with corresponding pairs coprime, provided the intervals are in $[n]$ and their lengths are $>c(\log n)^2$, for a positive constant $c$. This improves on a recent result of Bohman and Peng. As in their paper, the result has an application to the lonely runner conjecture.

On the critical exponent for $k$-primitive sets

2020-12-03
Tsz Ho Chan , Jared Duker Lichtman , Carl Pomerance
A set of positive integers is primitive (or 1-primitive) if no member divides another. Erdős proved in 1935 that the weighted sum $\sum1/(n \log n)$ for $n$ ranging over a … A set of positive integers is primitive (or 1-primitive) if no member divides another. Erdős proved in 1935 that the weighted sum $\sum1/(n \log n)$ for $n$ ranging over a primitive set $A$ is universally bounded over all choices for $A$. In 1988 he asked if this universal bound is attained by the set of prime numbers. One source of difficulty in this conjecture is that $\sum n^{-\lambda}$ over a primitive set is maximized by the primes if and only if $\lambda$ is at least the critical exponent $\tau_1 \approx 1.14$. A set is $k$-primitive if no member divides any product of up to $k$ other distinct members. One may similarly consider the critical exponent $\tau_k$ for which the primes are maximal among $k$-primitive sets. In recent work the authors showed that $\tau_2 < 0.8$, which directly implies the Erdős conjecture for 2-primitive sets. In this article we study the limiting behavior of the critical exponent, proving that $\tau_k$ tends to zero as $k\to\infty$.

Long gaps in sieved sets

2020-11-15
Kevin Ford , Sergey Konyagin , James Maynard +2 more
For each prime p , let I_p \subset \mathbb{Z}/p\mathbb{Z} denote a collection of residue classes modulo p such that the cardinalities |I_p| are bounded and about 1 on average. We … For each prime p , let I_p \subset \mathbb{Z}/p\mathbb{Z} denote a collection of residue classes modulo p such that the cardinalities |I_p| are bounded and about 1 on average. We show that for sufficiently large x , the sifted set \{n \in \mathbb{Z}: n (\mathrm {mod}\: p) \not \in I_p \: \mathrm {for \: all} p \leq x\} contains gaps of size x (\log x)^{\delta} depends only on the densitiy of primes for which I_p \neq \emptyset . This improves on the "trivial'' bound of \gg x . As a consequence, for any non-constant polynomial f: \mathbb{Z} \to \mathbb{Z} with positive leading coefficient, the set \{n \leq X: f(n) \; \mathrm {composite}\} contains an interval of consecutive integers of length \ge (\log X) (\log\log X)^{\delta} for sufficiently large X , where \delta &gt; 0 depends only on the degree of f .
View PDF Chat

On primes and practical numbers

2020-07-21
Carl Pomerance , Andreas Weingartner
A number $n$ is practical if every integer in $[1,n]$ can be expressed as a subset sum of the positive divisors of $n$. We consider the distribution of practical numbers … A number $n$ is practical if every integer in $[1,n]$ can be expressed as a subset sum of the positive divisors of $n$. We consider the distribution of practical numbers that are also shifted primes, improving a theorem of Guo and Weingartner. In addition, essentially proving a conjecture of Margenstern, we show that all large odd numbers are the sum of a prime and a practical number. We also consider an analogue of the prime $k$-tuples conjecture for practical numbers, proving the correct upper bound, and for pairs, improving on a lower bound of Melfi.

Phi, primorials, and Poisson

2020-07-01
Paul Pollack , Carl Pomerance
The primorial p # of a prime p is the product of all primes q ≤ p . Let pr ( n ) denote the largest prime p with p … The primorial p # of a prime p is the product of all primes q ≤ p . Let pr ( n ) denote the largest prime p with p # ∣ ϕ ( n ) , where ϕ is Euler's totient function. We show that the normal order of pr ( n ) is log log n / log log log n ; that is, pr ( n ) ∼ log log n / log log log n as n → ∞ on a set of integers of asymptotic density 1. In fact, we show there is an asymptotic secondary term and, on a tertiary level, there is an asymptotic Poisson distribution. We also show an analogous result for the largest integer k with k ! ∣ ϕ ( n ) .
View PDF Chat

Elliptic curves with Galois-stable cyclic subgroups of order 4

2020-04-30
Carl Pomerance , Edward F. Schaefer
Infinitely many elliptic curves over ${\bf Q}$ have a Galois-stable cyclic subgroup of order 4. Such subgroups come in pairs, which intersect in their subgroups of order 2. Let $N_i(X)$ … Infinitely many elliptic curves over ${\bf Q}$ have a Galois-stable cyclic subgroup of order 4. Such subgroups come in pairs, which intersect in their subgroups of order 2. Let $N_i(X)$ denote the number of elliptic curves over ${\bf Q}$ with at least $i$ pairs of Galois-stable cyclic subgroups of order 4, and height at most $X$. In this article we show that $N_1(X) = c_{1,1}X^{1/3}+c_{1,2}X^{1/6}+O(X^{0.105})$. We also show, as $X\to \infty$, that $N_2(X)=c_{2,1}X^{1/6}+o(X^{1/12})$, the precise nature of the error term being related to the prime number theorem and the zeros of the Riemann zeta-function in the critical strip. Here, $c_{1,1}= 0.95740\ldots$, $c_{1,2}=- 0.87125\ldots$, and $c_{2,1}= 0.035515\ldots$ are calculable constants. Lastly, we show that $N_i(X)=0$ for $i > 2$ (the result being trivial for $i>3$ given that an elliptic curve has 6 cyclic subgroups of order 4).

Counting elliptic curves with an isogeny of degree three

2020-03-04
Maggie Pizzo , Carl Pomerance , John Voight
We count by height the number of elliptic curves over <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper Q"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">Q</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbb {Q}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> that … We count by height the number of elliptic curves over <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper Q"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">Q</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbb {Q}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> that possess an isogeny of degree <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="3"> <mml:semantics> <mml:mn>3</mml:mn> <mml:annotation encoding="application/x-tex">3</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.
View PDF Chat

On the equation $\varphi (n)=\varphi (n+1)$

2020-01-01
Paul Kinlaw , Mitsuo KOBAYASHI , Carl Pomerance
We consider solutions of the equation $\varphi (n)=\varphi (n+1)$, where $\varphi $ denotes Euler’s function. Improving on previous work, we show that the reciprocal sum over all such $n$ is … We consider solutions of the equation $\varphi (n)=\varphi (n+1)$, where $\varphi $ denotes Euler’s function. Improving on previous work, we show that the reciprocal sum over all such $n$ is less than $8$.

On primes and practical numbers

2020-01-01
Carl Pomerance , Andreas Weingartner
A number $n$ is practical if every integer in $[1,n]$ can be expressed as a subset sum of the positive divisors of $n$. We consider the distribution of practical numbers … A number $n$ is practical if every integer in $[1,n]$ can be expressed as a subset sum of the positive divisors of $n$. We consider the distribution of practical numbers that are also shifted primes, improving a theorem of Guo and Weingartner. In addition, essentially proving a conjecture of Margenstern, we show that all large odd numbers are the sum of a prime and a practical number. We also consider an analogue of the prime $k$-tuples conjecture for practical numbers, proving the "correct" upper bound, and for pairs, improving on a lower bound of Melfi.

Elliptic curves with Galois-stable cyclic subgroups of order 4

2020-01-01
Carl Pomerance , Edward F. Schaefer
Infinitely many elliptic curves over ${\bf Q}$ have a Galois-stable cyclic subgroup of order 4. Such subgroups come in pairs, which intersect in their subgroups of order 2. Let $N_i(X)$ … Infinitely many elliptic curves over ${\bf Q}$ have a Galois-stable cyclic subgroup of order 4. Such subgroups come in pairs, which intersect in their subgroups of order 2. Let $N_i(X)$ denote the number of elliptic curves over ${\bf Q}$ with at least $i$ pairs of Galois-stable cyclic subgroups of order 4, and height at most $X$. In this article we show that $N_1(X) = c_{1,1}X^{1/3}+c_{1,2}X^{1/6}+O(X^{0.105})$. We also show, as $X\to \infty$, that $N_2(X)=c_{2,1}X^{1/6}+o(X^{1/12})$, the precise nature of the error term being related to the prime number theorem and the zeros of the Riemann zeta-function in the critical strip. Here, $c_{1,1}= 0.95740\ldots$, $c_{1,2}=- 0.87125\ldots$, and $c_{2,1}= 0.035515\ldots$ are calculable constants. Lastly, we show that $N_i(X)=0$ for $i > 2$ (the result being trivial for $i>3$ given that an elliptic curve has 6 cyclic subgroups of order 4).

Residue classes free of values of Euler's function

2020-01-01
Kevin R. Ford , Sergeĭ Konyagin , Carl Pomerance
We characterize which residue classes contain infinitely many totients (values of Euler's function) and which do not. We show that the union of all residue classes that are totient-free has … We characterize which residue classes contain infinitely many totients (values of Euler's function) and which do not. We show that the union of all residue classes that are totient-free has asymptotic density 3/4, that is, almost all numbers that are 2 mod 4 are in a residue class that is totient-free. In the other direction, we show the existence of a positive density of odd numbers m, such that for any $s\ge0$ and any even number $a$, the residue class $a\pmod{2^sm}$ contains infinitely many totients.
View PDF Chat

Cyclotomic Coincidences

2019-09-17
Carl Pomerance , Simon Rubinstein‐Salzedo
Let Φn denotes the nth cyclotomic polynomial. In this paper, we show that if m and n are distinct positive integers and x is a nonzero real number with Φm(x)=Φn(x), … Let Φn denotes the nth cyclotomic polynomial. In this paper, we show that if m and n are distinct positive integers and x is a nonzero real number with Φm(x)=Φn(x), then 12<|x|<2 except when {m,n}={2,6} and x = 2. We also observe that 2 appears to be the largest real limit point of the set of values of x for which Φm(x)=Φn(x) for some m≠n.
View PDF Chat

Proof of the Sheldon Conjecture

2019-09-14
Carl Pomerance , Chris Spicer
In [3 Byrnes, J., Spicer, C., Turnquist, A. (2015). The Sheldon conjecture. Math Horizons. 23(2): 12–15. DOI: 10.4169/mathhorizons.23.2.12.[Taylor & Francis Online] , [Google Scholar]], the authors introduce the concept of … In [3 Byrnes, J., Spicer, C., Turnquist, A. (2015). The Sheldon conjecture. Math Horizons. 23(2): 12–15. DOI: 10.4169/mathhorizons.23.2.12.[Taylor & Francis Online] , [Google Scholar]], the authors introduce the concept of a Sheldon prime, based on a conversation between several characters in the CBS television situation comedy The Big Bang Theory. The authors of [3 Byrnes, J., Spicer, C., Turnquist, A. (2015). The Sheldon conjecture. Math Horizons. 23(2): 12–15. DOI: 10.4169/mathhorizons.23.2.12.[Taylor & Francis Online] , [Google Scholar]] leave open the question of whether 73 is the unique Sheldon prime. This article answers this question in the affirmative.

COUNTING INTEGERS WITH A SMOOTH TOTIENT

2019-09-10
William D. Banks , John Friedlander , Carl Pomerance +1 more
Abstract In an earlier paper we considered the distribution of integers $n$ for which Euler’s totient function at $n$ has all small prime factors. Here we obtain an improvement that … Abstract In an earlier paper we considered the distribution of integers $n$ for which Euler’s totient function at $n$ has all small prime factors. Here we obtain an improvement that is likely to be best possible.
View PDF Chat

Algorithms for the Multiplication Table Problem

2019-08-12
Richard P. Brent , Carl Pomerance , David Purdum +1 more
Let $M(n)$ denote the number of distinct entries in the $n \times n$ multiplication table. The function $M(n)$ has been studied by Erd\H{o}s, Tenenbaum, Ford, and others, but the asymptotic … Let $M(n)$ denote the number of distinct entries in the $n \times n$ multiplication table. The function $M(n)$ has been studied by Erd\H{o}s, Tenenbaum, Ford, and others, but the asymptotic behaviour of $M(n)$ as $n \to \infty$ is not known precisely. Thus, there is some interest in algorithms for computing $M(n)$ either exactly or approximately. We compare several algorithms for computing $M(n)$ exactly, and give a new algorithm that has a subquadratic running time. We also present two Monte Carlo algorithms for approximate computation of $M(n)$. We give the results of exact computations for values of $n$ up to $2^{30}$, and of Monte Carlo computations for $n$ up to $2^{100,000,000}$, and compare our experimental results with Ford's order-of-magnitude result.

Symmetric primes revisited

2019-08-01
William D. Banks , Paul Pollack , Carl Pomerance
A pair of odd primes is said to be symmetric if each prime is congruent to one modulo their difference. A theorem from 1996 by Fletcher, Lindgren, and the third … A pair of odd primes is said to be symmetric if each prime is congruent to one modulo their difference. A theorem from 1996 by Fletcher, Lindgren, and the third author provides an upper bound on the number of primes up to x that belong to a symmetric pair. In the present paper, that theorem is improved to what is likely to be the best possible result. We also establish that there exist infinitely many symmetric pairs of primes. In fact, we show that for every integer m at least 2 there is a string of m consecutive primes, any two of which form a symmetric pair.

Progress towards a nonintegrality conjecture

2019-07-17
Shanta Laishram , Daniel López-Aguayo , Carl Pomerance +1 more
View PDF Chat

Counting elliptic curves with an isogeny of degree three

2019-06-19
Maggie Pizzo , Carl Pomerance , John Voight
We count by height the number of elliptic curves over the rationals that possess an isogeny of degree three. We count by height the number of elliptic curves over the rationals that possess an isogeny of degree three.

The Erdős conjecture for primitive sets

2019-04-10
Jared Duker Lichtman , Carl Pomerance
A subset of the integers larger than 1 is <italic>primitive</italic> if no member divides another. Erdős proved in 1935 that the sum of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1 slash left-parenthesis … A subset of the integers larger than 1 is <italic>primitive</italic> if no member divides another. Erdős proved in 1935 that the sum of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1 slash left-parenthesis a log a right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>a</mml:mi> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>a</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">1/(a\log a)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a"> <mml:semantics> <mml:mi>a</mml:mi> <mml:annotation encoding="application/x-tex">a</mml:annotation> </mml:semantics> </mml:math> </inline-formula> running over a primitive set <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A"> <mml:semantics> <mml:mi>A</mml:mi> <mml:annotation encoding="application/x-tex">A</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is universally bounded over all choices for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A"> <mml:semantics> <mml:mi>A</mml:mi> <mml:annotation encoding="application/x-tex">A</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. In 1988 he asked if this universal bound is attained for the set of prime numbers. In this paper we make some progress on several fronts and show a connection to certain prime number “races” such as the race between <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="pi left-parenthesis x right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>π<!-- π --></mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\pi (x)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal l normal i left-parenthesis x right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">l</mml:mi> <mml:mi mathvariant="normal">i</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {li}(x)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.
View PDF Chat

Progress towards a nonintegrality conjecture

2019-03-19
Shanta Laishram , Daniel López-Aguayo , Carl Pomerance +1 more
Given $r \in \mathbb{N}$, define the function $S_{r}: \mathbb{N} \rightarrow \mathbb{Q}$ by $S_{r}(n)=\displaystyle \sum_{k=0}^{n} \frac{k}{k+r} \binom{n}{k}$. In $2015$, the second author conjectured that there are infinitely many $r \in \mathbb{N}$ … Given $r \in \mathbb{N}$, define the function $S_{r}: \mathbb{N} \rightarrow \mathbb{Q}$ by $S_{r}(n)=\displaystyle \sum_{k=0}^{n} \frac{k}{k+r} \binom{n}{k}$. In $2015$, the second author conjectured that there are infinitely many $r \in \mathbb{N}$ such that $S_{r}(n)$ is nonintegral for all $n \geq 1$, and proved that $S_{r}(n)$ is not an integer for $r \in \{2,3,4\}$ and for all $n \geq 1$. In $2016$, Florian Luca and the second author raised the stronger conjecture that for any $r \geq 1$, $S_{r}(n)$ is nonintegral for all $n \geq 1$. They proved that $S_{r}(n)$ is nonintegral for $r \in \{5,6\}$ and that $S_{r}(n)$ is not an integer for any $r \geq 2$ and $1 \leq n \leq r-1$. In particular, for all $r \geq 2$, $S_{r}(n)$ is nonintegral for at least $r-1$ values of $n$. In $2018$, the fourth author gave sufficient conditions for the nonintegrality of $S_{r}(n)$ for all $n \geq 1$, and derived an algorithm to sometimes determine such nonintegrality; along the way he proved that $S_{r}(n)$ is nonintegral for $r \in \{7,8,9,10\}$ and for all $n \geq 1$. By improving this algorithm we prove the conjecture for $r\le 22$. Our principal result is that $S_r(n)$ is usually nonintegral in that the upper asymptotic density of the set of integers $n$ with $S_r(n)$ integral decays faster than any fixed power of $r^{-1}$ as $r$ grows.

Primes in prime number races

2019-02-08
Jared Duker Lichtman , Greg Martin , Carl Pomerance
Rubinstein and Sarnak have shown, conditional on the Riemann hypothesis (RH) and the linear independence hypothesis (LI) on the non-real zeros of $\zeta(s)$, that the set of real numbers $x\ge2$ … Rubinstein and Sarnak have shown, conditional on the Riemann hypothesis (RH) and the linear independence hypothesis (LI) on the non-real zeros of $\zeta(s)$, that the set of real numbers $x\ge2$ for which $\pi(x)>$ li$(x)$ has a logarithmic density, which they computed to be about $2.6\times10^{-7}$. A natural problem is to examine the actual primes in this race. We prove, assuming RH and LI, that the logarithmic density of the set of primes $p$ for which $\pi(p)>$ li$(p)$ relative to the prime numbers exists and is the same as the Rubinstein-Sarnak density. We also extend such results to a broad class of prime number races, including the "Mertens race" between $\prod_{p< x}(1-1/p)^{-1}$ and $e^{\gamma}\log x$ and the "Zhang race" between $\sum_{p\ge x}1/(p\log p)$ and $1/\log x$. These latter results resolve a question of the first and third author from a previous paper, leading to further progress on a 1988 conjecture of Erd\H{o}s on primitive sets.
View PDF Chat

Primality testing with Gaussian periods

2019-01-08
Hendrik W. Lenstra , Carl Pomerance
We exhibit a deterministic algorithm that, for some effectively computable real number c , decides whether a given integer n &gt; 1 is prime within time \mathrm {log} n)^6\cdot(2+\mathrm {log\log} … We exhibit a deterministic algorithm that, for some effectively computable real number c , decides whether a given integer n &gt; 1 is prime within time \mathrm {log} n)^6\cdot(2+\mathrm {log\log} n)^c . The same result, with 21/2 in place of 6 , was proved by Agrawal, Kayal, and Saxena. Our algorithm follows the same pattern as theirs, performing computations in an auxiliary ring extension of \mathbb Z/n\mathbb Z . We allow our rings to be generated by Gaussian periods rather than by roots of unity, which leaves us greater freedom in the selection of the auxiliary parameters and enables us to obtain a better run time estimate. The proof depends on results in analytic number theory and on the following theorem from additive number theory, which was provided by D. Bleichenbacher: if t is a real number with 0 &lt; t \le1 , and S is an open subset of the interval (0,t) with \int_S\mathrm d x/x &gt; t , then each real number greater than or equal to 1 is in the additive semigroup generated by S . A byproduct of our main result is an improved algorithm for constructing finite fields of given characteristic and approximately given degree.
View PDF Chat

Eigenvalues of the Laplacian on domains with fractal boundary

2019-01-01
Paul Pollack , Carl Pomerance
View PDF Chat

Symmetric primes revisited

2019-01-01
William D. Banks , Paul Pollack , Carl Pomerance
A pair of odd primes is said to be symmetric if each prime is congruent to one modulo their difference. A theorem from 1996 by Fletcher, Lindgren, and the third … A pair of odd primes is said to be symmetric if each prime is congruent to one modulo their difference. A theorem from 1996 by Fletcher, Lindgren, and the third author provides an upper bound on the number of primes up to x that belong to a symmetric pair. In the present paper, that theorem is improved to what is likely to be the best possible result. We also establish that there exist infinitely many symmetric pairs of primes. In fact, we show that for every integer m at least 2 there is a string of m consecutive primes, any two of which form a symmetric pair.

Algorithms for the Multiplication Table Problem

2019-01-01
Richard P. Brent , Carl Pomerance , David Purdum +1 more
Let $M(n)$ denote the number of distinct entries in the $n \times n$ multiplication table. The function $M(n)$ has been studied by Erd\H{o}s, Tenenbaum, Ford, and others, but the asymptotic … Let $M(n)$ denote the number of distinct entries in the $n \times n$ multiplication table. The function $M(n)$ has been studied by Erd\H{o}s, Tenenbaum, Ford, and others, but the asymptotic behaviour of $M(n)$ as $n \to \infty$ is not known precisely. Thus, there is some interest in algorithms for computing $M(n)$ either exactly or approximately. We compare several algorithms for computing $M(n)$ exactly, and give a new algorithm that has a subquadratic running time. We also present two Monte Carlo algorithms for approximate computation of $M(n)$. We give the results of exact computations for values of $n$ up to $2^{30}$, and of Monte Carlo computations for $n$ up to $2^{100,000,000}$, and compare our experimental results with Ford's order-of-magnitude result.
View PDF Chat

Counting elliptic curves with an isogeny of degree three

2019-01-01
Maggie Pizzo , Carl Pomerance , John Voight
We count by height the number of elliptic curves over the rationals that possess an isogeny of degree three. We count by height the number of elliptic curves over the rationals that possess an isogeny of degree three.
View PDF Chat

Progress towards a nonintegrality conjecture

2019-01-01
Shanta Laishram , Daniel López-Aguayo , Carl Pomerance +1 more
Given $r \in \mathbb{N}$, define the function $S_{r}: \mathbb{N} \rightarrow \mathbb{Q}$ by $S_{r}(n)=\displaystyle \sum_{k=0}^{n} \frac{k}{k+r} \binom{n}{k}$. In $2015$, the second author conjectured that there are infinitely many $r \in \mathbb{N}$ … Given $r \in \mathbb{N}$, define the function $S_{r}: \mathbb{N} \rightarrow \mathbb{Q}$ by $S_{r}(n)=\displaystyle \sum_{k=0}^{n} \frac{k}{k+r} \binom{n}{k}$. In $2015$, the second author conjectured that there are infinitely many $r \in \mathbb{N}$ such that $S_{r}(n)$ is nonintegral for all $n \geq 1$, and proved that $S_{r}(n)$ is not an integer for $r \in \{2,3,4\}$ and for all $n \geq 1$. In $2016$, Florian Luca and the second author raised the stronger conjecture that for any $r \geq 1$, $S_{r}(n)$ is nonintegral for all $n \geq 1$. They proved that $S_{r}(n)$ is nonintegral for $r \in \{5,6\}$ and that $S_{r}(n)$ is not an integer for any $r \geq 2$ and $1 \leq n \leq r-1$. In particular, for all $r \geq 2$, $S_{r}(n)$ is nonintegral for at least $r-1$ values of $n$. In $2018$, the fourth author gave sufficient conditions for the nonintegrality of $S_{r}(n)$ for all $n \geq 1$, and derived an algorithm to sometimes determine such nonintegrality; along the way he proved that $S_{r}(n)$ is nonintegral for $r \in \{7,8,9,10\}$ and for all $n \geq 1$. By improving this algorithm we prove the conjecture for $r\le 22$. Our principal result is that $S_r(n)$ is usually nonintegral in that the upper asymptotic density of the set of integers $n$ with $S_r(n)$ integral decays faster than any fixed power of $r^{-1}$ as $r$ grows.
View PDF Chat

Cyclotomic Coincidences

2019-01-01
Carl Pomerance , Simon Rubinstein‐Salzedo
In this paper, we show that if $m$ and $n$ are distinct positive integers and $x$ is a nonzero real number with $\Phi_m(x)=\Phi_n(x)$, then $\frac{1}{2}<|x|<2$ except when $\{m,n\}=\{2,6\}$ and $x=2$. … In this paper, we show that if $m$ and $n$ are distinct positive integers and $x$ is a nonzero real number with $\Phi_m(x)=\Phi_n(x)$, then $\frac{1}{2}<|x|<2$ except when $\{m,n\}=\{2,6\}$ and $x=2$. We also observe that 2 appears to be the largest limit point of the set of values of $x$ for which $\Phi_m(x)=\Phi_n(x)$ for some $m\neq n$.
View PDF Chat
Coauthor Papers Together
Florian Luca 27
Igor E. Shparlinski 16
Paul Pollack 15
Paul Erdős 13
Andràs Sárközy 10
Pär Kurlberg 9
William D. Banks 8
Richard E. Crandall 8
Sergeĭ Konyagin 8
David E. Penney 7
Kevin Ford 7
Andreas Weingartner 6
P. Erdős 6
Samuel S. Wagstaff 6
Jared Duker Lichtman 6
John Friedlander 5
Jeffrey C. Lagarias 5
Andrew Granville 5
Greg Martin 4
Daniel M. Gordon 4
Lola Thompson 4
E. Rodney Canfield 4
H. W. Lenstra 4
Shanta Laishram 3
Maggie Pizzo 3
David H. Bailey 3
John Voight 3
Jonathan M. Borwein 3
Edward F. Schaefer 3
Helmut Maier 3
Andrew R. Booker 3
Thotsaphon Thongjunthug 3
Gérald Tenenbaum 3
Douglas Ulmer 3
Daniel López-Aguayo 3
J. L. Selfridge 3
Juan José Alba González 3
Richard S. Crandall 3
Tsz Ho Chan 2
Simon Rubinstein‐Salzedo 2
Zachary Franco 2
Richard P. Brent 2
Richard J. Nowakowski 2
Melvyn B. Nathanson 2
Michel L. Lapidus 2
W. R. Alford 2
Sam Chow 2
Régis de la Bretèche 2
Michael Filaseta 2
C. L. Stewart 2

Approximate formulas for some functions of prime numbers

1962-03-01
J. Barkley Rosser , Lowell Schoenfeld
View PDF Chat

On The Number of Positive Integers ≤ x and Free of Prime Factors &gt; y

1951-01-01
N.G. de Bruijn

There are Infinitely Many Carmichael Numbers

1994-05-01
W. R. Alford , Andrew Granville , Carl Pomerance

On the distribution of amicable numbers. II.

1981-06-01
Carl Pomerance

On a problem of Oppenheim concerning “factorisatio numerorum”

1983-08-01
E. Rodney Canfield , Paul Erdős , Carl Pomerance

Multiplicative Number Theory

1980-01-01
H. Davenport

ON THE NORMAL NUMBER OF PRIME FACTORS OF <i>p</i>-1 AND SOME RELATED PROBLEMS CONCERNING EULER'S ø-FUNCTION

1935-01-01
P. Erdős
Journal Article ON THE NORMAL NUMBER OF PRIME FACTORS OF p-1 AND SOME RELATED PROBLEMS CONCERNING EULER'S ø-FUNCTION Get access PAUL ERDóS PAUL ERDóS Manchester Search for other works by … Journal Article ON THE NORMAL NUMBER OF PRIME FACTORS OF p-1 AND SOME RELATED PROBLEMS CONCERNING EULER'S ø-FUNCTION Get access PAUL ERDóS PAUL ERDóS Manchester Search for other works by this author on: Oxford Academic Google Scholar The Quarterly Journal of Mathematics, Volume os-6, Issue 1, 1935, Pages 205–213, https://doi.org/10.1093/qmath/os-6.1.205 Published: 01 January 1935 Article history Received: 13 November 1934 Published: 01 January 1935

Shifted primes without large prime factors

1998-01-01
Roger C. Baker , G. Harman
Ë Ø ÔÖ Ñ × Ë Ø ÔÖ Ñ ×
View PDF Chat

Carmichael's lambda function

1991-01-01
P. Erdős , Carl Pomerance , Eric Schmutz
View PDF Chat

An Introduction to the Theory of Numbers. By G. H. Hardy and E. M. Wright. 2nd edition. Pp. xvi, 407 25s. 1945. (Oxford)

1946-02-01
T. A. A. B.

Introduction to Analytic and Probabilistic Number Theory

2015-07-16
Gérald Tenenbaum
Elementary methods Some tools from real analysis Prime numbers Arithmetic functions Average orders Sieve methods Extremal orders The method of van der Corput Diophantine approximation Complex analysis methods The Euler … Elementary methods Some tools from real analysis Prime numbers Arithmetic functions Average orders Sieve methods Extremal orders The method of van der Corput Diophantine approximation Complex analysis methods The Euler gamma function Generating functions: Dirichlet series Summation formulae The Riemann zeta function The prime number theorem and the Riemann hypothesis The Selberg-Delange method Two arithmetic applications Tauberian theorems Primes in arithmetic progressions Probabilistic methods Densities Limiting distributions of arithmetic functions Normal order Distribution of additive functions and mean values of multiplicative functions Friable integers The saddle-point method Integers free of small factors Bibliography Index

Popular values of Euler's function

1980-06-01
Carl Pomerance

An introduction to the theory of numbers

1960-12-01
G. H. Hardy
View PDF Chat

On the distribution of pseudoprimes

1981-01-01
Carl Pomerance
Let<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper P left-parenthesis x right-parenthesis"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">P</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\mathcal {P}(x)</mml:annotation></mml:semantics></mml:math></inline-formula>denote the pseudoprime counting function. With<disp-formula content-type="math/mathml">\[<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L left-parenthesis x right-parenthesis equals exp … Let<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper P left-parenthesis x right-parenthesis"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">P</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\mathcal {P}(x)</mml:annotation></mml:semantics></mml:math></inline-formula>denote the pseudoprime counting function. With<disp-formula content-type="math/mathml">\[<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L left-parenthesis x right-parenthesis equals exp left-brace log x log log log x slash log log x right-brace comma"><mml:semantics><mml:mrow><mml:mi>L</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>exp</mml:mi><mml:mo>⁡<!-- ⁡ --></mml:mo><mml:mo fence="false" stretchy="false">{</mml:mo><mml:mi>log</mml:mi><mml:mo>⁡<!-- ⁡ --></mml:mo><mml:mi>x</mml:mi><mml:mi>log</mml:mi><mml:mo>⁡<!-- ⁡ --></mml:mo><mml:mi>log</mml:mi><mml:mo>⁡<!-- ⁡ --></mml:mo><mml:mi>log</mml:mi><mml:mo>⁡<!-- ⁡ --></mml:mo><mml:mi>x</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>log</mml:mi><mml:mo>⁡<!-- ⁡ --></mml:mo><mml:mi>log</mml:mi><mml:mo>⁡<!-- ⁡ --></mml:mo><mml:mi>x</mml:mi><mml:mo fence="false" stretchy="false">}</mml:mo><mml:mo>,</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">L(x) = \exp \{ \log x\log \log \log x/\log \log x\} ,</mml:annotation></mml:semantics></mml:math>\]</disp-formula>we prove<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper P left-parenthesis x right-parenthesis less-than-or-slanted-equals x bullet upper L left-parenthesis x right-parenthesis Superscript negative 1 slash 2"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">P</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>⩽<!-- ⩽ --></mml:mo><mml:mi>x</mml:mi><mml:mo>∙<!-- ∙ --></mml:mo><mml:mi>L</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:msup><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>−<!-- − --></mml:mo><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msup></mml:mrow></mml:mrow><mml:annotation encoding="application/x-tex">\mathcal {P}(x) \leqslant x \bullet L{(x)^{ - 1/2}}</mml:annotation></mml:semantics></mml:math></inline-formula>for large<italic>x</italic>, an improvement on the 1956 work of Erdös. We conjecture that<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper P left-parenthesis x right-parenthesis equals x bullet upper L left-parenthesis x right-parenthesis Superscript negative 1 plus o left-parenthesis 1 right-parenthesis"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">P</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>x</mml:mi><mml:mo>∙<!-- ∙ --></mml:mo><mml:mi>L</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:msup><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>−<!-- − --></mml:mo><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msup></mml:mrow></mml:mrow><mml:annotation encoding="application/x-tex">\mathcal {P}(x) = x \bullet L{(x)^{ - 1 + o(1)}}</mml:annotation></mml:semantics></mml:math></inline-formula>.
View PDF Chat

On pseudoprimes and Carmichael numbers

2022-07-01
P. Erdős

On the number of restricted prime factors of an integer. I

1976-12-01
Karl K. Norton
View PDF Chat

On Artin's conjecture.

1967-01-01
C. Hooley

Unsolved Problems in Number Theory

1994-01-01
Richard K. Guy
View PDF Chat

On the Normal Behavior of the Iterates Of some Arithmetic Functions

1990-01-01
Paul Erdős , Andew Granvilie , Carl Pomerance +1 more

On generalizing Artins conjecture on primitive roots to composite moduli

2003-01-18
Shuguang Li , Carl Pomerance
Article On generalizing Artins conjecture on primitive roots to composite moduli was published on March 18, 2003 in the journal Journal für die reine und angewandte Mathematik (volume 2003, issue … Article On generalizing Artins conjecture on primitive roots to composite moduli was published on March 18, 2003 in the journal Journal für die reine und angewandte Mathematik (volume 2003, issue 556).

Factoring Integers with Elliptic Curves

1987-11-01
H. W. Lenstra
This paper 19 devoted to the deacnption and analysis of a new algonthm to factor positive mtegers It depends on the use of elliptic curves The new m et b … This paper 19 devoted to the deacnption and analysis of a new algonthm to factor positive mtegers It depends on the use of elliptic curves The new m et b öd α obtained from Pollird's p-1-method (Proc Cambridge Philos Soc 76 (187-1), 521-528) by replacing the multiplicative group by tbe group of points on a random elliptic curve 1t u conjectured thit the algonthm determmes a non-tnvial divuor of a composite number n m expected time at most K(p)(logn)2, where p is the least pnme dmding n and K u a function for which logK(t)=v'(2+o(l))logiloElogz for t->oo In the worst case, when n la the product of two pnmes of the same order of magnitude, this is exp((l+o(l))\/lognloglogn) (for n->oo) There are several other factonng algonthms of which the conjectural expected running time is given by the latter formula However, these algonthms have a running time (hat is basically lodependent of the size of the pnme factors of n, whereas the new elliptic curve method is subatantially faster for amall p
View PDF Chat

An Introduction To The Theory Of Numbers

2008-07-31
G. H. Hardy , E. M. Wright
Abstract An Introduction to the Theory of Numbers by G.H. Hardy and E. M. Wright is found on the reading list of virtually all elementary number theory courses and is … Abstract An Introduction to the Theory of Numbers by G.H. Hardy and E. M. Wright is found on the reading list of virtually all elementary number theory courses and is widely regarded as the primary and classic text in elementary number theory. Developed under the guidance of D.R. Heath-Brown this Sixth Edition of An Introduction to the Theory of Numbers has been extensively revised and updated to guide today's students through the key milestones and developments in number theory. Updates include a chapter by J.H. Silverman on one of the most important developments in number theory -- modular elliptic curves and their role in the proof of Fermat's Last Theorem -- a foreword by A. Wiles, and comprehensively updated end-of-chapter notes detailing the key developments in number theory. Suggestions for further reading are also included for the more avid reader The text retains the style and clarity of previous editions making it highly suitable for undergraduates in mathematics from the first year upwards as well as an essential reference for all number theorists.
View PDF Chat

The pseudoprimes to 25⋅10⁹

1980-01-01
Carl Pomerance , J. L. Selfridge , Samuel S. Wagstaff
The odd composite<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n less-than-or-slanted-equals 25 dot 10 Superscript 9"><mml:semantics><mml:mrow><mml:mi>n</mml:mi><mml:mo>⩽<!-- ⩽ --></mml:mo><mml:mn>25</mml:mn><mml:mo>⋅<!-- ⋅ --></mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:msup><mml:mn>10</mml:mn><mml:mn>9</mml:mn></mml:msup></mml:mrow></mml:mrow><mml:annotation encoding="application/x-tex">n \leqslant 25 \cdot {10^9}</mml:annotation></mml:semantics></mml:math></inline-formula>such that<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 Superscript n minus 1 … The odd composite<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n less-than-or-slanted-equals 25 dot 10 Superscript 9"><mml:semantics><mml:mrow><mml:mi>n</mml:mi><mml:mo>⩽<!-- ⩽ --></mml:mo><mml:mn>25</mml:mn><mml:mo>⋅<!-- ⋅ --></mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:msup><mml:mn>10</mml:mn><mml:mn>9</mml:mn></mml:msup></mml:mrow></mml:mrow><mml:annotation encoding="application/x-tex">n \leqslant 25 \cdot {10^9}</mml:annotation></mml:semantics></mml:math></inline-formula>such that<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 Superscript n minus 1 Baseline identical-to 1 left-parenthesis mod n right-parenthesis"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:msup><mml:mn>2</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>n</mml:mi><mml:mo>−<!-- − --></mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:mrow><mml:mo>≡<!-- ≡ --></mml:mo><mml:mn>1</mml:mn><mml:mspace width="thickmathspace" /><mml:mspace width="0.667em" /><mml:mo stretchy="false">(</mml:mo><mml:mi>mod</mml:mi><mml:mspace width="0.333em" /><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">{2^{n - 1}} \equiv 1\;\pmod n</mml:annotation></mml:semantics></mml:math></inline-formula>have been determined and their distribution tabulated. We investigate the properties of three special types of pseudoprimes: Euler pseudoprimes, strong pseudoprimes, and Carmichael numbers. The theoretical upper bound and the heuristic lower bound due to Erdös for the counting function of the Carmichael numbers are both sharpened. Several new quick tests for primality are proposed, including some which combine pseudoprimes with Lucas sequences.
View PDF Chat

The distribution of integers with a divisor in a given interval

2008-09-01
Kevin Ford
We determine the order of magnitude of H(x, y, z), the number of integers n ≤ x having a divisor in (y, z], for all x, y and z.We also … We determine the order of magnitude of H(x, y, z), the number of integers n ≤ x having a divisor in (y, z], for all x, y and z.We also study H r (x, y, z), the number of integers n ≤ x having exactly r divisors in (y, z].When r = 1 we establish the order of magnitude of H 1 (x, y, z) for all x, y, z satisfying z ≤ x 1/2-ε .For every r ≥ 2, C > 1 and ε > 0, we determine the order of magnitude of H r (x, y, z) uniformly for y large and y + y/(log y) log 4-1-ε ≤ z ≤ min(y C , x 1/2-ε ).As a consequence of these bounds, we settle a 1960 conjecture of Erdős and some conjectures of Tenenbaum.One key element of the proofs is a new result on the distribution of uniform order statistics.
View PDF Chat

Integers without large prime factors

1993-01-01
Adolf Hildebrand , Gérald Tenenbaum
View PDF Chat

On Distinguishing Prime Numbers from Composite Numbers

1983-01-01
Leonard M. Adleman , Carl Pomerance , Robert Rumely

Probabilistic Number Theory I

1979-01-01
P. D. T. A. Elliott

The Difference between Consecutive Prime Numbers

1938-10-01
R. A. Rankin

Bemerkung zu der Arbeit �ber vollkommene Zahlen in Math. Ann. Bd. 133, S. 431?438 (1957)

1959-08-01
Eduard Wirsing

A new lower bound for the pseudoprime counting function

1982-03-01
Carl Pomerance

On the proportion of numbers coprime to a given integer

2008-07-18
Paul Erdős , Florian Luca , Carl Pomerance

Approximate Formulas for Some Functions of Prime Numbers

1963-07-01
D. S. , J. Barkley Rosser , Lowell Schoenfeld
View PDF Chat

The Difference between Consecutive Prime Numbers, III

1947-07-01
R. A. Rankin

Almost all primes can be quickly certified

1986-01-01
S. Goldwasser , Joe Kilian
Article Free Access Share on Almost all primes can be quickly certified Authors: S Goldwasser EECS Department and Laboratory for Computer Science, Massachusetts Institute of Technology EECS Department and Laboratory … Article Free Access Share on Almost all primes can be quickly certified Authors: S Goldwasser EECS Department and Laboratory for Computer Science, Massachusetts Institute of Technology EECS Department and Laboratory for Computer Science, Massachusetts Institute of TechnologyView Profile , J Kilian Department of Mathematics and Laboratory for Computer Science, Massachusetts Institute of Technology Department of Mathematics and Laboratory for Computer Science, Massachusetts Institute of TechnologyView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986Pages 316–329https://doi.org/10.1145/12130.12162Published:01 November 1986Publication History 103citation1,142DownloadsMetricsTotal Citations103Total Downloads1,142Last 12 Months171Last 6 weeks33 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
View PDF Chat

On the greatest common divisor of a number and its sum of divisors

2011-03-31
Paul Pollack

On the normal number of prime factors of $\phi(n)$

1985-06-01
Paul Erdős , Carl Pomerance
View PDF Chat

The large sieve

1973-12-01
Hugh L. Montgomery , R. C. Vaughan
View PDF Chat

The exceptional set of Goldbach's problem

1975-01-01
H. Montgomery , R. C. Vaughan
View PDF Chat

Note on Sequences of Integers No One of Which is Divisible By Any Other

1935-04-01
P. Erdős

On Euler’s totient function

1932-01-01
D. H. Lehmer
View PDF Chat

The fractional parts of the bernoulli numbers

1980-03-01
P. Erdős , Samuel S. Wagstaff
The fractional parts of the Bernoulli numbers are dense in the interval $(0,1)$. For every positive integer $k$, the set of all $m$ for which $B_{2m}$ has the same fractional … The fractional parts of the Bernoulli numbers are dense in the interval $(0,1)$. For every positive integer $k$, the set of all $m$ for which $B_{2m}$ has the same fractional part as $B_{2k}$ has positive asymptotic density.
View PDF Chat

Strong Carmichael numbers

1976-06-01
D. H. Lehmer
A composite number N is called a pseudoprime for the base a in case . An odd pseudoprime N is called strong for the base a . A composite number N is called a pseudoprime for the base a in case . An odd pseudoprime N is called strong for the base a .
View PDF Chat

On the Number of False Witnesses for a Composite Number

1986-01-01
Paul Erdős , Carl Pomerance
If u is not a multiple of n and a”-’ l 1 mod n 1 then n must be composite and u is called a “witness” for n. Let F(n) … If u is not a multiple of n and a”-’ l 1 mod n 1 then n must be composite and u is called a “witness” for n. Let F(n) denote the number of “false witnesses” for n, that is, the number of u mod n with CI”~ ’ = 1 mod n, Considered here is the normal and average size of F(n) for )I composite. Also considered is the situation for the more stringent Euler and strong pseudoprime tests.

On the number of positive integers ≤ x and free of prime factors &gt; y, II

1966-01-01
N.G. de Bruijn

Multiplicative structure of values of the Euler function

2004-05-25
William D. Banks , John Friedlander , Carl Pomerance +1 more
We establish upper bounds for the number of smooth values of the Euler function.In particular, although the Euler function has a certain "smoothing" effect on its integer arguments, our results … We establish upper bounds for the number of smooth values of the Euler function.In particular, although the Euler function has a certain "smoothing" effect on its integer arguments, our results show that, in fact, most values produced by the Euler function are not smooth.We apply our results to study the distribution of "strong primes", which are commonly encountered in cryptography.We also consider the problem of obtaining upper and lower bounds for the number of positive integers n ≤ x for which the value of the Euler function ϕ(n) is a perfect square and also for the number of n ≤ x such that ϕ(n) is squarefull.We give similar bounds for the Carmichael function λ(n).
View PDF Chat

On the Distribution of Pseudoprimes

1981-10-01
Carl Pomerance
Let 9 (x) denote the pseudoprime counting function.With L(x) = exp{log x log log log x/log log *}> we prove 9(x) < x ■ L(x)~'/2 for large x, an improvement … Let 9 (x) denote the pseudoprime counting function.With L(x) = exp{log x log log log x/log log *}> we prove 9(x) < x ■ L(x)~'/2 for large x, an improvement on the 1956 work of Erdös.We conjecture that 9(x) = x-L(x)"1+o(1).
View PDF Chat

The Brun-Titchmarsh Theorem on average

1996-01-01
Roger C. Baker , G. Harman
Throughout this paper a denotes a fixed non-zero integer and the letter p with or without subscript denotes a prime variable. As usual, for (q, a) = 1 we write … Throughout this paper a denotes a fixed non-zero integer and the letter p with or without subscript denotes a prime variable. As usual, for (q, a) = 1 we write $$ \pi \left( {x;\,q,\,a} \right)\, = \,\sum\limits_{\mathop {p \leqslant x}\limits_{p \equiv a(\bmod \,q)} } {1.} $$

Product-free sets with high density

2012-01-01
Pär Kurlberg , Jeffrey C. Lagarias , Carl Pomerance
We show that there are sets of integers with asymptotic density arbitrarily close to 1 in which there is no solution to the equation ab=c, with a,b,c in the set. … We show that there are sets of integers with asymptotic density arbitrarily close to 1 in which there is no solution to the equation ab=c, with a,b,c in the set. We also consider some natural generalizations, as well as a specific numerical example of a product-free set of integers with asymptotic density greater than 1/2.
View PDF Chat

Some problems of ‘Partitio numerorum’; III: On the expression of a number as a sum of primes

1923-01-01
G. H. Hardy , J. E. Littlewood
z.I.It was asserted by GOLDBACH, in a letter to "EuLER dated 7 June, 1742 , that every even number 2m is the sum o/two odd primes, ai~d this propos ition … z.I.It was asserted by GOLDBACH, in a letter to "EuLER dated 7 June, 1742 , that every even number 2m is the sum o/two odd primes, ai~d this propos ition has generally been described as 'Goldbach's Theorem'.There is no reasonable doubt that the theorem is correct, and that the number of representations is large when m is large; but all attempts to obtain a proof have been completely unsuccessful.Indeed it has never been shown that every number (or every large number, any number, that is to say, from a certain point onwards) is the sum of xo primes, or of i oooooo; and the problem was quite recently classified as among those 'beim gegenwiirtigen Stande der Wissensehaft unangreifbar'.~In this memoir we attack the problem with the aid of our new transcendental method in 'additiver Zahlentheorie'.~ We do not solve it: we do not
View PDF Chat

Estimating $\pi (x)$ and related functions under partial RH assumptions

2015-04-08
Jan Büthe
The aim of this paper is to give a direct interpretation of the validity of the Riemann hypothesis up to a certain height $T$ in terms of the prime-counting function … The aim of this paper is to give a direct interpretation of the validity of the Riemann hypothesis up to a certain height $T$ in terms of the prime-counting function $\pi(x)$. This is done by proving the well-known explicit Schoenfeld bound on the RH to hold as long as $4.92 \sqrt{x/\log(x)} \leq T$. Similar statements are proven for the Riemann prime-counting function and the Chebyshov functions $\psi(x)$ and $\vartheta(x)$. Apart from that, we also improve some of the existing bounds of Chebyshov type for the function $\psi(x)$.
View PDF Chat