Number theory problem on divisors!

So I saw the comments talking about $31$ and $47$ and eventually $61$ that cannot be found. And I started assembling a proof that $31$ or $47$ cannot be found.

But in the end I arrived at solutions for these numbers.

Extending the search, I end up with a somehow efficient algorithm for finding the solutions.

Here are solutions to all primes under $1000$.

(3, [2, 1])
(5, [2, 1, 1])
(7, [8, 5, 4])
(11, [8, 4, 2, 1])
(13, [8, 5, 4, 3])
(17, [4, 2, 2, 1, 1])
(19, [14, 7, 2, 1, 1])
(23, [40, 6, 3, 2, 2])
(29, [19, 17, 16, 11, 7])
(31, [54, 52, 47, 31, 27])
(37, [14, 9, 7, 2, 1, 1])
(41, [10, 8, 5, 4, 2, 1])
(43, [90031, 33, 3, 2, 2, 2])
(47, [82, 8, 6, 4, 3, 2])
(53, [13, 2, 2, 2, 1, 1, 1])
(59, [162, 5, 3, 2, 1, 1, 1])
(61, [76, 4, 2, 2, 2, 1, 1])
(67, [184, 10, 5, 2, 2, 1, 1])
(71, [2112, 8, 5, 3, 3, 1, 1])
(73, [2281, 12, 3, 3, 2, 2, 1])
(79, [59, 8, 5, 4, 4, 2, 1])
(83, [62, 2, 2, 1, 1, 1, 1, 1])
(89, [22, 2, 2, 2, 1, 1, 1, 1])
(97, [121, 2, 2, 2, 2, 1, 1, 1])
(101, [25, 4, 2, 2, 2, 1, 1, 1])
(103, [283, 5, 2, 2, 2, 1, 1, 1])
(107, [5002, 17, 16, 8, 7, 6, 5])
(109, [27, 8, 4, 2, 2, 1, 1, 1])
(113, [28, 14, 7, 2, 2, 1, 1, 1])
(127, [1111, 14, 7, 3, 2, 2, 1, 1])
(131, [2456, 4, 4, 4, 2, 2, 2, 1])
(137, [445, 8, 6, 4, 2, 2, 2, 1])
(139, [382, 6, 5, 4, 3, 2, 2, 1])
(149, [37, 2, 2, 2, 1, 1, 1, 1, 1])
(151, [51151, 526, 406, 2, 2, 2, 2, 2])
(157, [2551, 8, 6, 5, 4, 2, 2, 2])
(163, [122, 12, 2, 2, 1, 1, 1, 1, 1])
(167, [292, 3, 2, 2, 2, 1, 1, 1, 1])
(173, [43, 7, 2, 2, 2, 1, 1, 1, 1])
(179, [134, 67, 2, 2, 2, 1, 1, 1, 1])
(181, [45, 12, 3, 2, 2, 1, 1, 1, 1])
(191, [143, 12, 10, 2, 2, 1, 1, 1, 1])
(193, [1041862, 8984, 6, 5, 5, 5, 5, 4])
(197, [49, 8, 4, 2, 2, 2, 1, 1, 1])
(199, [348, 10, 4, 2, 2, 2, 1, 1, 1])
(211, [3323, 17, 4, 4, 2, 2, 1, 1, 1])
(223, [204212, 240, 5, 4, 3, 2, 1, 1, 1])
(227, [15606, 19, 17, 16, 16, 12, 12, 11])
(229, [3034, 26, 4, 4, 2, 2, 2, 1, 1])
(233, [78812, 24, 20, 19, 19, 16, 16, 16])
(239, [5437, 7, 6, 6, 3, 2, 2, 1, 1])
(241, [475312, 11, 6, 3, 3, 3, 2, 1, 1])
(251, [86281, 148, 121, 2, 2, 2, 2, 2, 1])
(257, [39062, 321, 2, 1, 1, 1, 1, 1, 1, 1])
(263, [177196, 58, 5, 3, 3, 3, 2, 2, 1])
(269, [67, 2, 2, 2, 2, 1, 1, 1, 1, 1])
(271, [2281, 474, 12, 3, 3, 3, 2, 2, 1])
(277, [2562, 92, 2, 2, 1, 1, 1, 1, 1, 1])
(281, [3442, 6, 6, 4, 3, 3, 2, 2, 2])
(283, [212, 4, 2, 2, 2, 1, 1, 1, 1, 1])
(293, [12379, 229, 6, 6, 4, 2, 2, 2, 2])
(307, [10361, 40, 13, 6, 4, 3, 2, 2, 2])
(311, [544, 8, 8, 6, 4, 4, 3, 2, 2])
(313, [391, 7, 2, 2, 2, 2, 1, 1, 1, 1])
(317, [79, 13, 2, 2, 2, 2, 1, 1, 1, 1])
(331, [1572, 9, 4, 2, 2, 2, 1, 1, 1, 1])
(337, [84, 12, 3, 3, 2, 2, 1, 1, 1, 1])
(347, [607, 6, 3, 2, 2, 2, 2, 1, 1, 1])
(349, [87, 8, 8, 6, 5, 5, 4, 4, 3])
(353, [1147, 6, 4, 2, 2, 2, 2, 1, 1, 1])
(359, [279571, 44, 3, 2, 2, 2, 2, 1, 1, 1])
(367, [25231, 22, 5, 2, 2, 2, 2, 1, 1, 1])
(373, [93, 8, 4, 4, 2, 2, 2, 1, 1, 1])
(379, [51070, 24, 5, 3, 2, 2, 2, 1, 1, 1])
(383, [38587, 30, 15, 8, 6, 5, 5, 5, 4])
(389, [97, 8, 5, 4, 3, 2, 2, 1, 1, 1])
(397, [1687, 8, 6, 5, 3, 2, 2, 1, 1, 1])
(401, [18947, 13, 8, 4, 3, 2, 2, 1, 1, 1])
(409, [10327, 656, 4, 3, 2, 2, 2, 2, 1, 1])
(419, [144031, 364, 170, 2, 2, 2, 2, 2, 1, 1])
(421, [526, 8, 5, 4, 3, 2, 2, 2, 1, 1])
(431, [1616, 76, 13, 4, 2, 2, 2, 2, 1, 1])
(433, [5737, 26, 6, 4, 3, 2, 2, 2, 1, 1])
(439, [2524, 11, 8, 4, 4, 2, 2, 2, 1, 1])
(443, [97792, 97571, 4, 4, 3, 3, 2, 2, 1, 1])
(449, [112, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1])
(457, [1028, 8, 8, 4, 4, 4, 2, 2, 1, 1])
(461, [1037, 62, 2, 2, 1, 1, 1, 1, 1, 1, 1])
(463, [6366, 722, 5, 4, 4, 4, 2, 2, 1, 1])
(467, [4531, 2218, 13, 4, 2, 2, 2, 2, 2, 1])
(479, [262372, 156, 40, 3, 3, 2, 2, 2, 2, 1])
(487, [33481, 25, 5, 4, 4, 3, 2, 2, 2, 1])
(491, [30319, 256, 7, 6, 4, 2, 2, 2, 2, 1])
(499, [198976, 101, 5, 4, 4, 4, 2, 2, 2, 1])
(503, [4904, 144, 6, 4, 4, 4, 2, 2, 2, 1])
(509, [127, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1])
(521, [130, 7, 2, 2, 2, 2, 1, 1, 1, 1, 1])
(523, [14011562, 862, 17, 3, 1, 1, 1, 1, 1, 1, 1])
(541, [25562, 102, 10, 2, 2, 1, 1, 1, 1, 1, 1])
(547, [597187, 992, 5, 3, 2, 1, 1, 1, 1, 1, 1])
(557, [2112, 1810, 3, 2, 2, 2, 1, 1, 1, 1, 1])
(563, [422, 12, 3, 3, 2, 2, 1, 1, 1, 1, 1])
(569, [142, 14, 7, 2, 2, 2, 1, 1, 1, 1, 1])
(571, [1570, 87, 5, 2, 2, 2, 1, 1, 1, 1, 1])
(577, [144, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1])
(587, [2788, 943, 9, 6, 4, 3, 3, 3, 2, 2])
(593, [148, 8, 8, 6, 5, 4, 4, 3, 2, 2])
(599, [1048, 58, 3, 2, 2, 2, 2, 1, 1, 1, 1])
(601, [30200, 33, 8, 6, 4, 4, 4, 3, 2, 2])
(607, [1062, 6, 4, 3, 2, 2, 2, 1, 1, 1, 1])
(613, [5057, 5, 4, 4, 2, 2, 2, 1, 1, 1, 1])
(617, [615920, 1822, 6, 5, 5, 5, 3, 3, 3, 2])
(619, [144072, 85, 3, 3, 2, 2, 2, 1, 1, 1, 1])
(631, [1735, 22, 5, 3, 2, 2, 2, 1, 1, 1, 1])
(641, [722, 160, 4, 4, 2, 2, 2, 1, 1, 1, 1])
(643, [3697, 11, 7, 4, 2, 2, 2, 1, 1, 1, 1])
(647, [728, 485, 364, 2, 2, 2, 2, 1, 1, 1, 1])
(653, [13876, 8, 7, 7, 2, 2, 2, 1, 1, 1, 1])
(659, [1812, 7, 6, 5, 3, 2, 2, 1, 1, 1, 1])
(661, [1487, 8, 5, 4, 4, 2, 2, 1, 1, 1, 1])
(673, [841, 8, 4, 4, 2, 2, 2, 2, 1, 1, 1])
(677, [107812, 17, 8, 6, 6, 6, 5, 4, 3, 3])
(683, [1878, 5, 4, 4, 3, 2, 2, 2, 1, 1, 1])
(691, [47506, 17, 5, 4, 2, 2, 2, 2, 1, 1, 1])
(701, [175, 8, 5, 4, 3, 2, 2, 2, 1, 1, 1])
(709, [13648, 84, 5, 3, 3, 2, 2, 2, 1, 1, 1])
(719, [1977, 367, 8, 8, 6, 5, 5, 5, 4, 4])
(727, [2726, 14, 10, 8, 8, 7, 5, 5, 4, 4])
(733, [4581, 12, 8, 4, 4, 2, 2, 2, 1, 1, 1])
(739, [10900, 3687, 6, 3, 3, 3, 2, 2, 1, 1, 1])
(743, [1300, 6, 4, 4, 3, 2, 2, 2, 2, 1, 1])
(751, [2065, 6, 5, 4, 3, 2, 2, 2, 2, 1, 1])
(757, [23656, 2065, 5, 4, 2, 2, 2, 2, 2, 1, 1])
(761, [2473, 121, 6, 4, 2, 2, 2, 2, 2, 1, 1])
(769, [192, 8, 8, 5, 4, 4, 2, 2, 1, 1, 1])
(773, [118462, 306, 6, 3, 3, 2, 2, 2, 2, 1, 1])
(787, [221737, 2281, 11, 3, 3, 2, 2, 2, 2, 1, 1])
(797, [4981, 10, 8, 5, 4, 2, 2, 2, 2, 1, 1])
(809, [65731, 16906, 4, 4, 2, 2, 2, 2, 2, 2, 1])
(811, [15206, 9392, 4, 4, 4, 3, 2, 2, 2, 1, 1])
(821, [10057, 37, 6, 6, 3, 3, 2, 2, 2, 1, 1])
(823, [12962, 76, 6, 4, 4, 3, 2, 2, 2, 1, 1])
(827, [2281, 620, 12, 4, 3, 3, 2, 2, 2, 1, 1])
(829, [207, 62, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1])
(839, [6502, 263, 6, 4, 4, 4, 2, 2, 2, 1, 1])
(853, [63335, 39062, 49, 2, 1, 1, 1, 1, 1, 1, 1, 1])
(857, [214, 8, 8, 5, 4, 4, 3, 2, 2, 1, 1])
(859, [2362, 5, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1])
(863, [74002, 17, 8, 6, 4, 3, 3, 2, 2, 1, 1])
(877, [90031, 1096, 33, 4, 3, 2, 2, 2, 2, 2, 1])
(881, [220, 12, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1])
(883, [662, 13, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1])
(887, [1552, 40, 6, 6, 3, 3, 2, 2, 2, 2, 1])
(907, [1587, 857, 12, 2, 2, 1, 1, 1, 1, 1, 1, 1])
(911, [13437, 32, 29, 2, 2, 1, 1, 1, 1, 1, 1, 1])
(919, [39287, 112, 47, 2, 2, 1, 1, 1, 1, 1, 1, 1])
(929, [18812, 32, 12, 3, 2, 1, 1, 1, 1, 1, 1, 1])
(937, [4539062, 1076, 62, 20, 1, 1, 1, 1, 1, 1, 1, 1])
(941, [2373437, 147, 47, 47, 1, 1, 1, 1, 1, 1, 1, 1])
(947, [1657, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1])
(953, [238, 13, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1])
(967, [2659, 49, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1])
(971, [728, 364, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1])
(977, [244, 122, 12, 2, 2, 2, 1, 1, 1, 1, 1, 1])
(983, [737, 162, 5, 3, 2, 2, 1, 1, 1, 1, 1, 1])
(991, [6689, 5312, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1])
(997, [6013156, 21326, 5, 5, 4, 3, 3, 2, 2, 2, 2])

