5
$\begingroup$

A p-rough number, or p-jagged number, is an integer whose smallest prime factor is $p$ (Finch, 2001).

The $3$-rough numbers are the odd numbers. The $7$-rough numbers are numbers not divisible by $2, 3,$ or $5,$ that is:

$ \left \{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, ...\right \} $.

  • I am struggling to find an explicit formula for the 7-rough numbers
  • I also wonder whether there is some recurrence or other method that can be used to find the $n^{th}$ number of a $p$-rough sequence for any possible $p$.

Thanks in advance!


Edit

I found on OEIS the following formula by Gary Detlefs (Sep 15, 2013) for the $7$-rough numbers:

$$a(n) = \frac{6f(n) - 3 + (-1)^{f(n)}}{2}$$

where

$$f(n)= n + \lfloor\frac{n}{4}\rfloor + \lfloor\frac{(n+4) \mod 8}{6}\rfloor.$$

I wonder how it is derived and if it is possible to find an equivalent or alternative formula without the floor and mod operations in it.

$\endgroup$
10
  • 1
    $\begingroup$ Hint: reduce each of the numbers in your sequence $\bmod 30$. Why $30?$ $\endgroup$ Nov 27, 2022 at 14:35
  • 1
    $\begingroup$ Yes, modulo reduction is just finding the remainder after dividing by the modulus. All the numbers in your list have one of eight remainders. All the other numbers up to $30$ have a factor of $2,3,$ or $5$. Your formula is one of those $8$ remainders plus some multiple of $30$. If you add a multiple of $30$ to a number that has no factors $2,3,5$ you get another. You should be able to prove that. $\endgroup$ Nov 27, 2022 at 15:47
  • 1
    $\begingroup$ Your formula misses $7,11,13$ but is otherwise fine. $\endgroup$ Nov 27, 2022 at 20:30
  • 1
    $\begingroup$ There are several formulas given in the OEIS entry including my own. What is the problem with floor and mod? They express the periodicity of the sequence modulo 30 as in "a(n) mod 30 has period 8 repeating [1, 7, 11, 13, 17, 19, 23, 29]." $\endgroup$
    – Somos
    Dec 6, 2022 at 17:16
  • 1
    $\begingroup$ As an alternative, you can express the periodicity using sums of roots of unity raised to $n$th power. For example: $\lfloor n/2\rfloor = n/2 + ((-1)^n-(1)^n)/4.$ A similar formula using $30$-th roots of unity would work for your sequence. $\endgroup$
    – Somos
    Dec 6, 2022 at 17:27

1 Answer 1

4
+100
$\begingroup$

For the $7$-rough numbers, using $8$-th roots of unity you can get $$ a_n = \frac{15}4 n + \frac18 (-15+ (1+i)i^n+(-1)^n+(1-i)(-i)^n) +\\ \frac18 i^{n/2}( ((1-3i)-(2+i)\sqrt{2}) + ((1+3i)+(2-i)\sqrt{2})i^n+\\ ((1-3i)+(2+i)\sqrt{2})(-1)^n + ((1+3i)-(2-i)\sqrt{2})(-i)^n). $$

Noticing the period $8$ behavior it is only a matter of solving for the coefficients of the $8$th roots of unity. A similar method would work for any specific $p$-rough sequence.

More explicitly, in general, the $p$-rough integer sequence has a linear average behavior. Subtracting off this linear function leaves a purely periodic sequence. Any such sequence can be expressed as $\,a_n=\sum_{k=0}^{N-1} c_k (\zeta^k)^n$ for some coefficients $c_k$ where $\zeta^k=e^{2\pi i k/N}$ are the $N$th roots of unity and where $N$ is the period. The coefficients can be found by solving a system of $N$ linear equations as in the Discrete Fourier Transform.

In the case of $7$-rough, the linear function is $\frac{15}4n$ and the remainder is a period $8$ sequence.

Notice that the $7$-rough numbers are all odd. Further, $ (a(n+1) - a(n-1))/2$ is a bounded integer with average value of $15/4$ and a period of $8$. Thus, a good approximation is $a (n) \approx \lfloor 15n/4\rfloor.$ But this is always $\le 0$. A more balanced formula is $a(n) = 3d(n) + e(n)$ where $d(n):=\lfloor 5n/4\rfloor,$ and $e(n+8)=e(n).$ We just have to find a formula for $e(n)$ which depends only on $n \pmod 8$. The Detlefs formula is once such.

$\endgroup$
7
  • $\begingroup$ Thank you for the answer! $\endgroup$ Dec 6, 2022 at 20:20
  • $\begingroup$ Is it $\zeta_k^{n}$ or $\zeta^{kn}$? $\endgroup$ Dec 7, 2022 at 10:49
  • $\begingroup$ @Shootforthemoon Both are equivalent and commonly used. $\endgroup$
    – Somos
    Dec 7, 2022 at 11:39
  • $\begingroup$ k being used as an index in both cases, not as a power, right? $\endgroup$ Dec 7, 2022 at 13:53
  • 1
    $\begingroup$ @Shootforthemoon Okay. I will try to get the Detlefs formula somehow. Wait for it. $\endgroup$
    – Somos
    Dec 8, 2022 at 17:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .