Perfect Totient Numbers

January 8, 2019

A perfect number is a number for which the sum of its proper divisors is equal to the number; for instance, 28 is a perfect number because it is the sum of its proper divisors 1 + 2 + 4 + 7 + 14 = 28.

A perfect totient number (A082897) is a number for which the sum of its iterated totients is equal to the number. For instance, 327 is a perfect totient number; its iterated totients are φ(327) = 216, φ(216) = 80, …, and the sum of 216 + 80 + … = 327. I love number theory; it’s totally useless, and endlessly fascinating, as you will see if you follow the links on OEIS.

Your task is to compute the perfect totient numbers less than 10,000. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

7 Responses to “Perfect Totient Numbers”

  1. matthew said

    Sieving is nice, and we can roll calculating the totient sums into the sieving loop:

    def perfecttotient(N):
        a = list(range(N))
        for p in range(2,N):
            if a[p] == p:
                for q in range(p,N,p):
                    a[q] = a[q]//p*(p-1);
            a[p] += a[a[p]]
            if a[p]-1 == p: yield p
    
    for n in perfecttotient(10000000): print(n)
    

    gets up to 9056583 in 20 seconds or so.

  2. max said

    what’s a totient?

  3. Paul said

    @ max, maybe try Google

  4. programmingpraxis said

    @max: The totatives of a positive integer n are those positive integers less than n that are coprime to n; that is positive integers m for which gcd(m, n) = 1. For instance, the totatives of 30 are 1, 7, 11, 13, 17, 19, 23 and 29. The totient of a positive integer n is the number of totatives of n, so φ(30) = 8.

  5. matthew said

    And this similar C++ program gets up to 918330183 in a couple of minutes. After that memory gets a bit tight on my laptop.

    #include <stdio.h>
    #include <stdint.h>
    #include <stdlib.h>
    #include <vector>
    
    typedef uint32_t T;
    
    int main(int argc, char *argv[]) {
      T N = 10000;
      if (argc > 1) N = strtoul(argv[1],0,0);
      std::vector<T> a(N);
      for (T i = 0; i < N; i++) a[i] = i;
      for (T p = 2; p < N; p++) {
        if (a[p] == p) {
          for (T q = p; q < N; q += p) {
            a[q] = a[q]/p*(p-1);
          }
        }
        a[p] += a[a[p]];
        if (a[p]-1 == p) printf("%u\n", p);
      }
    }
    
  6. matthew said

    One useful place the totient function appears is in Euler’s Theorem: https://en.wikipedia.org/wiki/Euler%27s_theorem, which is fundamental to the correctness of RSA encryption.

  7. matthew said

    Or maybe not, if the comment in that Wikipedia page is to be believed.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: