On the Generating Functions of p-Rough Numbers and their Inverse Z-Transforms

Abstract

A p-rough number for some prime p, is a member of the set of numbers not divisible by any prime \(q<p\). This document will note down the generating functions for the first few prime-rough numbers, and discuss their inverse Z-transforms, i.e a function \(a(n)\) that gives the \(n^{th}\) member of the set.

Introduction

The 3-rough numbers are simply the odd numbers \(1,3,5,7,9,11\cdots\), the numbers which are not divisible by \(p\in\{2\}\), See the table below for the appropriate OEIS label.

\[\begin{array}{|c|c|} \hline p & \mathrm{OEIS\;ID\;for\;}p\mathrm{-rough\;numbers.} \\ \hline 2 & A000027 & 1,2,3,4,5,6,7\\ 3 & A005408 & 1,3,5,7,9,11,13\\ 5 & A007310 & 1,5,7,11,13,17,19\\ 7 & A007775 & 1, 7, 11, 13, 17, 19, 23\\ 11 & A008364& 1, 11, 13, 17, 19, 23, 29\\ 13 & A008365& 1, 13, 17, 19, 23, 29, 31\\ 17 & A008366& 1, 17, 19, 23, 29, 31, 37,\\ 19 & A166061& 1, 19, 23, 29, 31, 37, 41\\ 23 & A166063& 1, 23, 29, 31, 37, 41, 43\\ \hline \end{array}\]

From the table above we can see the first entry is always \(1\), the second entry is the \(n^{th}\) prime, (i.e the index in the name of that sequence) and the next entry is the name of the next sequence. There are an increasing number of primes in each sequence, rather the probability of finding a prime number is higher.

Generating Functions

A generating function for a sequence with terms \(a(n)\) is simply the series, \[G_a(z)=a(0)z^0 + a(1)z^1 + a(2)z^2 + \cdots= \sum_{n=0}^\infty a(n)z^n,\] however, for some sequences it makes more sense to count from \(1\), giving the description \[G_a(z)=a(1)z^1 + a(2)z^2 + \cdots= \sum_{n=1}^\infty a(n)z^n,\] the latter is the description we will use. We can see that the generating function for the natural numbers \(1,2,3,\cdots\) (which are also the 2-rough numbers) is then \[G_2(z)=\frac{z}{(z-1)^2}=z+2z^2+3z^3+\cdots\\ a_2(n)=n\] Then for the 3-rough numbers we have the odd numbers, \[G_3(z)=\frac{z(1+z)}{(z-1)^2} \\ a_3(n) = 2n-1\] we can use the Mathematica expression \[\mathrm{F[z\_]=z(1+z)/(z-1)^2}\\ \mathrm{Simplify[InverseZTransform[F[1/z],z,n],Element[n,Integers]\&\&n>0]}\] to extract the sequence function \(a_3(n)\). For the 5-rough numbers we have numbers congruent to 1 or 5 mod 6, \[G_5(z) =\frac{z(1+4z+z^2)}{(1-z)^2(1+z)}\\ a_5(n) = \frac{1}{2}(6n+(-1)^n-3)\]

From these we notice that \[G_3(z)=G_2(z)(1+z)\\ G_5(z)=\frac{G_2(z)^2}{G_3(z)}(1+4z+z^2)\]

From here on things get less simple. The next sequence is the 7-rough numbers \[G_7(z)=\frac{z(1+6z+4z^2+2z^3+4z^4+2z^5+4z^6+6z^7+z^8)}{(1+z)(z^2+1)(z^4+1)(z-1)^2}\] But the sequence description \(a(n)\) is terribly complicated \[a_7(n)= \frac{1}{8}e^{-\frac{3}{4}in\pi}\left((1-3i)+(2+i)\sqrt{2}+(-1)^n\left((1-3i)-(2+i)\sqrt{2}+((i-14)+30n)\cos(n\pi/4)+(2+6i)\cos(n\pi/2)+(2-i)\cos(3n\pi/4)+((16i-1)-30in)\sin(n\pi/4)+(2+4i)\sqrt{2}\sin(n\pi/2)-\sin(3n\pi/4)\right)\right)\]

