To my surprise, I discovered that the identification of untouchable numbers was not included in my daily number analysis. Of course, the identification is covered in the Numbers Aplenty website but part of the reason for setting up my own daily number analysis was the unreliability of that website. It was often inaccessible. However, I've copied all the number types that the site covers and these are listed below.
ABA 162 288 324 + 985608 aban 52 88 96 + 996 abundant 88 96 120 + 999996 Achilles 288 1944 3872 + 990584 admirable 88 120 246 + 999786 alternating 52 96 210 + 989896 amenable 52 88 96 + 999996 apocalyptic 540 612 624 + 30000 arithmetic 96 188 206 + 999996 astonishing 216 3078 3388 + 23490 automorphic 9376 Bell 52 betrothed 2024 8892 9504 + 266000 binomial 120 210 276 + 990528 c.heptagonal 7568 11572 30598 + 999916 c.nonagonal 406 7750 12880 + 958420 c.pentagonal 276 766 1266 + 981256 c.triangular 976 8326 10210 + 995116 cake 576 1160 2048 + 956040 canyon 206 216 304 + 987678 compositorial 1728 207360 congruent 52 88 96 + 999996 constructible 96 120 408 + 986880 cube 216 1728 5832 + 941192 Cunningham 120 124 288 + 998000 Curzon 146 210 306 + 999830 d-powerful 262 372 518 + 996732 decagonal 52 540 976 + 990522 deficient 52 124 146 + 999970 dig.balanced 52 120 210 + 999996 droll 4224 5184 33280 + 451584 Duffinian 324 576 784 + 984064 eban 52 2036 2050 + 66066 economical 146 162 448 + 998144 emirpimes 326 562 718 + 999478 enlightened 2048 2304 2500 + 250000 equidigital 146 162 448 + 998144 eRAP 10620 13350 23408 + 958112 esthetic 210 898 1212 + 987878 Eulerian 120 2036 2416 + 524268 evil 96 120 210 + 999996 factorial 120 40320 362880 fibodiv 1822 2602 5204 + 974994 Fibonacci 10946 46368 Friedman 216 1296 2048 + 997246 frugal 2048 10240 10368 + 979776 gapful 120 792 1060 + 999990 Gilda 628 5346 65676 202196 Giuga 66198 happy 188 262 326 + 999928 harmonic 8190 18600 30240 + 950976 Harshad 120 162 210 + 999990 heptagonal 342 540 1288 + 981882 hexagonal 120 276 1128 + 990528 highly composite 120 1680 15120 + 720720 hoax 336 516 562 + 999860 house 1716 25884 56560 + 758952 iban 120 124 210 + 777774 iccanobiF 124 836 idoneal 88 120 210 + 520 impolite 2048 65536 inconsummate 216 276 326 + 999912 interprime 120 246 288 + 999970 Jordan-Polya 96 120 216 + 967680 junction 206 210 216 + 999952 Kaprekar 5292 7272 77778 + 500500 katadrome 52 96 210 + 987652 Leyland 2530 16580 69632 + 262468 lonely 120 1342 19634 + 370312 Lucas 322 5778 Lynch-Bell 124 162 216 + 984312 magic 16400 32020 296394 + 629910 magnanimous 52 518 556 + 979592 metadrome 124 146 238 + 245678 modest 206 406 818 + 982222 Moran 372 516 518 + 999548 Motzkin 5798 113634 mountain 120 162 262 + 898752 nialpdrome 52 88 96 + 999996 nonagonal 474 750 1956 + 985536 nude 88 124 162 + 999396 oban 88 96 306 + 996 octagonal 96 408 936 + 994176 odious 52 88 124 + 999968 palindromic 88 262 292 + 890098 pancake 326 562 2212 + 983504 pandigital 120 210 216 + 44760 partition 792 1002 1958 + 831820 pentagonal 210 782 852 + 986176 pernicious 52 88 96 + 999968 plaindrome 88 124 146 + 788888 power 216 324 576 + 984064 powerful 216 288 324 + 990584 practical 88 96 120 + 999990 prim.abundant 88 246 304 + 999786 primorial 210 510510 productive 52 306 336 + 967708 pronic 210 306 342 + 999000 pseudoperfect 88 96 120 + 999996 repdigit 88 66666 222222 repfigit 3684 156146 298320 repunit 20440 60880 621436 + 866496 Rhonda 5664 5832 52374 + 513744 Ruth-Aaron 714 1682 2108 + 999072 Saint-Exupery 6240 15540 30720 + 960960 Sastry 13224 self 288 626 670 + 999842 semiprime 146 206 262 + 999806 sliding 52 290 520 + 785000 Smith 562 576 852 + 999970 sphenic 238 246 290 + 999898 square 324 576 784 + 984064 straight-line 210 246 852 + 765432 strobogrammatic 88 96 818 + 998866 super Niven 120 210 306 + 999000 super-d 336 782 784 + 999894 superabundant 120 1680 15120 + 720720 tau 88 96 248 + 999928 taxicab 4104 39312 65728 + 994688 tetrahedral 120 2024 2600 + 988260 tetranacci 39648 triangular 120 210 276 + 990528 tribonacci 3136 5768 66012 trimorphic 624 9376 890624 uban 52 88 96 Ulam 206 238 324 + 999836 undulating 262 292 474 + 969696 unprimeable 206 322 324 + 999996 upside-down 852 2198 2828 + 899112 vampire 6880 104260 105210 + 815958 wasteful 52 88 96 + 999996 weird 836 7192 7912 + 997570 Woodall 15624 Zuckerman 216 612 624 + 972216 Zumkeller 88 96 120 + 99988 zygodrome 88 3366 3388 + 999966
Here is a complete and comprehensive guide to determining if a number is untouchable, alongside the exact SageMath program you need.Understanding Untouchable NumbersA positive integer $n$ is considered untouchable if it cannot be expressed as the sum of the proper divisors of any integer $x$.The sum of the proper divisors of $x$ is known as the aliquot sum, denoted mathematically as $s(x) = \sigma_1(x) - x$, where $\sigma_1(x)$ is the sum of all positive divisors of $x$.To write a program that definitively checks this, we need a mathematical upper limit to our search so the program knows when to stop looking.⚬ For any composite number $x$, its smallest prime factor is at most $\sqrt{x}$.⚬ Consequently, its largest proper divisor is at least $\sqrt{x}$.⚬ Therefore, the aliquot sum $s(x) \ge \sqrt{x}$.This gives us our boundary: if we are looking for a number $x$ such that $s(x) = n$, we only need to search up to $x \le n^2$. If we check every number up to $n^2$ and none of their proper divisors sum to $n$, the number is definitively untouchable.SageMath ImplementationBelow is the complete SageMath program. It relies on Sage's highly optimized sigma(x, 1) function to compute the sum of all divisors, subtracting $x$ to get the proper divisors.
I won't include a link to the program because it was woefully slow but Gemini did add the following:
Characteristics of the Algorithm and Number Spaces
When working with this algorithm, here are the mathematical aspects that govern how untouchable numbers operate:
⚬ Computation Time for Large Numbers: Because the upper bound strictly requires iterating up to $n^2$, processing large numbers like 28254 demands significant computational time. The loop for 28254 will search through 798,288,516 integers. While mathematically correct and guaranteed to provide the right answer, testing numbers this high in a single-threaded loop will take several minutes to run to completion.
⚬ The Odd Number Phenomenon: It is widely theorized (and relies on a slightly stronger version of Goldbach's conjecture) that 5 is the only odd untouchable number. If an odd number $n > 5$ is given, $n-1$ is an even number greater than 4. By Goldbach's conjecture, $n-1$ can be expressed as the sum of two distinct primes, $p$ and $q$. The aliquot sum of their product, $s(p \cdot q)$, equates exactly to $p + q + 1 = n$.
⚬ Abundance of Even Untouchable Numbers: In contrast to odd numbers, even untouchable numbers are relatively common. They never end in 0 and are never one less than a prime number.
Here was my complaint:
Even to verify that one number like 28254 is untouchable is very processor intensive. I thought that there might be a list of untouchable number somewhere on the Internet. For example, Numbers Aplenty displays the first 600 untouchable numbers. Furthermore, the Numbers Aplenty website quickly determines whether a given number is untouchable or not. Maybe give this problem deeper consideration.
Here was Gemini's response:
To rapidly evaluate whether a number like 28,254 is untouchable, we must move away from brute-forcing every integer up to $n^2$. Fast computational repositories, like Numbers Aplenty, achieve rapid results by exploiting the structural properties of the aliquot sum function $s(x)$ to categorically eliminate vast portions of the search space.
By categorizing the prime factor makeup of any potential preimage $x$, we can reduce the search bound from $n^2$ down to $n\sqrt{n}$ (and process prime pairings in linear time).
The Algorithmic Framework
If an integer $x$ has an aliquot sum equal to $n$, $x$ must fall into one of three structural categories based on its total number of prime factors, denoted by $\Omega(x)$:
1. Exactly two identical prime factors ($x = p^2$)
The proper divisors of $p^2$ are $p$ and $1$. Therefore, $s(x) = p + 1$.
If $s(x) = n$, then $p = n - 1$.
Optimization: We only need to check if $n - 1$ is a prime number. If it is, $n$ is touchable via $x = (n-1)^2$.
2. Exactly two distinct prime factors ($x = p \cdot q$)
The proper divisors are $p, q,$ and $1$. Therefore, $s(x) = p + q + 1$.
If $s(x) = n$, then $p + q = n - 1$.
Optimization: Instead of iterating through large values of $x$, we simply iterate a prime $p$ up to $(n-1)/2$ and check if $n - 1 - p$ is also prime. If such a pair exists, $n$ is touchable via $x = p \cdot q$.
3. Three or more prime factors ($\Omega(x) \ge 3$)
For any number with three or more prime factors, mathematical bounds dictate that $x$ must be significantly constrained.
If $p$ is the smallest prime factor of $x$, the largest proper divisor is $x/p$. Since $x$ has at least one other proper divisor, $s(x) > x/p$.
This tells us that $n > x/p \implies x < p \cdot n$.
Because $x$ has at least three prime factors, $x \ge p^3$. Combining these inequalities yields $p^3 < p \cdot n \implies p < \sqrt{n}$.
Substitute $p < \sqrt{n}$ back into $x < p \cdot n$, and we get the absolute hard limit: $x < n\sqrt{n}$.
Optimization: The exhaustive search loop only needs to run up to $n\sqrt{n}$, not $n^2$. For $n = 28,254$, this reduces the iteration ceiling from ~798,000,000 down to roughly 4,749,000.
The Optimized SageMath Script
Here is the program utilizing these constraints. It will process 28,254 in a fraction of a second: permalink.
Well, maybe not in a fraction of a second. It still times out in SageMathCell but it takes an acceptable amount of time in my Jupyter notebook. Gemini added the following:
Execution Behavior
When run, the script will rapidly clear Conditions 1 and 2. Because $n = 28,254$ is even, $n-1 = 28,253$, which is an odd number. An odd number can only be expressed as the sum of two primes if one of those primes is $2$. It checks $2 + 28,251$ (where 28,251 is composite), eliminating Condition 2 almost instantly. It then sieves up to 4.7 million for Condition 3, definitively verifying its untouchable status without exhausting processor limits.
I discuss untouchable numbers in this blog post from May of 2022 and again in this post from May of 2024. Just to summarise:
There are exactly 5,324 untouchable numbers in the range up to 40,000.
To determine the percentage, you divide the number of untouchable numbers by the total numbers in that range:
5,324 ÷ 40,000 = 0.1331
Therefore, exactly 13.31% of numbers in the range up to 40,000 are untouchable.
No comments:
Post a Comment