Some explanation on the algorithm:

Since my original aim was to prove that some numbers cannot be expressed, I started with the observation that the number of factors is kind of limited, because every factor is somewhat $2 - \epsilon$.

I then rewrite the formula as $$\prod_{i = 1}^k(1 - \frac{1}{4b_i + 2}) = \frac{p}{2^k}.$$

Now the observation is that one of the factors must be at most $\frac{p^{\frac{1}{k}}}{2}$. So there is an upper bound to the smallest $b_i$.

I just go through all possibilities of this smallest $b_i$, and use a recursive call on the remaining $k - 1$ factors.

One key parameter is $k$, the number of factors. I use multithreading on different $k$, and kill all threads once one thread finds a solution.

Using three threads, I find solutions to all primes under $1000$ within a minute or so.

It is worth noting that using only two threads (i.e. only check the optimal number or (optimal number + 1) of factors) one can also find solutions to all primes under $1000$, just taking longer. I guess it would even work with only one thread, but the current algorithm will be too slow for that.

You may try my codes by pasting the following into this website and press "Evaluate".

RR = RealField(200)
giveup = False
def Find(x, k, lbd):
    if giveup: return None
    if k == 1:
        n = (1/(1 - x) - 2) / 4
        if n.denominator() == 1:
            return [n]
        else:
            return None
    bd = Integer(floor((1 / (1 - RR(x)^(RR(1) / k)) - 2) / 4))

    for n in range(bd, lbd - 1, -1):
        newx = x / (1 - 1 / (4 * n + 2))
        if newx >= 1: break
        res = Find(newx, k - 1, n)
        if res is None: continue
        res.append(n)
        return res
    return None