Then we have the 11-rough numbers \[G_{11}(z) = \frac{z(z^{48} + 10z^{47} + 2z^{46} + 4z^{45} + 2z^{44} + 4z^{43} + 6z^{42} + 2z^{41} + 6z^{40} + 4z^{39} + 2z^{38} + 4z^{37} + 6z^{36} + 6z^{35} + 2z^{34} + 6z^{33} + 4z^{32} + 2z^{31} + 6z^{30} + 4z^{29} + 6z^{28} + 8z^{27} + 4z^{26} + 2z^{25} + 4z^{24} + 2z^{23} + 4z^{22} + 8z^{21} + 6z^{20} + 4z^{19} + 6z^{18} + 2z^{17} + 4z^{16} + 6z^{15} + 2z^{14} + 6z^{13} + 6z^{12} + 4z^{11} + 2z^{10} + 4z^9 + 6z^8 + 2z^7 + 6z^6 + 4z^5 + 2z^4 + 4z^3 + 2z^2 + 10z + 1)}{(z^{49} - z^{48} - z + 1)} \\ G_{11}(z) = \frac{z(z^{48}+1 + 2(z^{46}+ z^{44}+ z^{41}+ z^{38}+ z^{34}+ z^{31}+ z^{25}+ z^{23}+ z^{17}+ z^{14}+ z^{10}+ z^7+ z^4+ z^2) + 4(z^{45} + z^{43} + z^{39} + z^{37} + z^{32}+ z^{29}+ z^{26} + z^{24} + z^{22} + z^{19} + z^{16} + z^{11}+z^9+z^5+z^3) + 6(z^{42} + z^{40} + z^{36} + z^{35} + z^{33} + z^{30} + z^{28} + z^{20} + z^{18} + z^{15} + z^{13} + z^{12} + z^8 + z^6) + 8(z^{27} + z^{21})+ 10(z^{47}+z) )}{(z^{49} - z^{48} - z + 1)}\]

Whose sequence description takes us a few screens and is silly to place here...

For this we have learnt that the generating functions remain somewhat simple compared to the sequence descriptions.

Analysis of the Generating Functions

We can observe the pattern of coefficients in the main bracket of each of the generating functions \[\begin{matrix} G_2(z) \to 1 \\ G_3(z) \to 1,&1 \\ G_5(z) \to 1,&4,&1 \\ G_7(z) \to 1,&6,&4,&2,&4,&2,&4,&6,&1 \\ G_{11}(z) \to 1,&10,&2,&4,&2,&4,&6,&2,&6,&4,&2,&4,&6,&6,&2,&6,&4,&2,&6,&4,&6,&8,&4,&2,&4,&2,&4,&8,&6,...\\ G_{13}(z) \to 1,&12,&4,&2,&4,&6,&2,&6,&4,&2,&4,&6,&6,&2,&6,&4,&2,&6,&4,&6,&8,&4,&2,&4,&2,&4,&14,&4,&6,2,10,2,6,6,4,2,4,6,2,10,2,4,2,12,10,2 \\ G_{17}(z) \to 1,&16,&2,&4,&6,&2,&6,&4,&2,&4,&6,&6,&2,&6,&4,&2,&6,&4, \end{matrix}\]

Some conjectures: It would appear the first coeff. is always \(1\), the largest is next and if able to appear seems to have the value \(p-1\), where \(p\) is the prime in \(G_p(z)\), the central is always \(4\) and there is symmetry about this central \(4\). All coeffs. are even except \(1\). All even coeffs between the largest and \(1\) appear to be present, in each.

We can clearly see a pattern of repetition in the anti-diagonals, where \(G_{17}\) has been filled in to demonstrate.

The order of the main polynomial is \[G_2(z) \to 0\\ G_3(z) \to 1\\ G_5(z) \to 2\\ G_7(z) \to 8\\ G_{11}(z) \to 48\\\]

We may observe that A002110, the primorials “1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690”, may be connected to these numbers through the Euler Totient function, as \[\varphi(1)=1\\ \varphi(2)=1\\ \varphi(6)=2\\ \varphi(30)=8\\ \varphi(210)=48\\ \varphi(2310)=480\\\] Meaning we should expect, the \(G_{13}(z)\), generating function to have a polynomial of order \(480\), and we should expect the \(G_p(z)\) generating function to have a polynomial of order \(\varphi(p\#)\)

The denominator of the generating function can be rewritten as follows \[G_2(z) \to 1-z-z+z^2\\ G_3(z) \to 1-z-z+z^2\\ G_5(z) \to 1-z-z^2+z^3\\ G_7(z) \to 1-z-z^8+z^9\\ G_{11}(z) \to 1-z-z^{48}+z^{49}\]

Describing the Generating Functions more compactly

We may define a function \[\chi_5(n)=\begin{cases} 1 & n=0,2\\ 4 & n=1\\ 0 & \mathrm{ow.} \end{cases}\] This allows us to write \[G_5(z) = \frac{z}{(z-1)^2}\frac{\sum_{k=0}^{\varphi(p_2\#)} \chi_5(k)z^k}{\prod_{k=0}^0(1+z^{2^k})}\]

We may define a function \[\chi_7(n)=\begin{cases} 1 & n=0,8\\ 2 & n=3,5\\ 4 & n=2,4,6\\ 6 & n=1,7\\ 0 & \mathrm{ow.} \end{cases}\] This allows us to write \[G_7(z) = \frac{z}{(z-1)^2}\frac{\sum_{k=0}^{\varphi(p_3\#)} \chi_7(k)z^k}{\prod_{k=0}^2(1+z^{2^k})}\]

Similarly we may write \[\chi_{11}(n)=\begin{cases} 1 & n=0,48\\ 2 & n=2,4,7,10,14,17,23,25,31,34,38,41,44,46\\ 4 & n=3,5,9,11,16,19,22,24,26,29,32,37,39,43,45\\ 6 & n=6,8,12,13,15,18,20,28,30,33,35,36,40,42\\ 8 & n=27,21\\ 10& n=1,47\\ 0 & \m