|
|
| Line 4: |
Line 4: |
| | of n (including 1 and n itself). Determine all positive integers k such that | | of n (including 1 and n itself). Determine all positive integers k such that |
| | <math>d(n^2)/d(n) = k</math> for some n. | | <math>d(n^2)/d(n) = k</math> for some n. |
| − |
| |
| − | ===Solution===
| |
| − |
| |
| − | First we must determine general values for d(n):
| |
| − | Let <math>n=P1^(A1) * P2^(A2) * .. * Pc^(Ac)</math>, if d is an arbitrary divisor of n then d must have the same prime factors of n, each with an exponent <math>Bi</math> being: <math>0\leq Bi\leq Ai</math>.
| |
| − | Hence there are <math>Ai + 1</math> choices for each exponent of Pi in the number d => there are <math>(A1 + 1)(A2 + 1)..(Ac + 1)</math> such d
| |
| − |
| |
| − | => <math>d(n) = (A1 + 1)(A2+1)..(Ac+1)</math> where Ai are exponents of the prime numbers in the prime factorisation of n.
| |
| − |
| |
| − | => <math>d(n^2)/d(n) = {(2A1 + 1)(2A2 + 1)..(2Ac + 1)}/{A1+1)..(Ac+1)}
| |
| − |
| |
| − | So we want to find all integers k that can be represented by the product of fractions of the form </math>(2n+1)/(n+1)<math>
| |
| − | Obviously k is odd as the numerator is always odd.
| |
| − | It's possible for 1 (1/1) and 3 (5/3 * 9/5), which suggests that it may be possible for all odd integers, which we can show by induction.
| |
| − |
| |
| − | P(k): It's possible to represent k as the product of fractions </math>(2n+1)/(n+1)<math>
| |
| − | Base case: k = 1: (2(0) + 1) / (0 + 1)
| |
| − | Now assume that for </math>k\geq 3<math> it's possible for all odds < k.
| |
| − |
| |
| − | Since k is odd, </math>k+1 = 2^z * y$ where y is odd and y < k
| |
Revision as of 02:28, 2 April 2022
Problem
For any positive integer n, let d(n) denote the number of positive divisors
of n (including 1 and n itself). Determine all positive integers k such that
for some n.
for some n.
