A005598 -id:A005598 - cp's OEIS frontend

A049703 a(0) = 0; for n>0, a(n) = A005598(n)/2.

0, 1, 2, 4, 7, 12, 18, 27, 38, 52, 68, 89, 112, 141, 173, 209, 249, 297, 348, 408, 472, 542, 617, 703, 793, 893, 999, 1114, 1235, 1370, 1509, 1663, 1825, 1997, 2177, 2369, 2567, 2783, 3008, 3245, 3490, 3755, 4026, 4318

Offset: 0

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 0..5000

Cf. A005598, A046657, A049695.

A049703:= func< n | n eq 0 select 0 else (1 +(&+[(n-j+1)*EulerPhi(j): j in [1..n]]))/2 >;
[A049703(n): n in [0..60]]; // G. C. Greubel, Dec 08 2022

A005598[n_]:= A005598[n]= 1 +Sum[(n-j+1)*EulerPhi[j], {j,n}];
A049703[n_]:= If[n==0, 0, A005598[n]/2];
Table[A049703[n], {n,0,50}] (* G. C. Greubel, Dec 08 2022 *)

@CachedFunction
def A049703(n): return 0 if (n==0) else (1 + sum((n-j+1)*euler_phi(j) for j in range(1,n+1)))/2
[A049703(n) for n in range(61)] # G. C. Greubel, Dec 08 2022

a(n) = (1/2)*Sum_{j=0..n} T(j, n-j), for array T in A049695.

a(n) = (1/2)*(1 + (n+1)*A002088(n) - A011755(n)), with a(0) = 0. - G. C. Greubel, Dec 08 2022

Edited by N. J. A. Sloane, Apr 04 2007.

A049701 Duplicate of A005598.

Original entry on oeis.org

0, 2, 4, 8, 14, 24, 36, 54, 76, 104, 136, 178, 224, 282, 346, 418, 498, 594, 696, 816

Offset: 0

dead

A049695 Array T read by diagonals; T(i,j) is the number of nonnegative slopes of lines determined by 2 lattice points in [ 0,i ] X [ 0,j ] if i > 0; T(0,j)=1 if j > 0; T(0,0)=0.

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 4, 4, 1, 1, 5, 6, 6, 5, 1, 1, 6, 7, 8, 7, 6, 1, 1, 7, 9, 10, 10, 9, 7, 1, 1, 8, 10, 13, 12, 13, 10, 8, 1, 1, 9, 12, 14, 16, 16, 14, 12, 9, 1, 1, 10, 13, 17, 17, 20, 17, 17, 13, 10, 1, 1, 11, 15, 19, 21, 22, 22, 21, 19, 15, 11, 1, 1, 12, 16, 21, 23, 27, 24, 27

Offset: 0

Clark Kimberling

The infinity slope is not counted unless i=0 and j>0. - Max Alekseyev, Oct 23 2008

			Diagonals (each starting on row 1): {0}; {1,1}; {1,2,1}; ...

Max A. Alekseyev. On the number of two-dimensional threshold functions, arXiv:math/0602511 [math.CO], 2006-2010; SIAM J. Disc. Math. 24(4), 2010, pp. 1617-1631. doi:10.1137/090750184.

Cf. A005598, A049703, A114043.

For m,n > 0, T(m,n) = 1 + U(m,n) = 1 + Sum_{i=1..m, j=1..n, gcd(i,j)=1} 1. - Max Alekseyev, Oct 23 2008

More terms from Max Alekseyev, Oct 23 2008

A360042 Number of vertices in a Farey fan of order n.

Original entry on oeis.org

4, 6, 11, 17, 29, 39, 59, 79, 107, 133, 175, 213, 271, 323, 385, 451, 541, 621, 731, 835, 955, 1073, 1225, 1367, 1541, 1707, 1897, 2087, 2321, 2535, 2801, 3061, 3345, 3625, 3937, 4243, 4609, 4957, 5335, 5713, 6155, 6569, 7055, 7529, 8031, 8531, 9101, 9649, 10265, 10859

Offset: 1

Scott R. Shannon, N. J. A. Sloane and M. Douglas McIlroy Jan 23 2023

nonn

See the reference for the definition of a 'Farey fan'.
The number of vertices along each edge is A005728(n), while the number of regions is conjectured to equal A005598(n) = 1 + Sum_{i=1..n} (n-i+1)*phi(i). The regions count the number of distinct approximate representations of straight lines y = mx + b that can be drawn on an x-y integer raster, where x, y, and b are restricted to [0,n) and 0 <= m <=1.
It is also worth noting that for 3 <= n <= 10 this sequence equals 2*A005728(n) + A174030(n-2), where A174030(n) = Sum_{i=1..n} (i where phi(i)|i). That is, the number of internal vertices of the Farey fan equals A174030(n) in this range. This may suggest a possible attack on finding a formula for the present sequence.

M. Douglas McIlroy, A Note on Discrete Representation of Lines, AT&T Technical Journal, 64 (1985), 481-490.
Scott R. Shannon, Image for n = 2.
Scott R. Shannon, Image for n = 3.
Scott R. Shannon, Image for n = 4.
Scott R. Shannon, Image for n = 5.
Scott R. Shannon, Image for n = 6.
Scott R. Shannon, Image for n = 10.

Cf. A005598 (regions), A360043 (edges), A360044 (k-gons), A005728, A174030, A359974, A359968, A359690.

A180239 a(n) is the number of distinct billiard words with length n on an alphabet of 4 symbols.

Original entry on oeis.org

1, 4, 16, 64, 244, 856, 2776, 8356, 23032, 59200, 142624, 324484, 696256, 1422436, 2779900, 5219452, 9455596

Offset: 0

Fred Lunnon, Aug 18 2010

Computation: Fred Lunnon for n <= 16 (Magma).

			For n = 5 there are a(5) = 856 words, permutations on {1,2,3,4} of the 42 words
11111, 11112, 11121, 11123, 11211, 11212, 11213, 11231, 11234, 12111, 12112, 12113, 12121, 12122, 12123, 12131, 12132, 12134, 12212, 12213, 12221, 12222, 12223, 12231, 12232, 12234, 12311, 12312, 12313, 12314, 12321, 12322, 12323, 12324, 12331, 12332, 12333, 12334, 12341, 12342, 12343, 12344.

Jean-Pierre Borel, A geometrical Characterization of factors of multidimensional Billiards words and some Applications, Theoretical Computer Science 380 (2007) 286--303.
Fred Lunnon, Magma Program
Laurent Vuillon, Balanced Words, Bull. Belg. Math. Soc. 10 (2003), 787-805.

See A005598 for 2 symbols, A180238 for 3 symbols.

Magma
```
// See Links.
```

Expensive linear programming inequality analysis may be reduced by projecting each candidate word onto the axis hyperplanes, yielding m new (m-1)-symbol words which are necessarily also billiard, and can be validated from a precomputed list for dimension m-1. If any of these fails, the candidate fails; and if only one candidate remains after n-th symbols are attached to a valid (n-1)-length word, there is still no need for inequality analysis -- the ball cannot avoid bouncing next against some wall pair!

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

Original entry on oeis.org

0, 1, 3, 7, 13, 23, 35, 53, 75, 103, 135, 177, 223, 281, 345, 417, 497, 593, 695, 815, 943, 1083, 1233, 1405, 1585, 1785, 1997, 2227, 2469, 2739, 3017, 3325, 3649, 3993, 4353, 4737, 5133, 5565, 6015, 6489, 6979, 7509, 8051, 8635, 9239, 9867, 10517, 11213, 11925

Offset: 0

N. J. A. Sloane, Apr 04 2007

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Cf. A000010, A005598.

A103116:= func< n | n eq 0 select 0 else (&+[(n-j+1)*EulerPhi(j): j in [1..n]]) >;
[A103116(n): n in [0..60]]; // G. C. Greubel, Dec 08 2022

b:= proc(n) option remember; `if`(n<1, [0$2],
      (p-> p+[numtheory[phi](n), p[1]])(b(n-1)))
    end:
a:= n-> b(n+1)[2]:
seq(a(n), n=0..55);  # Alois P. Heinz, Oct 07 2021

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

@CachedFunction
def A103116(n): return sum( (n-j+1)*euler_phi(j) for j in range(1, n+1) )
[A103116(n) for n in range(61)] # G. C. Greubel, Dec 08 2022

a(n) = A005598(n) - 1.

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

A180238 a(n) is the number of distinct billiard words with length n on an alphabet of 3 symbols.

Original entry on oeis.org

