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

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

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.

Formula

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

Example

tau(16)=5 and 5 is prime.

Mathematica

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

Prog

(Haskell)
a009087 n = a009087_list !! (n-1)
a009087_list = filter ((== 1) . a010051 . (+ 1) . a100995) a000961_list
-- Reinhard Zumkeller, Jun 05 2013
(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

Crossrefs

Subsequence of A000961.

Cf. A023194, A036454, A203967.

Sequence in context: A066724 A089237 A352870 * A026477 A079852 A084400

Adjacent sequences: A009084 A009085 A009086 * A009088 A009089 A009090

Keyword

nice,nonn,easy,changed

Author

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

Status

approved