Untouchable numbers: Difference between revisions

Content added Content deleted

Inline

Revision as of 03:00, 11 February 2021

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 p² 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
... 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 100,000 (inclusive).
Wikipedia: untouchable number.
Wikipedia: Goldbach's conjecture.

Go

Translation of: Wren

<lang go>package main

import "fmt"

func sumDivisors(n int) int {

   sum := 0
   i := 1
   k := 2
   if n%2 == 0 {
       k = 1
   }
   for i*i <= n {
       if n%i == 0 {
           sum += i
           j := n / i
           if j != i {
               sum += j
           }
       }
       i += k
   }
   return sum - n

}

func sieve(n int) []bool {

   n++
   s := make([]bool, n*4) // all false by default
   for i := 0; i <= n; i++ {
       s[sumDivisors(i)] = true
   }
   return s

}

func isPrime(n int) bool {

   if n < 2 {
       return false
   }
   if n%2 == 0 {
       return n == 2
   }
   if n%3 == 0 {
       return n == 3
   }
   d := 5
   for d*d <= n {
       if n%d == 0 {
           return false
       }
       d += 2
       if n%d == 0 {
           return false
       }
       d += 4
   }
   return true

}

func commatize(n int) string {

   s := fmt.Sprintf("%d", n)
   if n < 0 {
       s = s[1:]
   }
   le := len(s)
   for i := le - 3; i >= 1; i -= 3 {
       s = s[0:i] + "," + s[i:]
   }
   if n >= 0 {
       return s
   }
   return "-" + s

}

func main() {

   limit := 100000
   s := sieve(14 * limit)
   untouchable := []int{2, 5}
   for n := 6; n <= limit; n += 2 {
       if !s[n] && !isPrime(n-1) && !isPrime(n-3) {
           untouchable = append(untouchable, n)
       }
   }
   fmt.Println("List of untouchable numbers <= 2,000:")
   count := 0
   for i := 0; untouchable[i] <= 2000; i++ {
       fmt.Printf("%6s", commatize(untouchable[i]))
       if (i+1)%10 == 0 {
           fmt.Println()
       }
       count++
   }
   fmt.Printf("\n\n%6s untouchable numbers were found  <=   2,000\n", commatize(count))
   p := 10
   count = 0
   for _, n := range untouchable {
       count++
       if n > p {
           cc := commatize(count - 1)
           cp := commatize(p)
           fmt.Printf("%6s untouchable numbers were found  <= %7s\n", cc, cp)
           p = p * 10
           if p == limit {
               break
           }
       }
   }
   cu := commatize(len(untouchable))
   cl := commatize(limit)
   fmt.Printf("%6s untouchable numbers were found  <= %s\n", cu, cl)

}</lang>

Output:

List of untouchable numbers <= 2,000:
     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,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

   196 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,212 untouchable numbers were found  <=  10,000
13,863 untouchable numbers were found  <= 100,000

Phix

Note: the limit of 18*n is unsound, albeit matching the above b005114.txt list, see talk page (1464) <lang Phix>procedure untouchable(integer n, cols=0, tens=0)

   bool tell = n>0
   n = abs(n)
   sequence sums = repeat(0,n+3)
   for i=1 to n do
       integer p = get_prime(i)
       if p>n then exit end if
       sums[p+1] = 1
       sums[p+3] = 1
   end for
   sums[5] = 0

-- for j=2 to 2*n do

   for j=2 to 18*n do  -- see talk page (1464)
       integer y = sum(factors(j,-1))
       if y<=n then
           sums[y] = 1
       end if
   end for
   if tell then
       printf(1,"The list of all untouchable numbers <= %d:\n",{n})
   end if
   string line = "       2       5"
   integer cnt = 2
   for t=6 to n by 2 do
       if sums[t]=0 then
           cnt += 1
           if tell then
               line &= sprintf("%,8d",t)
               if remainder(cnt,cols)=0 then
                   printf(1,"%s\n",line)
                   line = ""
               end if
           end if
       end if
   end for
   if tell then
       if line!="" then
           printf(1,"%s\n",line)
       end if
       printf(1,"\n")
   end if
   printf(1,"%,20d untouchable numbers were found <= %,d\n",{cnt,n})
   for p=1 to tens do
       untouchable(-power(10,p))
   end for

end procedure

untouchable(2000, 10, 5)</lang>

Output:

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,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

                 196 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,212 untouchable numbers were found <= 10,000
              13,863 untouchable numbers were found <= 100,000

REXX

Some optimization was done to the code to produce prime numbers, since a simple test could be made to exclude
the calculation of touchability for primes as the aliquot sum of a prime is unity.
This saved around 15% of the running time.

A fair amount of code was put into the generation of primes, but the computation of the aliquot sum was the area
that consumed the most CPU time. <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=="," | cols==0 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 * 18 /*call routine to generate some primes.*/ u.= 0 /*define all possible aliquot sums ≡ 0.*/

         do p=1  for #;   _= @.p + 1;   u._= 1  /*any prime+1  is  not  an untouchable.*/
                          _= @.p + 3;   u._= 1  /* "  prime+3   "   "    "      "      */
         end   /*p*/                            /* [↑]  this will also rule out  5.    */

