Partitioning a sequence of characters into groups of $3$ or $4$

Question

I have some computer code that outputs character sequences of various lengths. For readability, I would like to format output sequences as groups of $3$ or $4$ characters. Examples:

• The sequence ABCDEF could be formatted as ABC DEF ($2$ groups of $3$ characters)
• The sequence ABCDEFGHIJK could be formatted as ABC DEFG HIJK ($1$ group of $3$ and $2$ groups of $4$ characters

It appears to me that any sequence with $6$ or more characters could be divided into groups of $3$ or $4$ characters without any remainder. That is, for a sequence of length $n$, where $n > 5$, it appears possible to always find a non-negative integer solution for $a$ and $b$ in the equation $ n = a \times 3 + b \times 4$.

To this, I have two math questions:

1. Am I correct in my assumption that this is always possible?
2. Is there a fast and direct way to compute $a$ and $b$ for a given $n$?

Answer 1

(1) Yes, and the bound of $6$ is sharp: Given coprime numbers $m, n$, the largest integer that cannot be written as a nonnegative integral combination of $m$ and $n$ (the so-called Frobenius number) is $m n - m - n$. This is the two-coin case of the Frobenius Coin Problem.

(2) Here's part of a "greedy algorithm" that minimizes the number of groups (i.e., maximizes the number of groupings of $4$): For a given sequence length $L$, let $q := \left\lfloor\frac{L}{4}\right\rfloor$ and let $r$ be the remainder of dividing $L$ by $4$, so that $L = 4 q + r$, $r \in \{0, 1, 2, 3\}$:

• If $r = 2$, then we can write $L$ as $$L = 4 q + 2 = [(q - 1) \cdot 4 + 4] + 2 = (q - 1) \cdot 4 + 2 \cdot 3 ,$$ so we can break $L$ into $q - 1$ groups of $4$ and $2$ groups of $3$.

Can you work out the cases $r = 0, 1, 3$?

Note that in general there is more than one solution: For $L \geq 18$ we will have at least four groups of $3$ or three groups of $4$, but one can always replace one of these groupings with the other.

Answer 2

Your assumption is correct. Your problem is equivalent to the coin problem (https://en.m.wikipedia.org/wiki/Coin_problem ): that of knowing what is the biggest amount of money that cannot be paid with coins of values 3 and 4. If the coins are of $a $ and $b $, such amount has been proven to be $ab - a - b $. Making $a=3, b=4$ gives $5$, so any amount of money worth $6$ or more can be paid with coins of $3$ and $4$. For your specific problem, you can divide such sequences of characters into those groups.

As to how to do it: try making groups of 3 until the remaining is a multiple of 4.

Answer 3

The OP presents the equation $$ n = 3a + 4b $$ and assumes that it is possible to always find a non-negative integer solution for $a$ and $b$ given any $n > 5$, where $n \in \Bbb{Z}$.

1. Am I correct in my assumption that this is always possible?

This is answered and confirmed by RSerrao and Travis, referring to the two-coin case of the Coin Problem.

2. Is there a fast and direct way to compute $a$ and $b$ for a given $n$?

Following the lead from Travis, let $a \in \{0, 1, 2, 3\}$ to minimize the number of groups, let $q = \lfloor n/4 \rfloor$ be the quotient and $r = n \bmod 4$ be the remainder of dividing $n$ by $4$. This gives four cases for solving the equation $n=3a+4b$ with non-negative integers: $$ n = \begin{cases} 3 \times 0 + 4 \times (q - 0), & \text{if $r = 0$} \\ 3 \times 3 + 4 \times (q - 2), & \text{if $r = 1$} \\ 3 \times 2 + 4 \times (q - 1), & \text{if $r = 2$} \\ 3 \times 1 + 4 \times (q - 0), & \text{if $r = 3$} \end{cases} $$ From this, it can be shown that $a$, the minimum number of groups of $3$, can be expressed as$$ a = 3-(n+3)\bmod4 $$ and $b$, the corresponding number of groups of $4$, can then be expressed as$$b = (n - 3a)/4$$