Untouchable numbers
- Definitions
-
- Untouchable numbers are also known as nonaliquot numbers.
- An untouchable number is a positive integer that cannot be expressed as the sum of all the proper divisors of any positive integer. (From Wikipedia)
- The sum of all the proper divisors is also known as the aliquot sum.
- An untouchable are those numbers that are not in the image of the aliquot sum function. (From Wikipedia)
- Untouchable numbers: impossible values for the sum of all aliquot parts function. (From OEIS: The On-line Encyclopedia of Integer Sequences®)
- An untouchable number is a positive integer that is not the sum of the proper divisors of any number. (From MathWorld™)
- Observations and conjectures
All untouchable numbers > 5 are composite numbers.
No untouchable number is perfect.
No untouchable number is sociable.
No untouchable number is a Mersenne prime.
No untouchable number is one more than a prime number, since if p is prime, then the sum of the proper divisors of p2 is p + 1.
No untouchable number is three more than an odd prime number, since if p is an odd prime, then the sum of the proper divisors of 2p is p + 3.
The number 5 is believed to be the only odd untouchable number, but this has not been proven: it would follow from a slightly stronger version of the Goldbach's conjecture, since the sum of the proper divisors of pq (with p, q being distinct primes) is 1 + p + q.
There are infinitely many untouchable numbers, a fact that was proven by Paul Erdős.
According to Chen & Zhao, their natural density is at least d > 0.06.
- Task
-
- show (in a grid format) all untouchable numbers ≤ 2,000.
- show (for the above) the count of untouchable numbers.
- show the count of untouchable numbers from unity up to (inclusive):
- 10
- 100
- 1,000
- 10,000
- 100,000
- 1,000,000
- 10,000,000
- ... or as high as is you think is practical.
- all output is to be shown here, on this page.
- See also
-
- Wolfram MathWorld: untouchable number.
- OEIS: A005114 untouchable numbers.
- OEIS: a list of all untouchable numbers below 10,000 (inclusive).
- Wikipedia: untouchable number.
- Wikipedia: Goldbach's conjecture, since
REXX
<lang rexx>/*REXX pgm finds N untouchable numbers (numbers that can't be equal to any aliquot sum).*/ parse arg n cols tens . /*obtain optional arguments from the CL*/ if n= | n=="," then n= 2000 /*Not specified? Then use the default.*/ if cols= | cols=="," then cols= 10 /* " " " " " " */ if tens= | tens=="," then tens= 0 /* " " " " " " */ tell= n>0; n= abs(n) /*N>0? Then display the untouchable #s*/ call genP n /*call routine to generate some primes.*/ !.= 0 /*define all possible aliquot sums ≡ 0.*/
do p=1 for #; _= @.p+1; !._= 1 /*any prime+1 is not an untouchable.*/
_= @.p+3; !._= 1 /* " prime+3 " " " " */
end /*p*/ /* [↑] this will also rule out 5. */
!.5= 0 /*special case as primes 2+3 sum to 5. */
do j=2 for n+n; y= sigma(j) /*check all numbers for touchability. */
if y>n then iterate; !.y= 1 /*mark Y number as a touchable number. */
end /*j*/
if tell then say 'The list of all untouchable numbers ≤' n":" /*display title of the #s*/
$= ' 2 5'; cnt= 2 /*start the list of an even prime and 5*/
do t=6 by 2 to n /*traipse through the even numbers. */
if !.t==1 then iterate /*Is it touchable? Then skip this #. */
cnt= cnt + 1 /*bump the count of untouchable numbers*/
if \tell then iterate /*Not telling? Then skip grid build. */
$= $ right( commas(t), 7) /*add a number to the list; bump count.*/
if cnt//cols\==0 then iterate /*allow X untouchable numbers per line.*/
say $; $= /*display a line of untouchables; clear*/
end /*t*/
if tell & $\== then say $ /*display a residual line, if any. */
if tell then say say right( commas(cnt),20) ' untouchable numbers were found ≤ ' commas(n) if tens==0 then exit cnt /*Any "tens" specified? No, then exit.*/
do p=1 for tens; z= untoucha(-(10**p) ) /*invoke this program recursively. */
end /*pow*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: @.1= 2; @.2= 3; #= 2 /*define the start of some low primes. */
do j=@.#+2 by 2 to n /*find odd primes from here on forward.*/
do k=2 while k*k<=j /* [↓] divide by the known odd primes.*/
if j // @.k == 0 then iterate j /*J ÷ by a prime? Then ¬prime. ___ */
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j /*bump number of primes; assign prime.*/
end /*j*/; return /*#: is the number of primes generated*/
/*──────────────────────────────────────────────────────────────────────────────────────*/ sigma: procedure; parse arg x; od= x // 2 /*use either EVEN or ODD integers. */
s= 1 /*set initial sigma sum to unity. ___*/
do j=2+od by 1+od while j*j<x /*divide by all integers up to the √ x */
if x//j==0 then s= s + j + x%j /*add the two divisors to the sum. */
end /*j*/ /* [↑] % is REXX integer division. */
/* ___ */
if j*j==x then return s + j /*Was Z a square? If so, add √ x */
return s /*return (sigma) sum of the divisors. */</lang>
- output when using the default inputs:
The list of all untouchable numbers ≤ 2000:
2 5 52 88 96 120 124 146 162 188
206 210 216 238 246 248 262 268 276 288
290 292 304 306 322 324 326 336 342 372
406 408 426 430 448 472 474 498 516 518
520 530 540 552 556 562 576 584 612 624
626 628 658 668 670 708 714 718 726 732
738 748 750 756 766 768 782 784 792 802
804 818 836 848 852 872 892 894 896 898
902 926 934 936 964 966 976 982 996 1,002
1,028 1,044 1,046 1,060 1,068 1,074 1,078 1,080 1,102 1,116
1,128 1,134 1,146 1,148 1,150 1,160 1,162 1,168 1,180 1,186
1,192 1,200 1,212 1,222 1,236 1,246 1,248 1,254 1,256 1,258
1,266 1,272 1,288 1,296 1,312 1,314 1,316 1,318 1,326 1,332
1,342 1,346 1,348 1,360 1,380 1,388 1,398 1,404 1,406 1,418
1,420 1,422 1,438 1,464 1,476 1,506 1,508 1,510 1,522 1,528
1,538 1,542 1,566 1,578 1,588 1,596 1,632 1,642 1,650 1,680
1,682 1,692 1,716 1,718 1,728 1,732 1,746 1,758 1,766 1,774
1,776 1,806 1,816 1,820 1,822 1,830 1,838 1,840 1,842 1,844
1,852 1,860 1,866 1,884 1,888 1,894 1,896 1,920 1,922 1,944
1,956 1,958 1,960 1,962 1,972 1,986 1,992
197 untouchable numbers were found ≤ 2,000
2 untouchable numbers were found ≤ 10
5 untouchable numbers were found ≤ 100
89 untouchable numbers were found ≤ 1,000
1,216 untouchable numbers were found ≤ 10,000
13,886 untouchable numbers were found ≤ 100,000
150,355 untouchable numbers were found ≤ 1,000,000