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

Comments

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

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

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) <= A141197(n). - Reinhard Zumkeller, Oct 06 2008

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

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.

Formula

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

Example

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.

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 *)

Prog

(PARI) a(n)=sumdiv(n, d, isprime(d+1)) \\ Charles R Greathouse IV, Dec 23 2011
(Haskell)
a067513 = sum . map (a010051 . (+ 1)) . a027750_row
-- Reinhard Zumkeller, Jul 31 2012
(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

Crossrefs

Even-indexed terms give A046886.

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

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

Sequence in context: A079728 A181801 A029244 * A116372 A232465 A029242

Adjacent sequences: A067510 A067511 A067512 * A067514 A067515 A067516

Keyword

easy,nonn,nice

Author

Amarnath Murthy, Feb 12 2002

Extensions

Edited by Dean Hickerson, Feb 12 2002

Status

approved