import threading, time
TLIMIT = 3
for p in range(3, 1000, 2):
    if is_prime(p):
        k = ceil(log(RR(p))/log(RR(2)))
        res = None
        giveup = False
        def ThreadFunc(x, k, lbd):
            global res
            myRes = Find(x, k, lbd)
            if myRes is not None: res = myRes
            return
        threads = []
        for j in range(TLIMIT):
            newThread = threading.Thread(target = ThreadFunc, args = (p/2**k, k, 1))
            threads.append(newThread)
            newThread.start()
            k += 1
        while True:
            allEnd = True
            for t in threads:
                if t.is_alive():
                    allEnd = False
                    break
            if allEnd: break
            if res is not None: giveup = True
            time.sleep(0.1)
        print(p, res)

All odd numbers and only them are representable in the form $d(n^2)/d(n)$. But the proof is tricky!

It is clear that no even number is representable as the numerator is always odd.

For $k$ odd we proceed by induction, clearly $1 = d(1^2)/d(1)$ so $1$ is representable. Now suppose that $k>1$ and that all odd integers up to $k-2$ are representable then if $2^a$ is the largest power of $2$ that divides $k+1$, write $$ k = 2^at-1 $$ with $t$ odd and $a \ge 1$, then $$ (2^a-1)k = 2^{a+1}(2^{a-1}t-\tfrac{t+1}2)+1 = 2^{a+1}b+1$$ whith $b = 2^{a-1}t-\tfrac{t+1}2$. Now we see that $2b+1 = (2^a-1)t$ and so: $$ \frac{2^{a+1}b+1}{2^ab+1}\cdot \frac{2^{a}b+1}{2^{a-1}b+1}\cdot \dots \cdot \frac{2^2b + 1}{2b+1} = \frac{(2^a-1)k}{(2^a-1)t} = \frac{k}{t}$$ As $t < k$ is odd, using the induction hypothesis we can find $m$ such that $$ t = \frac{d(m^2)}{d(m)} $$ But then chosing primes $p,q,\dots,s$ coprime with $m$ we find that