1, 3, 9, 27, 75, 189, 447, 951, 1911, 3621, 6513, 11103, 18267, 29013, 44691, 67251, 98547, 140865, 197679, 272799, 370659, 497403, 658371, 859863, 1110453, 1420527, 1799373, 2260161, 2815401, 3479235, 4269279

Offset: 0

Fred Lunnon, Aug 18 2010

Computation: Allan C. Wechsler for n <= 5 (manual), Fred Lunnon for n <= 8 (Maple), Michael Kleber for n <= 30 (Mathematica).

			For n = 5 there are a(5) = 189 words, permutations on the alphabet {1,2,3} of the 32 words
11111, 11112, 11121, 11123, 11211, 11212, 11213, 11231, 12111, 12112, 12113, 12121, 12122, 12123, 12131, 12132, 12212, 12213, 12221, 12222, 12223, 12231, 12232, 12311, 12312, 12313, 12321, 12322, 12323, 12331, 12332, 12333.

N. Bedaride, Classification of rotations on the torus T^2, Theoretical Computer Science, 385 (2007), 214-225.
J.-P. Borel, A geometrical Characterization of factors of multidimensional Billiards words and some Applications, Theoretical Computer Science, 380 (2007) 286-303.
L. Vuillon, Balanced Words, Bull. Belg. Math. Soc., 10 (2003), 787-805.

See A005598 for 2 symbols, A180239 for 4 symbols.

