9
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Reto Koradi Aug 4 '15 at 16:02
  • \$\begingroup\$ 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. \$\endgroup\$ – Kade Aug 4 '15 at 16:06
  • \$\begingroup\$ @vihan Definitely not. \$\endgroup\$ – Kade Aug 4 '15 at 16:30
6
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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++;
            }
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$

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--
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.