Abstract Search

ISEF | Projects Database | Finalist Abstract

Back to Search Results | Print PDF

Chance or Coincidence-Counting 3-Arithmetic Progression in Block-Generated Thue-Morse String

Booth Id:



Finalist Names:
Juang, Yuan-Jung (School: Newport Senior High School)

Problems involving arithmetic progressions are of interest in number theory, combinatorics, and computer science, from both theoretical and applied points of view. In 2004, Ben Green and Terence Tao proved that the sequence of prime numbers contains arbitrarily long arithmetic progressions. However, it is difficult to count the number of arithmetic progressions with k terms for a sequence of any type. Most existing results only estimate the lower/upper bounds for the number. In this work, we try to count the exact number of arithmetic progressions with 3 terms (3-AP in short) that are contained in the block-generated Thue-Morse (T-M in short) binary string. A block-generated Thue-Morse binary string starts with a block B and is always appended by the Boolean complement (B') of the existing string at the end recursively. The truncated T-M sequence cuts off a shorter T-M from the beginning and therefore the resulting string is no longer of a T-M type. The block-generated T-M binary string replaces 0 and 1 with a generator B and its Boolean complement B', where B can be any binary string. By observing an important symmetric-across property from the particular string patter BB'B'B, we discover an amazing result that the number of 3-AP not completely contained in the first half B B' or the second half of B'B is half of the length of B, regardless what content in B there might be. This property can be applied repeatedly to give the formula for the exact number of 3-AP in the truncated/block-generated T-M binary strings. The results depend only on the length of string B, but not the content of it. Some other extensions of the symmetric-across property on BB'BB'BB'BB', for example, can be likewise discussed to deepen our findings.

Awards Won:
American Mathematical Society: Third Award of $500