Density of Carmichael numbers with three prime factors

We get an upper bound of on the number of Carmichael numbers with exactly three prime factors.

     

Elementary and combinatorial methods for counting prime numbers

Although prime numbers are elementary objects in number theory, the first non-trivial results about their distribution in history rely on analytical methods (see [10]). It was a big surprise when Erd?s [5] and Selberg [12] discovered new proofs of the celebrated prime number theorem without the help of advanced tools from (complex) analysis. However, both approaches, which are not completely unrelated (see [8]), still make use of limits, in particular the real logarithm. In this article we shall introduce a rational logarithm without using any limit, and then derive classical results first due to Euler, Chebyshev and Mertens. Moreover, we revisit all necessary elementary results about prime numbers, sometimes proven in a more combinatorial fashion than usual.     

A combinatorial identity involving relatively prime integers

In this note we establish an identity concerning the number of ways an element in the semigroup generated by two relatively prime integers can be written in terms of the other elements of the semigroup.     

On a class of relatively prime sequences

For each natural number n, let a₀(n) = n, and if a₀(n),…,a_i(n) have already been defined, let a_i+1(n) > a_i(n) be minimal with (a_i+1(n), a₀(n) … a_i(n)) = 1. Let g(n) be the largest a_i(n) not a prime or the square of a prime. We show that g(n) ～ n and that $\text{g(n) > n + cn}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{log}\text{(n)}$ for some c > 0. The true order of magnitude of g(n) ? n seems to be connected with the fine distribution of prime numbers. We also show that “most” a_i(n) that are not primes or squares of primes are products of two distinct primes. A result of independent interest comes of one of our proofs: For every sufficiently large n there is a prime $\text{p < n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ with [$\text{n}\text{p}$] composite.     

Special prime numbers and discrete logs in finite prime fields

A set of primes involving numbers such as , where and , is defined. An algorithm for computing discrete logs in the finite field of order with is suggested. Its heuristic expected running time is for , where as , , and . At present, the most efficient algorithm for computing discrete logs in the finite field of order for general is Schirokauer's adaptation of the Number Field Sieve. Its heuristic expected running time is for . Using rather than general does not enhance the performance of Schirokauer's algorithm. The definition of the set and the algorithm suggested in this paper are based on a more general congruence than that of the Number Field Sieve. The congruence is related to the resultant of integer polynomials. We also give a number of useful identities for resultants that allow us to specify this congruence for some .

     

Cycles of relatively prime length and the road coloring problem

We give a partial answer to theroad coloring problem, a purely graphtheoretical question with applications in both symbolic dynamics and automata theory. The question is whether for any positive integerk and for any aperiodic and strongly connected graphG with all vertices of out-degreek, we can labelG with symbols in an alphabet ofk letters so that all the edges going out from a vertex take a different label and all paths inG presenting a wordW terminate at the same vertex, for someW. Such a labelling is calledsynchronizing coloring ofG. Anyaperiodic graphG contains a setS of cycles where the greatest common divisor of the lengths equals 1. We establish some geometrical conditions onS to ensure the existence of a synchronizing coloring.     

Partition into terms with prime numbers

The survey covers works on the additive number theory during the period 1954–1977. Results pertaining to the classical problems of Goldbach, Hardy-Littlewood, and analogous problems are considered.Translated from Itogi Nauki i Tekhniki, Algebra, Topologiya, Geometriya, Vol. 16, pp. 5–33, 1978.     

Distribution of generalized Fermat prime numbers

Numbers of the form are called Generalized Fermat Numbers (GFN). A computational method for testing the probable primality of a GFN is described which is as fast as testing a number of the form . The theoretical distributions of GFN primes, for fixed , are derived and compared to the actual distributions. The predictions are surprisingly accurate and can be used to support Bateman and Horn's quantitative form of ``Hypothesis H" of Schinzel and Sierpinski. A list of the current largest known GFN primes is included.

     

Class numbers with many prime factors

Here, we construct infinitely many number fields of any given degree d>1 whose class numbers have many prime factors.     

The Noether numbers for cyclic groups of prime order

The Noether number of a representation is the largest degree of an element in a minimal homogeneous generating set for the corresponding ring of invariants. We compute the Noether number for an arbitrary representation of a cyclic group of prime order, and as a consequence prove the “2p−3 conjecture.”     

Chebyshev's bias for composite numbers with restricted prime divisors

Let denote the number of primes with . Chebyshev's bias is the phenomenon for which ``more often' \pi(x;d,r)$">, than the other way around, where is a quadratic nonresidue mod and is a quadratic residue mod . If for every up to some large number, then one expects that for every . Here denotes the number of integers such that every prime divisor of satisfies . In this paper we develop some tools to deal with this type of problem and apply them to show that, for example, for every .

In the process we express the so-called second order Landau-Ramanujan constant as an infinite series and show that the same type of formula holds for a much larger class of constants.

     

Exceptional characters and prime numbers in short intervals

Under the assumption of the Riemann hypothesis the asymptotic value y/log x is known to hold for the number of primes in the short interval [x - y, x] for for every fixed . We show under the assumption of the existence of exceptional Dirichlet characters the same asymptotic formula holds in the shorter intervals, for some \, in wide ranges of x depending on the characters.     

Prime and prime power divisibility of Catalan numbers

For any prime p, the sequence of Catalan numbers

$\text{a}{}_{\mathrm{n}}\text{=}\text{1}\text{n}\text{2n?2}\text{n?1}$

is divided by the a_n prime to p into blocks B_k(k > 0) of a_n divisible by p. The lengths and positions of the B_k are determined. Additional results are obtained on prime power divisibility of Catalan numbers.