A009087 Numbers whose number of divisors is prime (i.e., numbers of the form p^(q-1) for primes p,q).

2, 3, 4, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239

Offset: 1

Author

Simon Colton (simonco(AT)cs.york.ac.uk)

Keywords

• nice
• nonn
• easy

Comments

Invented by the HR Automatic Concept Formation Program. If the sum of divisors is prime, then the number of divisors is prime, i.e., this is a supersequence of A023194.

A010055(a(n)) * A010051(A100995(a(n))+1) = 1. - Reinhard Zumkeller, Jun 06 2013

Examples

			tau(16)=5 and 5 is prime.
		

References

• S. Colton, Automated Theory Formation in Pure Mathematics. New York: Springer (2002)

Links

• Indranil Ghosh, Table of n, a(n) for n = 1..12546 (terms 1..1000 from T. D. Noe)
• S. Colton, Refactorable Numbers - A Machine Invention, J. Integer Sequences, Vol. 2, 1999, #2.

Crossrefs

Subsequence of A000961.

Cf. A023194, A036454, A203967.

Programs

Haskell

a009087 n = a009087_list !! (n-1)
a009087_list = filter ((== 1) . a010051 . (+ 1) . a100995) a000961_list
-- Reinhard Zumkeller, Jun 05 2013

Mathematica

Select[Range[250],PrimeQ[DivisorSigma[0,#]]&] (* Harvey P. Dale, Sep 28 2011 *)

PARI

is(n)=isprime(isprimepower(n)+1) \\ Charles R Greathouse IV, Sep 16 2015

Python

from sympy import primepi, integer_nthroot, primerange
def A009087(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return int(n+x-sum(primepi(integer_nthroot(x,k-1)[0]) for k in primerange(x.bit_length()+1)))
    return bisection(f,n,n) # Chai Wah Wu, Feb 22 2025

Formula

p^(q-1), p, q primes.