A337005 Leech's order 13 uniform cyclic squarefree word.

0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 2, 1, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 0, 2, 1, 2, 0, 1, 0, 2, 1, 0, 1, 2, 0, 1, 0, 2, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 2, 1, 0, 2, 0, 1, 0, 2, 1, 0, 1, 2, 0, 1, 0, 2, 1, 2, 0, 2, 1, 0, 2, 0, 1

Offset: 0

Author

Kevin Ryde, Aug 11 2020

Keywords

• base
• nonn

Comments

This morphism is uniform (each expansion the same length) and cyclic (the expansions of 1 and 2 are the same as the expansion of 0 but each term +1 and +2 (mod 3) respectively). Leech chooses this in order to reduce the cases which need to be considered to prove the word is squarefree (no repeat X X for a block X of any length).

a(n) can be calculated by writing n in base 13 and summing expansion terms, mod 3, for each digit (formula below). The pattern of the expansion terms can be illustrated as follows, with negatives where term 0 followed by 2 can be taken as a downwards step before mod 3.

Term: 0,1,2,1,0,2,1,2,0,1,2,1,0 (by base 13 digit)

Pattern: 2 2

1 1 1 1

0 0 0 0

-1 -1

-2

Leech calls the three expansion blocks A,B,C. The sequence here expands 0,1,2 -> A,B,C respectively. Leech allows for a different order, so for example 0,1,2 -> B,A,C. The effect is a re-mapping of symbols (0,1,2 -> 1,0,2 before expansion) and so remains squarefree.

Leech notes the expansions are symmetric (the same read forward or reversed), and in particular that taking the middle as the zero point can form symmetric bi-directional squarefree words.

Leech makes a final remark that the morphism was constructed by trial assuming symmetry and cyclic relationships and that it is the shortest such. The type of computer search made by Zolotov confirms it is the shortest, and that it is the sole order 13, up to re-mappings of the symbols. This is so even with non-symmetrics allowed, since the shortest uniform cyclic non-symmetrics are at order 18.

Links

• Kevin Ryde, Table of n, a(n) for n = 0..6590
• Rob Burns, Synchronisation of running sums of automatic sequences, arXiv:2405.17536 [math.NT], 2024. See p. 13.
• John Leech, A Problem on Strings of Beads, The Mathematical Gazette, volume 41, number 338, December 1957, item 2726, pages 277-278.
• Boris Zolotov, Another Solution to the Thue Problem of Non-Repeating Words, arXiv:1505.00019 [math.CO], 2015. (Section 2 morphism 3, then section 5 result 8 and proofs in section 9.)
• Index entries for sequences that are fixed points of mappings
• Index entries for sequences related to squarefree words

Crossrefs

Cf. A170823.

Programs

PARI

my(table=[0,1,2,1,0,2,1,2,0,1,2,1,0]); a(n) = my(v=digits(n,#table)); sum(i=1,#v, table[v[i]+1])%3;

Formula

Fixed point of the morphism, starting from 0,

0 -> 0,1,2,1,0,2,1,2,0,1,2,1,0 [Leech]

1 -> 1,2,0,2,1,0,2,0,1,2,0,2,1

2 -> 2,0,1,0,2,1,0,1,2,0,1,0,2

a(n) = (Sum_{d each base 13 digit of n} t(d)) mod 3, where t(d) = 0,1,2,1,0,2,1,2,0,1,2,1,0 according as d=0 to 12 respectively.