Prime factorization formalism
up vote
0
down vote
favorite
I was hoping someone might know the name for this representation of the positive integers. The idea is similar to Peano's arithmetic but applied to multiplication. So we have $1$, multiplication and a function $p$. We map onto the normal integers by having p map to the nth prime. To illustrate the first few integers would be $1, p(1), p(p(1)), p(1)p(1), p(p(p(1)))$.
This representation has some unusual properties. Computing whether a number is prime is trivial, as is factorization and multiplication.
Addition however is rather tricky since you have to convert back to a normal representation, perform the addition then recursively factorized the result!
prime-numbers prime-factorization
edited Nov 23 at 11:34
amWhy
191k28224439
asked Sep 9 at 22:31
Mumrah
11
add a comment |
up vote
0
down vote
favorite
I was hoping someone might know the name for this representation of the positive integers. The idea is similar to Peano's arithmetic but applied to multiplication. So we have $1$, multiplication and a function $p$. We map onto the normal integers by having p map to the nth prime. To illustrate the first few integers would be $1, p(1), p(p(1)), p(1)p(1), p(p(p(1)))$.
This representation has some unusual properties. Computing whether a number is prime is trivial, as is factorization and multiplication.
Addition however is rather tricky since you have to convert back to a normal representation, perform the addition then recursively factorized the result!
prime-numbers prime-factorization
edited Nov 23 at 11:34
amWhy
191k28224439
asked Sep 9 at 22:31
Mumrah
11
Do you have a finite length recipe (i.e. without pre-specifying the value of every prime in a long list) for performing addition in this setting? Even an indirect description of the form '+ is the only binary operation with this this and this property' leaving all the hard work to the reader would be fine. If such a thing exists, that is. I am not so sure here...
– Vincent
Nov 23 at 12:52
I don't have any such mechanism no. You can show its related to a hard problem. Suppose we could efficiently (in polynomial time) compute addition and divide-and-remainder in this representation. It is trivial to convert a binary number into this form since 2^n is simply p(1)^n and we can therefore use addition to covert from binary into this form efficiently. But now we can use repeatedly perform divide and remainder by 2 on the factorized form to compute the binary representation of the prime components. This would allow us to extract the prime factors.
– Mumrah
Nov 27 at 16:00
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I was hoping someone might know the name for this representation of the positive integers. The idea is similar to Peano's arithmetic but applied to multiplication. So we have $1$, multiplication and a function $p$. We map onto the normal integers by having p map to the nth prime. To illustrate the first few integers would be $1, p(1), p(p(1)), p(1)p(1), p(p(p(1)))$.
This representation has some unusual properties. Computing whether a number is prime is trivial, as is factorization and multiplication.
Addition however is rather tricky since you have to convert back to a normal representation, perform the addition then recursively factorized the result!
prime-numbers prime-factorization
edited Nov 23 at 11:34
amWhy
191k28224439
asked Sep 9 at 22:31
Mumrah
11
I was hoping someone might know the name for this representation of the positive integers. The idea is similar to Peano's arithmetic but applied to multiplication. So we have $1$, multiplication and a function $p$. We map onto the normal integers by having p map to the nth prime. To illustrate the first few integers would be $1, p(1), p(p(1)), p(1)p(1), p(p(p(1)))$.
This representation has some unusual properties. Computing whether a number is prime is trivial, as is factorization and multiplication.
Addition however is rather tricky since you have to convert back to a normal representation, perform the addition then recursively factorized the result!
prime-numbers prime-factorization
prime-numbers prime-factorization
edited Nov 23 at 11:34
amWhy
191k28224439
asked Sep 9 at 22:31
Mumrah
11
edited Nov 23 at 11:34
amWhy
191k28224439
asked Sep 9 at 22:31
Mumrah
11
edited Nov 23 at 11:34
amWhy
191k28224439
edited Nov 23 at 11:34
amWhy
191k28224439
edited Nov 23 at 11:34
amWhy
191k28224439
191k28224439
asked Sep 9 at 22:31
Mumrah
11
asked Sep 9 at 22:31
Mumrah
11
asked Sep 9 at 22:31
Mumrah
11
11
Do you have a finite length recipe (i.e. without pre-specifying the value of every prime in a long list) for performing addition in this setting? Even an indirect description of the form '+ is the only binary operation with this this and this property' leaving all the hard work to the reader would be fine. If such a thing exists, that is. I am not so sure here...
– Vincent
Nov 23 at 12:52
I don't have any such mechanism no. You can show its related to a hard problem. Suppose we could efficiently (in polynomial time) compute addition and divide-and-remainder in this representation. It is trivial to convert a binary number into this form since 2^n is simply p(1)^n and we can therefore use addition to covert from binary into this form efficiently. But now we can use repeatedly perform divide and remainder by 2 on the factorized form to compute the binary representation of the prime components. This would allow us to extract the prime factors.
– Mumrah
Nov 27 at 16:00
add a comment |
Do you have a finite length recipe (i.e. without pre-specifying the value of every prime in a long list) for performing addition in this setting? Even an indirect description of the form '+ is the only binary operation with this this and this property' leaving all the hard work to the reader would be fine. If such a thing exists, that is. I am not so sure here...
– Vincent
Nov 23 at 12:52
I don't have any such mechanism no. You can show its related to a hard problem. Suppose we could efficiently (in polynomial time) compute addition and divide-and-remainder in this representation. It is trivial to convert a binary number into this form since 2^n is simply p(1)^n and we can therefore use addition to covert from binary into this form efficiently. But now we can use repeatedly perform divide and remainder by 2 on the factorized form to compute the binary representation of the prime components. This would allow us to extract the prime factors.
– Mumrah
Nov 27 at 16:00
Do you have a finite length recipe (i.e. without pre-specifying the value of every prime in a long list) for performing addition in this setting? Even an indirect description of the form '+ is the only binary operation with this this and this property' leaving all the hard work to the reader would be fine. If such a thing exists, that is. I am not so sure here...
– Vincent
Nov 23 at 12:52
Do you have a finite length recipe (i.e. without pre-specifying the value of every prime in a long list) for performing addition in this setting? Even an indirect description of the form '+ is the only binary operation with this this and this property' leaving all the hard work to the reader would be fine. If such a thing exists, that is. I am not so sure here...
– Vincent
Nov 23 at 12:52
I don't have any such mechanism no. You can show its related to a hard problem. Suppose we could efficiently (in polynomial time) compute addition and divide-and-remainder in this representation. It is trivial to convert a binary number into this form since 2^n is simply p(1)^n and we can therefore use addition to covert from binary into this form efficiently. But now we can use repeatedly perform divide and remainder by 2 on the factorized form to compute the binary representation of the prime components. This would allow us to extract the prime factors.
– Mumrah
Nov 27 at 16:00
I don't have any such mechanism no. You can show its related to a hard problem. Suppose we could efficiently (in polynomial time) compute addition and divide-and-remainder in this representation. It is trivial to convert a binary number into this form since 2^n is simply p(1)^n and we can therefore use addition to covert from binary into this form efficiently. But now we can use repeatedly perform divide and remainder by 2 on the factorized form to compute the binary representation of the prime components. This would allow us to extract the prime factors.
– Mumrah
Nov 27 at 16:00
add a comment |
active
oldest
votes
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%2f2911251%2fprime-factorization-formalism%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f2911251%2fprime-factorization-formalism%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
Do you have a finite length recipe (i.e. without pre-specifying the value of every prime in a long list) for performing addition in this setting? Even an indirect description of the form '+ is the only binary operation with this this and this property' leaving all the hard work to the reader would be fine. If such a thing exists, that is. I am not so sure here...
– Vincent
Nov 23 at 12:52
I don't have any such mechanism no. You can show its related to a hard problem. Suppose we could efficiently (in polynomial time) compute addition and divide-and-remainder in this representation. It is trivial to convert a binary number into this form since 2^n is simply p(1)^n and we can therefore use addition to covert from binary into this form efficiently. But now we can use repeatedly perform divide and remainder by 2 on the factorized form to compute the binary representation of the prime components. This would allow us to extract the prime factors.
– Mumrah
Nov 27 at 16:00