(* Number of ways to interleave N elements from 3 arithmetic seqs *)
(* Program due to Michael Kleber, Aug 2010 *)
(* Given a string like "ABCABA", produce a set of inequalities *)
(* about the three arithmetic progressions giving successive A/B/Cs *)
(* The N-th occurrence (1-indexed) of character X corresponds to the value *)
(* BASE[X] + N * DELTA[X] *)
(* In all functions, seq is eg {"A", "B", "C", "A", "B", "A"} *)
(* The arithmetic-progression value of the i-th element of seq *)
value[seq_, i_] := BASE[seq[[i]]] + DELTA[seq[[i]]] * numoccur[seq,i]
numoccur[seq_, i_] := Count[Take[seq,If[i>0,i,Length[seq]+i+1]],seq[[i]]]
(* First element of the seq is greater than anything that would precede it*)
lowerbound[seq_] := (BASE[ # ] < value[seq,1])& /@ Union[seq]
(* Each element of the seq is greater than the previous one *)
upperbound[seq_] := (value[seq,-1] < value[Append[seq,# ],-1])& /@ Union[seq]
(* Last element of the seq is less than anything that would follow it *)
ordering[seq_] := Table[value[seq,i] < value[seq,i+1], {i,Length[seq]-1}]
ineqs[seq_] := Join[ lowerbound[seq], ordering[seq], upperbound[seq] ]
vars[seq_] := Join @@ ({BASE[ # ],DELTA[ # ]}& /@ Union[seq])
witness[seq_] := FindInstance[ ineqs[seq], vars[seq] ]
witness[s_String] := witness[Characters[s]]
(* All obtainable length-n shuffles of three arithmetic seqs: *)
names = {"A", "B", "C"}
shuf[0] := {""}
candidates[n_] := Flatten[Table[ob<>ch, {ob,shuf[n-1]}, {ch, names}]]
shuf[n_] := shuf[n] = Select[ candidates[n], witness[ # ] != {}& ]
(* Typical session *)
In[18]:= Table[Length[shuf[i]],{i,0,12}]
Out[18]= {1, 3, 9, 27, 75, 189, 447, 951, 1911, 3621, 6513, 11103, 18267}
In[19]:= TimeUsed[]/60 Out[19]= 6.73642

Computation may be expedited by generating only words in which the symbols occur in increasing alphabetic order: this was done in the production version.

A274005 Number of length-n binary sequences where the sum of each subblock differs by at most 2 from every other subblock of the same length.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 62, 120, 222, 410, 728, 1294, 2220, 3816, 6380, 10690, 17486, 28704, 46180, 74464, 118226, 188158, 295062, 464146, 721500, 1123384, 1731646, 2676538, 4094776, 6279380, 9562698, 14563312, 22043302, 33433502, 50357062, 75988618, 114092544

Offset: 0

Jeffrey Shallit, Jun 06 2016

nonn

			For n = 6, the strings 000111 and 111000 are not counted, since the sum of length-3 subblocks that begin and end differ by 3.

Rémy Sigrist, PARI program for A274005

Cf. A005598, which is the analogous sequence where "2" is replaced by "1".

Cf. A362063.

A274005 := proc(n)
    local a,b,lbdgs,bdgs,i,j,wrks,stri ;
    a := 0 ;
    for b from 0 to 2^n-1  do
        bdgs := convert(b,base,2) ;
        lbdgs := nops(bdgs) ;
        bdgs := [op(bdgs),seq(0,i=1..n-lbdgs)] ;
        wrks := true;
        for stri from 3 to n/2 do
            for i from 1 to n-stri do
            for j from i+1 to n-stri+1 do
                if abs(add(bdgs[u],u=i..i+stri-1) - add(bdgs[u],u=j..j+stri-1)) >2 then
                    wrks := false;
                end if ;
                if not wrks then
                    break;
                end if;
            end do:
            end do:
            if not wrks then
                break;
            end if;
        end do ;
        if wrks then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Jun 16 2016

PARI
```
See Links section.
```

More terms from Rémy Sigrist, Jun 24 2021

A180437 a(n) counts the distinct cubical (on alphabet of 3 symbols) billiard words with length n, acting as prefix to just k = 1 such word of length n+1 (that is, not "special").

Original entry on oeis.org

0, 0, 0, 6, 24, 78, 186, 372, 876, 1632, 3024, 5310, 8496, 13344, 21186, 31878, 46752, 66936, 94800, 130194

Offset: 0

Fred Lunnon, Sep 05 2010

By symmetry under reversal, a(n) also counts length n cubical billiard words acting as suffix to just k length n+1 cubical billiard words. The attached program counts k-special words for k = 1,...,m, where m = 3 denotes the size of the alphabet.

Fred Lunnon, Magma program

Cf. A005598, A180238, A180239, A180438, A180439.

Magma
```
// See Links.
```

A360044 Table read by rows: T(n,k) is the number of k-gons, 3<=k<=4, in a Farey fan of order n.

Original entry on oeis.org

0, 1, 4, 0, 6, 2, 10, 4, 14, 10, 22, 14, 30, 24, 42, 34, 54, 50, 74, 62, 94, 84, 118, 106, 142, 140, 178, 168, 214, 204, 258, 240, 302, 292, 358, 338, 414, 402, 478, 466, 542, 542, 626, 608, 710, 696, 802, 784, 894, 892, 1010, 988, 1126, 1102, 1254, 1216, 1382, 1358, 1526, 1492

Offset: 1

Scott R. Shannon, N. J. A. Sloane and M. Douglas McIlroy , Jan 23 2023

See the reference for the definition of a 'Farey fan', along with a proof that only 3-gons and 4-gons are created. See A360042 for further details and images of the graph.

			The table begins:
0, 1;
4, 0;
6, 2;
10, 4;
14, 10;
22, 14;
30, 24;
42, 34;
54, 50;
74, 62;
94, 84;
118, 106;
142, 140;
178, 168;
214, 204;
.
.

M. D. McIlroy, A Note on Discrete Representation of Lines, AT&T Technical Journal, 64 (1985), 481-490.
Scott R. Shannon, Image for n = 3.
Scott R. Shannon, Image for n = 4.
Scott R. Shannon, Image for n = 5.
Scott R. Shannon, Image for n = 6.
Scott R. Shannon, Image for n = 10.

Cf. A005598 (regions), A360042 (vertices), A360043 (edges), A005728, A174030, A359977, A359971, A359694.

cp's OEIS Frontend

A049703 a(0) = 0; for n>0, a(n) = A005598(n)/2.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

Extensions

A049701 Duplicate of A005598.

Views

Author

Keywords

A049695 Array T read by diagonals; T(i,j) is the number of nonnegative slopes of lines determined by 2 lattice points in [ 0,i ] X [ 0,j ] if i > 0; T(0,j)=1 if j > 0; T(0,0)=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A360042 Number of vertices in a Farey fan of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

A180239 a(n) is the number of distinct billiard words with length n on an alphabet of 4 symbols.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A180238 a(n) is the number of distinct billiard words with length n on an alphabet of 3 symbols.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A274005 Number of length-n binary sequences where the sum of each subblock differs by at most 2 from every other subblock of the same length.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

Extensions

A180437 a(n) counts the distinct cubical (on alphabet of 3 symbols) billiard words with length n, acting as prefix to just k = 1 such word of length n+1 (that is, not "special").