Jamie Simpson - cp's OEIS frontend

User: Jamie Simpson

Jamie Simpson has authored 4 sequences.

A274170 Christoffel words as binary numbers.

2, 4, 6, 8, 14, 16, 20, 26, 30, 32, 62, 64, 72, 84, 106, 118, 126, 128, 164, 218, 254, 256, 272, 340, 426, 494, 510, 512, 584, 950, 1022, 1024, 1056, 1160, 1316, 1364, 1706, 1754, 1910, 2014, 2046, 2048, 2708, 3434, 4094, 4096, 4160, 4368, 4680, 5284, 5460, 6826, 7002, 7606, 7918, 8126, 8190

Offset: 1

Jamie Simpson, Jun 11 2016

The Christoffel word of slope b/a is defined as follows:

Start at (0,0) in the 2-dimensional integer lattice and move up if possible, otherwise right, always keeping below or on the line y = b*x/a. Write down x for a horizontal move and y for a vertical move. The first move is necessarily horizontal, so the sequence always begins with x. Stop when you get to (a,b). The word then has length a+b and contains a copies of x and b of y (see Berstel et al., p. 6, Fig. 2). The symbols x and y are arbitrary: we replace x with 1 and y with 0 and treat the resulting word as a binary number. The sequence is in increasing order of decimal equivalents. The Christoffel word with least decimal equivalent is 10 with decimal equivalent 2.

			The Christoffel word of slope 4/7 is xxyxxyxxyxy which becomes 11011011010 with decimal equivalent 1754.

J. Berstel et al., Combinatorics on Words: Christoffel Words and Repetitions in Words, Amer. Math. Soc., 2008.

Cf. A144595-A144602 (with slightly different definition of Christoffel word).

christoffel := proc (a, b) local n, x, y, ans; x := 1; y := 0; ans := 2^(a+b-1); for n to a+b-1 do if y+1 <= a*x/b then y := y+1 else ans := ans+2^(a+b-n-1); x := x+1 end if end do; ans end proc;
for n from 2 to 12 do for b to n-1 do a := n-b; if gcd(a, n) = 1 then printf("%4d, ", christoffel(a, b)) end if end do end do

A268084 Minimum number of occurrences of abelian squares in a binary word of length n.

Original entry on oeis.org

0, 0, 0, 1, 2, 3, 4, 4, 5, 6, 7, 8, 10, 11, 12, 14, 15, 17, 18, 20, 21, 23, 24, 26, 28, 29, 30, 32, 34, 35, 37, 39, 41, 43, 44

Offset: 1

Jamie Simpson, Jan 26 2016

A binary word is a sequence each member of which belongs to an alphabet of size 2 such as {a,b}. An abelian square is an even length factor whose first half is an anagram of the second half, for example abaaaaab.
One can also ask for the minimum number of distinct abelian squares in a word of length n and the minimum number of nonequivalent abelian squares. Two abelian squares are equivalent if they are anagrams of each other.
For example the word ababbaaabaa contains 5 distinct abelian squares, aa, bb, abab, abba and baaaba, but only 4 nonequivalent abelian squares since abab and abba are equivalent. It's conjectured that both the minimum number of distinct abelian squares in a binary word of length n and the minimum number of nonequivalent abelian squares equal floor(n/4)

			For example the least number of occurrences of abelian squares in a binary word of length 11 is 7. There are 12 words which attain this minimum.  One is ababbaaabaa which contains 3 occurrences of aa and one each of bb, abab, abba and baaaba.

G. Fici and A. Saarela, On the minimum number of abelian squares in a word, Combinatorics and Algorithmics of Strings, Dagstuhl Reports, 4(2014), pages 34-35.

A. S. Fraenkel, J. Simpson, and M. Paterson, On weak circular squares in binary words, Combinatorial Pattern Matching, Springer Berlin Heidelberg, 1997, pages 76-82.
Jamie Simpson, Solved and unsolved problems about abelian squares, arXiv:1802.04481 [math.CO], 2018.

