Problem #498
✰ - click to bookmark
★ - in your bookmarks
Tags:
unlabeled
There are unsolved problems in Mathematics. For example the task on Collatz Conjecture inroduces one of them. Another infamous problems were the Fermat's (Last) Theorem and the Four-Color Problem - these, however, were solved few decades ago. Of course math has many more unsolved puzzles, but many are hard to understand without advanced math skills.
But don't despair! Here comes the whole bunch of unsolved puzzles known for thousand years and related to simple math operation - caclculating sum of divisors of a number.
Let's write down divisors of a number and sum them up. For example 30 is divisible by 1, 2, 3, 5, 6, 10, 15, 30 - they give 72 in total.
Let us call the function which converts a number N to sum of its divisors sod(N). However such a sum always includes the number itself and
thus is definitely larger than the number. It's not very interesting, so let's introduce two "reduced" versions.
sopd(N) = sod(N) - N - sum of "proper" divisors (i.e. not including the number itself);sontd(N) = sod(N) - N - 1 - sum of "non-trivial" divisors (excluding N and 1).There are "proper names" for such functions and other concepts covered in this text - but they are a bit confusing or use rare words, so we won't use them for now.
Now, both sopd and sontd functions may result in a number which is smaller or greater than the argument. Or, sometimes, even equal to it,
for example sopd(28) = 28. Greeks called such numbers "perfect".
Are there numbers for which sontd(N) = N?
Are there odd numbers (N mod 2 = 1) for which sopd(N) = N?
Is the set of perfect numbers finite or infinite?
No one knows yet (as of July 2026). You can become famous if you just find example for the first or second question :)
Are there such pairs of numbers, which are converted to each other when sopd or sontd function is applied? I.e. sopd(M) = N, sopd(N) = M or
sontd(M) = N, sontd(N) = M respectively.
It is easy to find, with a simple program, with paper and pencil, or just with mental calculations - that such pairs truly exist!
sontd(48) = 75, sontd(75) = 48;sopd(220) = 284, sopd(284) = 220.Though for sontd the pair is found earlier, it looks the pairs for sopd are more frequent. Try to see yourself how many of them exist, for
example, below 1000000.
Do sopd-pairs composed of numbers with different parity exist? (sopd(N) = M, sopd(M) = N, M mod 2 = 1 - (N mod 2))
Do sontd-pairs composed of numbers with same parity exist? (sontd(N) = M, sontd(M) = N, M mod 2 = N mod 2)
Is the amount of such pairs finite or infinite?
Again, these are unsolved (yet) problems.
It's natural to investigate more general question: let's build a sequence of integers, such that X[n+1] = sopd(X[n]) and investigate its behavior.
Trying to do this with pencil and paper (or even in one's head) we can quickly find that many starting numbers make less or more
steadily decreasing sequence, ending with 1:
8 -> 7 -> 1
12 -> 16 -> 15 -> 9 -> 4 -> 3 -> 1
We stop at 1 since the sopd function is not clearly defined for it - we want sum of divisors starting from 1 and up to but not including
the number itself - but what if the "number itself" is 1?
Some sequences, however, create "loops", returning to numbers already encountered earlier. We have seen such examples:
25 -> 6 -> 6 -> ...
562 -> 284 -> 220 -> 284 -> ...
These two examples come to loops of "length" 1 and 2 respectively, but larger loops exist also - we leave the joy of searching for them
to you (though of course many simple examples can be simply googled).
Most curious thing is that some sequences may grow significantly, for example 42 peaks at 259 before going down to 1.
42 -> 54 -> 66 -> 78 -> 90 -> 144 -> 259 -> 45 -> 33 -> 15 -> 9 -> 4 -> 3 -> 1
Even if you search among numbers below 200 you may find quite impressive chains (beware, that calculations won't fit 32-bit integers).
We don't want to bereave you of this small fun.
Moreover you may find some basic idea about which numbers demonstrate steady "periods of growth".
Some starting numbers (there are handful even below 1000) produce sequences which were not yet calulated till the end! This brings us to the
central unsolved problem of the whole story:
It is still not known, whether such sequences can grow indefinitely, or are always doomed to end with 1 or with a loop.
It is a matter of Catalan conjecture (also called Catalan–Dickson). Unlike with Fermat's theorem or Collatz conjecture, where matematicians had or have strong feeling the hypothesis is true - in this case there are scientists who feel quite unsure about result.
Situation with sequences constructed using sontd function looks less dramatic - they have greater tendency to decrease. And even if they come
to loops, there are less varieties of such loops, most of them having length 2 (you may have fun looking for the first larger loop - and even
greater fun looking for the second).
Let's build sequences mentioned in the last statement of the previous paragraph - and investigate their behavior. As suggested, find the smallest
number M, which generates the loop of length greater than 2. Then find the next number N which also generates the loop of length greater than 2,
and which is not part of the loop, generated by previous number (M). Well, regard this as a joke. Instead, given an integer range, find the
number, producing the longest sequence, and peaking above the starting number.
Report the number itself, the length of the sequence and it's peak value. In case of several sequences with equal length pick the one with the
highest peak (the first of them if there are several with same length and peak).
Length of the sequence counts the terminal value - either 0 or the first reapeating value in the case of a loop.
Example
input data:
1000 3000
answer:
1458 19 2883