Integer Sequences by Counting Rules

Abstract

This document explains a method of creating an integer sequence by a counting rule. The integer sequence made relates to the place values of the digits in numbers created by the counting rule. Such rules create the numbers bases \(b\), the factorial base numbers, the Catalan numbers, the Motzkin numbers, and more.

Main

When counting regularly in a given base \(b\), the ’rule’ of counting is that we increment the right most digit by one until it exceeds \(b-1\). At this point we carry a \(1\) to the next digit, (apply the rule again further up the number if necessary). This document goes beyond the concept of a constant \(b\), and extends to arbitrary rules for counting. This concept has already been seen in the factorial counting system, where for the \(k^{th}\) digit in a number (indexed from \(1\)), that digit may not exceed \(k\). Such a rule leads to the values of each digit or place value, being the factorial numbers, as opposed to the regular powers \(b^{k}\). For the base \(b\) numbers we can write the ’rule’ for when to carry a \(1\),

\begin{equation} \mathrm{Carry}(d_{k})\;\mathrm{if}\;d_{k}>b-1\\ \end{equation}

for the factorial base we can write

\begin{equation} \mathrm{Carry}(d_{k})\;\mathrm{if}\;d_{k}>k\\ \end{equation}

where ’carry’ is the operation, ”set \(d\) to zero and let \(d_{k+1}=d_{k+1}+1\)”.

The table below displays some examples for counting in the factorial base

\begin{equation} \begin{matrix}\text{Factorial Base}&\text{Decimal Value}\\ \\ 0&0\\ 1&1\\ 10&2\\ 11&3\\ 20&4\\ 21&5\\ 100&6\\ \cdots\\ 321&23\\ 1000&24\\ \cdots\\ 4321&119\\ 10000&120\end{matrix}\\ \end{equation}

In order for the left notation generated by the rule to equal the decimal notation on the right, the digits must be worth \(1,2,6,24,...\), the factorial numbers. The problem with general rules is that a countably infinite number of unique symbols are required to represent arbitrarily large numbers. Thus they do not make ’nice’ natural counting systems from a social perspective. However, from a mathematical perspective, the numbers that equal \(1,10,100,1000,\cdots\) and so on have combinatorial interpretations.

Catalan Numbers

We can generate a simple rule where the digits \(d_{k}\) of a number written in the ’Catalan Base’ must equal the Catalan numbers A000108(k). The rule is that a digit is carried when it exceeds the digit to its left plus one. We can again write more concisely

\begin{equation} \mathrm{Carry}(d_{k})\;\mathrm{if}\;d_{k}>d_{k+1}+1\\ \end{equation}
\begin{equation} \begin{matrix}\text{Catalan Base}&\text{Decimal Value}\\ \\ 0&0\\ 1&1\\ 10&2\\ 11&3\\ 12&4\\ 100&5\\ 101&6\\ 110&7\\ 111&8\\ 112&9\\ 120&10\\ 121&11\\ 122&12\\ 123&13\\ 1000&14\end{matrix}\\ \end{equation}

We see the individual digits must take the values \(1,2,5,14,...\), which make the Catalan numbers. However, unlike the factorial base numbers we easily lose the property of the notation that the sum of the digits weighted by their place values equals the decimal value to the right. For example \(120\to 10\), but \(5+2+2\neq 10\). Due to this it is not strictly speaking correct to call the numbers \(1,10,100,1000\) place values. However, when the counting system arrives at these values, it denotes the end of a cycle of some kind through permutations of the lower digits.

Motzkin Numbers

If we add an extra condition, that we carry if current digit is greater than the next digit \(\mathrm{OR}\) the next next digit plus \(1\), then we arrive at the Motzkin numbers, A001006.

\begin{equation} \mathrm{Carry}(d_{k})\;\mathrm{if}\;d_{k}>d_{k+1}+1\;\mathrm{OR}\;d_{k}>d_{k+2}+1\\ \end{equation}

there is clearly a combinatorial interpretation of the way the numbers are being counted.

’AND’ Motzkin Numbers

What happens if we change the \(\mathrm{OR}\) for an \(\mathrm{AND}\) in the above example?

\begin{equation} \mathrm{Carry}(d_{k})\;\mathrm{if}\;d_{k}>d_{k+1}+1\;\mathrm{AND}\;d_{k}>d_{k+2}+1\\ \end{equation}

This produces sequence \(A275605\), which was not previously in the OEIS. Does this sequence have a nice combinatoric interpretation?

A254439

This methodology along with some experimentation produced the terms of a sequence with the ”more” flag, on OEIS, we have the rule

