# Formula for the number of numbers $\le n$ with same prime factors as $n$?

Is there a more concise formula for this? I threw this one together,

$\sum_{j=1}^{n}(\lfloor\frac{n^{j}}{j}\rfloor-\lfloor\frac{n^{j}-1}{j}\rfloor)(\lfloor\frac{j^{n}}{n}\rfloor-\lfloor\frac{j^{n}-1}{n}\rfloor)=$ number of numbers $\le n$ with same prime factors as $n$.

I can show this by proving that the term in the left parenthesis is only $1$ or $0$ depending on whether or not $j|n^{j},$ which can only happen if the factors in prime factorization of $j$ are a subset of $n$'s. The function in the parenthesis on the right is $1$ or $0$ depending on whether or not $n|j^{n},$ which only occurs if $j$ is a multiple of $rad(n)$, the product of the distinct prime factors of $n$. So, the sum counts the number of numbers $j\le n$ whose prime factorization is a subset of $n$'s and is a multiple of $rad(n)$. This leaves only those with the same factors. I give this info on the sum because people always ask, but I really just need another version.

I'm looking for a different representation of this function than the one I have created above. I can't find a formula for this anywhere. Anybody got one?

Example of the function is, for $n=24$, the prime factors of $24$ are $2$ and $3$. There are $4$ numbers with these factors $\le n,$ which are $(6,12,18,24),$ so the function at $24=4.$ Sequence is A008479 in oeis, but no formula.

• "I want to know what to equate it to instead of writing out what it equals". I really can't tell what this sentence is supposed to mean. May 20, 2016 at 4:27
• @ErickWong I believe a more formal expression is needed for <question title>. May 20, 2016 at 4:28
• I don't think he considered $\sum_{j=1}^n 1_{j | n^j} 1_{ n | j^n}$ but instead $\sum_{k=1}^n 1_{\omega(k) = \omega(n)}$ @YakovShklarov May 20, 2016 at 4:29
• @YakovShklarov Sure, but the formula in the question is already a formal expression. Maybe it isn't equal to the desired quantity, but it's really hard to guess what OP is looking for. That is, what property does the current formula have that is not desirable? Or what property is desirable in an answer that the current formula lacks? May 20, 2016 at 4:30
• but yes, $\sum_{k=1}^n 1_{rad(k) = rad(n)} = \sum_{d | \frac{n}{rad(n)}} 1 = \sigma(\frac{n}{rad(n)})$ is clearly "Number of numbers <= n with same prime factors as n." i.e. oeis.org/A008479 , but is not $\sum_{k=1}^n 1_{\omega(k) = \omega(n)}$, since $rad$ and $\omega$ are not the same : $$rad(n) = \prod_{p | n} p$$ while $$\omega(n) = \sum_{p | n} 1$$ May 20, 2016 at 4:36

Let $\omega(n)$ (OEIS A001221) represent the number of distinct prime factors of $n$. Then a (fairly) transparent expression for what you want is

$$\sum_{1 \leqslant k \leqslant n} [\omega(k) = \omega(n) = \omega(\gcd(k,n))],$$

where $[\cdot]$ is the Iverson bracket, equal to $1$ when the condition inside is satisfied and $0$ otherwise. So we're tallying up the $k$s which have precisely the same number of prime factors as $n$ and no extra ones. Note that $\operatorname{lcm}$ would work just as well: $\omega(\gcd(k,n))$ is the number of distinct prime factors shared by both $k$ and $n$; $\omega(\operatorname{lcm}(k,n))$ is the number of distinct primes present in either $k$ or $n$ or both.

It really is necessary to specify the second equality, otherwise you end up including terms like $15=5 \cdot 3$ for $n=24 = 2^3 \cdot 3$. Notice that $\omega(\operatorname{lcm}(15,24)) = 3 \ne 2$ and $\omega(\gcd(15,24)) = 1 \ne 2$.

