Question

Factorials and grouping troubles

Answer 1

Suppose I have a number of things, so let's look at 4 things. Some of them can be the same or different, I'd like to know how they all can be sorted into different groups basically, I can express this better in symbols I think

\[\Large [p, p,p,q] \implies 3(p,p) + 3(p,q) \\ \Large [p, p,q,q] \implies 1(p,p) + 1 (q,q) +4(p,q) \\ \Large [p,p,q,r] \implies 1(p,p) + 1(q,r)+2(p,q)+2(qr)\\ \Large etc... \] How do I calculate these coefficients? I know that the total of all the coefficients is always 6 because \[\Large \frac{4!}{(4-2)!2!} = 6\] Since we're taking 4 things and sorting it into groups of 2. I just can't seem to break it down further to get the coefficients, any ideas?

Answer 2

Gibe medal

Answer 3

I don't know how you are getting the coefficients

Answer 4

Sorry, I'll try to explain better. So let's start out with [a,b,c,d] and split them all up into pairs: (a,b), (a,c), (a,d), (b,c), (b,d), (c,d) and since there are 6 different ways to pick pairs. So I'm saying each of these has a "coefficient" of 1. Now if we substitute in a=b=c=p and d=q we end up with 3(p,p) and 3(p,q).

Answer 5

Another example that might help or hinder you is that this is a generalization of the arithmetic derivative where (pq)' = 1 and p'=0. So for example, if I use this to represent the "double arithmetic derivative" \[\large (12)^{(2)} = (2*2*3)^{(2)}= \\ \large (2*2)^{(2)}*3 + (2*3)^{(2)}*2+(2*3)^{(2)}*2 = \\ \large 3+2+2 = \\ \Large 1*3+2*2=7\] Notice that the last line I rewrote 3 with a coefficient of 1 and 2 with a coefficient of 2 because 3!/(3-2)!2!=3 and this is the sum of the coefficients...

Answer 6

See I found out if you make this kind of generalization to the arithmetic derivative you can seamlessly connect ordinary derivatives of calculus to the arithmetic derivative through a simple polynomial, but I also want a way to just express these higher "order?" arithmetic derivatives independently of the polynomial.

Answer 7

Will it always be sorted?

Answer 8

The polynomial looks like this: \[\Large P(x) = n-n'x+n^{(2)}x^2-n^{(3)}x^3+ \cdots\]\[\Large P(x) = - \prod_i (x-p_i)^{a_i}\]

Where \[\Large n = \prod_i p_i^{a_i}\]

Answer 9

Well, the array \[
[p,p,p,q]
\]Can be written as \[
[3,1]
\]And your transformation of coefficients is: \[
[3,3]
\]

Answer 10

So by this sort of idea, let's look at this: \[\Large 12^{(0)}=12 \\ \Large 12' = 16 \\ \Large 12^{(2)}=7 \\ \Large 12^{(3)}=1 \\ \Large 12^{(n>3)}=0\] If we write it out we get: \[\Large P(x)=12-16x+7x^2-x^3\] but since we have this equivalence, we can immediately factor it if we know the factors of 12: \[\Large 12 = 2^23^1\]\[\Large P(x) = -(x-2)^2(x-3)^1\]So it has roots at all the factors of 12, and at x=0 it evaluates to the number itself. Take the nth derivative of this and divide by ((-1)^n * n!) and you get the nth arithemetic derivative. So the first one will be: \[\Large \ln(-P(x)) =2 \ln(x-2)+1\ln(x-3) \\ \Large \frac{P'(x)}{P(x)}=\frac{2}{x-2}+\frac{1}{x-3}\] See how this resembles the exact form we have seen before? Exponent on top and prime on the bottom, pretty interesting considering I haven't thought about arithmetic derivatives in maybe 2 months lol.

Answer 11

\[
[1,1,1,1 ] \to [1,1,1,1,1,1]\\
[2,1,1]\to [1,2,2,1]\\
[2,2]\to [1,4,1]\\
[3,1]\to [3,3]\\
[4]\to [6]\\
\]

Answer 12

The first one and last one are the most obvious

Answer 13

So how do I connect them up, for example 2,1,1 to 1,2,2,1 I guess I'm not seeing how to assign what pair to which very easily.

Answer 14

For totals of 3, it seems the coefficient is just the cardinality or something\[
[1,1,1]\to [1,1,1]\\
[2,1] \to [2,1]\\
[3]\to [3]
\]

Answer 15

I've notice something interesting though...

Answer 16

Comparing 3s to 4s, it seems that if you append a 1 to the end, it just ends up repeating the sequence.

Answer 17

Maybe not repeat... more like it flips it and then it concatenates

Answer 18

I dunno that there is a simply way to express the coefficients

Answer 19

I'm sort of looking at trying to somehow add on to the arithmetic derivative definition somehow. It's weird I don't know. It's like we're going through all the pairs of numbers not just the individual ones.

Answer 20

\[
2\\
pp\to 1pp\\
pq\to 1pq\\
3\\
ppp\to 3pp\\
ppq\to 1pp+2pq\\
pqr\to 1pq+1pr+1qr\\
4\\
pppp\to 6pp\\
pppq\to 3pp+3pq\\
ppqq\to 1pp + 4pq + 1qq\\
ppqr\to 1pp+2pq+2pr+1qp\\
pqrs\to 1pp+1pq+1pr+1ps+1qr+1qs+1rs\\
5\\
ppppp\to 10pp\\
ppppq\to 6pp+4pq\\
pppqq\to 3pp+6pq +1qq\\
pppqr\to 3pp+3pq+3pr+1qr\\
ppqqr\to 1pp+4pq+2pr+1qq+2qr\\
ppqrs\to 1pp+2pq+2pr+2ps+1qr+1qs+1rs\\
pqrst\to 1pp+1pq+1pr+1ps+1pt+1qr+1qs+1qt+1rs+1rt+1st
\]

Answer 21

There are really 2 rules I see

Answer 22

It looks like it's related to the multinomial theorem, but I don't know how to make that work out very well.

Answer 23

\[
\text{coefficient}(p,p)={\text{count}(p)\choose 2}\]\[
\text{coefficient}(p,q) =\text{count}(p)\cdot \text{count}(q)
\]

Answer 24

In our case: \({1\choose 2}=0\)

Answer 25

That actually looks like something I have, I feel bad now for not thinking to show this: \[\Large n = \prod_{i=1}^{\omega(n)}p_i^{\alpha_i}\] Here I'm saying that \[\Large \omega(n) = \text{number of unique prime factors of n}\] So then \[\Large \binom{\omega(n)}{d} = \text{ sum of coefficients on } n^{(d)}\] and we are looking at d=2.

Another useful function to try to help might be: \[\Large \Omega(n) = \text {number of prime factors of n}\] So to prevent confusion, here's an inequality \[\Large \Omega(n) \ge \omega(n)\]

Answer 26

We have loops for \(p^p\), so for example \(2^2=4\) will loop to be \(4-4x+4x^2+\ldots\) right?

Answer 27

Well this is subtle because this isn't the same thing as the arithmetic derivative. It's not like taking the first derivative and then taking the first derivative again. It's more like taking a "double" derivative where you are obeying the leibniz law but "biting off" more with the higher orders. So to contrast here: \[(30)'' = (2*3*5)'' = (2'*3*5+2*3'*5+2*3*5')' \\ (15+10+6)'= (31)'=1 \\ (30)^{(2)}=(2*3*5)^{(2)}=(2*3)^{(2)}*5+(2*5)^{(2)}*3+(3*5)^{(2)}*2 \\ 5+3+2 = 10\]

Answer 28

So to clarify, here is where the similarities are: \[\Large n=n^{(0)} \\ \Large n' = n^{(1)} \\ \Large n'' \ne n^{(2)} \\ \Large n'' = n^{(1)(1)}\]

Answer 29

Actually is there something stopping us from taking derivatives of this expression? \[\Large F(x) = -\prod_{k=1}^{\omega(n)} (x-p_k)^{\alpha_k}\] since \[\Large \frac{1}{(-1)^k k!}\frac{d^k F(0)}{dx^k}= n^{(k)}\]

Answer 30

So \[
(abc)^{(2)} = a(bc)^{(2)} +b(ac)^{(2)} +c(ab)^{(2)}
\]

Answer 31

That looks like what you were doing

Answer 32

Yeah, that's exactly the idea! =D for example we can show stuff like: \[\Large 1'' = (1*1*1)'' = 3(1*1)''=3(1)'' \\ \Large 1'' = (1*1*1*1)'' = 4(1*1)''=4(1)'' \\ \Large 3(1)'' = 4 (1)'' \implies (1)'' = 0\]

Answer 33

I prefer to show the double prime to mean my notation since ordinarily the double prime is easier to write and since it's not linear it has very little significance in its meaning.

Answer 34

I think I messed up what I was saying but maybe you know what I meant to say. Like \[\Large n'' =???\] normally since the second derivative isn't linear. But \[ n^{(2)} = (n_1n_2)^{(2)}n_3 \cdots n_k +n_1(n_2n_3) ^{(2)} \cdots n_k+ n_2(n_1n_3)^{(2)} \cdots n_k+...\] So I would prefer and find it nicer to reverse the notation. lol

Answer 35

I found an expression though: \[\large n^{(2)} = \frac{1}{2} \prod_{k=1}^{\omega(n)} (-p_k)^{\alpha_k} \left[ \sum_{i = 1}^{\omega(n)}\frac{\alpha_i}{p_i^2}-\left( \sum_{j=1}^{\omega(n)} \frac{\alpha_j}{-p_j} \right)^2 \right]\] I haven't checked it yet though.

Answer 36

I am guessing that for any two primes \(p,q\) we say: \[
(pq)''=1
\]and we can use the recursive property?

Answer 37

Hmm, I'm just wondering about what the precise definition would be, and how to get \(1''=0\) from that.

Answer 38

Yeah exactly, and we can do the same thing with (pqr)''' and other higher or lower orders. Basically a number with n prime factors will return 1 from the nth derivative.

Answer 39

@wio this is the proof of exactly that which I wrote above: \[\Large 1'' = (1*1*1)'' = 3(1*1)''=3(1)'' \\ \Large 1'' = (1*1*1*1)'' = 4(1*1)''=4(1)'' \\ \Large 3(1)'' = 4 (1)'' \implies (1)'' = 0\]

Answer 40

How did you get \(4(1\cdot 1)''\)?

Answer 41

I hope the weird notation I just invented helps show the 4 different terms. Pretend that (a)b(cd) is the same as b(acd) I just wanted to show that each one was separate.

(1*1*1*1)'' = 1 (1*1*1)'' + (1)1(1*1)'' + (1*1)1(1)'' + (1*1*1)'' 1

Answer 42

So then I guess we say: \[
(p^n)'' = {n\choose2}p^{n-2}
\]While \[
((p^n)')' = n'p^{n-1}+(n)(n-1)p^{n-2}
\]

Answer 43

I think so, ut I'm not sure. That second line there is the ordinary arithmetic derivative applied twice?

Another related partial proof : \[\Large (pq*1)'' = (pq)'' 1 + p(q*1)'' + q(p*1)'' \\ \Large (pq)'' = (pq)'' \]

Answer 44

Yeah yeah! What you're saying looks right I think so. =D

Answer 45

This is another one I'm thinking about: \[
(p^nq^k)'' = {n\choose2}p^{n-2}q+nkp^{n-1}q^{k-1}+{k\choose2}p^nq^{k-2}
\]

Answer 46

More generally then I guess: \[\Large (p^n)^{(k)} =\binom{\Omega(p^n)}{k}p^{n-k}=\binom{n}{k}p^{n-k}\] since \[\Large \Omega(p^n) = n\]

Answer 47

You are going general in another direction that I'm looking for I'm liking this this is helping a lot thanks man.

Answer 48

So the recursive definition for this is: \[
(pq)'' = 1\\
(abc)'' = a(bc)''+b(ac)''+c(ab)''
\]Right? That is what everything should be derived from?

Answer 49

Yes, I believe that's correct. I mean I don't know if I would use _should_ since if there is some sort of unforseen difficulty with that we can always change it since that's not exactly the idea itself, just a manifestation of it. Like the map is not the territory kind of thing.

The main point is that it plays off of this relationship:

\[\Large F(x) =a_0+a_1x+a_2x^2+x^3 \\ \Large F(x) = (x-r_1)(x-r_2)(x-r_3) = \\ \large -r_1r_2r_3 +(r_1r_2+r_1r_3+r_2r_3)x- (r_1+r_2+r_3)x^2+x^3\]

See how if all the roots are primes then we have exactly \[\Large -a_0 = n \\ \Large a_1 = n' \\ \Large -a_2 = n'' \\ \Large a_3 = n'''\] as long as n has 3 or less total prime factors, or to put a fancy way: \[\Large \Omega(n) \le 3\] But of course this is only a specific case, it extends to an arbitrary number of factors.

Answer 50

The "fundamental" equation I'm looking at is this: \[\Large \sum_{k=0}^{\Omega(n)} n^{(k)}(-x)^k = - \prod_{i=1}^{\omega(n)} (x-p_i)^{\alpha_i}\] or you can rewrite the product as this: \[\Large \sum_{k=0}^{\Omega(n)} n^{(k)}(-x)^k = - \prod_{i=1}^{\Omega(n)} (x-p_i)\] but the bottom equation implies a larger product with repeating terms. Keep in mind this is for the definition of a number with its prime factorization as: \[\Large n = \prod_{k=1}^{\omega(n)}p_k^{\alpha_k}\] or if you like the other version where we count primes multiple times instead of represent their powers (kind of less precise since it hides the fact that k=1, k=2, k=3 might all be the prime 2 since we don't have the exponent. But it allows us to express it with capital Omega.) \[\Large n = \prod_{k=1}^{\Omega(n)}p_k\]

Answer 51

I see how \(1''=p''=0\) now.

Answer 52

Yeah, so maybe this can help us solve that project euler question LOL

Answer 53

Cool, so I think we're on the same page. I didn't want to start out with this cause I didn't really think it would attract many people. But weirdly enough I picked today to be interested in this again and you were on just completely random.

The main things I want to do aside from get the general formulas for the n^(k) derivatives is show that they are bounded above and below using similar proofs to prove these facts: \[\Large k n^{\frac{k -1}{k}} \le n' \le \frac{n}{r}\log_r (n)\] where r is the smallest prime factor in n and k is the capital Omega function of n (total prime factors in n).

Answer 54

Those are interesting proofs by themselves, and I think they might be able to get hijacked over to the other derivatives fairly simply. It's just a kind of hard task that I'm kind of not sure I want to attack right now.

Answer 55

\[
(x-r_1)(x-r_2)(x-r_3)= (r_1+r_2+r_3)x^2+(r_1r_2+r_1r_3+r_2r_3)x+\ldots
\]If we multiply by \(x-r_4\), then we get: \[
(x-r_1)(x-r_2)(x-r_3)(x-r_4)\\\quad =-r_4 (r_1+r_2+r_3)x^2+ (r_1r_2+r_1r_3+r_2r_3)x^2+ \ldots
\]Hmmmm

Answer 56

So maybe we can say: \[
(an)^{(k)} = -an^{(k)}+n^{(k-1)}
\]

Answer 57

I may be missing something here

Answer 58

I'm not really sure what you're saying, but I'll reply what it makes me think. We might have some way to construct derivatives of larger numbers knowing the derivatives of their factors. So we can calculate the polynomial for 50 if we know the polynomials of its factors.

Then for your second post it makes me think we can write derivatives as part of other numbers and other derivatives some how, interesting.

Answer 59

Basically, you are saying if you prime factor where \(k\) is number of primes: \[
n=r_1r_2\ldots r_k
\]Then you make the polynomial: \[
P(x)=(x-r_1)(x-r_2)\ldots (x-r_k)
\]We say: \[
n=P(0) \\
n'=P'(0)\\
n''=P''(0)\\
n^{(m)}=P^{(m)}(0)
\]And such is how you're generalizing arithmetic derivatives.
I'm looking at \(pn\) where \(p\) is prime.
Seems to me that: \[
pn = (x-p)P(x) = xP(x)-pP(x)
\]Therefore: \[
(pn)^{(m)} = (xP(x))^{(m)}-pP^{(m)}(x)=P^{(m-1)}(x)-pP^{(m)}(x)
\]When we let \(x=0\), we get:\[
P^{(m-1)}(0)-pP^{(m)}(0) = n^{(m-1)}-pn^{(m)}
\]

Answer 60

I'm running into a problem with a negative sign, but here's an example where n=pq and m=pqr = nr
\[\Large n-n'x+n''x^2 = - (x-p)(x-q) \\ \Large (x-r)(n-n'x+n''x^2) = - (x-p)(x-q)(x-r) \\ \Large nx-n'x^2+n''x^3 -rn+rn'x-rn''x^2 \\ \Large -nr+(n+rn')x-(n'+rn'')x^2+n''x^3 \\ \Large -m+m'x-m''x^2 +m'''x^3\] The last step is really nice except that it's all negative lol.

Answer 61

Yeah I think what you're saying is kind of the general form of what I'm trying to get at, let me look at it, I think there has to be a negative sign fixed somewhere and I'm trying to find out where exactly.

Answer 62

Also, a quick note you're not entirely correct when you say that, it needs corrections on the derivatives \[\Large n'' = \frac{(-1)^2}{2!}P''(0)\]

Answer 63

Hmmmm

Answer 64

Why the division?

Answer 65

Well when you take the nth derivative you will have n! on top that needs to go away.

Answer 66

well... Here let me show you \[\Large \frac{d^2}{dx^2}(n'' x^2) = 2n''\] That's why we need the corrction factor.

Answer 67

correction* lolol

Answer 68

Okay then \[
n^{(m)} = \frac{(-1)^{m+1}}{m!}P^{(m)}(0)
\]

Answer 69

I figured out the problem. We need to represent the formula as this: \[\Large P(x) = \prod_{i=1}^{\omega(n)} (p_i-x)^{\alpha_i}\] That will stop the sign from oscillating around on us.

Answer 70

Does that give us the same results though?

Answer 71

The new fundamental equation: \[\Large P(x) =\sum_{k=0}^{\Omega(n)}n^{(k)}(-x)^k = \prod_{i=1}^{\omega(n)} (p_i-x)^{\alpha_i}\] We can see that in the product we will always have a positive sign on the first term without an x and similarly her we have the first term without the problem.

Actually there seems to be another hint that this is correct, if we plug in -x for x it seems like we completely lose the alternating signs. But the crazy thing is I don't kknow if the x's mean roots anymore. Weird. I'll make a quick example.

Answer 72

\[\Large (p+x)(q+x)= pq + (p+q)x+x^2 \\ \Large (p+x)(q+x)(r+x)= \\ \Large pqr + (pq+qr+pr)x+(p+q+r)x^2+x^3\] I feel like I discovered something so incredibly mundane from a very weird standpoint lol.

Answer 73

In that case, we wouldn't need to use any negative signs at all. Why did we start with negative signs?

Answer 74

This feels like trivial garbage now. I started with them just because I wanted the roots of the polynomial to be the factors of n. I didn't really think about it, I just noticed there was a connection between a polynomial that had the same roots as the number also gave rise to the arithmetic derivative on one of the terms and that got me interested in a generalized derivative "with respect to multiple primes".

Answer 75

oh, I see

Answer 76

Well then again, maybe this is really a good thing, it makes a lot of things seem to collapse down and make sense again and not only that we also have the omegas around and roots. We can now say P(-x)=0 at the roots of n and stuff.

Answer 77

Okay, well if talking about the roots, then maybe \(x-p_i\) form makes most sense.

Answer 78

However, if you were to make every prime negative, then\[
x-(-p_i)=x+p_i
\]To do that we mutliply by \((-1)^k\) where \(k\) is number of prime factors.

Answer 79

