Factorisations which don't use $2$ as a factor.
", "name": "good_target_factorisations"}, "smallest_answer": {"templateType": "anything", "group": "New thing", "definition": "if(len(answer)=1,0,min(answer))", "description": "", "name": "smallest_answer"}, "scenarios": {"templateType": "anything", "group": "New thing", "definition": "[[12, [11, 6]], [13, [9]], [15, [8]], [18, [17, 10]], [28, [12]], [31, [16, 25]], [39, [18]], [91, [36]], [93, [50]], [124, [48, 75]], [217, [100]], [403, [144, 225]]]", "description": "Scenarios are picked so that:
\n5 of 12 scenarios have two answers. In 2 of the scenarios, the target is one more than a prime.
\nEach scenario is a structure of the form [target number, [answers]], where $\\sigma(answer) = target$.
Data for the given number
\n[0] is the value of phi
\n", "name": "d"}, "m": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d[j][0]", "description": "", "name": "m"}, "j": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(0..11 except 5)", "description": "", "name": "j"}, "d93": {"templateType": "anything", "group": "Divisor data", "definition": "[93,[3,31,0],[0,0],[[2,1],[5,2]]]", "description": "", "name": "d93"}, "biggest_prime": {"templateType": "anything", "group": "New thing", "definition": "max(primes)", "description": "", "name": "biggest_prime"}, "d217": {"templateType": "anything", "group": "Divisor data", "definition": "[217,[7,31,0],[0,0],[[2,2],[5,2]]]", "description": "", "name": "d217"}, "pri": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(d[j][1][2]=1,\n 'Note that since $\\\\var{m}-1$ is prime, then $n=\\\\var{m-1}$ is a choice for $n$',\n 'In this case, $\\\\var{m}-1$ is not prime, so $\\\\var{m-1}$ is not a solution. '\n)", "description": "", "name": "pri"}, "scenario": {"templateType": "anything", "group": "New thing", "definition": "random(scenarios)", "description": "", "name": "scenario"}, "d24": {"templateType": "anything", "group": "Divisor data", "definition": "[24,[4,6,1],[3,8],[[3,1],[5,1]]]", "description": "", "name": "d24"}, "second_decomposition": {"templateType": "anything", "group": "New thing", "definition": "if(len(good_target_factorisations)>1,\n if(len(good_target_factorisations[1])>1,true,false),\n false\n)", "description": "", "name": "second_decomposition"}, "d78": {"templateType": "anything", "group": "Divisor data", "definition": "[78,[6,13,0],[3,26],[[5,1],[3,2]]]", "description": "", "name": "d78"}, "d42": {"templateType": "anything", "group": "Divisor data", "definition": "[42,[6,7,1],[3,14],[[5,1],[2,2]]]", "description": "", "name": "d42"}, "d403": {"templateType": "anything", "group": "Divisor data", "definition": "[403,[13,31,0],[0,0],[[3,2],[5,2]]]", "description": "", "name": "d403"}, "af1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d[j][2][0]", "description": "", "name": "af1"}, "af2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d[j][2][1]", "description": "", "name": "af2"}, "inverse_sigma_primes": {"templateType": "anything", "group": "New thing", "definition": "inverse_sigma_prime(good_target_factorisations)", "description": "", "name": "inverse_sigma_primes"}}, "ungrouped_variables": ["af1", "af2", "altf", "ans1", "ans2", "d", "f1", "f2", "inv", "j", "m", "n1", "n2", "pri", "v"], "name": "Find n such that $\\sigma(n)$ is the given number", "functions": {"good_factorisations": {"type": "list", "language": "javascript", "definition": "return fs.filter(function(f){ return !f.contains(2)})", "parameters": [["fs", "list"]]}, "factorisations": {"type": "list", "language": "javascript", "definition": "function fns(factors) {\n if(factors.length==0) {\n return [[]];\n }\n var p = factors[0][0];\n var k = factors[0][1];\n if(factors.length>1) {\n var others = Numbas.util.product(factors.slice(1).map(function(f) {\n var out = [];\n var p = f[0];\n var k = f[1];\n for(var i=0;i<=k;i++) {\n out.push([p,i,k-i]);\n }\n return out;\n }));\n } else {\n var others = [[]];\n }\n \n var out = [];\n for(var i=1;i<=k;i++) {\n var t = Math.pow(p,i);\n others.map(function(other) {\n var t2 = t;\n var rest = [];\n other.map(function(f) {\n t2 *= Math.pow(f[0],f[1]);\n if(f[2]>0) {\n rest.push([f[0],f[2]]);\n }\n })\n if(iIf there are two values of $n$ enter in decreasing order.
\nIf there is only one value for $n$ enter that value in the first answer field and enter 0 in the second field.
\nLargest value for $n = \\;\\;$[[0]]
\nSmallest value for $n=\\;\\;$[[1]] (enter 0 if there is no second value for $n$)
", "showCorrectAnswer": true, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "steps": [{"showCorrectAnswer": true, "customName": "", "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "useCustomName": false, "prompt": "If $n = p_1^{\\beta_1}p_2^{\\beta_2}\\cdots p_s^{\\beta_s}$ into powers of distinct primes, then we have the sum over all divisors is given by :
\n\\[\\begin{eqnarray*} \\sigma(n)&=& \\sigma(p_1^{\\beta_1})\\times \\sigma(p_1^{\\beta_1}) \\times\\cdots \\times\\sigma(p_s^{\\beta_s})\\\\ &=& \\frac{(p_1^{\\beta_1+1}-1)}{p_1-1}\\times \\frac{(p_2^{\\beta_2+1}-1)}{p_2-1} \\times \\cdots \\times \\frac{(p_m^{\\beta_m+1}-1)}{p_m-1} \\end{eqnarray*} \\]
\nSo for this example we have to examine how $\\var{m}$ can be split into factors corresponding to such a prime decomposition.
\nWe build up a table of values of $\\sigma(q^\\beta)$ for various values of primes $q$ and powers $\\beta$.
\nWe leave out those values of $\\sigma(q^\\beta)$ which are too big for the examples you are given, for example $\\beta \\lt 4$ and for primes $q \\gt 5$ we need not consider any powers of 2 or greater.
\nOther labour saving comments are that if $\\sigma(n)=m$ and $m-1$ is a prime number then we have $\\sigma(m-1)=1+(m-1)=m$ so you have a solution immediately!
\nAlso note that in the following table, $2$ is never a value of $\\sigma(q^{\\beta})$ so any factorization of $m$ which involves $2$ can be ignored.
\n| $q$ | $q^{\\beta}$ | $\\sigma(q^{\\beta})$ | Value |
|---|---|---|---|
| $q=2$ | \n$2^1$ | \n$1+2$ | \n$3$ | \n
| \n | $2^2$ | \n$1+2+4$ | \n$7$ | \n
| \n | $2^3$ | \n$1+2+4+8$ | \n$15$ | \n
| \n | Too big! | \n\n | \n |
| $q=3$ | \n$3^1$ | \n$1+3$ | \n$4$ | \n
| \n | $3^2$ | \n$1+3+9$ | \n$13$ | \n
| \n | Too big! | \n\n | \n |
| $q=5$ | \n$5^1$ | \n$1+5$ | \n$6$ | \n
| \n | $5^2$ | \n$1+5+25$ | \n$31$ | \n
| \n | Too big! | \n\n | \n |
We demonstrate this using the example $\\sigma(n) = 60$. Note that since $60-1=59$ is prime we already have a solution, $n=59$.
\n$60$ can be factorized in several different ways. Most of the factorizations do not correspond to values of $\\sigma(q^\\beta)$ in the table.
\n\\[\\begin{eqnarray*} 60 &=& 1\\times60,\\mbox{ we have a solution corresponding to this, }n=59 \\leftarrow\\\\ 60&=& 2 \\times 30\\mbox{, no solution as 2 is a factor}\\\\ 60&=& 3 \\times 20\\mbox{, no solution as 20 does not appear in the above table}\\\\ 60&=&4 \\times 15.\\mbox{ both 4 and 15 appear in the table, for different primes } 4=\\sigma(3^1),\\;15=\\sigma(2^3) \\leftarrow\\\\ 60&=& 5\\times 12\\mbox{, no solution as neither 5 nor 12 appear in the above table}\\\\ 60&=& 6 \\times 10\\mbox{, no solution as 10 does not appear in the above table}\\\\ 60&=& 2 \\times 3 \\times 10\\mbox{, no solution as 2 is a factor}\\\\ 60&=&2 \\times 5 \\times 6\\mbox{, no solution as 2 is a factor}\\\\ 60&=& 3\\times 4 \\times 5\\mbox{, no solution as 5 does not appear in the table} \\end{eqnarray*} \\]
So we see that we have a solution corresponding to:
\\[\\sigma(n)= 60 = 4 \\times 15 = \\sigma(3^1)\\times \\sigma(2^3)=\\sigma(3 \\times 8)=\\sigma(24)\\]
Hence $n=24$ is a solution as well as $n=59$.
\nYou can check this as $24$ has divisors, $1,\\;2,\\;3,\\;4,\\;6,\\;8,\\;12,\\;24$ and summing up these gives $60$.
", "unitTests": [], "showFeedbackIcon": true, "scripts": {}, "type": "information", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0}], "useCustomName": false, "customName": "", "unitTests": [], "sortAnswers": false, "scripts": {}, "gaps": [{"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "{ans1}", "useCustomName": false, "customName": "", "unitTests": [], "showFractionHint": true, "correctAnswerStyle": "plain", "mustBeReducedPC": 0, "showFeedbackIcon": true, "scripts": {}, "type": "numberentry", "notationStyles": ["plain", "en", "si-en"], "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "maxValue": "{ans1}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "extendBaseMarkingAlgorithm": true, "minValue": "{ans2}", "useCustomName": false, "customName": "", "unitTests": [], "showFractionHint": true, "correctAnswerStyle": "plain", "mustBeReducedPC": 0, "showFeedbackIcon": true, "scripts": {}, "type": "numberentry", "notationStyles": ["plain", "en", "si-en"], "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "maxValue": "{ans2}"}], "type": "gapfill", "stepsPenalty": 0, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}], "statement": "", "tags": ["checked2015", "divisors", "Factorisation", "factorisation", "factorization", "Factors", "factors", "number theory", "Number theory", "prime decomposition", "sigma(n)", "sum of divisors"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": "question.primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]"}, "type": "question", "extensions": [], "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Given $m \\in \\mathbb{N}$, find values of $n\\in \\mathbb{N}$ such that $\\sigma(n)=m$.
\nThere are at most two such solutions in this question.
"}, "advice": "First, recall that for a prime $p$, $\\sigma(p^\\alpha) = \\frac{p^{\\alpha+1}-1}{p-1}$, and that $\\sigma$ is mulitplicative.
\nIf $n$ is decomposed into powers of distinct primes, $n = p_1^{\\beta_1}p_2^{\\beta_2}\\cdots p_s^{\\beta_s}$, then the sum of all divisors of $n$ is given by
\n\\begin{align}
\\sigma(n) &= \\sigma(p_1^{\\beta_1})\\times \\sigma(p_2^{\\beta_2})\\times\\cdots \\times\\sigma(p_s^{\\beta_s}) \\\\[0.5em]
&= \\frac{(p_1^{\\beta_1+1}-1)}{p_1-1}\\times \\frac{(p_2^{\\beta_2+1}-1)}{p_2-1} \\times \\cdots \\times \\frac{(p_m^{\\beta_m+1}-1)}{p_m-1}
\\end{align}
So for this example we have to examine how $\\var{target}$ can be split into factors corresponding to such a prime decomposition.
\n$\\var{target}$ can be factorised in the following ways:
\n$\\var{latex(show_factorisations(target,target_factorisations))}$
\nNote that there is no $n$ such that $\\sigma(n) = 2$, so we can ignore the factorisations which involve $2$.
\nAlso note that if $\\sigma(n)=m$, and $m-1$ is a prime number, then we have $\\sigma(m-1)=1+(m-1)=m$ so we have a solution immediately!
\nSince $\\var{target}-1 = \\var{target-1}$ is prime, $n = \\var{target-1}$ is a solution.
\nIn this case, $\\var{m}-1$ is not prime, so $\\var{m-1}$ is not a solution.
\nNow, we build up a table of values of $\\sigma(q^\\beta)$ for various primes $q$ and powers $\\beta$, stopping when $\\sigma(q^{\\beta})$ is bigger than any of the factors in our list.
\n| $q$ | $q^{\\beta}$ | $\\sigma(q^{\\beta})$ | Value |
|---|---|---|---|
| $q=2$ | \n$2^1$ | \n$1+2$ | \n$3$ | \n
| \n | $2^2$ | \n$1+2+4$ | \n$7$ | \n
| \n | $2^3$ | \n$1+2+4+8$ | \n$15$ | \n
| \n | Too big! | \n\n | \n |
| $q=3$ | \n$3^1$ | \n$1+3$ | \n$4$ | \n
| \n | $3^2$ | \n$1+3+9$ | \n$13$ | \n
| \n | Too big! | \n\n | \n |
| $q=5$ | \n$5^1$ | \n$1+5$ | \n$6$ | \n
| \n | $5^2$ | \n$1+5+25$ | \n$31$ | \n
| \n | Too big! | \n\n | \n |
We see from the table that
\n\\begin{align}
\\var{target} &= \\var{good_target_factorisations[0][0]} \\times \\var{good_target_factorisations[0][1]} \\\\
&= \\sigma(\\var{inverse_sigma_primes[0][0]}^\\var{inverse_sigma_primes[0][1]}) \\times \\sigma(\\var{inverse_sigma_primes[1][0]}^\\var{inverse_sigma_primes[1][1]}) \\\\
&= \\sigma(\\var{answer[0]})
\\end{align}
So $n=\\var{v}$ is a solution.
\n