Another (perhaps more clear) way is to simply write

$$\sum_{1 \leqslant k \leqslant n} [p | n \Leftrightarrow p | k, \text{ for all prime }p].$$

• the same number of prime factors, or the exactly the same prime factors (as I find above) ? May 20, 2016 at 3:50
• I'm not sure what you're asking -- $k$ is the index variable. Yes, I found the number of $k$s with the exact same prime factors. I added a small note -- does that clarify things? May 20, 2016 at 3:53
• Ahh, I see now! Nope, $\omega$ retains the meaning I claimed for it, my proof holds. May 20, 2016 at 4:27
• @user1952009 There's no significant difference between having the same number of prime factors and having the same prime factors in this case. The inequality $\omega(\gcd(k,n)) \ge \omega(n)$ forces $k$ to have at least the same prime factors as $n$, while $\omega(k) \le \omega(n)$ precludes $k$ from having any additional primes. May 20, 2016 at 4:44
• @ErickWong : you are saying that $1_{\omega(k) = \omega(n) = \omega(gcd(k,n))} = 1_{rad(k) = rad(n)}$ ? yes it is obvious indeed, but very weirdly formulated in my opinion, I just understood what it meant right now :D May 20, 2016 at 4:53

(I prefer the notation $\displaystyle \sum_{j=1}^n 1_{j | n^j} 1_{ n | j^n}$, and using that for integers $\lfloor \frac{a}{b}\rfloor-\lfloor \frac{a-1}{b}\rfloor= 1_{b|a}$, and $rad(n) = \prod_{p | n} p$)

we get $$1_{ a | b^a} = 1_{ rad(a) | b} = 1_{ rad(a) | rad(b)}$$ thus

$$1_{j | n^j} 1_{ n | j^n} = 1_{ rad(j) | rad(n)}1_{ rad(n) | rad(j)} = 1_{ rad(j)= rad(n)}$$ and $rad(j)= rad(n),\ j \le n$ iff $j = d \ rad(n)$ with $rad(d) | rad(n)$ i.e. iff $d | n^d$ hence $$\displaystyle \sum_{j=1}^n 1_{ j | n^j} 1_{ n | j^n} = \sum_{j=1}^n 1_{ rad(j) = rad(n)} = \sum_{d=1}^{n/rad(n)} 1_{rad(d)|rad(n)} = \sum_{d=1}^{n/rad(n)} 1_{d | n^d}$$

and I'm not sure there is much simpler anymore, since this $\sum_{d=1}^{n/rad(n)} 1_{rad(d)|rad(n)}$ seems to depend on the precise prime factors of $n$, say if $p | n$, it depends on the maximum power of $p$ that is $\le \frac{n}{rad(n)}$, and hence on the other prime factors of $n$

• @e2theipi2026 : I don't know, as usual with your questions, I didn't understand what you expected as result. do you have a proof that the result isn't $\frac{n}{rad(n)}$? May 20, 2016 at 3:53
• I don't buy it: $\sigma(24/rad(24)) = \sigma(24/6) = \sigma(4) = 3 \ne 4$; it also fails for $n=18$. May 20, 2016 at 4:26
• @user1952009 The problem with $\sigma(n/\text{rad}(n))$ is that it only counts the values dividing $n$ rather than all the values $\le n$. For instance $2\cdot 3^2$ has the same prime factors as $n = 2^3 \cdot 3$ and is $\le n$, but it doesn't divide $n$ and falls out of the above count. May 20, 2016 at 4:35
• I like your expression $\sum_{j=1}^n 1_{rad(j)=rad(n)}$, it's a tad more concise than mine and doesn't rely on as much trickery (though there is still some trickery: maybe someone could find an even cleaner expression?) But how did you make the leap to the next sum? May 20, 2016 at 4:41
• @e2theipi2026 I edited to say that I'm not sure there is a much simpler formulation May 20, 2016 at 4:50