login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005598 a(n) = 1 + Sum_{i=1..n} (n-i+1)*phi(i).
(Formerly M1097)
15
1, 2, 4, 8, 14, 24, 36, 54, 76, 104, 136, 178, 224, 282, 346, 418, 498, 594, 696, 816, 944, 1084, 1234, 1406, 1586, 1786, 1998, 2228, 2470, 2740, 3018, 3326, 3650, 3994, 4354, 4738, 5134, 5566, 6016, 6490, 6980, 7510, 8052, 8636, 9240, 9868, 10518, 11214 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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, 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, Mar 30 2005

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

Also, the number of finite Sturmian words of length n. The considered orders are exactly the balanced words, which have been proved to be the factors of Sturmian sequences. An explicit formula was exhibited by Mignosi in 1991. Berstel and Pocchiola gave a geometric proof of this, using Euler's 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

The first difference of a(n) is the number of 'special' words, prefix of two Sturmian words of length n+1; see A002088. The second difference of a(n) is the number of palindromic 'bispecial' words, prefix and suffix of two Sturmian words of length n+1; see A000010. - Fred Lunnon, Sep 05 2010

REFERENCES

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.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

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

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

C. A. Berenstein and 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.

Michelangelo Bucci, Alessandro De Luca, Amy Glen and Luca Q. Zamboni, A connection between palindromic and factor complexity using return words, arXiv:0802.1332 [math.CO], 2008.

Aldo de Luca and Stefano Varricchio,  Finiteness and regularity in semigroups and formal languages, Monographs in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 1999. x+240 pp. ISBN: 3-540-63771-0 MR1696498 (2000g:68001). See p. 25.

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.

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

FORMULA

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

G.f.: 1/(1 - x) + (1/(1 - x)^2)*Sum_{k>=1} mu(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Mar 16 2017

EXAMPLE

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, Mar 30 2005

MAPLE

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

MATHEMATICA

Accumulate@Accumulate@EulerPhi@Range[0, 100]+1 (* Vladimir Joseph Stephan Orlovsky, Apr 21 2011 *)

Nest[Accumulate[#]&, EulerPhi[Range[0, 50]], 2]+1 (* Harvey P. Dale, Feb 07 2015 *)

PROG

(Haskell)

a005598 n = 1 + sum (zipWith (*) [n, n - 1 .. 1] a000010_list)

-- Reinhard Zumkeller, Apr 14 2013

(PARI) a(n) = 1 + sum(i=1, n, (n-i+1)*eulerphi(i)); \\ Michel Marcus, Aug 04 2016

CROSSREFS

Equals 2*A049703. Cf. A049695, A103116.

Cf. A000010.

Sequence in context: A101687 A096461 A049701 * A290845 A100250 A053800

Adjacent sequences:  A005595 A005596 A005597 * A005599 A005600 A005601

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Extended by John W. Layman, Mar 30 2005

More terms from Emeric Deutsch, Feb 04 2006

Entry revised by N. J. A. Sloane, Apr 04 2007

Minor English revisions by Jeffrey Shallit, Aug 04 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 18:12 EST 2019. Contains 329847 sequences. (Running on oeis4.)