cp's OEIS Frontend

A005598 a(n) = 1 + Sum_{i=1..n} (n-i+1)*phi(i).

%I A005598 M1097 #65 Jan 24 2023 07:51:00
%S A005598 1,2,4,8,14,24,36,54,76,104,136,178,224,282,346,418,498,594,696,816,
%T A005598 944,1084,1234,1406,1586,1786,1998,2228,2470,2740,3018,3326,3650,3994,
%U A005598 4354,4738,5134,5566,6016,6490,6980,7510,8052,8636,9240,9868,10518,11214
%N A005598 a(n) = 1 + Sum_{i=1..n} (n-i+1)*phi(i).
%C A005598 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.
%C A005598 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
%C A005598 Also, "digital lines": number of straight binary strings of length n [Dorst]. This was the original source for this sequence.
%C A005598 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
%C A005598 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
%C A005598 Conjectured to be the number of regions in a Farey fan of order n. See A360042 for further details. - _Scott R. Shannon_, Jan 24 2023
%D A005598 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.
%D A005598 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005598 T. D. Noe, <a href="/A005598/b005598.txt">Table of n, a(n) for n = 0..1000</a>
%H A005598 C. A. Berenstein and D. Lavine, <a href="http://dx.doi.org/10.1016/S0734-189X(87)80146-9">A Geometric Approach to Subpixel Registration Accuracy</a>, CVGIP 40, 1987, 334-360.
%H A005598 C. A. Berenstein and D. Lavine, <a href="http://dx.doi.org/10.1109/34.9109">On the Number of Digital Straight Line Segments</a>, IEEE PAMI, vol.10, no.6, 1988, 880-887
%H A005598 J. Berstel and M. Pocchiola, <a href="http://dx.doi.org/10.1142/S0218196793000238">A geometric proof of the enumeration formula for Sturmian words</a>, Internat. J. Algeb. Comput., 3(3):349-355, 1993.
%H A005598 Michelangelo Bucci, Alessandro De Luca, Amy Glen and Luca Q. Zamboni, <a href="http://arxiv.org/abs/0802.1332">A connection between palindromic and factor complexity using return words</a>, arXiv:0802.1332 [math.CO], 2008.
%H A005598 Aldo de Luca and Stefano Varricchio,  <a href="http://dx.doi.org/10.1007/978-3-642-59849-4">Finiteness and regularity in semigroups and formal languages</a>, 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.
%H A005598 L. Dorst, <a href="http://resolver.tudelft.nl/uuid:b70b9de8-cb8b-480f-8a98-7bb07dee5a16">Discrete Straight Line Segments: Parameters, Primitives and Properties</a>, Ph. D. Dissertation, Delft Univ. Technology, 1986. See p. 85.
%H A005598 L. Dorst and A. W. M. Smeulders, <a href="http://doi.ieeecomputersociety.org/10.1109/TPAMI.1984.4767550">Discrete Representation of Straight Lines</a>, IEEE PAMI-6, no.4, 1984, pp. 450-463.
%H A005598 F. Mignosi, <a href="http://dx.doi.org/10.1016/0304-3975(91)90172-X">On the Number of Factors of Sturmian Words</a>, Theor. Comput. Sci. 82(1): 71-84 (1991)
%F A005598 a(n) = 2*A049703(n) for n >= 1.
%F A005598 a(n) = Sum_{i=0..n} A049695(i,n-i). - _Clark Kimberling_
%F A005598 Asymptotically, a(n) behaves like n^3/Pi^2. - Leo Dorst (leo(AT)science.uva.nl), Apr 02 2007
%F A005598 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
%F A005598 a(n) = 1 + (n+1)*A002088(n) - A011755(n). - _G. C. Greubel_, Dec 07 2022
%e A005598 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.
%e A005598 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
%p A005598 f:= m -> add((m-i+1)*phi(i),i=1..m)+1; (Jamet)
%t A005598 Accumulate@Accumulate@EulerPhi@Range[0,100]+1 (* _Vladimir Joseph Stephan Orlovsky_, Apr 21 2011 *)
%t A005598 Nest[Accumulate[#]&,EulerPhi[Range[0,50]],2]+1 (* _Harvey P. Dale_, Feb 07 2015 *)
%o A005598 (Haskell)
%o A005598 a005598 n = 1 + sum (zipWith (*) [n, n - 1 .. 1] a000010_list)
%o A005598 -- _Reinhard Zumkeller_, Apr 14 2013
%o A005598 (PARI) a(n) = 1 + sum(i=1, n, (n-i+1)*eulerphi(i)); \\ _Michel Marcus_, Aug 04 2016
%o A005598 (Magma)
%o A005598 A005598:= func< n | n eq 0 select 1 else 1 +(&+[(n-j+1)*EulerPhi(j): j in [1..n]]) >;
%o A005598 [A005598(n): n in [0..60]]; // _G. C. Greubel_, Dec 07 2022
%o A005598 (SageMath)
%o A005598 @CachedFunction
%o A005598 def A005598(n): return 1 + sum( (n-j+1)*euler_phi(j) for j in range(1,n+1) )
%o A005598 [A005598(n) for n in range(61)] # _G. C. Greubel_, Dec 07 2022
%Y A005598 Cf. A000010, A002088, A011755, A049695, A049703, A103116.
%K A005598 nonn,nice
%O A005598 0,2
%A A005598 _N. J. A. Sloane_
%E A005598 Extended by _John W. Layman_, Mar 30 2005
%E A005598 More terms from _Emeric Deutsch_, Feb 04 2006
%E A005598 Entry revised by _N. J. A. Sloane_, Apr 04 2007
%E A005598 Minor English revisions by _Jeffrey Shallit_, Aug 04 2016