Periodicity and Correlation Properties of d-FCSR Sequences

A d-feedback-with-carry shift register (d-FCSR) is a finite state machine, similar to a linear feedback shift register (LFSR), in which a small amount of memory and a delay (by d-clock cycles) is used in the feedback algorithm (see Goresky and Klapper [4,5]). The output sequences of these simple devices may be described using arithmetic in a ramified extension field of the rational numbers. In this paper we show how many of these sequences may also be described using simple integer arithmetic, and consequently how to find such sequences with large periods. We also analyze the arithmetic cross-correlation between pairs of these sequences and show that it often vanishes identically.     

Greedy algorithm, arithmetic progressions, subset sums and divisibility

We consider a number of density problems for integer sequences with certain divisibility properties and sequences free of arithmetic progressions. Sequences of the latter type that are generated by a computer using modifications of the greedy algorithm are also provided.     

Structure of three-interval exchange transformations II: a combinatorial description of the tranjectories

Astract  We describe an algorithm for generating the symbolic sequences which code the orbits of points under an interval exchange transformation on three intervals. The algorithm has two components. The first is an arithmetic division algorithm applied to the lengths of the intervals. This arithmetic construction was originally introduced by the authors in an earlier paper and may be viewed as a two-dimensional generalization of the regular continued fraction. The second component is a combinatorial algorithm which generates the bispecial factors of the associated symbolic subshift as a function of the arithmetic expansion. As a consequence, we obtain a complete characterization of those sequences of block complexity 2n+1 which are natural codings of orbits of three-interval exchange transformations, thereby answering an old question of Rauzy. Partially supported by NSF grant INT-9726708.     

Primes in arithmetic progression

A method for a computer search of primes in arithmetic progression is described. Six sequences of length 16 and 21 sequences of length 15 were found as well as numerous sequences of lengths 13 and 14.     

递推序列的一个注记

我们给出变系数线性递推序列的一个算术性质，它类似于常系数线性递推序列的情形。     

Seven consecutive primes in arithmetic progression

It is conjectured that there exist arbitrarily long sequences of consecutive primes in arithmetic progression. In 1967, the first such sequence of 6 consecutive primes in arithmetic progression was found. Searching for 7 consecutive primes in arithmetic progression is difficult because it is necessary that a prescribed set of at least 1254 numbers between the first and last prime all be composite. This article describes the search theory and methods, and lists the only known example of 7 consecutive primes in arithmetic progression.

     

Monochromatic paths for the integers

Recall that van der Waerden’s theorem states that any finite coloring of the naturals has arbitrarily long monochromatic arithmetic sequences. We explore questions about the set of differences of those sequences.     

An uncertainty principle for function fields

In a recent paper, Granville and Soundararajan (2007) [5] proved an “uncertainty principle” for arithmetic sequences, which limits the extent to which such sequences can be well-distributed in both short intervals and arithmetic progressions. In the present paper we follow the methods of Granville and Soundararajan (2007) [5] and prove that a similar phenomenon holds in Fq[t].     

Intrinsic Compiler Support for Interval Arithmetic

Interval arithmetic provides an efficient method for monitoring errors in numerical computations and for solving problems that cannot be efficiently solved with floating-point arithmetic. To support interval arithmetic, several software tools have been developed including interval arithmetic libraries, extended scientific programming languages, and interval-enhanced compilers. The main disadvantage of these software tools is their speed, since interval operations are implemented using function calls. In this paper, compiler support for interval arithmetic is investigated. In particular, the performance benefits of having the compiler inline interval operations to eliminate function call overhead is researched. Interval operations are inlined with the GNU gcc compiler and the performance of interval arithmetic is evaluated on a superscalar architecture. To implement interval operations with compiler support, the compiler produces sequences of instructions that use existing floating point hardware. Simulation results show that the compiler implementation of interval arithmetic is approximately 4 to 5 times faster than a functionally equivalent interval arithmetic software implementation with function call overhead and approximately 1.2 to 1.5 times slower than a dedicated interval arithmetic hardware implementation.     

A simple characterization of disjoint covering systems

A simple necessary and sufficient condition for a system of arithmetic sequences to cover the set of all integers is given.     

On the zeros of recurrence sequences with non-constant coefficients

The paper deals with the zeros of sequences, which satisfy linear recurrences with non-constant coefficients. We prove a weaker analogon of the Skolem-Mahler-Lech theorem on ordinary recurrent sequences. The proof relies on Szemerédi's theorem on arithmetic progressions in sets of positive density.     

Discrepancy of Fractions with Divisibility Constraints

We provide bounds for the absolute discrepancy of sequences of fractions with denominators streaming in a given arithmetic progression and satisfying divisibility constraints. Supported by the CERES Program 4-147/2004 of the Romanian Ministry of Education and Research.     

Discrepancy of Fractions with Divisibility Constraints

We provide bounds for the absolute discrepancy of sequences of fractions with denominators streaming in a given arithmetic progression and satisfying divisibility constraints.     

由有理数Cauchy列定义的实数的无限十进小数展开

讨论了有理数Cauchy列定义的实数系的一种等价形式———无限十进小数展开,定义了其上的算术运算与顺序并证明了它们和已有的定义一致.     

Infinite arithmetic formulas and the reflection principle

An extension of the language of arithmetic is constructed such that it allows us to work with recursive sequences of arithmetic formulas as if it were a single formula. It is proved that Feferman's reflection principles are inferable in the extension obtained. Supported by the Competitive Center for Basic Research (CCBR), grant No. 93-1-88-12. Translated fromAlgebra i Logika, Vol. 36, No. 3, pp. 245–258, May–June, 1997.     

The catenary degrees of elements in numerical monoids generated by arithmetic sequences

We compute the catenary degree of elements contained in numerical monoids generated by arithmetic sequences. We find that this can be done by describing each element in terms of the cardinality of its length set and of its set of factorizations. As a corollary, we find for such monoids that the catenary degree becomes fixed on large elements. This allows us to define and compute the dissonance number- the largest element with a catenary degree different from the fixed value. We determine the dissonance number in terms of the arithmetic sequence’s starting point and its number of generators.     

The Computational Complexity of Extrapolation Methods

This paper analyzes the cost of extrapolation methods for non-stiff ordinary differential equations depending on the number of digits of accuracy requested. Extrapolation of the explicit midpoint rule is applied for various number sequences. We show that for sequences with arithmetic growth, the cost of the method is polynomial in the number of digits of accuracy, while for sequences of numbers with geometric growth, the cost is super-polynomial with respect to the same parameter.     

关于Minc-Sathre不等式的推广与加强

利用不等式的等价形式和一个已知不等式,将Minc-Sathre不等式推广和加强至一类正项等差数列,得出一个优于Minc-Sathre不等式的结果,并对这一结果提供一个应用实例.     

Concentration of the Ratio between the Geometric and Arithmetic Means

We explore the concentration properties of the ratio between the geometric mean and the arithmetic mean, showing that for certain sequences of weights, one does obtain concentration around a value that depends on the sequence.     

Experiments on orthogonalization by biorthogonal representations of orthogonal projectors

A number of experiments are performed with the aim of enhancing a particular feature arising when biorthogonal sequences are used for the purpose of orthogonalization. It is shown that an orthogonalization process executed by biorthogonal sequences and followed by a re-orthogonalization step admits four numerically different realizations. The four possibilities are originated by the fact that, although an orthogonal projector is by definition a self-adjoint operator, due to numerical errors in finite precision arithmetic the biorthogonal representation does not fulfil such a property. In the experiments presented here one of the realizations is shown clearly numerically superior to the remaining three.