Approximating the number of integers without large prime factors

denotes the number of positive integers and free of prime factors . Hildebrand and Tenenbaum gave a smooth approximation formula for in the range , where is a fixed positive number . In this paper, by modifying their approximation formula, we provide a fast algorithm to approximate . The computational complexity of this algorithm is . We give numerical results which show that this algorithm provides accurate estimates for and is faster than conventional methods such as algorithms exploiting Dickman's function.

     

Approximating the number of integers free of large prime factors

Define to be the number of positive integers such that has no prime divisor larger than . We present a simple algorithm that approximates in floating point operations. This algorithm is based directly on a theorem of Hildebrand and Tenenbaum. We also present data which indicate that this algorithm is more accurate in practice than other known approximations, including the well-known approximation , where is Dickman's function.

     

The sum-product estimate for large subsets of prime fields

Let be the field of prime order It is known that for any integer one can construct a subset with such that

One of the results of the present paper implies that if with then

     

Additive problems for integers with a given number of prime divisors

The asymptotics of sums of the form Στ(|bn−a|) (summation overn<N, ω(n)=k) is studied, whereω(n) is the number of distinct prime divisors ofn, andτ(n) is the number of all divisors. Translated fromMatematicheskie Zametki, Vol. 63, No. 5, pp. 749–762, May, 1998. In conclusion, the author wishes to express his gratitude to Professor N. M. Timofeev for valuable advice. This research was supported by the Russian Foundation for Basic Research under grant No. 96-01-00502.     

On the difference between the number of prime divisors at consecutive integers

Suppose thatg(n) is equal to the number of divisors ofn, counting multiplicity, or the number of divisors ofn, a≠0 is an integer, andN(x,b)=|{n∶n≤x, g(n+a)−g(n)=b orb+1}|. In the paper we prove that sup _b N(x,b)≤C(a)x)(log log 10 _x )^−1/2 and that there exists a constantC(a,μ)>0 such that, given an integerb |b|≤μ(log logx)^1/2,x≥x _o, the inequalityN(x,b)≥C(a,μ)x(log logx(^−1/2) is valid. Translated fromMatematicheskie Zametki, Vol. 66, No. 4, pp. 579–595, October, 1999.     

A theorem on the -adic representation of positive integers

In this paper, a theorem on the asymptotic property of a summation of digits in a -adic representation is presented.

     

On the number of distinct prime factors of an odd perfect number

It is not known whether or not there exists an odd perfect number. We describe an algorithmic approach for showing that if there is an odd perfect number then it has t distinct prime factors, and we discuss its application towards showing that t9.     

Computing automorphisms of abelian number fields

Let be an abelian number field of degree . Most algorithms for computing the lattice of subfields of require the computation of all the conjugates of . This is usually achieved by factoring the minimal polynomial of over . In practice, the existing algorithms for factoring polynomials over algebraic number fields can handle only problems of moderate size. In this paper we describe a fast probabilistic algorithm for computing the conjugates of , which is based on -adic techniques. Given and a rational prime which does not divide the discriminant of , the algorithm computes the Frobenius automorphism of in time polynomial in the size of and in the size of . By repeatedly applying the algorithm to randomly chosen primes it is possible to compute all the conjugates of .

     

A Barban-Davenport-Halberstam theorem for integers with fixed number of prime divisors

The purpose of this paper is to study the distribution of integers with a given number prime divisors over arithmetic progressions, via using the large-sieve inequality, Huxley-Hooley contour and the zero-density estimate, and present a Barban-Davenport-Halberstam type theorem for it.     

Error estimate in a finite volume approximation of the partial asymptotic domain decomposition

The method of asymptotic partial domain decomposition has been proposed for partial differential equations set in rod structures, depending on a small parameter. It reduces the dimension of the problem (or simplifies it in another way) in the main part of the domain keeping the initial formulation in the remaining part and prescribing the asymptotically precise conditions on the interface. This paper is devoted to the finite volume implementation of the method of asymptotic partial domain decomposition. We consider a model problem in a thin domain (its thickness is a small parameter). We obtain an error estimate, expressed in terms of the small parameter and the step of the mesh. Copyright © 2013 John Wiley & Sons, Ltd.     

An additive divisor problem with a growing number of factors

Let τk(n) be the number of representations ofn as the product ofk positive factors, τ(n)=τ(n). The asymptotics of Σ _n≤x τ _k (n)τ(n+1) for 80k ¹⁰ (lnlnx)³≤lnx is shown to be uniform with respect tok. Translated fromMatematicheskie Zametki, Vol. 61, No. 3, pp. 391–406, March, 1997. Translated by N. K. Kulman     

Multicolor bipartite Ramsey number of C4 and large Kn,n

Let br_k(C₄;K_{n, n}) be the smallest N such that if all edges of K_{N, N} are colored by k + 1 colors, then there is a monochromatic C₄ in one of the first k colors or a monochromatic K_{n, n} in the last color. It is shown that br_k(C₄;K_{n, n}) = Θ(n²/log²n) for k?3, and br₂(C₄;K_{n, n})≥c(n n/log²n)² for large n. The main part of the proof is an algorithm to bound the number of large K_{n, n} in quasi‐random graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 47‐54, 2011     

Asymptotic estimate of the sum of a Dirichlet series on curves

Under quite general conditions, we obtain an asymptotic estimate of the sum of an entire Dirichlet series on curves. The result generalizes the well-known Pavlov and Kövari theorems     

The number of powers of 2 in a representation of large even integers II

It is proved that for any integerk≥ 54 000, there isN _k >0 depending onk only such that every even integer ≥N _k is a sum of two odd prime numbers andk powers of 2. Project partially supported by RGC Research Grant (No.HKU 7122/97P) and Post-Doctoral Fellowship of the University of Hong Kong.     

Slip and slide method of factoring trinomials with integer coefficients over the integers

In intermediate and college algebra courses there are a number of methods for factoring quadratic trinomials with integer coefficients over the integers. Some of these methods have been given names, such as trial and error, reversing FOIL, AC method, middle term splitting method and slip and slide method. The purpose of this article is to discuss the Slip and Slide Method and present a theoretical justification of why it works.     

The number of powers of 2 in a representation of large even integers (I)

Under the Generalized Riemann Hypothesis, it is proved that for any integer k⩾770 there is N_k>0 depending onk only such that every even integer ⩾N_k is a sum of two odd prime numbers andk powers of 2. The research is partially supported by RGC research grant (HKU 518/96P). The first author is supported by Post-Doctoral Fellowship of The University of Hong Kong.