The Untouchables

Question

Untouchable Numbers^α

An untouchable number is a positive integer that cannot be expressed as the sum of all the proper divisors of any positive integer (including the untouchable number itself).

For example, the number 4 is not untouchable as it is equal to the sum of the proper divisors of 9: 1 + 3 = 4. The number 5 is untouchable as it is not the sum of the proper divisors of any positive integer. 5 = 1 + 4 is the only way to write 5 as the sum of distinct positive integers including 1, but if 4 divides a number, 2 does also, so 1 + 4 cannot be the sum of all of any number's proper divisors (since the list of factors would have to contain both 4 and 2).

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 conjecture. ^β

There are infinitely many untouchable numbers, a fact that was proven by Paul Erdős.

A few properties of untouchables:

• No untouchable is 1 greater than a prime
• No untouchable is 3 greater than a prime, except 5
• No untouchable is a perfect number
• Up to now, all untouchables aside from 2 and 5 are composite.

Objective

Create a program or function that takes a natural number n via standard input or function parameters and prints the first n untouchable numbers.

The output must have separation between the numbers, but this can be anything (i.e. newlines, commas, spaces, etc).

This should be able to work at least 1 <= n <= 8153. This is based on the fact that the b-file provided for the OEIS entry^γ goes up to n = 8153.

Standard loopholes are disallowed, as per usual.

Example I/O

1 -> 2
2 -> 2, 5
4 -> 2, 5, 52, 88
10 -> 2, 5, 52, 88, 96, 120, 124, 146, 162, 188
8153 -> 2, 5, 52, 88, 96, 120, ..., ..., ..., 59996

This is code-golf, so least number of bytes wins.

---

^{α - Wikipedia, β - MathWorld, γ - OEIS}

---

^{For some reason this was marked as a duplicate to the 'finding semiperfect numbers' question, however the tasks are completely different. In this case, you must check to make sure that no sum of perfect divisors of any natural number can equal a certain number.}

• Reto Koradi: This is purely speculative, since I haven't really thought about how I would solve this yet: Would it be cheating if I assumed an upper limit on the resulting numbers? Say, if I wrote code that only finds untouchable numbers up to 60,000? That would be enough to cover the input range. But of course I only know that based on the partial results you provided.
• Kade: I guess it would be okay. It's not technically hardcoding the results, doesn't violate standard loopholes as far as I know. As long as it fits the rest of the spec that will be fine.
• Kade: @vihan Definitely not.

Answer 1

Pyth, 21 bytes

.f!fqZsf!%TYStTSh^Z2Q

Warning: Incredibly slow. Test run and timing below.

$ time pyth -c '.f!fqZsf!%TYStTSh^Z2Q' <<< 3
[2, 5, 52]
real 2m46.463s
user 2m46.579s
sys 0m0.004s

It's basically as brute force as possible, tests factorizations up to the potential lonely number squared plus one.

Answer 2

C, 104 bytes

j,i,z,w;u(y){for(z=2;y;z++)for(w=0;(++w<z*z||0&printf("%i ",z)+y--)&&j^z;)for(i=j=0;++i<w;j+=i*!(w%i));}

It will take a few minutes for y> 20, but whatever.

Answer 3

Java, 310 Bytes

class U{int[] p;U(int e){p=new int[(int)4e9];for(int i=1,c=0;c<e;i++)if(u(i)>0){System.out.println(i);c++;}}int p(int n){if(p[n]!=0)return p[n];int i,s=1;for(i=2;i<=n-1;i++)s+=n%i==0?i+(n/i!=i?n/i:0):0;return(p[n]=s);}int u(int n){if(n==1)return 0;for(int i=2;i<=(n-1)*(n-1);i++)if(p(i)==n)return 0;return 1;}}

Golfed as well as I could but, I was more interested in making sure it ran in reasonable time. The unglofed version is probably more interesting

