6
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ "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. $\endgroup$
    – Erick Wong
    May 20, 2016 at 4:27
  • 1
    $\begingroup$ @ErickWong I believe a more formal expression is needed for <question title>. $\endgroup$
    – Yakov Shklarov
    May 20, 2016 at 4:28
  • 1
    $\begingroup$ 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 $\endgroup$
    – reuns
    May 20, 2016 at 4:29
  • 1
    $\begingroup$ @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? $\endgroup$
    – Erick Wong
    May 20, 2016 at 4:30
  • 2
    $\begingroup$ 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$$ $\endgroup$
    – reuns
    May 20, 2016 at 4:36

2 Answers 2

Reset to default
3
$\begingroup$

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].$$

$\endgroup$
8
  • 1
    $\begingroup$ the same number of prime factors, or the exactly the same prime factors (as I find above) ? $\endgroup$
    – reuns
    May 20, 2016 at 3:50
  • 1
    $\begingroup$ 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? $\endgroup$
    – Yakov Shklarov
    May 20, 2016 at 3:53
  • 1
    $\begingroup$ Ahh, I see now! Nope, $\omega$ retains the meaning I claimed for it, my proof holds. $\endgroup$
    – Yakov Shklarov
    May 20, 2016 at 4:27
  • 1
    $\begingroup$ @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. $\endgroup$
    – Erick Wong
    May 20, 2016 at 4:44
  • 1
    $\begingroup$ @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 $\endgroup$
    – reuns
    May 20, 2016 at 4:53
3
$\begingroup$

(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$

$\endgroup$
11
  • 1
    $\begingroup$ @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)}$? $\endgroup$
    – reuns
    May 20, 2016 at 3:53
  • 1
    $\begingroup$ I don't buy it: $\sigma(24/rad(24)) = \sigma(24/6) = \sigma(4) = 3 \ne 4$; it also fails for $n=18$. $\endgroup$
    – Yakov Shklarov
    May 20, 2016 at 4:26
  • 1
    $\begingroup$ @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. $\endgroup$
    – Erick Wong
    May 20, 2016 at 4:35
  • 1
    $\begingroup$ 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? $\endgroup$
    – Yakov Shklarov
    May 20, 2016 at 4:41
  • 1
    $\begingroup$ @e2theipi2026 I edited to say that I'm not sure there is a much simpler formulation $\endgroup$
    – reuns
    May 20, 2016 at 4:50

You must log in to answer this question.

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