// Numbas version: exam_results_page_options {"name": "Find n such that $\\sigma(n)$ is the given number", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"variablesTest": {"condition": "len(good_target_factorisations[0])=1", "maxRuns": 100}, "variables": {"good_target_factorisations": {"templateType": "anything", "group": "New thing", "definition": "good_factorisations(target_factorisations)", "description": "

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:

\n
\n
• there are at most two answers
• \n
• when an answer isn't just $n-1$, no prime greater than 5 and no power greater than 3 is required.
• \n
• each target has at most two factorisations which don't have a separate factor of 2 (since there's no $n$ such that $\\sigma(n)=2$)
• \n
• one of the answers is not a prime
• \n
\n

5 of 12 scenarios have two answers. In 2 of the scenarios, the target is one more than a prime.

\n

Each scenario is a structure of the form [target number, [answers]], where $\\sigma(answer) = target$.

", "name": "scenarios"}, "v": {"templateType": "anything", "group": "Ungrouped variables", "definition": "((n1[0])^(n1[1]))*((n2[0])^(n2[1]))", "description": "", "name": "v"}, "f1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d[j][1][0]", "description": "", "name": "f1"}, "n1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d[j][3][0]", "description": "", "name": "n1"}, "answer": {"templateType": "anything", "group": "New thing", "definition": "scenario[1]", "description": "", "name": "answer"}, "d28": {"templateType": "anything", "group": "Divisor data", "definition": "[28,[4,7,0],[0,0],[[3,1],[2,2]]]", "description": "", "name": "d28"}, "d12": {"templateType": "anything", "group": "Divisor data", "definition": "[12,[3,4,1],[0,0],[[2,1],[3,1]]]", "description": "", "name": "d12"}, "d18": {"templateType": "anything", "group": "Divisor data", "definition": "[18,[3,6,1],[0,0],[[2,1],[5,1]]]", "description": "", "name": "d18"}, "n2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d[j][3][1]", "description": "", "name": "n2"}, "target": {"templateType": "anything", "group": "New thing", "definition": "scenario[0]", "description": "", "name": "target"}, "ans1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(d[j][1][2]=1,max(v,m-1),v)", "description": "", "name": "ans1"}, "target_one_more_than_a_prime": {"templateType": "anything", "group": "New thing", "definition": "(target-1) in primes", "description": "", "name": "target_one_more_than_a_prime"}, "biggest_answer": {"templateType": "anything", "group": "New thing", "definition": "max(answer)", "description": "", "name": "biggest_answer"}, "f2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d[j][1][1]", "description": "", "name": "f2"}, "d39": {"templateType": "anything", "group": "Divisor data", "definition": "[39,[3,13,0],[0,0],[[2,1],[3,2]]]", "description": "", "name": "d39"}, "inv": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(2|m, ', forgetting those with $2$ as a factor, ',' ')", "description": "", "name": "inv"}, "altf": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(d[j][2][0]=0, \n 'There are no other factorizations of $\\\\var{m}$ into powers of prime factors which can give values of $n$.',\n 'Another factorization of $\\\\var{m}$ is given by $\\\\var{m}= \\\\var{d[j][2][0]}\\\\times \\\\var{d[j][2][1]}$, but as $\\\\var{d[j][2][1]}$ does not appear on our table as a possible value of $\\\\sigma$, this does not give a value of $n$'\n)", "description": "", "name": "altf"}, "d91": {"templateType": "anything", "group": "Divisor data", "definition": "[91,[7,13,0],[0,0],[[2,2],[3,2]]]", "description": "", "name": "d91"}, "primes": {"templateType": "anything", "group": "New thing", "definition": "[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,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]", "description": "", "name": "primes"}, "target_factorisations": {"templateType": "anything", "group": "New thing", "definition": "factorisations(target)", "description": "", "name": "target_factorisations"}, "ans2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(d[j][1][2]=1,min(v,m-1),0)", "description": "", "name": "ans2"}, "d124": {"templateType": "anything", "group": "Divisor data", "definition": "[124,[4,31,0],[0,0],[[3,1],[5,2]]]", "description": "", "name": "d124"}, "d": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[d12,d18,d24,d28,d39,d42,d78,d91,d93,d124,d217,d403]", "description": "

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(i0});\n\nreturn fns(factors);", "parameters": [["n", "number"]]}, "show_factorisations": {"type": "number", "language": "javascript", "definition": "fs = fs.map(function(f){ return f.join(' \\\\times '); });\nreturn '\\\\begin{align}\\n'+n+' &= '+fs.join('\\\\\\\\ \\n &= ')+'\\n\\\\end{align}';", "parameters": [["n", "number"], ["fs", "list"]]}, "inverse_sigma_prime": {"type": "list", "language": "javascript", "definition": "console.clear();\n\nvar 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,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997];\nfunction inverse_sigma(n) {\n var out = [];\n for(var i=0;iFind values of $n$ such that $\\sigma(n)=\\var{m}$. There are at most 2.

\n

If there are two values of $n$ enter in decreasing order.

\n

If there is only one value for $n$ enter that value in the first answer field and enter 0 in the second field.

\n

Largest value for $n = \\;\\;$[[0]]

\n

Smallest 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*} \$

\n

So for this example we have to examine how $\\var{m}$ can be split into factors corresponding to such a prime decomposition.

\n

We build up a table of values of $\\sigma(q^\\beta)$ for various values of primes $q$ and powers $\\beta$.

\n

We 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.

\n

Other 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!

\n

Also 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\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
$q$$q^{\\beta}$$\\sigma(q^{\\beta})$Value
$q=2$$2^1$$1+2$$3 2^2$$1+2+4$$7 2^3$$1+2+4+8$$15 Too big! q=3$$3^1$$1+3$$4$
$3^2$$1+3+9$$13$
Too big!
q=5$$5^1$$1+5$$6 5^2$$1+5+2531 Too big! \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)\$ \n Hence n=24 is a solution as well as n=59. \n You 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. \n There 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. \n If 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} \n 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))} \n Note that there is no n such that \\sigma(n) = 2, so we can ignore the factorisations which involve 2. \n Also 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! \n Since \\var{target}-1 = \\var{target-1} is prime, n = \\var{target-1} is a solution. \n In this case, \\var{m}-1 is not prime, so \\var{m-1} is not a solution. \n Now, 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\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n qq^{\\beta}$$\\sigma(q^{\\beta})Value q=2$$2^1$$1+2$$3
$2^2$$1+2+4$$7$
$2^3$$1+2+4+8$$15$
Too big!
$q=3$$3^1$$1+3$$4 3^2$$1+3+9$$13 Too big! q=5$$5^1$$1+5$$6$
$5^2$$1+5+25$$31$
Too big!
\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]}) \\\\
So $n=\\var{v}$ is a solution.