A262249 gives the maximum number of distinct abelian squares in a binary word of length n and A262265 gives the maximum number of nonequivalent abelian squares.

from itertools import product, permutations
def count_overlaps(subs, s):
  c = i = 0
  while i != -1:
    i = s.find(subs, i)
    if i != -1: c += 1; i += 1
  return c
def a(n): # only check words starting with 0 by symmetry
  ar = ("".join(u) for r in range(1, n//2+1) for u in product("01",
repeat=r))
  abel_squares = set(w+"".join(wp) for w in ar for wp in permutations(w))
  words = ("0"+"".join(w) for w in product("10", repeat=n-1))
  themin = n*n
  for w in words:
    numw = 0
    for s in abel_squares:
      numw += count_overlaps(s, w)
      if numw >= themin: break
    else: themin = min(themin, numw)
  return themin
print([a(n) for n in range(1, 14)]) # Michael S. Branicky, Dec 20 2020

a(21)-a(35) from Lars Blomberg, Feb 04 2016

A123298 Number of incongruent restricted disjoint covering systems (IRDCS) of length n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 4, 6, 18, 14, 26, 84, 88, 46, 176, 380, 812, 844, 1770, 2164, 5554, 9244, 25384, 62092, 68176, 85762, 304892, 855072, 1229050, 1805096

Offset: 1

Jamie Simpson, Jun 25 2007, corrected Sep 11 2007

An IRDCS of length n is a sequence of n integers s(1),...,s(n) with the property that if s(i)=m for some m then the other terms of the sequence with value m are precisely s(i+k*m) for all k such that i+k*m is in [1,n] and further such that any integer appearing in the sequence appears at least twice. For example, the two IRDCS of length n are 6,9,3,4,5,3,6,4,3,5,9 and its reverse.

Gerry Myerson, Jacky Poon and Jamie Simpson, Incongruent restricted disjoint covering systems, preprint.

A089187 a(n) is the minimal area of a convex lattice polygon with 2n sides.

Original entry on oeis.org

1, 3, 7, 14, 24, 40, 59, 87, 121, 164, 210, 274, 345, 430, 523, 632, 749, 890, 1039, 1222, 1412, 1620, 1838, 2088, 2357, 2651, 2953, 3278, 3612, 4020, 4439, 4902, 5387, 5898, 6418, 6974, 7557, 8182, 8835, 9512, 10218, 10984, 11759, 12635, 13525, 14448, 15399, 16415, 17473, 18570

Offset: 2

Jamie Simpson, Dec 07 2003

nonn

For polygons with an odd number of sides see A070911.

			The first entry is 1 because the convex lattice quadrilateral of minimal area is a unit square. The minimal area hexagon has area 3.

Günter Rote, Table of n, a(n) for n = 2..100
Charles J. Colbourn and R. J. Simpson, A note on bounds on the minimum area of convex lattice polygons, Bull. Austral. Math. Soc., 45[1992], 237-240.
Stanley Rabinowitz, Convex Lattice Polygons, Ph.D. Dissertation (Polytechnic University, Brooklyn, New York, 1986).
Günter Rote, a(n), together with coordinates of some smallest 2n-gon, for n=2..100, (2023).
Günter Rote, Python program for this sequence, and for A070911, (2023).
R. J. Simpson, Convex lattice polygons of minimum area, Bull. Austral. Math. Soc., 42[1990], 353-367.

The even-indexed subsequence of A070911. See also A063984.

a(22) onwards from Günter Rote, Sep 17 2023

cp's OEIS Frontend

User: Jamie Simpson

A274170 Christoffel words as binary numbers.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Maple

A268084 Minimum number of occurrences of abelian squares in a binary word of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

Extensions

A123298 Number of incongruent restricted disjoint covering systems (IRDCS) of length n.

Views

Author

Keywords

Comments

References

A089187 a(n) is the minimal area of a convex lattice polygon with 2n sides.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions