Mixing
Reasoning about factorials: is this equation correct?
I was playing around with the möbius inversion formula and factorials and I came up with an equation that I found interesting:
$$prod_{ige2}leftlfloorfrac{x}{i}rightrfloor! = prod_{i ge 2}prod_{j ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{-mu(i)}$$
I'm not sure if this equation is valid.
Here is the reasoning:
(1) Let $text{lcm}(x) = $ the least common multiple of ${1, 2, 3, dots, x}$
(2) Using a well known equation:
$$x! = prod_{i ge 1}text{lcm}left(leftlfloorfrac{x}{i}rightrfloorright)$$
(3) Using mobius inversion, I believe that this is now valid:
$$text{lcm}(x) = prod_{i ge 1}left(leftlfloorfrac{x}{i}rightrfloor!right)^{mu(i)}$$
(4) Combining the two equations gets me to:
$$x! = prod_{j ge 1}prod_{i ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{mu(i)}$$
(5) Since order of the products doesn't matter:
$$x! = prod_{i ge 1}prod_{j ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{mu(i)}$$
(6) Since for $i=1,j=1$, $x! = left(frac{x}{ij}!right)^{mu(i)}$:
$$1 = prod_{i ge 1}prod_{j ge 1text{ and }jne1text{ if }i=1 }left(leftlfloorfrac{x}{ij}rightrfloor!right)^{mu(i)}$$
(7) We can now use division to separate the remaining cases of $i=1$ so that we get:
$$prod_{j ge 2}leftlfloorfrac{x}{j}rightrfloor! = prod_{i ge 2}prod_{j ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{-mu(i)}$$
Is this equation correct? And if correct, is it well known?
proof-verification factorial least-common-multiple mobius-inversion
asked Nov 10 '18 at 17:59
Larry FreemanLarry Freeman
3,23921239
add a comment |
I was playing around with the möbius inversion formula and factorials and I came up with an equation that I found interesting:
$$prod_{ige2}leftlfloorfrac{x}{i}rightrfloor! = prod_{i ge 2}prod_{j ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{-mu(i)}$$
I'm not sure if this equation is valid.
Here is the reasoning:
(1) Let $text{lcm}(x) = $ the least common multiple of ${1, 2, 3, dots, x}$
(2) Using a well known equation:
$$x! = prod_{i ge 1}text{lcm}left(leftlfloorfrac{x}{i}rightrfloorright)$$
(3) Using mobius inversion, I believe that this is now valid:
$$text{lcm}(x) = prod_{i ge 1}left(leftlfloorfrac{x}{i}rightrfloor!right)^{mu(i)}$$
(4) Combining the two equations gets me to:
$$x! = prod_{j ge 1}prod_{i ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{mu(i)}$$
(5) Since order of the products doesn't matter:
$$x! = prod_{i ge 1}prod_{j ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{mu(i)}$$
(6) Since for $i=1,j=1$, $x! = left(frac{x}{ij}!right)^{mu(i)}$:
$$1 = prod_{i ge 1}prod_{j ge 1text{ and }jne1text{ if }i=1 }left(leftlfloorfrac{x}{ij}rightrfloor!right)^{mu(i)}$$
(7) We can now use division to separate the remaining cases of $i=1$ so that we get:
$$prod_{j ge 2}leftlfloorfrac{x}{j}rightrfloor! = prod_{i ge 2}prod_{j ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{-mu(i)}$$
Is this equation correct? And if correct, is it well known?
proof-verification factorial least-common-multiple mobius-inversion
asked Nov 10 '18 at 17:59
Larry FreemanLarry Freeman
3,23921239
add a comment |
I was playing around with the möbius inversion formula and factorials and I came up with an equation that I found interesting:
$$prod_{ige2}leftlfloorfrac{x}{i}rightrfloor! = prod_{i ge 2}prod_{j ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{-mu(i)}$$
I'm not sure if this equation is valid.
Here is the reasoning:
(1) Let $text{lcm}(x) = $ the least common multiple of ${1, 2, 3, dots, x}$
(2) Using a well known equation:
$$x! = prod_{i ge 1}text{lcm}left(leftlfloorfrac{x}{i}rightrfloorright)$$
(3) Using mobius inversion, I believe that this is now valid:
$$text{lcm}(x) = prod_{i ge 1}left(leftlfloorfrac{x}{i}rightrfloor!right)^{mu(i)}$$
(4) Combining the two equations gets me to:
$$x! = prod_{j ge 1}prod_{i ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{mu(i)}$$
(5) Since order of the products doesn't matter:
$$x! = prod_{i ge 1}prod_{j ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{mu(i)}$$
(6) Since for $i=1,j=1$, $x! = left(frac{x}{ij}!right)^{mu(i)}$:
$$1 = prod_{i ge 1}prod_{j ge 1text{ and }jne1text{ if }i=1 }left(leftlfloorfrac{x}{ij}rightrfloor!right)^{mu(i)}$$
(7) We can now use division to separate the remaining cases of $i=1$ so that we get:
$$prod_{j ge 2}leftlfloorfrac{x}{j}rightrfloor! = prod_{i ge 2}prod_{j ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{-mu(i)}$$
Is this equation correct? And if correct, is it well known?
proof-verification factorial least-common-multiple mobius-inversion
asked Nov 10 '18 at 17:59
Larry FreemanLarry Freeman
3,23921239
I was playing around with the möbius inversion formula and factorials and I came up with an equation that I found interesting:
$$prod_{ige2}leftlfloorfrac{x}{i}rightrfloor! = prod_{i ge 2}prod_{j ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{-mu(i)}$$
I'm not sure if this equation is valid.
Here is the reasoning:
(1) Let $text{lcm}(x) = $ the least common multiple of ${1, 2, 3, dots, x}$
(2) Using a well known equation:
$$x! = prod_{i ge 1}text{lcm}left(leftlfloorfrac{x}{i}rightrfloorright)$$
(3) Using mobius inversion, I believe that this is now valid:
$$text{lcm}(x) = prod_{i ge 1}left(leftlfloorfrac{x}{i}rightrfloor!right)^{mu(i)}$$
(4) Combining the two equations gets me to:
$$x! = prod_{j ge 1}prod_{i ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{mu(i)}$$
(5) Since order of the products doesn't matter:
$$x! = prod_{i ge 1}prod_{j ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{mu(i)}$$
(6) Since for $i=1,j=1$, $x! = left(frac{x}{ij}!right)^{mu(i)}$:
$$1 = prod_{i ge 1}prod_{j ge 1text{ and }jne1text{ if }i=1 }left(leftlfloorfrac{x}{ij}rightrfloor!right)^{mu(i)}$$
(7) We can now use division to separate the remaining cases of $i=1$ so that we get:
$$prod_{j ge 2}leftlfloorfrac{x}{j}rightrfloor! = prod_{i ge 2}prod_{j ge 1}left(leftlfloorfrac{x}{ij}rightrfloor!right)^{-mu(i)}$$
Is this equation correct? And if correct, is it well known?
proof-verification factorial least-common-multiple mobius-inversion
proof-verification factorial least-common-multiple mobius-inversion
asked Nov 10 '18 at 17:59
Larry FreemanLarry Freeman
3,23921239
asked Nov 10 '18 at 17:59
Larry FreemanLarry Freeman
3,23921239
edited Nov 10 '18 at 18:06
Larry Freeman
asked Nov 10 '18 at 17:59
Larry FreemanLarry Freeman
3,23921239
asked Nov 10 '18 at 17:59
Larry FreemanLarry Freeman
3,23921239
asked Nov 10 '18 at 17:59
Larry FreemanLarry Freeman
3,23921239
3,23921239
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
The calculations are correct.
We have from OP's referenced formula (2) for positive integers $x$
begin{align*}
color{blue}{x!=prod_{j=1}^xmathrm{lcm}left(leftlfloorfrac{x}{j}rightrfloorright)}tag{1}
end{align*}
where $mathrm{lcm}(x)$ denotes the least common multiple of all numbers up to $x$. We can write (1) in the form
begin{align*}
logleft(x!right)&=log prod_{j=1}^{x}mathrm{lcm}left(leftlfloorfrac{x}{j}rightrfloorright)\
&=sum_{j=1}^xlogmathrm{lcm} left(leftlfloorfrac{x}{j}rightrfloorright)tag{2}
end{align*}
We recall an inversion formula which can be found for instance as Theorem 268 in An Introduction to the Theory of Numbers by G.H. Hardy and E.M. Wright:
If for all positive $x$
begin{align*}
G(x)=sum_{j=1}^{lfloor xrfloor} Fleft(frac{x}{j}right)qquadtext{ then}qquad
F(x)=sum_{j=1}^{lfloor xrfloor}mu(j)Gleft(frac{x}{j}right)tag{3}
end{align*}
With $G(x)=logleft(lfloor xrfloor !right)$ and $F(x)=logmathrm{lcm}left(leftlfloorfrac{x}{j}rightrfloorright)$ we obtain from (2) and (3)
begin{align*}
logmathrm{lcm}left(lfloor xrfloorright)&=sum_{j=1}^{lfloor xrfloor}mu(j)logleft(leftlfloorfrac{x}{j}rightrfloor !right)\
&=sum_{j=1}^{lfloor xrfloor}logleft(leftlfloor frac{x}{j}rightrfloor !right)^{mu(j)}\
&=logprod_{j=1}^{lfloor xrfloor}left(leftlfloor frac{x}{j}rightrfloor !right)^{mu(j)}\
color{blue}{mathrm{lcm}left(leftlfloor xrightrfloorright)}&
color{blue}{=prod_{j=1}^{lfloor xrfloor}left(leftlfloorfrac{x}{j}rightrfloor !right)^{mu(j)}}tag{4}
end{align*}
We obtain for positive integer $x$ from (1) and (4)
begin{align*}
x!&=prod_{j=1}^xmathrm{lcm}left(leftlfloor frac{x}{j}rightrfloorright)tag{5}\
&=prod_{j=1}^xprod_{k=1}^{lfloor x/jrfloor}left(leftlfloor leftlfloor frac{x}{j}rightrfloorfrac{1}{k}rightrfloor !right)^{mu(k)}tag{6}\
&=prod_{k=1}^xprod_{j=1}^xleft(left lfloorfrac{x}{jk}rightrfloor !right)^{mu(k)}tag{7}\
&=prod_{j=1}^xleft(leftlfloor frac{x}{j}right rfloor !right)prod_{k=2}^xprod_{j=1}^xleft(leftlfloorfrac{x}{jk}rightrfloor !right)^{mu(k)}tag{8}\
1&=prod_{j=2}^xleft(leftlfloorfrac{x}{j}rightrfloor !right)prod_{k=2}^xprod_{j=1}^xleft(leftlfloor frac{x}{jk}rightrfloor !right)^{mu(k)}tag{9}
end{align*}
from which finally OP's claim
begin{align*}
color{blue}{prod_{j=2}^xleft(leftlfloorfrac{x}{j}rightrfloor !right)=prod_{k=2}^xprod_{j=1}^xleft(leftlfloor frac{x}{jk}rightrfloor !right)^{-mu(k)}}tag{10}
end{align*}
follows.
Comment:
In (6) we substitute (4) in (5).
In (7) we use the identity $leftlfloor leftlfloor frac{x}{j} rightrfloor frac{1}{k}rightrfloor=leftlfloor frac{x}{jk}rightrfloor$. We also exchange the order of the products which is feasible since they are finite and we set the upper limit to $x$ without changing anything since we are only multiplying with $1$.
In (8) we separate the case $k=1$.
In (9) we divide by $x!$.
I've looked for a citation of formula (10) in
An Introduction to the Theory of Numbers by G.H. Hardy and E.M. Wright
Introduction to Analytic Number Theory by T.M. Apostol
Introduction to Arithmetical Functions by P.J. McCarthy
Arithmetical Functions by W. Schwarz and J. Spilker
Arithmetical Functions by K. Chandrasekharan
Arithmetic Functions and Integer Products by P.D.T.A. Elliott
but was not succssful. In fact I think the essential identities are (1) and the inversion formula (3). Since there are so many different variations we can build, it is not that asthonishing that OP's formula is not stated.
answered Nov 25 '18 at 8:28
Markus ScheuerMarkus Scheuer
60.3k455144
@LarryFreeman: Thanks a lot for accepting my answer and granting the bounty. I've added a proof of (1) which might be useful.
– Markus Scheuer
Nov 27 '18 at 23:08
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2992908%2freasoning-about-factorials-is-this-equation-correct%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
The calculations are correct.
We have from OP's referenced formula (2) for positive integers $x$
begin{align*}
color{blue}{x!=prod_{j=1}^xmathrm{lcm}left(leftlfloorfrac{x}{j}rightrfloorright)}tag{1}
end{align*}
where $mathrm{lcm}(x)$ denotes the least common multiple of all numbers up to $x$. We can write (1) in the form
begin{align*}
logleft(x!right)&=log prod_{j=1}^{x}mathrm{lcm}left(leftlfloorfrac{x}{j}rightrfloorright)\
&=sum_{j=1}^xlogmathrm{lcm} left(leftlfloorfrac{x}{j}rightrfloorright)tag{2}
end{align*}
We recall an inversion formula which can be found for instance as Theorem 268 in An Introduction to the Theory of Numbers by G.H. Hardy and E.M. Wright:
If for all positive $x$
begin{align*}
G(x)=sum_{j=1}^{lfloor xrfloor} Fleft(frac{x}{j}right)qquadtext{ then}qquad
F(x)=sum_{j=1}^{lfloor xrfloor}mu(j)Gleft(frac{x}{j}right)tag{3}
end{align*}
With $G(x)=logleft(lfloor xrfloor !right)$ and $F(x)=logmathrm{lcm}left(leftlfloorfrac{x}{j}rightrfloorright)$ we obtain from (2) and (3)
begin{align*}
logmathrm{lcm}left(lfloor xrfloorright)&=sum_{j=1}^{lfloor xrfloor}mu(j)logleft(leftlfloorfrac{x}{j}rightrfloor !right)\
&=sum_{j=1}^{lfloor xrfloor}logleft(leftlfloor frac{x}{j}rightrfloor !right)^{mu(j)}\
&=logprod_{j=1}^{lfloor xrfloor}left(leftlfloor frac{x}{j}rightrfloor !right)^{mu(j)}\
color{blue}{mathrm{lcm}left(leftlfloor xrightrfloorright)}&
color{blue}{=prod_{j=1}^{lfloor xrfloor}left(leftlfloorfrac{x}{j}rightrfloor !right)^{mu(j)}}tag{4}
end{align*}
We obtain for positive integer $x$ from (1) and (4)
begin{align*}
x!&=prod_{j=1}^xmathrm{lcm}left(leftlfloor frac{x}{j}rightrfloorright)tag{5}\
&=prod_{j=1}^xprod_{k=1}^{lfloor x/jrfloor}left(leftlfloor leftlfloor frac{x}{j}rightrfloorfrac{1}{k}rightrfloor !right)^{mu(k)}tag{6}\
&=prod_{k=1}^xprod_{j=1}^xleft(left lfloorfrac{x}{jk}rightrfloor !right)^{mu(k)}tag{7}\
&=prod_{j=1}^xleft(leftlfloor frac{x}{j}right rfloor !right)prod_{k=2}^xprod_{j=1}^xleft(leftlfloorfrac{x}{jk}rightrfloor !right)^{mu(k)}tag{8}\
1&=prod_{j=2}^xleft(leftlfloorfrac{x}{j}rightrfloor !right)prod_{k=2}^xprod_{j=1}^xleft(leftlfloor frac{x}{jk}rightrfloor !right)^{mu(k)}tag{9}
end{align*}
from which finally OP's claim
begin{align*}
color{blue}{prod_{j=2}^xleft(leftlfloorfrac{x}{j}rightrfloor !right)=prod_{k=2}^xprod_{j=1}^xleft(leftlfloor frac{x}{jk}rightrfloor !right)^{-mu(k)}}tag{10}
end{align*}
follows.
Comment:
In (6) we substitute (4) in (5).
In (7) we use the identity $leftlfloor leftlfloor frac{x}{j} rightrfloor frac{1}{k}rightrfloor=leftlfloor frac{x}{jk}rightrfloor$. We also exchange the order of the products which is feasible since they are finite and we set the upper limit to $x$ without changing anything since we are only multiplying with $1$.
In (8) we separate the case $k=1$.
In (9) we divide by $x!$.
I've looked for a citation of formula (10) in
An Introduction to the Theory of Numbers by G.H. Hardy and E.M. Wright
Introduction to Analytic Number Theory by T.M. Apostol
Introduction to Arithmetical Functions by P.J. McCarthy
Arithmetical Functions by W. Schwarz and J. Spilker
Arithmetical Functions by K. Chandrasekharan
Arithmetic Functions and Integer Products by P.D.T.A. Elliott
but was not succssful. In fact I think the essential identities are (1) and the inversion formula (3). Since there are so many different variations we can build, it is not that asthonishing that OP's formula is not stated.
answered Nov 25 '18 at 8:28
Markus ScheuerMarkus Scheuer
60.3k455144
@LarryFreeman: Thanks a lot for accepting my answer and granting the bounty. I've added a proof of (1) which might be useful.
– Markus Scheuer
Nov 27 '18 at 23:08
add a comment |
The calculations are correct.
We have from OP's referenced formula (2) for positive integers $x$
begin{align*}
color{blue}{x!=prod_{j=1}^xmathrm{lcm}left(leftlfloorfrac{x}{j}rightrfloorright)}tag{1}
end{align*}
where $mathrm{lcm}(x)$ denotes the least common multiple of all numbers up to $x$. We can write (1) in the form
begin{align*}
logleft(x!right)&=log prod_{j=1}^{x}mathrm{lcm}left(leftlfloorfrac{x}{j}rightrfloorright)\
&=sum_{j=1}^xlogmathrm{lcm} left(leftlfloorfrac{x}{j}rightrfloorright)tag{2}
end{align*}
We recall an inversion formula which can be found for instance as Theorem 268 in An Introduction to the Theory of Numbers by G.H. Hardy and E.M. Wright:
If for all positive $x$
begin{align*}
G(x)=sum_{j=1}^{lfloor xrfloor} Fleft(frac{x}{j}right)qquadtext{ then}qquad
F(x)=sum_{j=1}^{lfloor xrfloor}mu(j)Gleft(frac{x}{j}right)tag{3}
end{align*}
With $G(x)=logleft(lfloor xrfloor !right)$ and $F(x)=logmathrm{lcm}left(leftlfloorfrac{x}{j}rightrfloorright)$ we obtain from (2) and (3)
begin{align*}
logmathrm{lcm}left(lfloor xrfloorright)&=sum_{j=1}^{lfloor xrfloor}mu(j)logleft(leftlfloorfrac{x}{j}rightrfloor !right)\
&=sum_{j=1}^{lfloor xrfloor}logleft(leftlfloor frac{x}{j}rightrfloor !right)^{mu(j)}\
&=logprod_{j=1}^{lfloor xrfloor}left(leftlfloor frac{x}{j}rightrfloor !right)^{mu(j)}\
color{blue}{mathrm{lcm}left(leftlfloor xrightrfloorright)}&
color{blue}{=prod_{j=1}^{lfloor xrfloor}left(leftlfloorfrac{x}{j}rightrfloor !right)^{mu(j)}}tag{4}
end{align*}
We obtain for positive integer $x$ from (1) and (4)
begin{align*}
x!&=prod_{j=1}^xmathrm{lcm}left(leftlfloor frac{x}{j}rightrfloorright)tag{5}\
&=prod_{j=1}^xprod_{k=1}^{lfloor x/jrfloor}left(leftlfloor leftlfloor frac{x}{j}rightrfloorfrac{1}{k}rightrfloor !right)^{mu(k)}tag{6}\
&=prod_{k=1}^xprod_{j=1}^xleft(left lfloorfrac{x}{jk}rightrfloor !right)^{mu(k)}tag{7}\
&=prod_{j=1}^xleft(leftlfloor frac{x}{j}right rfloor !right)prod_{k=2}^xprod_{j=1}^xleft(leftlfloorfrac{x}{jk}rightrfloor !right)^{mu(k)}tag{8}\
1&=prod_{j=2}^xleft(leftlfloorfrac{x}{j}rightrfloor !right)prod_{k=2}^xprod_{j=1}^xleft(leftlfloor frac{x}{jk}rightrfloor !right)^{mu(k)}tag{9}
end{align*}
from which finally OP's claim
begin{align*}
color{blue}{prod_{j=2}^xleft(leftlfloorfrac{x}{j}rightrfloor !right)=prod_{k=2}^xprod_{j=1}^xleft(leftlfloor frac{x}{jk}rightrfloor !right)^{-mu(k)}}tag{10}
end{align*}
follows.
Comment:
In (6) we substitute (4) in (5).
In (7) we use the identity $leftlfloor leftlfloor frac{x}{j} rightrfloor frac{1}{k}rightrfloor=leftlfloor frac{x}{jk}rightrfloor$. We also exchange the order of the products which is feasible since they are finite and we set the upper limit to $x$ without changing anything since we are only multiplying with $1$.
In (8) we separate the case $k=1$.
In (9) we divide by $x!$.
I've looked for a citation of formula (10) in
An Introduction to the Theory of Numbers by G.H. Hardy and E.M. Wright
Introduction to Analytic Number Theory by T.M. Apostol
Introduction to Arithmetical Functions by P.J. McCarthy
Arithmetical Functions by W. Schwarz and J. Spilker
Arithmetical Functions by K. Chandrasekharan
Arithmetic Functions and Integer Products by P.D.T.A. Elliott
but was not succssful. In fact I think the essential identities are (1) and the inversion formula (3). Since there are so many different variations we can build, it is not that asthonishing that OP's formula is not stated.
answered Nov 25 '18 at 8:28
Markus ScheuerMarkus Scheuer
60.3k455144
@LarryFreeman: Thanks a lot for accepting my answer and granting the bounty. I've added a proof of (1) which might be useful.
– Markus Scheuer
Nov 27 '18 at 23:08
add a comment |
The calculations are correct.
We have from OP's referenced formula (2) for positive integers $x$
begin{align*}
color{blue}{x!=prod_{j=1}^xmathrm{lcm}left(leftlfloorfrac{x}{j}rightrfloorright)}tag{1}
end{align*}
where $mathrm{lcm}(x)$ denotes the least common multiple of all numbers up to $x$. We can write (1) in the form
begin{align*}
logleft(x!right)&=log prod_{j=1}^{x}mathrm{lcm}left(leftlfloorfrac{x}{j}rightrfloorright)\
&=sum_{j=1}^xlogmathrm{lcm} left(leftlfloorfrac{x}{j}rightrfloorright)tag{2}
end{align*}
We recall an inversion formula which can be found for instance as Theorem 268 in An Introduction to the Theory of Numbers by G.H. Hardy and E.M. Wright:
If for all positive $x$
begin{align*}
G(x)=sum_{j=1}^{lfloor xrfloor} Fleft(frac{x}{j}right)qquadtext{ then}qquad
F(x)=sum_{j=1}^{lfloor xrfloor}mu(j)Gleft(frac{x}{j}right)tag{3}
end{align*}
With $G(x)=logleft(lfloor xrfloor !right)$ and $F(x)=logmathrm{lcm}left(leftlfloorfrac{x}{j}rightrfloorright)$ we obtain from (2) and (3)
begin{align*}
logmathrm{lcm}left(lfloor xrfloorright)&=sum_{j=1}^{lfloor xrfloor}mu(j)logleft(leftlfloorfrac{x}{j}rightrfloor !right)\
&=sum_{j=1}^{lfloor xrfloor}logleft(leftlfloor frac{x}{j}rightrfloor !right)^{mu(j)}\
&=logprod_{j=1}^{lfloor xrfloor}left(leftlfloor frac{x}{j}rightrfloor !right)^{mu(j)}\
color{blue}{mathrm{lcm}left(leftlfloor xrightrfloorright)}&
color{blue}{=prod_{j=1}^{lfloor xrfloor}left(leftlfloorfrac{x}{j}rightrfloor !right)^{mu(j)}}tag{4}
end{align*}
We obtain for positive integer $x$ from (1) and (4)
begin{align*}
x!&=prod_{j=1}^xmathrm{lcm}left(leftlfloor frac{x}{j}rightrfloorright)tag{5}\
&=prod_{j=1}^xprod_{k=1}^{lfloor x/jrfloor}left(leftlfloor leftlfloor frac{x}{j}rightrfloorfrac{1}{k}rightrfloor !right)^{mu(k)}tag{6}\
&=prod_{k=1}^xprod_{j=1}^xleft(left lfloorfrac{x}{jk}rightrfloor !right)^{mu(k)}tag{7}\
&=prod_{j=1}^xleft(leftlfloor frac{x}{j}right rfloor !right)prod_{k=2}^xprod_{j=1}^xleft(leftlfloorfrac{x}{jk}rightrfloor !right)^{mu(k)}tag{8}\
1&=prod_{j=2}^xleft(leftlfloorfrac{x}{j}rightrfloor !right)prod_{k=2}^xprod_{j=1}^xleft(leftlfloor frac{x}{jk}rightrfloor !right)^{mu(k)}tag{9}
end{align*}
from which finally OP's claim
begin{align*}
color{blue}{prod_{j=2}^xleft(leftlfloorfrac{x}{j}rightrfloor !right)=prod_{k=2}^xprod_{j=1}^xleft(leftlfloor frac{x}{jk}rightrfloor !right)^{-mu(k)}}tag{10}
end{align*}
follows.
Comment:
In (6) we substitute (4) in (5).
In (7) we use the identity $leftlfloor leftlfloor frac{x}{j} rightrfloor frac{1}{k}rightrfloor=leftlfloor frac{x}{jk}rightrfloor$. We also exchange the order of the products which is feasible since they are finite and we set the upper limit to $x$ without changing anything since we are only multiplying with $1$.
In (8) we separate the case $k=1$.
In (9) we divide by $x!$.
I've looked for a citation of formula (10) in
An Introduction to the Theory of Numbers by G.H. Hardy and E.M. Wright
Introduction to Analytic Number Theory by T.M. Apostol
Introduction to Arithmetical Functions by P.J. McCarthy
Arithmetical Functions by W. Schwarz and J. Spilker
Arithmetical Functions by K. Chandrasekharan
Arithmetic Functions and Integer Products by P.D.T.A. Elliott
but was not succssful. In fact I think the essential identities are (1) and the inversion formula (3). Since there are so many different variations we can build, it is not that asthonishing that OP's formula is not stated.
answered Nov 25 '18 at 8:28
Markus ScheuerMarkus Scheuer
60.3k455144
The calculations are correct.
We have from OP's referenced formula (2) for positive integers $x$
begin{align*}
color{blue}{x!=prod_{j=1}^xmathrm{lcm}left(leftlfloorfrac{x}{j}rightrfloorright)}tag{1}
end{align*}
where $mathrm{lcm}(x)$ denotes the least common multiple of all numbers up to $x$. We can write (1) in the form
begin{align*}
logleft(x!right)&=log prod_{j=1}^{x}mathrm{lcm}left(leftlfloorfrac{x}{j}rightrfloorright)\
&=sum_{j=1}^xlogmathrm{lcm} left(leftlfloorfrac{x}{j}rightrfloorright)tag{2}
end{align*}
We recall an inversion formula which can be found for instance as Theorem 268 in An Introduction to the Theory of Numbers by G.H. Hardy and E.M. Wright:
If for all positive $x$
begin{align*}
G(x)=sum_{j=1}^{lfloor xrfloor} Fleft(frac{x}{j}right)qquadtext{ then}qquad
F(x)=sum_{j=1}^{lfloor xrfloor}mu(j)Gleft(frac{x}{j}right)tag{3}
end{align*}
With $G(x)=logleft(lfloor xrfloor !right)$ and $F(x)=logmathrm{lcm}left(leftlfloorfrac{x}{j}rightrfloorright)$ we obtain from (2) and (3)
begin{align*}
logmathrm{lcm}left(lfloor xrfloorright)&=sum_{j=1}^{lfloor xrfloor}mu(j)logleft(leftlfloorfrac{x}{j}rightrfloor !right)\
&=sum_{j=1}^{lfloor xrfloor}logleft(leftlfloor frac{x}{j}rightrfloor !right)^{mu(j)}\
&=logprod_{j=1}^{lfloor xrfloor}left(leftlfloor frac{x}{j}rightrfloor !right)^{mu(j)}\
color{blue}{mathrm{lcm}left(leftlfloor xrightrfloorright)}&
color{blue}{=prod_{j=1}^{lfloor xrfloor}left(leftlfloorfrac{x}{j}rightrfloor !right)^{mu(j)}}tag{4}
end{align*}
We obtain for positive integer $x$ from (1) and (4)
begin{align*}
x!&=prod_{j=1}^xmathrm{lcm}left(leftlfloor frac{x}{j}rightrfloorright)tag{5}\
&=prod_{j=1}^xprod_{k=1}^{lfloor x/jrfloor}left(leftlfloor leftlfloor frac{x}{j}rightrfloorfrac{1}{k}rightrfloor !right)^{mu(k)}tag{6}\
&=prod_{k=1}^xprod_{j=1}^xleft(left lfloorfrac{x}{jk}rightrfloor !right)^{mu(k)}tag{7}\
&=prod_{j=1}^xleft(leftlfloor frac{x}{j}right rfloor !right)prod_{k=2}^xprod_{j=1}^xleft(leftlfloorfrac{x}{jk}rightrfloor !right)^{mu(k)}tag{8}\
1&=prod_{j=2}^xleft(leftlfloorfrac{x}{j}rightrfloor !right)prod_{k=2}^xprod_{j=1}^xleft(leftlfloor frac{x}{jk}rightrfloor !right)^{mu(k)}tag{9}
end{align*}
from which finally OP's claim
begin{align*}
color{blue}{prod_{j=2}^xleft(leftlfloorfrac{x}{j}rightrfloor !right)=prod_{k=2}^xprod_{j=1}^xleft(leftlfloor frac{x}{jk}rightrfloor !right)^{-mu(k)}}tag{10}
end{align*}
follows.
Comment:
In (6) we substitute (4) in (5).
In (7) we use the identity $leftlfloor leftlfloor frac{x}{j} rightrfloor frac{1}{k}rightrfloor=leftlfloor frac{x}{jk}rightrfloor$. We also exchange the order of the products which is feasible since they are finite and we set the upper limit to $x$ without changing anything since we are only multiplying with $1$.
In (8) we separate the case $k=1$.
In (9) we divide by $x!$.
I've looked for a citation of formula (10) in
An Introduction to the Theory of Numbers by G.H. Hardy and E.M. Wright
Introduction to Analytic Number Theory by T.M. Apostol
Introduction to Arithmetical Functions by P.J. McCarthy
Arithmetical Functions by W. Schwarz and J. Spilker
Arithmetical Functions by K. Chandrasekharan
Arithmetic Functions and Integer Products by P.D.T.A. Elliott
but was not succssful. In fact I think the essential identities are (1) and the inversion formula (3). Since there are so many different variations we can build, it is not that asthonishing that OP's formula is not stated.
answered Nov 25 '18 at 8:28
Markus ScheuerMarkus Scheuer
60.3k455144
edited Dec 1 '18 at 22:10
answered Nov 25 '18 at 8:28
Markus ScheuerMarkus Scheuer
60.3k455144
answered Nov 25 '18 at 8:28
Markus ScheuerMarkus Scheuer
60.3k455144
answered Nov 25 '18 at 8:28
Markus ScheuerMarkus Scheuer
60.3k455144
60.3k455144
@LarryFreeman: Thanks a lot for accepting my answer and granting the bounty. I've added a proof of (1) which might be useful.
– Markus Scheuer
Nov 27 '18 at 23:08
add a comment |
@LarryFreeman: Thanks a lot for accepting my answer and granting the bounty. I've added a proof of (1) which might be useful.
– Markus Scheuer
Nov 27 '18 at 23:08
@LarryFreeman: Thanks a lot for accepting my answer and granting the bounty. I've added a proof of (1) which might be useful.
– Markus Scheuer
Nov 27 '18 at 23:08
@LarryFreeman: Thanks a lot for accepting my answer and granting the bounty. I've added a proof of (1) which might be useful.
– Markus Scheuer
Nov 27 '18 at 23:08
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2992908%2freasoning-about-factorials-is-this-equation-correct%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
