authorea.com/105676

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

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.

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.

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.

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}\]

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 & \mathrm{ow.} \end{cases}\] Which allows us to write \[G_{11}(z) = \frac{z}{(z-1)^2}\frac{\sum_{k=0}^{\varphi(p_4\#)} \chi_{11}(k)z^k}{\prod_{k=0}^3(1+z^{2^k})}\frac{1}{(1+z^{16}+z^{32})}\]

we can then speculate that, with \((13=p_6)\)\[G_{p_6}(z) = \frac{z\sum_{k=0}^{\varphi(p_5\#)} \chi_{p_6}(k)z^k}{1-z-z^{\varphi(p_5\#)}+z^{\varphi(p_5\#)+1}}\]

However finding the form of \(\chi_{13}(n)\) is the next problem to solve. There is a reasonable chance that the following is true \[\chi_{13}(n)=\begin{cases} 1 & n=0,480\\ 2 & n=\\ 4 & n=...,240\\ 6 & n=\\ 8 & n=\\ 10& n=\\ 12& n=1,479\\ 0 & \mathrm{ow.} \end{cases}\] We can use the following Mathematica code to get the coefficients of this generating function \[\mathrm{FF=Select[Range[3000],GCD[\#1,2310]==1\&];}\\ \mathrm{H[x\_]=x*Sum[aa[k]*x^k,{k,0,480}]/(1-x-x^{480}+x^{481});}\\ \mathrm{L=\{\};}\\ \mathrm{For[n=1, n<241, n++,}\\ \; \mathrm{QQ[n\_]=SeriesCoefficient[Series[H[x],{x,0,241}],n]==FF[[n]];}\\ \; \mathrm{AppendTo[L,QQ[n]]}\\ \mathrm{]}\\ \mathrm{Solve[L]}\] We find they begin \[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,4,2,4,6,\\ 2,6,4,6,6,6,2,6,4,2,6,\\ 4,6,8,4,2,4,6,8,6,10,2,\\ 4,6,2,6,6,4,2,4,6,2,6,4,\\ 2,6,10,2,10,2,4,2,4,6,8,\\ 4,2,4,12,2,6,4,2,6,4,6,\\ 12,2,4,2,4,8,6,4,6,2,4,\\ 6,2,6,10,2,4,6,2,6,4,2,\\ 4,2,10,2,10,2,4,6,6,2,6,\\ 6,4,6,6,2,6,4,2,6,4,6,8,\\ 4,2,6,4,8,6,4,6,2,4,6,8,\\ 6,4,2,10,2,6,4,2,4,2,10,\\ 2,10,2,4,2,4,8,6,4,2,4,6,\\ 6,2,6,4,8,4,6,8,4,2,4,2,4,\\ 8,6,4,6,6,6,2,6,6,4,2,4,6,2,\\ 6,4,2,4,2,10,2,10,2,6,4,6,2,\\ 6,4,2,4,6,6,8,4,2,6,10,8,4,2,4...\], up to the 240th, the rest of the terms are symmetric about this last 4! This adds power to the statement second coefficient is given by \(p_n-1\), however removes the highest coefficient being \(p_n-1\) theory.

\[\chi_{13}(n)=\begin{cases} 1 & n=0,480\\ 2 & n=3,6,9,13,16,22,24,29,31,35,38,40,42,45,47,50,56,59,65,71,74,78,81,84,87,89,91,96,99,102,107,109,115,118,121,124,127,129,131,133,137,143,146,152,159,165,167,170,172,174,176,178,183,187,195,197,205,209,212,215,217,219,221,225,228,234,239,241,246,252,255,259,261,263,265,268,271,275,283,285,293,297,302,304,306,308,310,313,315,321,328,334,337,343,347,349,351,353,356,359,362,365,371,373,378,381,384,389,391,393,396,399,402,406,409,415,421,424,430,433,435,438,440,442,445,449,451,456,458,464,467,471,474,477\\ 4 & n=2,4,8,10,15,18,21,23,25,27,34,36,41,46,48,52,58,61,64,66,72,77,79,83,90,92,95,97,101,104,108,110,113,116,122,126,128,134,140,145,148,151,154,157,160,164,169,171,177,179,182,184,189,191,194,196,198,201,208,210,214,216,223,227,229,233,238,240,242,247,251,253,257,264,266,270,272,279,282,284,286,289,291,296,298,301,303,309,311,316,320,323,326,329,332,335,340,346,352,354,358,364,367,370,372,376,379,383,385,388,390,397,401,403,408,414,416,419,422,428,432,434,439,444,446,453,455,457,459,462,465,470,472,476,478\\ 6 & n=5,7,11,12,14,17,19,28,32,33,37,49,51,53,54,55,57,60,62,67,69,73,75,76,80,82,85,93,100,103,105,112,114,117,119,123,125,135,136,138,139,141,142,144,147,149,153,156,158,161,163,168,181,185,186,188,192,200,202,203,204,206,207,211,213,222,224,226,230,231,235,245,249,250,254,256,258,267,269,273,274,276,277,278,280,288,292,294,295,299,312,317,319,322,324,327,331,333,336,338,339,341,342,344,345,355,357,361,363,366,368,375,377,380,387,395,398,400,404,405,407,411,413,418,420,423,425,426,427,429,431,443,447,448,452,461,463,466,468,469,473,475\\ 8 & n=20,63,68,94,111,150,155,162,180,190,193,199,232,237,243,248,281,287,290,300,318,325,330,369,386,412,417,460\\ 10& n=30,39,44,70,86,88,120,130,132,166,173,175,218,220,236,244,260,262,305,307,314,348,350,360,392,394,410,436,441,450\\ 12& n=1,43,98,106,374,382,437,479\\ 14& n=26,454\\ 0 & \mathrm{ow.} \end{cases}\]

We notice that the number of different coefficients in each of the polynomials follows the pattern \(1,1,2,4,6,8,11\) (where 1 has been included as a coefficient), there are not yet enough terms to guess a reasonable form for this sequence, but larger generating functions are under study.

Analysing the first 2000 coefficients of the next generating function we have \[\chi_{17}(n)=\begin{cases} 1&\\ 2& \\ 4& \\ 6& \\ 8& \\ 10& \\ 12& \\ 14& \\ 16& \\ 18& \\ 22& \\ 0 & \mathrm{ow.} \end{cases}\] this would make the next term in the series \(11\), matching now only \(2\) OEIS sequences, A079972 and, A084627. Where one more term would distinguish them.

## Share on Social Media