Prime and composite integers close to powers of a number

We prove that, for any real numbers ξ ≠ 0 and ν, the sequence of integer parts [ξ2 ⁿ  + ν], n = 0, 1, 2, . . . , contains infinitely many composite numbers. Moreover, if the number ξ is irrational, then the above sequence contains infinitely many elements divisible by 2 or 3. The same holds for the sequence [ξ( ? 2) ⁿ  + ν _n ], n = 0, 1, 2, . . . , where ν ₀, ν ₁, ν ₂, . . . all lie in a half open real interval of length 1/3. For this, we show that if a sequence of integers x ₁, x ₂, x ₃, . . . satisfies the recurrence relation x _n+d  = cx _n  + F(x _n+1, . . . , x _n+d-1) for each n  ≥  1, where c ≠ 0 is an integer, \({F(z_1,\dots,z_{d-1}) \in \mathbb {Z}[z_1,\dots,z_{d-1}],}\) and lim _{n→ ∞}|x _n | = ∞, then the number |x _n | is composite for infinitely many positive integers n. The proofs involve techniques from number theory, linear algebra, combinatorics on words and some kind of symbolic computation modulo 3.     

Prime and composite numbers as integer parts of powers

We study prime and composite numbers in the sequence of integer parts of powers of a fixed real number. We first prove a result which implies that there is a transcendental number ξ>1 for which the numbers [ξ^{n !}], n =2,3, ..., are all prime. Then, following an idea of Huxley who did it for cubics, we construct Pisot numbers of arbitrary degree such that all integer parts of their powers are composite. Finally, we give an example of an explicit transcendental number ζ (obtained as the limit of a certain recurrent sequence) for which the sequence [ζⁿ], n =1,2,..., has infinitely many elements in an arbitrary integer arithmetical progression. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Prime divisors of sparse integers

We obtain a lower bound on the number of prime divisors of integers whose g-ary expansion contains a fixed number of nonzero digits. This revised version was published online in August 2006 with corrections to the Cover Date.     

Prime factors of consecutive integers

This note contains a new algorithm for computing a function introduced by Erdős to measure the minimal gap size in the sequence of integers at least one of whose prime factors exceeds . This algorithm enables us to show that is not monotone, verifying a conjecture of Ecklund and Eggleton.

     

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.     

On sums of powers of integers

K. Thanigasalam has shown that for any positive integer k the sequence of positive integers represented by $\text{x}{}_2{}^2\text{+ x}{}_3{}^3\text{+ x}{}_5{}^5\text{+ x}{}_1{}^{\mathrm{k}}$ has positive density. Here we prove that the asymptotic density of this sequence is 1, a similar result is proved for the sequence represented by $\text{x}{}_2{}^2\text{+ x}{}_3{}^3\text{+ x}{}_5{}^6\text{+ x}{}_1{}^{\mathrm{k}}$.     

Polynomial interpolation and sums of powers of integers

In this note, we revisit the problem of polynomial interpolation and explicitly construct two polynomials in n of degree k + 1, P_k(n) and Q_k(n), such that P_k(n) = Q_k(n) = f_k(n) for n = 1, 2,…?, k, where f_k(1), f_k(2),…?, f_k(k) are k arbitrarily chosen (real or complex) values. Then, we focus on the case that f_k(n) is given by the sum of powers of the first n positive integers S_k(n) = 1^k + 2^k + ??? + n^k, and show that S_k(n) admits the polynomial representations S_k(n) = P_k(n) and S_k(n) = Q_k(n) for all n = 1, 2,…?, and k ≥ 1, where the first representation involves the Eulerian numbers, and the second one the Stirling numbers of the second kind. Finally, we consider yet another polynomial formula for S_k(n) alternative to the well-known formula of Bernoulli.     

Representing powers of 2 by a sum of four integers

We solve an arithmetic problem due to Erdös and Freud (1986) investigated also by Freiman, Nathanson and Sárközy: How many elements from a given set of integers one must take to represent a power of 2 by their sum?     

An additive problem about powers of fixed integers

Résumé  SoitA un ensemble fini d'entiers ≥2. Nous étudions les propriétés de l'ensemble Σ(Pow(A)) des entiers positifs qui sont une somme de puissances distinctes d'éléments deA. Erd?s posa le problème suivant: démontrer que Σ(Pow({3,4})) a densité asymtotique superieure positive. Nous démontrons que la fonction qui les énumère vérifieP _{3,4}(x)≫x^0.9659.      

Expressing powers of integers as the difference of squares

Three results are presented for expressing any power (greater than or equal to three) of any whole number as the difference of the squares of two other whole numbers.     

On powers of the Heaviside function for negative integers

