Mixing
Number theory tricky
$begingroup$
Let $f:mathbb{N}tomathbb{N}$
be defined as follows: for every natural number $m$, $f(m)$ is the smallest natural number $k$ such that there exists a sequence $m=a_1<a_2<...<a_t=k$ for which $a_1 cdot a_2 cdot cdots cdot a_t$ is a square.
Prove: $f$ is injective, and its range is exactly all of the composite numbers.
I've found that for prime numbers $p$ we have $f(p)=2p$, so it's injective on prime numbers. But I have no idea about the rest.
elementary-number-theory contest-math
edited Jan 30 at 14:18
YuiTo Cheng
2,1963937
asked Jan 30 at 12:51
No one No one
212
$endgroup$
add a comment |
$begingroup$
Let $f:mathbb{N}tomathbb{N}$
be defined as follows: for every natural number $m$, $f(m)$ is the smallest natural number $k$ such that there exists a sequence $m=a_1<a_2<...<a_t=k$ for which $a_1 cdot a_2 cdot cdots cdot a_t$ is a square.
Prove: $f$ is injective, and its range is exactly all of the composite numbers.
I've found that for prime numbers $p$ we have $f(p)=2p$, so it's injective on prime numbers. But I have no idea about the rest.
elementary-number-theory contest-math
edited Jan 30 at 14:18
YuiTo Cheng
2,1963937
asked Jan 30 at 12:51
No one No one
212
$endgroup$
$begingroup$
Welcome to MSE. Your questions lacks details and context. Why are you interested in this question and what have you tried so far? You can find some remarks about how to ask a good question here math.stackexchange.com/help/how-to-ask
$endgroup$
– James
Jan 30 at 12:58
$begingroup$
Why is $f(p)=2p$? With $p=3$, that would mean that there was a good sequence that ended in $6$, no? But the only options are ${3,6}$, ${3,5,6}$ (including the square $4$ can't change anything, right?) and neither of those work.
$endgroup$
– lulu
Jan 30 at 13:22
1
$begingroup$
@lulu, a bit of experimentation suggests that perhaps $f(p) = 2p$ for $p > 3$ a prime. So $2, 3$ are the exceptions. Edit: specifically, for $p > 3$ a prime, I always find twice a square in the interval $(p, 2p)$, so I can make the sequence $(p, 2n^2, 2p)$ for some $n$. Clearly $f(p) geq 2p$, so this works.
$endgroup$
– Mees de Vries
Jan 30 at 13:29
$begingroup$
I mean for primes greater than 3
$endgroup$
– No one
Jan 30 at 13:39
$begingroup$
@MeesdeVries Thanks.
$endgroup$
– lulu
Jan 30 at 16:22
add a comment |
$begingroup$
Let $f:mathbb{N}tomathbb{N}$
be defined as follows: for every natural number $m$, $f(m)$ is the smallest natural number $k$ such that there exists a sequence $m=a_1<a_2<...<a_t=k$ for which $a_1 cdot a_2 cdot cdots cdot a_t$ is a square.
Prove: $f$ is injective, and its range is exactly all of the composite numbers.
I've found that for prime numbers $p$ we have $f(p)=2p$, so it's injective on prime numbers. But I have no idea about the rest.
elementary-number-theory contest-math
edited Jan 30 at 14:18
YuiTo Cheng
2,1963937
asked Jan 30 at 12:51
No one No one
212
$endgroup$
Let $f:mathbb{N}tomathbb{N}$
be defined as follows: for every natural number $m$, $f(m)$ is the smallest natural number $k$ such that there exists a sequence $m=a_1<a_2<...<a_t=k$ for which $a_1 cdot a_2 cdot cdots cdot a_t$ is a square.
Prove: $f$ is injective, and its range is exactly all of the composite numbers.
I've found that for prime numbers $p$ we have $f(p)=2p$, so it's injective on prime numbers. But I have no idea about the rest.
elementary-number-theory contest-math
elementary-number-theory contest-math
edited Jan 30 at 14:18
YuiTo Cheng
2,1963937
asked Jan 30 at 12:51
No one No one
212
edited Jan 30 at 14:18
YuiTo Cheng
2,1963937
asked Jan 30 at 12:51
No one No one
212
edited Jan 30 at 14:18
YuiTo Cheng
2,1963937
edited Jan 30 at 14:18
YuiTo Cheng
2,1963937
edited Jan 30 at 14:18
YuiTo Cheng
2,1963937
2,1963937
asked Jan 30 at 12:51
No one No one
212
asked Jan 30 at 12:51
No one No one
212
asked Jan 30 at 12:51
No one No one
212
212
$begingroup$
Welcome to MSE. Your questions lacks details and context. Why are you interested in this question and what have you tried so far? You can find some remarks about how to ask a good question here math.stackexchange.com/help/how-to-ask
$endgroup$
– James
Jan 30 at 12:58
$begingroup$
Why is $f(p)=2p$? With $p=3$, that would mean that there was a good sequence that ended in $6$, no? But the only options are ${3,6}$, ${3,5,6}$ (including the square $4$ can't change anything, right?) and neither of those work.
$endgroup$
– lulu
Jan 30 at 13:22
1
$begingroup$
@lulu, a bit of experimentation suggests that perhaps $f(p) = 2p$ for $p > 3$ a prime. So $2, 3$ are the exceptions. Edit: specifically, for $p > 3$ a prime, I always find twice a square in the interval $(p, 2p)$, so I can make the sequence $(p, 2n^2, 2p)$ for some $n$. Clearly $f(p) geq 2p$, so this works.
$endgroup$
– Mees de Vries
Jan 30 at 13:29
$begingroup$
I mean for primes greater than 3
$endgroup$
– No one
Jan 30 at 13:39
$begingroup$
@MeesdeVries Thanks.
$endgroup$
– lulu
Jan 30 at 16:22
add a comment |
$begingroup$
Welcome to MSE. Your questions lacks details and context. Why are you interested in this question and what have you tried so far? You can find some remarks about how to ask a good question here math.stackexchange.com/help/how-to-ask
$endgroup$
– James
Jan 30 at 12:58
$begingroup$
Why is $f(p)=2p$? With $p=3$, that would mean that there was a good sequence that ended in $6$, no? But the only options are ${3,6}$, ${3,5,6}$ (including the square $4$ can't change anything, right?) and neither of those work.
$endgroup$
– lulu
Jan 30 at 13:22
1
$begingroup$
@lulu, a bit of experimentation suggests that perhaps $f(p) = 2p$ for $p > 3$ a prime. So $2, 3$ are the exceptions. Edit: specifically, for $p > 3$ a prime, I always find twice a square in the interval $(p, 2p)$, so I can make the sequence $(p, 2n^2, 2p)$ for some $n$. Clearly $f(p) geq 2p$, so this works.
$endgroup$
– Mees de Vries
Jan 30 at 13:29
$begingroup$
I mean for primes greater than 3
$endgroup$
– No one
Jan 30 at 13:39
$begingroup$
@MeesdeVries Thanks.
$endgroup$
– lulu
Jan 30 at 16:22
$begingroup$
Welcome to MSE. Your questions lacks details and context. Why are you interested in this question and what have you tried so far? You can find some remarks about how to ask a good question here math.stackexchange.com/help/how-to-ask
$endgroup$
– James
Jan 30 at 12:58
$begingroup$
Welcome to MSE. Your questions lacks details and context. Why are you interested in this question and what have you tried so far? You can find some remarks about how to ask a good question here math.stackexchange.com/help/how-to-ask
$endgroup$
– James
Jan 30 at 12:58
$begingroup$
Why is $f(p)=2p$? With $p=3$, that would mean that there was a good sequence that ended in $6$, no? But the only options are ${3,6}$, ${3,5,6}$ (including the square $4$ can't change anything, right?) and neither of those work.
$endgroup$
– lulu
Jan 30 at 13:22
$begingroup$
Why is $f(p)=2p$? With $p=3$, that would mean that there was a good sequence that ended in $6$, no? But the only options are ${3,6}$, ${3,5,6}$ (including the square $4$ can't change anything, right?) and neither of those work.
$endgroup$
– lulu
Jan 30 at 13:22
1
1
$begingroup$
@lulu, a bit of experimentation suggests that perhaps $f(p) = 2p$ for $p > 3$ a prime. So $2, 3$ are the exceptions. Edit: specifically, for $p > 3$ a prime, I always find twice a square in the interval $(p, 2p)$, so I can make the sequence $(p, 2n^2, 2p)$ for some $n$. Clearly $f(p) geq 2p$, so this works.
$endgroup$
– Mees de Vries
Jan 30 at 13:29
$begingroup$
@lulu, a bit of experimentation suggests that perhaps $f(p) = 2p$ for $p > 3$ a prime. So $2, 3$ are the exceptions. Edit: specifically, for $p > 3$ a prime, I always find twice a square in the interval $(p, 2p)$, so I can make the sequence $(p, 2n^2, 2p)$ for some $n$. Clearly $f(p) geq 2p$, so this works.
$endgroup$
– Mees de Vries
Jan 30 at 13:29
$begingroup$
I mean for primes greater than 3
$endgroup$
– No one
Jan 30 at 13:39
$begingroup$
I mean for primes greater than 3
$endgroup$
– No one
Jan 30 at 13:39
$begingroup$
@MeesdeVries Thanks.
$endgroup$
– lulu
Jan 30 at 16:22
$begingroup$
@MeesdeVries Thanks.
$endgroup$
– lulu
Jan 30 at 16:22
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let us first show that $f$ is injective.
Suppose to the contrary that $f$ is not. To be precise, suppose that $f(m_1) = f(m_2) = n$ and $m_1 < m_2$. By the hypothesis there are sequences ${m_1^0 = m_1, m_1^1 cdots, m_1^{l_1} = n}$ and ${m_2^0 = m_1, m_2^1 cdots, m_2^{l_2} = n}$ such that
$$
begin{aligned}
prod_{i=0}^{l_1} m_1^i &= M_1^2;\
prod_{i=0}^{l_2} m_2^i &= M_2^2,
end{aligned}
$$
for some $M_1, M_2 in mathbb N$, and no other such sequence starting with $m_1$
or $m_2$ terminates with smaller $n$.
Construct a new sequence by joining the two sequence together, arrange them in increasing order, and kill (both instances of) all duplicated terms. For instance, if the original sequences are ${2, 8}$ and ${3, 6, 8}$, then the new sequence will be ${2, 3, 6, not 8, not 8} = {2,3,6}$.
It is easy to see that the new sequence starts with $m_1$, terminates with something strictly less than $n$, and its product is a square, hence we arrive at a contradiction.
Now we show that the range of $f$ is exactly the composite numbers. Here I want to point out that since $f(1) = 1$, you need to consider $1$ as composite.
Let $n > 1$ be a composite number. For brevity suppose $n$ is not a square. We need to find a number $m$ such that $f(m) = n$. Since $n$ is composite, we have $n = d_1 d_2$ for some $2 leq d_1 < d_2$. So we have a sequence ${d_1, d_2, n}$ such that $d_1d_2n = n^2$. If $f(d_1) = n$, then we are done. If $f(d_1) = n' < n$, then we have a sequence ${m_0 = d_1, m_1 cdots, m_l = n'}$ such that
$$
prod_{i=0}^l m_i = M^2
$$
for some integer $M$.
Do the exclusive or (as in the first part) on the two sequences, and we will get a new sequence. The new sequence starts with something strictly larger than $d_1$, terminates with $n$, and the product of the sequence is a square. Repeat this process, and we will end up with some number $m$ such that $f(m) = n$.
Finally, as Mees de Vries suggested in the comment, we need to show that the primes are not in the range. This is true, since for any sequence ${m_0, cdots, m_l = p}$ which ends at a prime, we know that $p$ divides the product $prod_{i=0}^l m_i$, but $p^2$ does not, so the product cannot be a square.
answered Feb 4 at 23:35
Hw ChuHw Chu
3,337519
$endgroup$
1
$begingroup$
This answer is missing one (maybe too trivial to mention) detail: no prime $p$ is in the image of $f$, because the associated "$M^2$" could never have $p^2 mid M^2$, even though $p mid M^2$.
$endgroup$
– Mees de Vries
Feb 5 at 9:29
$begingroup$
You are right. As we need to show that the range is "exactly", but not only "containing" the composite numbers, your argument is essential. I will edit the post.
$endgroup$
– Hw Chu
Feb 5 at 13:47
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%2f3093492%2fnumber-theory-tricky%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
$begingroup$
Let us first show that $f$ is injective.
Suppose to the contrary that $f$ is not. To be precise, suppose that $f(m_1) = f(m_2) = n$ and $m_1 < m_2$. By the hypothesis there are sequences ${m_1^0 = m_1, m_1^1 cdots, m_1^{l_1} = n}$ and ${m_2^0 = m_1, m_2^1 cdots, m_2^{l_2} = n}$ such that
$$
begin{aligned}
prod_{i=0}^{l_1} m_1^i &= M_1^2;\
prod_{i=0}^{l_2} m_2^i &= M_2^2,
end{aligned}
$$
for some $M_1, M_2 in mathbb N$, and no other such sequence starting with $m_1$
or $m_2$ terminates with smaller $n$.
Construct a new sequence by joining the two sequence together, arrange them in increasing order, and kill (both instances of) all duplicated terms. For instance, if the original sequences are ${2, 8}$ and ${3, 6, 8}$, then the new sequence will be ${2, 3, 6, not 8, not 8} = {2,3,6}$.
It is easy to see that the new sequence starts with $m_1$, terminates with something strictly less than $n$, and its product is a square, hence we arrive at a contradiction.
Now we show that the range of $f$ is exactly the composite numbers. Here I want to point out that since $f(1) = 1$, you need to consider $1$ as composite.
Let $n > 1$ be a composite number. For brevity suppose $n$ is not a square. We need to find a number $m$ such that $f(m) = n$. Since $n$ is composite, we have $n = d_1 d_2$ for some $2 leq d_1 < d_2$. So we have a sequence ${d_1, d_2, n}$ such that $d_1d_2n = n^2$. If $f(d_1) = n$, then we are done. If $f(d_1) = n' < n$, then we have a sequence ${m_0 = d_1, m_1 cdots, m_l = n'}$ such that
$$
prod_{i=0}^l m_i = M^2
$$
for some integer $M$.
Do the exclusive or (as in the first part) on the two sequences, and we will get a new sequence. The new sequence starts with something strictly larger than $d_1$, terminates with $n$, and the product of the sequence is a square. Repeat this process, and we will end up with some number $m$ such that $f(m) = n$.
Finally, as Mees de Vries suggested in the comment, we need to show that the primes are not in the range. This is true, since for any sequence ${m_0, cdots, m_l = p}$ which ends at a prime, we know that $p$ divides the product $prod_{i=0}^l m_i$, but $p^2$ does not, so the product cannot be a square.
answered Feb 4 at 23:35
Hw ChuHw Chu
3,337519
$endgroup$
1
$begingroup$
This answer is missing one (maybe too trivial to mention) detail: no prime $p$ is in the image of $f$, because the associated "$M^2$" could never have $p^2 mid M^2$, even though $p mid M^2$.
$endgroup$
– Mees de Vries
Feb 5 at 9:29
$begingroup$
You are right. As we need to show that the range is "exactly", but not only "containing" the composite numbers, your argument is essential. I will edit the post.
$endgroup$
– Hw Chu
Feb 5 at 13:47
add a comment |
$begingroup$
Let us first show that $f$ is injective.
Suppose to the contrary that $f$ is not. To be precise, suppose that $f(m_1) = f(m_2) = n$ and $m_1 < m_2$. By the hypothesis there are sequences ${m_1^0 = m_1, m_1^1 cdots, m_1^{l_1} = n}$ and ${m_2^0 = m_1, m_2^1 cdots, m_2^{l_2} = n}$ such that
$$
begin{aligned}
prod_{i=0}^{l_1} m_1^i &= M_1^2;\
prod_{i=0}^{l_2} m_2^i &= M_2^2,
end{aligned}
$$
for some $M_1, M_2 in mathbb N$, and no other such sequence starting with $m_1$
or $m_2$ terminates with smaller $n$.
Construct a new sequence by joining the two sequence together, arrange them in increasing order, and kill (both instances of) all duplicated terms. For instance, if the original sequences are ${2, 8}$ and ${3, 6, 8}$, then the new sequence will be ${2, 3, 6, not 8, not 8} = {2,3,6}$.
It is easy to see that the new sequence starts with $m_1$, terminates with something strictly less than $n$, and its product is a square, hence we arrive at a contradiction.
Now we show that the range of $f$ is exactly the composite numbers. Here I want to point out that since $f(1) = 1$, you need to consider $1$ as composite.
Let $n > 1$ be a composite number. For brevity suppose $n$ is not a square. We need to find a number $m$ such that $f(m) = n$. Since $n$ is composite, we have $n = d_1 d_2$ for some $2 leq d_1 < d_2$. So we have a sequence ${d_1, d_2, n}$ such that $d_1d_2n = n^2$. If $f(d_1) = n$, then we are done. If $f(d_1) = n' < n$, then we have a sequence ${m_0 = d_1, m_1 cdots, m_l = n'}$ such that
$$
prod_{i=0}^l m_i = M^2
$$
for some integer $M$.
Do the exclusive or (as in the first part) on the two sequences, and we will get a new sequence. The new sequence starts with something strictly larger than $d_1$, terminates with $n$, and the product of the sequence is a square. Repeat this process, and we will end up with some number $m$ such that $f(m) = n$.
Finally, as Mees de Vries suggested in the comment, we need to show that the primes are not in the range. This is true, since for any sequence ${m_0, cdots, m_l = p}$ which ends at a prime, we know that $p$ divides the product $prod_{i=0}^l m_i$, but $p^2$ does not, so the product cannot be a square.
answered Feb 4 at 23:35
Hw ChuHw Chu
3,337519
$endgroup$
1
$begingroup$
This answer is missing one (maybe too trivial to mention) detail: no prime $p$ is in the image of $f$, because the associated "$M^2$" could never have $p^2 mid M^2$, even though $p mid M^2$.
$endgroup$
– Mees de Vries
Feb 5 at 9:29
$begingroup$
You are right. As we need to show that the range is "exactly", but not only "containing" the composite numbers, your argument is essential. I will edit the post.
$endgroup$
– Hw Chu
Feb 5 at 13:47
add a comment |
$begingroup$
Let us first show that $f$ is injective.
Suppose to the contrary that $f$ is not. To be precise, suppose that $f(m_1) = f(m_2) = n$ and $m_1 < m_2$. By the hypothesis there are sequences ${m_1^0 = m_1, m_1^1 cdots, m_1^{l_1} = n}$ and ${m_2^0 = m_1, m_2^1 cdots, m_2^{l_2} = n}$ such that
$$
begin{aligned}
prod_{i=0}^{l_1} m_1^i &= M_1^2;\
prod_{i=0}^{l_2} m_2^i &= M_2^2,
end{aligned}
$$
for some $M_1, M_2 in mathbb N$, and no other such sequence starting with $m_1$
or $m_2$ terminates with smaller $n$.
Construct a new sequence by joining the two sequence together, arrange them in increasing order, and kill (both instances of) all duplicated terms. For instance, if the original sequences are ${2, 8}$ and ${3, 6, 8}$, then the new sequence will be ${2, 3, 6, not 8, not 8} = {2,3,6}$.
It is easy to see that the new sequence starts with $m_1$, terminates with something strictly less than $n$, and its product is a square, hence we arrive at a contradiction.
Now we show that the range of $f$ is exactly the composite numbers. Here I want to point out that since $f(1) = 1$, you need to consider $1$ as composite.
Let $n > 1$ be a composite number. For brevity suppose $n$ is not a square. We need to find a number $m$ such that $f(m) = n$. Since $n$ is composite, we have $n = d_1 d_2$ for some $2 leq d_1 < d_2$. So we have a sequence ${d_1, d_2, n}$ such that $d_1d_2n = n^2$. If $f(d_1) = n$, then we are done. If $f(d_1) = n' < n$, then we have a sequence ${m_0 = d_1, m_1 cdots, m_l = n'}$ such that
$$
prod_{i=0}^l m_i = M^2
$$
for some integer $M$.
Do the exclusive or (as in the first part) on the two sequences, and we will get a new sequence. The new sequence starts with something strictly larger than $d_1$, terminates with $n$, and the product of the sequence is a square. Repeat this process, and we will end up with some number $m$ such that $f(m) = n$.
Finally, as Mees de Vries suggested in the comment, we need to show that the primes are not in the range. This is true, since for any sequence ${m_0, cdots, m_l = p}$ which ends at a prime, we know that $p$ divides the product $prod_{i=0}^l m_i$, but $p^2$ does not, so the product cannot be a square.
answered Feb 4 at 23:35
Hw ChuHw Chu
3,337519
$endgroup$
Let us first show that $f$ is injective.
Suppose to the contrary that $f$ is not. To be precise, suppose that $f(m_1) = f(m_2) = n$ and $m_1 < m_2$. By the hypothesis there are sequences ${m_1^0 = m_1, m_1^1 cdots, m_1^{l_1} = n}$ and ${m_2^0 = m_1, m_2^1 cdots, m_2^{l_2} = n}$ such that
$$
begin{aligned}
prod_{i=0}^{l_1} m_1^i &= M_1^2;\
prod_{i=0}^{l_2} m_2^i &= M_2^2,
end{aligned}
$$
for some $M_1, M_2 in mathbb N$, and no other such sequence starting with $m_1$
or $m_2$ terminates with smaller $n$.
Construct a new sequence by joining the two sequence together, arrange them in increasing order, and kill (both instances of) all duplicated terms. For instance, if the original sequences are ${2, 8}$ and ${3, 6, 8}$, then the new sequence will be ${2, 3, 6, not 8, not 8} = {2,3,6}$.
It is easy to see that the new sequence starts with $m_1$, terminates with something strictly less than $n$, and its product is a square, hence we arrive at a contradiction.
Now we show that the range of $f$ is exactly the composite numbers. Here I want to point out that since $f(1) = 1$, you need to consider $1$ as composite.
Let $n > 1$ be a composite number. For brevity suppose $n$ is not a square. We need to find a number $m$ such that $f(m) = n$. Since $n$ is composite, we have $n = d_1 d_2$ for some $2 leq d_1 < d_2$. So we have a sequence ${d_1, d_2, n}$ such that $d_1d_2n = n^2$. If $f(d_1) = n$, then we are done. If $f(d_1) = n' < n$, then we have a sequence ${m_0 = d_1, m_1 cdots, m_l = n'}$ such that
$$
prod_{i=0}^l m_i = M^2
$$
for some integer $M$.
Do the exclusive or (as in the first part) on the two sequences, and we will get a new sequence. The new sequence starts with something strictly larger than $d_1$, terminates with $n$, and the product of the sequence is a square. Repeat this process, and we will end up with some number $m$ such that $f(m) = n$.
Finally, as Mees de Vries suggested in the comment, we need to show that the primes are not in the range. This is true, since for any sequence ${m_0, cdots, m_l = p}$ which ends at a prime, we know that $p$ divides the product $prod_{i=0}^l m_i$, but $p^2$ does not, so the product cannot be a square.
answered Feb 4 at 23:35
Hw ChuHw Chu
3,337519
edited Feb 5 at 14:10
answered Feb 4 at 23:35
Hw ChuHw Chu
3,337519
answered Feb 4 at 23:35
Hw ChuHw Chu
3,337519
answered Feb 4 at 23:35
Hw ChuHw Chu
3,337519
3,337519
1
$begingroup$
This answer is missing one (maybe too trivial to mention) detail: no prime $p$ is in the image of $f$, because the associated "$M^2$" could never have $p^2 mid M^2$, even though $p mid M^2$.
$endgroup$
– Mees de Vries
Feb 5 at 9:29
$begingroup$
You are right. As we need to show that the range is "exactly", but not only "containing" the composite numbers, your argument is essential. I will edit the post.
$endgroup$
– Hw Chu
Feb 5 at 13:47
add a comment |
1
$begingroup$
This answer is missing one (maybe too trivial to mention) detail: no prime $p$ is in the image of $f$, because the associated "$M^2$" could never have $p^2 mid M^2$, even though $p mid M^2$.
$endgroup$
– Mees de Vries
Feb 5 at 9:29
$begingroup$
You are right. As we need to show that the range is "exactly", but not only "containing" the composite numbers, your argument is essential. I will edit the post.
$endgroup$
– Hw Chu
Feb 5 at 13:47
1
1
$begingroup$
This answer is missing one (maybe too trivial to mention) detail: no prime $p$ is in the image of $f$, because the associated "$M^2$" could never have $p^2 mid M^2$, even though $p mid M^2$.
$endgroup$
– Mees de Vries
Feb 5 at 9:29
$begingroup$
This answer is missing one (maybe too trivial to mention) detail: no prime $p$ is in the image of $f$, because the associated "$M^2$" could never have $p^2 mid M^2$, even though $p mid M^2$.
$endgroup$
– Mees de Vries
Feb 5 at 9:29
$begingroup$
You are right. As we need to show that the range is "exactly", but not only "containing" the composite numbers, your argument is essential. I will edit the post.
$endgroup$
– Hw Chu
Feb 5 at 13:47
$begingroup$
You are right. As we need to show that the range is "exactly", but not only "containing" the composite numbers, your argument is essential. I will edit the post.
$endgroup$
– Hw Chu
Feb 5 at 13:47
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.
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%2f3093492%2fnumber-theory-tricky%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
$begingroup$
Welcome to MSE. Your questions lacks details and context. Why are you interested in this question and what have you tried so far? You can find some remarks about how to ask a good question here math.stackexchange.com/help/how-to-ask
$endgroup$
– James
Jan 30 at 12:58
$begingroup$
Why is $f(p)=2p$? With $p=3$, that would mean that there was a good sequence that ended in $6$, no? But the only options are ${3,6}$, ${3,5,6}$ (including the square $4$ can't change anything, right?) and neither of those work.
$endgroup$
– lulu
Jan 30 at 13:22
1
$begingroup$
@lulu, a bit of experimentation suggests that perhaps $f(p) = 2p$ for $p > 3$ a prime. So $2, 3$ are the exceptions. Edit: specifically, for $p > 3$ a prime, I always find twice a square in the interval $(p, 2p)$, so I can make the sequence $(p, 2n^2, 2p)$ for some $n$. Clearly $f(p) geq 2p$, so this works.
$endgroup$
– Mees de Vries
Jan 30 at 13:29
$begingroup$
I mean for primes greater than 3
$endgroup$
– No one
Jan 30 at 13:39
$begingroup$
@MeesdeVries Thanks.
$endgroup$
– lulu
Jan 30 at 16:22