u.5= 0 /*special case as prime 2 + 3 sum to 5.*/

         do j=2  for lim;  if !.j  then iterate /*Is  J  a prime?   Yes, then skip it. */
         odd= j // 2                            /*use either  EVEN  or  ODD  integers. */
         y= 1                                   /*set initial sigma sum (Y) to 1.   ___*/
             do m=2+odd  by 1+odd  while  m*m<j /*divide by all integers up to the √ J */
             if j//m==0  then y= y + m + j%m    /*add the two divisors to the sum.     */
             end   /*m*/                        /* [↑]  %  is REXX integer division.   */
                                                /*                                 ___ */
         if m*m==j  then    y= y + m            /*Was  J  a square?   If so, add  √ J  */
         if y<=n    then  u.y= 1                /*mark  Y  as a touchable if in range. */
         end  /*j*/

call show /*maybe show untouchable #s and a count*/ if tens>0 then call powers /*Any "tens" specified? Calculate 'em.*/ exit cnt /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? grid: $= $ right( commas(t), w); if cnt//cols==0 then do; say $; $=; end; return powers: do pr=1 for tens; call 'UNTOUCHA' -(10**pr); end /*recurse*/; return /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: #= 9; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; @.7=17; @.8=19; @.9=23 /*a list*/

     !.=0;  !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1; !.19=1  !.23=1 /*primes*/
     parse arg lim;                 sq.10= 100  /*limit;  square;  start of trial ÷'s. */
       do j=@.#+6  by 2  to lim                 /*find odd primes from here on forward.*/
       parse var  j      -1  _;   if     _==5  then iterate;  if j// 3==0  then iterate
       if j// 7==0  then iterate;   if j//11==0  then iterate;  if j//13==0  then iterate
       if j//17==0  then iterate;   if j//19==0  then iterate;  if j//23==0  then iterate
              do k=10  while sq.k<=j            /* [↓]  divide  Y  by known odd primes.*/
              if j//@.k==0  then iterate j      /*J ÷ by a prime?  Then ¬prime.   ___  */
              end   /*k*/                       /* [↑]  only process numbers  ≤  √ J   */
       #= #+1                                   /*bump the number  (count)  of primes. */
       !.j= 1;      @.#= j;      sq.#= j*j      /*assign the #th prime;  flag as prime.*/
       end          /*j*/;       return         /*#:  is the number of primes generated*/

/*──────────────────────────────────────────────────────────────────────────────────────*/ show: w=7; $= right(2, w+1) right(5, w) /*start the list of an even prime and 5*/

                            cnt= 2              /*count of the only two primes in list.*/
       do t=6  by 2  to n;  if u.t then iterate /*Is  T  touchable?    Then skip it.   */
       cnt= cnt + 1;     if tell then call grid /*bump count;  maybe show a grid line. */
       end   /*t*/
                   if tell & $\==  then say $ /*display a residual grid line, if any.*/
                   if tell           then say   /*add a spacing blank line for output. */
     if n>0  then say right( commas(cnt), 20)  ,
                    ' untouchable numbers were found  ≤ '    commas(n);            return</lang>

output when using the default inputs:

       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,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

                 196  untouchable numbers were found  ≤  2,000

output when using the inputs: 0 , 5

                   2  untouchable numbers were found  ≤  10
                   5  untouchable numbers were found  ≤  100
                  89  untouchable numbers were found  ≤  1,000
               1,212  untouchable numbers were found  ≤  10,000
              13,863  untouchable numbers were found  ≤  100,000
             150,253  untouchable numbers were found  ≤  1,000,000

Due to complications of choosing an overreach limit, I cannot be sure to any certainty that the count is correct for one million.

Wren

Library: Wren-seq

Library: Wren-math

Library: Wren-fmt

Not an easy task as, even allowing for the prime tests, it's difficult to know how far you need to sieve to get the right answers. The parameters here were found by trial and error. <lang ecmascript>import "/math" for Int, Nums import "/seq" for Lst import "/fmt" for Fmt

var sieve = Fn.new { |n|

   n = n + 1
   var s = List.filled(n*4, false)
   for (i in 0..n) {
       var sum = Nums.sum(Int.properDivisors(i)) 
       s[sum] = true
   }
   return s

}

var limit = 1e5 var s = sieve.call(14 * limit) var untouchable = [2, 5] var n = 6 while (n <= limit) {

   if (!s[n] && !Int.isPrime(n-1) && !Int.isPrime(n-3)) untouchable.add(n)
   n = n + 2

}

System.print("List of untouchable numbers <= 2,000:") for (chunk in Lst.chunks(untouchable.where { |n| n <= 2000 }.toList, 10)) {

   Fmt.print("$,6d", chunk)

} System.print() Fmt.print("$,6d untouchable numbers were found <= 2,000", untouchable.count { |n| n <= 2000 }) var p = 10 var count = 0 for (n in untouchable) {

   count = count + 1
   if (n > p) {
       Fmt.print("$,6d untouchable numbers were found  <= $,7d", count-1, p)
       p = p * 10
       if (p == limit) break
   }

} Fmt.print("$,6d untouchable numbers were found <= $,d", untouchable.count, limit)</lang>

Output:

List of untouchable numbers <= 2,000:
     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,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

   196 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,212 untouchable numbers were found  <=  10,000
13,863 untouchable numbers were found  <= 100,000