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, A333123 that 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 preprint (2022). arXiv:2208.06704 [math.NT]

Yuchen Ding, On a conjecture of R. M. Murty and V. K. Murty II, arXiv preprint (2022). arXiv:2209.01087 [math.NT]

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 gives 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