0,2

Number of possible interleaving orders for n consecutive distinct values from two arithmetic progressions. ABABBBA is impossible, for example, because "ABA" implies that the spacing between B's must be greater than 1/2 the spacing between A's. But "ABBBA" implies that the B-spacing must be less than 1/2 the A-spacing. - Allan C. Wechsler (acw(AT)ascent.com), Mar 16 2005. Since the interchange of A's and B's gives essentially the same order pattern, all terms will be even for n>0.

The SemialgebraicComponents procedure in the Algebra`AlgebraicInequalities` package of Mathematica may be used to determine whether a particular pattern is possible. - John W. Layman (layman(AT)math.vt.edu), Mar 30 2005.

Also, "digital lines": number of straight binary strings of length n [Dorst]. This was the original source for this sequence.

Also, number of finite Sturmian words of length n. The considered orders are exactly the balanced words, which have been proved to be the factors Sturmian sequences. An explicit formula has been exhibited by Mignosi in 1991. Berstel and Pocchiola gave a geometric proof of this, using Euler function for counting partitions of a unit cube. - Damien Jamet (jamet(AT)lirmm.fr), Apr 01 2005

a(n)=Sum{T(i,n-i): i=0,1,...,n}, array T as in A049695. - Clark Kimberling (ck6(AT)evansville.edu)

C. A. Berenstein and D. Lavine, A Geometric Approach to Subpixel Registration Accuracy, CVGIP 40, 1987, 334-360.

C. A. Berenstein amd D. Lavine, On the Number of Digital Straight Line Segments, IEEE PAMI, vol.10, no.6, 1988, 880-887

J. Berstel and M. Pocchiola. A geometric proof of the enumeration formula for Sturmian words. Internat. J. Algeb. Comput., 3(3):349-355, 1993.

L. Dorst, Discrete Straight Line Segments: Parameters, Primitives and Properties. Ph. D. Dissertation, Delft Univ. Technology, 1986. See p. 85.

L. Dorst and A. W. M. Smeulders, Discrete Representation of Straight Lines, IEEE PAMI-6, no.4, 1984, pp. 450-463.

L. Dorst and A. W. M. Smeulders, Discrete straight line segments: parameters, primitives and properties. Vision geometry (Hoboken, NJ, 1989), 45-62, Contemp. Math., 119, Amer. Math. Soc., Providence, RI, 1991.

F. Mignosi: On the Number of Factors of Sturmian Words. Theor. Comput. Sci. 82(1): 71-84 (1991)

T. D. Noe, Table of n, a(n) for n=0..1000

Asymptotically, a(n) behaves like n^3/pi^2. - Leo Dorst (leo(AT)science.uva.nl), Apr 02 2007

a(4) = 14 because of the 16 possible four-letter words from an alphabet of two letters, only AABB and BBAA are not possible interleaving orders for two arithmetic progressions.

For n=7, the pattern BAAAABA gives a possible ordering for the two arithmetic progressions {A, A+a, A+2a, A+3a,...} and {B, B+b, B+2b, B+3b,...} if the system of inequalities {a>0, b>0, A<B, B<A+a, A+4a<B+b, B+b<A+5a, A+5a<B+2b} has a solution. (Note: A<B is included to preclude a fifth A-term from lying between the two B-terms; similarly, A+5a<B+2b is included to preclude a second B-term from lying between the final two A-terms.) The SemialgebraicComponents procedure gives the solution {A,a,B,b}={0,1,1/8,4}; thus BAAAABA is one of the 54 possible orders of length 7. - John W. Layman (layman(AT)math.vt.edu), Mar30 2005.

f:= m -> add((m-i+1)*phi(i), i=1..m)+1; (Jamet)

Equals 2*A049703. Cf. A049695, A103116.

Sequence in context: A101687 A096461 A049701 this_sequence A100250 A053800 A091774

Adjacent sequences: A005595 A005596 A005597 this_sequence A005599 A005600 A005601

nonn,nice

njas

Extended by John W. Layman (layman(AT)math.vt.edu), Mar 30 2005

More terms from Emeric Deutsch (deutsch(AT)duke.poly.edu), Feb 04 2006

Entry revised by njas, Apr 04 2007