$$ n = p^{2^{a}b}q^{2^{a-1}b}\dots s^{2b} m $$ verifies $$ \frac{d(n^2)}{d(n)} = \frac{d(p^{2^{a+1}b}q^{2^{a}b}\dots s^{2^2 b})}{d(p^{2^{a}b}q^{2^{a-1}b}\dots s^{2 b})} \cdot \frac{d(m^2)}{d(m)} = \frac{k}t\cdot t = k$$ and the proof is complete!.


Note that if the prime decomposition of $n$ is $\prod\limits_{i\in I} p_i^{a_i}$, then we have the fraction $$\prod\limits_{i\in I}\frac{2a_i+1}{a_i+1}$$

Note that in particular, the numerator must always be odd, which implies that so must the denominator for the fraction to be integral. So, $a_i$ must be even for all $i$. This implies that $n$ must be a perfect square.

So, if we let $2b_i=a_i$ for every $a_i$, then we get $$\prod\limits_{i\in I}\frac{4b_i+1}{2b_i+1}$$

Next, I want to show that we can express any odd number as one of these fractions. Note clearly that if any odd number can be expressed as one of these fractions, then any power of it can as well (take the same prime decomposition, but repeat it $n$ times with different primes).

So, we simply need to show that this can be done for any odd prime. We can prove this via strong induction. Suppose prime $p$ is of the form $4n+1$ for some $n\in\mathbb N$. Then, we let $b_1=n$, and then we note that the denominator will be of the form $2b_i+1$, which we know that we can express as a result of the product. So, we are done.

The logic for primes of the form $4n+3$ is trickier. To finish later.

Tags:

Number Theory

Related

How do you divide an inequality by another inequality? Ring of integers and unit group for local fields Group with simple relations Arrange all numbers from 1 to n such that no 3 of them are in Arithmetic Progression Opposite of Coupon Collector / Birthday Problems? Demonstrate that there are no perfect squares ending with $8$ Determine all $P(x) \in \mathbb R[x]$ such that $P(x^2) + x\big(mP(x) + nP(-x)\big) = \big(P(x)\big)^2 + (m - n)x^2$, $\forall x \in \mathbb R$. $\int \frac{dx}{\sin x-\cos x}$ The set of entire function follow the condition ${|f'(z)| \leq |f(z)|}$ Does an unbounded open subset of $\mathbb{R}$ contain infinitely many multiples of some number? Proving a much stronger version of AM-GM for three variables The lore of the game Numenera mentions "an irrational number that may be a four-dimensional equivalent of $\pi$". What could this mean?

Recent Posts