A067513 Number of divisors d of n such that d+1 is prime.

1, 2, 1, 3, 1, 3, 1, 3, 1, 3, 1, 5, 1, 2, 1, 4, 1, 4, 1, 4, 1, 3, 1, 5, 1, 2, 1, 4, 1, 5, 1, 4, 1, 2, 1, 7, 1, 2, 1, 5, 1, 4, 1, 4, 1, 3, 1, 6, 1, 3, 1, 4, 1, 4, 1, 4, 1, 3, 1, 8, 1, 2, 1, 4, 1, 5, 1, 3, 1, 4, 1, 8, 1, 2, 1, 3, 1, 4, 1, 6, 1, 3, 1, 7, 1, 2, 1, 5, 1, 6, 1, 4, 1, 2, 1, 7, 1, 2, 1, 5, 1, 4, 1

Offset: 1

Author

Amarnath Murthy, Feb 12 2002

Keywords

• easy
• nonn
• nice

Comments

1, 2 and 4 are the only numbers such that for every divisor d, d+1 is a prime.

These and only these primes appear as prime divisors of any term of InvPhi(n) set if n is not empty, i.e., if n is from A002202. - Labos Elemer, Jun 24 2002

a(n) is the number of integers k such that n = k - k/p where p is one of the prime divisors of k. (See, e.g., A064097 and A333123, which are related to the mapping k -> k - k/p.) - Robert G. Wilson v, Jun 12 2022

Examples

			a(12) = 5 as the divisors of 12 are 1, 2, 3, 4, 6 and 12 and the corresponding primes are 2,3,5,7 and 13. Only 3+1 = 4 is not a prime.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Yuchen Ding, On a conjecture of R. M. Murty and V. K. Murty, arXiv:2208.06704 [math.NT], 2022.
• Yuchen Ding, On a conjecture of R. M. Murty and V. K. Murty II, arXiv:2209.01087 [math.NT], 2022-2023.
• Steve Fan and Carl Pomerance, Shifted-prime divisors, arXiv:2401.10427 [math.NT], 2024.
• Mikhail R. Gabdullin, Moments of the shifted prime divisor function, arXiv preprint (2025). arXiv:2505.24050 [math.NT]
• M. Ram Murty and V. Kumar Murty, A variant of the Hardy-Ramanujan theorem, Hardy-Ramanujan Journal, Vol. 44 (2021), pp. 32-40.
• Karl Prachar, Über die Anzahl der Teiler einer natürlichen Zahl, welche die Form p-1 haben, Monatshefte für Mathematik, Vol. 59 (1955), pp. 91-97.

Crossrefs

Even-indexed terms give A046886.

Cf. A000005, A001221, A001222, A002202, A027750, A064097, A141197, A185633, A202727, A202728, A322312, A322976, A333123, A346467, A355452.

Cf. A005408 (positions of 1's), A051222 (of 2's).

Programs

Haskell

a067513 = sum . map (a010051 . (+ 1)) . a027750_row
-- Reinhard Zumkeller, Jul 31 2012

Maple

A067513 := proc(n)
    local a,d;
    a := 0 ;
    for d in numtheory[divisors](n) do
        if isprime(d+1) then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc:
seq(A067513(n),n=1..100) ; # R. J. Mathar, Aug 07 2022

Mathematica

a[n_] := Length[Select[Divisors[n]+1, PrimeQ]]
Table[Count[Divisors[n],?(PrimeQ[#+1]&)],{n,110}] (* _Harvey P. Dale, Feb 29 2012 *)
a[n_] := DivisorSum[n, 1 &, PrimeQ[# + 1] &]; Array[a, 100] (* Amiram Eldar, Jan 11 2025 *)

PARI

a(n)=sumdiv(n,d,isprime(d+1)) \\ Charles R Greathouse IV, Dec 23 2011

Python

from sympy import divisors, isprime
def a(n): return sum(1 for d in divisors(n, generator=True) if isprime(d+1))
print([a(n) for n in range(1, 104)]) # Michael S. Branicky, Jul 12 2022

Formula

a(n) = 2 iff Bernoulli number B_{n} has denominator 6 (cf. A051222). - Vladeta Jovovic, Feb 13 2002

a(n) <= A141197(n). - Reinhard Zumkeller, Oct 06 2008

a(n) = A001221(A027760(n)). - Enrique Pérez Herrero, Dec 23 2011

a(n) = Sum_{k = 1..A000005(n)} A010051(A027750(n,k)+1). - Reinhard Zumkeller, Jul 31 2012

a(n) = A001221(A185633(n)) = A001222(A322312(n)). - Antti Karttunen, Jul 12 2022

Sum_{k=1..n} a(k) = n * (log(log(n)) + B) + O(n/log(n)), where B is a constant (Prachar, 1955). - Amiram Eldar, Jan 11 2025

Extensions

Edited by Dean Hickerson, Feb 12 2002