public class Untouchable {
 int[] properDivisorSumMap;
 
 
 public Untouchable(int estimatedMaxium){
 properDivisorSumMap = new int[(estimatedMaxium-1)*(estimatedMaxium-1)];
 }
 
 
 public int properDivisorSum(int n){
 if(properDivisorSumMap[n] != 0){
 return properDivisorSumMap[n];
 }
 
 int sum = 1;
 for(int i=2;i<=(int)Math.sqrt(n);i++){
 if(n%i==0){
 sum+=i;
 if(n/i != i){
 sum+=n/i;
 }
 }
 }
 properDivisorSumMap[n] = sum;
 return sum;
 }
 
 
 public boolean untouchable(int n){
 if(n==1){
 return false;
 }
 for(int i=2;i<=(n-1)*(n-1);i++){
 if(properDivisorSum(i) == n){
 return false;
 }
 } 
 return true;
 }
 
 public static void main(String[] args){
 Untouchable test = new Untouchable(8480);
 
 int elements = Integer.parseInt(args[0]);
 
 for(int i=1,count=0;count < elements;i++){
 if(test.untouchable(i)){
 System.out.printf("%4d: %4d%n",count,i);
 count++;
 }
 }
 }
}

Answer 4

Go, 396 bytes

Not really golfed, but it can do all of the required range. Runs in about ~20min and needs ~7GB (independent of n). Makes a giant array to compute the sum of divisors for all numbers up to 59997 squared.

func untouchable(n int) {
 const C = 59997
 const N = C * C
 s := make([]uint16, N)
 for d := 1; d < N; d++ {
 for i := 2 * d; i < N; i += d {
 v := int(s[i]) + d
 if v > C {
 v = C + 1 // saturate at C+1
 }
 s[i] = uint16(v)
 }
 }
 var m [C]bool
 for i := 2; i < N; i++ {
 if s[i] < C {
 m[s[i]] = true
 }
 }
 for i := 2; n > 0; i++ {
 if !m[i] {
 println(i)
 n--
 }
 }
}

• noodle person: I'm over 8 years late, but you forgot to post the golfed version!

Answer 5

R, 122 bytes

function(n)while(n){T=T+1
m=T^2
t=0
while(m<-m-1){i=s=0;while((i=i+1)<m)if(!m%%i)s=s+i;t=t+(T==s)}
if(!t){print(T);n=n-1}}

Try it online!

Anyone familiar with R programming will certainly wince when they look at this. Loops in general are horribly inefficient in R, and the fast and idiomatic way to tackle this kind of question would normally be to use vectorized functions.

Unfortunately, the maximum size of a vector in R is 2^31-1 elements, which is smaller than the square of 59996, the highest number that we need to test for untouchability, so we can't easily find divisors by checking a large vector.

So here we use a set of nested while loops to avoid making the big vectors that we really want. If you aren't used to R, this will probably seem quite unremarkable, and you'll probably also be surprised at just how slowly it runs (n=4 times-out on TIO!).

If only R used un-signed integers to index vectors, and so could manage vectors with 2^32 elements, the code would be only 80 bytes:

Imaginary R with 2^32-sized vectors, 80 bytes

function(n,m=1:4e9,a=!m){for(y in m)a[sum(which(!y%%(2:y-1)))]=T
which(!a)[1:n]}

Try it online! (but it won't work for large n)

Answer 6

Jelly, (削除) 10 (削除ここまで) 9 bytes

22Æṣ€ḟƑƊ#

Try it online!

Times out on TIO for \$n > 3\$, but works in theory for all \$n\$. Relies on the assumption that for a given \$x \ge 2\$, \$x\$ is untouchable if none of the proper divisor sums between \1ドル\$ and \$x^2\$ equals \$x\$. Takes \$n\$ on STDIN.

How it works

22Æṣ€ḟƑƊ# - Main link. Takes no arguments
 Ɗ - Group the previous 3 links together into a monad f(k):
 2 - k2
 € - Over each 1, 2, ..., k2:
 Æṣ - Proper divisor sum
 Ƒ - Is the list of proper divisor sums unchanged after:
 ḟ - removing k from it?
2 # - Count up k = 2, 3, ... until n such k's return true under f(k)