\begin{equation} \mathrm{Carry}(d_{k})\;\mathrm{if}\;d_{k}>3d_{k+1}+1\\ \end{equation}

which produces place values of \(1,2,7,47,682,23132,1913821,397731998,\cdots\). It is possible to explain these terms using a formal but increasingly intractable ’chain of sums’

\begin{equation} 7=\sum_{i_{1}=1}^{2}(3i_{1}-1)\\ 47=\sum_{i_{1}=1}^{2}\sum_{i_{2}=1}^{3i_{1}-1}(3i_{2}-1)\\ 682=\sum_{i_{1}=1}^{2}\sum_{i_{2}=1}^{3i_{1}-1}\sum_{i_{3}=1}^{3i_{2}-1}(3i_{3}-1)\\ \cdots\\ a(n)=\underbrace{\sum_{i_{1}=1}^{2}\cdots\sum_{i_{n}=1}^{3i_{n-1}-1}}_{\text{n Sums}}(3i_{n}-1)\\ \end{equation}

Tabulation of Rules and Sequences

The following table is not rigorously proved! I have tabulated some results I have seen so far, some have no entry in the OEIS.

\begin{equation} \begin{matrix}\mathrm{Rule}&\mathrm{Sequence}\\ d_{k}>b-1&\text{Numbers base b}\\ d_{k}>k&\text{Factorial Base}\\ d_{k}>d_{k+1}+1&\text{Catalan Numbers}\\ d_{k}>d_{k+1}+1\;\mathrm{OR}\;d_{k}>d_{k+2}+1&\text{Motzkin Numbers}\\ d_{k}>d_{k+1}+1\;\mathrm{AND}\;d_{k}>d_{k+2}+1&\text{A275605}\\ d_{k}>d_{k+1}+2\;\mathrm{OR}\;d_{k}>d_{k+2}+2&A063020\\ d_{k}>d_{k+2}+1&A005817\\ d_{k}>2d_{k+1}+1&A002449\\ d_{k}>d_{k+2}+2&1,3,9,36,144,660,3025,15015,74529,389844,2039184,11069856,60093504\\ d_{k}^{2}>d_{k+1}+1&A000079&\text{Powers of 2}\\ d_{k}^{2}>d_{k+1}+d_{k}+1&A001519\\ d_{k}^{2}>d_{k+1}+d_{k}+2&A000244&\text{Powers of 3}\\ d_{k}^{2}+d_{k+1}^{2}>d_{k+2}^{2}+1&A000045&\text{Fibonacci}\\ d_{k}^{2}>d_{k+1}^{2}+d_{k+2}^{2}+2&1,2,4,9,21,52,133,353,963,2705,7812,23289,72057,233771,807131,3028323,12676939,60959699,345934925\\ d_{k}^{2}>2*d_{k+1}*d_{k+2}+2&1,2,4,9,21,51,127,323,836,2202,5910,16222,45821,134565,417568,1403052,5279866,23142475,122222895\\ d_{k}>d_{k+1}*d_{k+2}+1&1,2,4,9,22,64,288,5758,2715615\\ d_{k}>d_{k+1}+d_{k+2}+1&1,2,5,17,74,425,3229,33220,470345,9341720\\ d_{k}>d_{k+1}+1&1,2,5,16,99,8764,464897407\\ d_{k}>d_{k+3}+1&1,2,4,8,20,50,125,350,980,2744,8232,24696,74088,232848,731808,2299968,7474896,24293412,78953589\\ d_{k}>d_{k+1}+1\;\mathrm{OR}\;d_{k}>d_{k+2}+1\;\mathrm{OR}\;d_{k}>d_{k+3}+1&A004148\\ d_{k}>d_{k+1}+k&A101482\\ d_{k}+d_{k+1}>d_{k+2}+1&1,2,3,6,10,358056266,1431798090,3904618790\\ d_{k}>d_{k+2}+d_{k+3}+1&1,2,4,10,31,106,444,2153,12200,82857,659178,6292825,72012699\\ d_{k}>d_{k+2}+d_{k+3}-d_{k+1}+1&1,2,3,6,12,25,54,118,271,624,1487,3572,8795,21874,55340,141593,366858,960966,2542355,6793664,18307745,49774625\\ d_{k}>\frac{d_{k+1}^{2}}{2}+2&1,3,11,51,441,53371\\ d_{k}>k^{2}&A101686\\ d_{k}>k^{2}-k&A130032\\ d_{k}>e^{k}&1,3,24,504,27720,4130280,\\ d_{k}>log(k)&1,2,4,8,16,32,96,288,864,2592,7776,23328,69984,209952,629856,1889568,5668704,17006112\\ d_{k}>d_{k+1}+log(k)&1,4,14,48,165,572,5070,38050,267252,1813998\\ d_{k}>d_{k+1}+k^{2}&1,2,20,635,43095,5075200,919589971\\ d_{k}>|d_{k+1}-d_{k+2}|&1,2,5,13,36,104,307,930,2855,8883,27950,88668,283555,912647,2954111,9611223,31408216\\ d_{k}>\sqrt{k}+1&1,3,9,27,108,432,1728,6912,27648,138240,691200,3456000,17280000\\ d_{k}>\sqrt{k}&1,2,4,8,24,72,216,648,1944,7776,31104,124416,497664,1990656,7962624\\ d_{k}>\mathrm{gcd}(d_{k+1},d_{k+2})&1,2,5,14,43,137,446,1477,4942,16656,56439,191995,655119,2240706,7678343,26351967\\ d_{k}>\mathrm{gcd}(d_{k+1},3)&A003946\\ d_{k}>(d_{k+1}\;\mathrm{mod}\;2)+1&A000129\\ d_{k}>(d_{k+1}+1\;\mathrm{mod}\;2)+1&A001906\\ d_{k}>(d_{k+1}\;\mathrm{mod}\;3)+1&A202207\\ d_{k}>(d_{k+1}+1\;\mathrm{mod}\;3)+1&A084084\\ d_{k}>(d_{k+1}+2\;\mathrm{mod}\;3)+1&A052529\\ d_{k}>(d_{k+2}\;\mathrm{mod}\;2)+1&A089928\\ d_{k}>(d_{k+1}\;\mathrm{mod}\;2)(d_{k+2}\;\mathrm{mod}\;2)+1&A008998\\ d_{k}>\frac{\log(d_{k+1})}{k}+1&A084215\\ d_{k}>\sqrt{d_{k+2}}+1&A166516\\ d_{k}>\sqrt{d_{k+1}}+1&A001519\\ d_{k}>\sin(k\pi/2)+1&A026532\\ d_{k}>2\sqrt{(}d_{k+1})+1&A124292\\ d_{k}>\frac{3}{2}\sqrt{d_{k+1}}+1&A124302\\ d_{k}>\frac{4}{3}\sqrt{d_{k+1}}+1&A001519\\ d_{k}>2\sqrt{\sqrt{d_{k+1}}}+1&A006012\\ d_{k}>d_{k+d_{k+1}+1}+1&1,2,4,9,21,51,128,331,879,2394,6685,19123,56006,167878,514941,1616006,5186700\\ d_{k}>d_{k+d_{k}+1}+1&1,2,4,8,20,50,125,325,890,2440,6744,18996,54090,155290,448586\\ d_{k}>d_{k+d_{k}}+1&1,2,4,10,25,65,178,492,1386,3954,11426,33275,97633,288384,856355,2555366,7656046,23022604\\ d_{k}>\sqrt{2+d_{k+1}}+1&A007052\\ d_{k}>\sqrt{3+d_{k+1}}+1&A001835\\ d_{k}>\sqrt{4+d_{k+1}}+1&A000302&\text{Powers of 4}\\ d_{k}>\sqrt{5+2d_{k+1}}+1&A052913\end{matrix}\\ \end{equation}

Extensions

We can implement other variables into the ’rule’. For example, the previous place value can feature. If we start a variable \(p=0\), at the start of counting, after the next term is found we can increment \(p\), then \(p\) may directly appear in the rule to generate even more complicated rules. Finding a known sequence with these rules is very rare so far. Some examples are

\begin{equation} \begin{matrix}\mathrm{Rule}&\mathrm{Sequence}\\ d_{k}>k-\frac{p}{2}+1&1,3,7,25,43,139,235,835,1435,5755,10075,45355,80635,403195,725755,3991675,7257595,43545595,79833595\\ d_{k}>k-p+1&1,2,3,4,5,6,7,8,9\\ d_{k}>k-\frac{p}{\pi}&1,2,3,7,11,29,125,221,821,5141,9461,44741,367301,689861,3955781,40243781\\ d_{k}>d_{k+1}+1+p&1,3,21,271,5246,136552,4489516,178921726\\ d_{k}>k-\frac{p}{e}&1,2,3,4,8,26,44,140,740,1340,5660,9980,45260,367820,690380,3956300,40244300,76532300\\ \end{matrix}\\ \end{equation}

References

N. J. A. Sloane, editor, The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org