The distributions and were defined as the neutrix limit of the sequences and respectively for , see [J.D. Nicholos, B. Fisher, The distribution composition , J. Math. Anal. Appl. 258 (2001) 131-145; B. Fisher, On defining the distribution , Univ. u Novom Sadu Zb. Rad. Prirod. Mat. Fak. Ser. Mat. 15 (1985) 119-129]. We here consider these distributions when r=0. In other words, we define the sth powers of the Heaviside function H(x) in the distributional sense for negative integers. Further compositions are also considered.     

On sets of integers whose shifted products are powers

Let N be a positive integer and let A be a subset of {1,…,N} with the property that aa^′+1 is a pure power whenever a and a^′ are distinct elements of A. We prove that |A|, the cardinality of A, is not large. In particular, we show that |A|?(logN)^2/3(loglogN)^1/3.     

Simultaneous rational approximation to the successive powers of a real number

Let n be an integer ≥ 1 and let θ be a real number which is not an algebraic number of degree ≤ [n/2]. We show that there exist ? > 0 and arbitrary large real numbers X such that the system of linear inequalities |x₀| ≤ X and |x₀θ^j − x_j| ≤ ?X^−1/[n/2] for 1 < j < n, has only the zero solution in rational integers x₀,…, x_n. This result refines a similar statement due to H. Davenport and W. M. Schmidt, where the upper integer part [n/2] is replaced everywhere by the integer part [n/2]. As a corollary, we improve slightly the exponent of approximation to 0 by algebraic integers of degree n + 1 over Q obtained by these authors.     

Possible isolation number of a matrix over nonnegative integers

Let ?₊ be the semiring of all nonnegative integers and A an m × n matrix over ?₊. The rank of A is the smallest k such that A can be factored as an m × k matrix times a k×n matrix. The isolation number of A is the maximum number of nonzero entries in A such that no two are in any row or any column, and no two are in a 2 × 2 submatrix of all nonzero entries. We have that the isolation number of A is a lower bound of the rank of A. For A with isolation number k, we investigate the possible values of the rank of A and the Boolean rank of the support of A. So we obtain that the isolation number and the Boolean rank of the support of a given matrix are the same if and only if the isolation number is 1 or 2 only. We also determine a special type of m×n matrices whose isolation number is m. That is, those matrices are permutationally equivalent to a matrix A whose support contains a submatrix of a sum of the identity matrix and a tournament matrix.     

Formulas for sums of powers of integers by functional equations

This paper presents a direct and simple approach to obtaining the formulas forS _k(n)= 1 ^k + 2 ^k + ... +n ^k wheren andk are nonnegative integers. A functional equation is written based on the functional properties ofS _k (n) and several methods of solution are presented. These lead to several recurrence relations for the functions and a simple one-step differential-recurrence relation from which the polynomials can easily be computed successively. Arbitrary constants which arise are (almost) the Bernoulli numbers when evaluated and identities for these modified Bernoulli numbers are obtained. The functional equation for the formulas leads to another functional equation for the generating function for these formulas and this is used to obtain the generating functions for theS _k 's and for the modified Bernoulli numbers. This leads to an explicit representation, not a recurrence relation, for the modified Bernoulli numbers which then yields an explicit formula for eachS _k not depending on the earlier ones. This functional equation approach has been and can be applied to more general types of arithmetic sequences and many other types of combinatorial functions, sequences, and problems.     

Representations of integers as sums of powers with increasing exponents

Let(n) be the least integer such thatn may be represented in the formn=x ₁ ² +x ₂ ³ +...+x _(n) ⁽ⁿ⁾⁺¹ wherex ₁,x ₂, ...,x _(n) are natural numbers. We computed(n) forn 250 000 and found that(n) 5 for all thesen exceptn=56, 160 for which(n)=6. Also(n) 4 for 41542<n<=250 000.     

On fractional parts of powers of real numbers close to 1

We prove that there exist arbitrarily small positive real numbers ε such that every integral power ${(1 + \varepsilon)^n}$ is at a distance greater than ${2^{-17} \varepsilon |\log \varepsilon |^{-1}}$ to the set of rational integers. This is sharp up to the factor ${2^{-17} |\log\varepsilon |^{-1}}$ . We also establish that the set of real numbers α > 1 such that the sequence of fractional parts ${(\{\alpha^n\})_{n\ge 1}}$ is not dense modulo 1 has full Hausdorff dimension.     

Prime and composite Laurent polynomials

In the paper [J. Ritt, Prime and composite polynomials, Trans. Amer. Math. Soc. 23 (1922) 51-66] Ritt constructed the theory of functional decompositions of polynomials with complex coefficients. In particular, he described explicitly polynomial solutions of the functional equation f(p(z))=g(q(z)). In this paper we study the equation above in the case where f,g,p,q are holomorphic functions on compact Riemann surfaces. We also construct a self-contained theory of functional decompositions of rational functions with at most two poles generalizing the Ritt theory. In particular, we give new proofs of the theorems of Ritt and of the theorem of Bilu and Tichy.