Another nice relation from this \[\Large P(x) =\sum_{k=0}^{\Omega(n)}n^{(k)}x^k = \prod_{i=1}^{\omega(n)} (p_i+x)^{\alpha_i}\] We can say \[\Large P(0) =\sum_{k=0}^{\Omega(n)}n^{(k)}0^k = \prod_{i=1}^{\omega(n)} p_i^{\alpha_i}\] Allowing 0^0=1 in this case gives us what we know \[\Large n^{(0)} =n= \prod_{i=1}^{\omega(n)} p_i^{\alpha_i}\] And just for fun P(-x)=0 at the roots of n. We also have the derivative rule to get the higher order arithmetic derivatives. There might be some utility in this, I just wish I knew more about generating functions since that's what this looks like.

Answer 80

Since\[
n=p_1p_2\ldots p_k = (-1)^k(-p_1)(-p_2)\ldots (-p_k)
\]

Answer 81

Yeah that's probably the correction I should have found earlier. Oh well, I wonder if there's some kind of recursion thing we can do or some such with this to find something interesting out about the arithmetic derivative.

Answer 82

So we're just going to stick with the \(x+p_i\) version then?

Answer 83

Yeah, since we can always recover the x-p version by plugging in -x and factoring out a - from the product side if that's what we want, unless there is some really useful or compelling reason to put it back in the root form, I mean we might still discover something cool lol.

Answer 84

So in general: \[
n^{(k)} = \frac{P^{(k)}(0)}{k!}
\]

Answer 85

Yeah, that's pretty nice looking.

Answer 86

Using \[\Large \ln \left( \prod_i a_i \right) = \sum_i \ln(a_i)\] I think we can simplify the derivative to get general expressions for the nth derivative.

Answer 87

\[
(pn)^{(k)} = \frac{d^k}{dx^k}\bigg((x+p)P(x)\bigg)\bigg|^{x=0}
\]

Answer 88

This is when \(p\) is a prime.

Answer 89

Ahh, I am starting to see we might be able to do something fun: \[\Large \frac{d}{dx}[(x+p)P_n(x) ] = P_n(x) + (x+p)P_n'(x) \\ \Large P_n(0)+pP_n'(0) = P_{n*p}'(0)\]

Answer 90

\[
\frac{d^k}{dx^k}\bigg(pP(x)\bigg)\bigg|^{x=0} =pP^{(k)}(0)
\]

Answer 91

\[
\frac{d^k}{dx^k}\bigg(xP(x)\bigg)\bigg|^{x=0} =\sum_{i=0}^k{k\choose i}x^{(i)}P^{(k-i)}(x)\bigg|^{x=0}
\]The only nonzero term for \(x^{(i)}\) is when \(i=1\), so\[
\frac{d^k}{dx^k}\bigg(xP(x)\bigg)\bigg|^{x=0} = {k\choose 1}P^{(k-1)}(0) = kP^{(k-1)}(0)
\]

Answer 92

So in general: \[
n^{(k)} = \frac{P^{(k)}(0)}{k!}\iff k!n^{(k)}=P^{(k)}(0)
\]

Answer 93

So this leaves us with: \[
(pn)^{(k)} = kP^{(k-1)}(0) +pP^{(k)}(0) = k(k-1)!n^{(k-1)}+pk!n^{(k)} \\
\quad = k!\bigg(n^{(k-1)}+pn^{(k)}\bigg)
\]

Answer 94

Ok wait can we change notation a bit to square brackets for the generalized arithmetic derivative so we can use the regular derivative unambiguously \[
n^{[k]} = \frac{P^{(k)}(0)}{k!}
\]

Answer 95

I'm still reading what you've wrote, I'm not sure I understand your last post really, it's kind of like saying we have a recursive definition somehow I guess.

Answer 96

\[
(pn)''=2(n'+pn'')
\]

Answer 97

Ok I see, interesting. Just sort of switching around to substituting it in backwards of what I would have thought to do.

Answer 98

Hmmm, interesting\[
(ab)^{[k]} =\frac{[P(x)G(x)]^{(k)} }{k!}\bigg|^{x=0} = \sum_{i=0}^k{k\choose i}P^{(i)}(x)G^{(k-i)}(x)\bigg|^{x=0}
\\\quad \quad =\sum_{i=0}^k{k\choose i}i!a^{[i]}(k-i)!b^{[k-i]}
\]