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

%I #78 Aug 18 2024 23:03:56

%S 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,

%T 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,

%U 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

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

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

%C a(n) = 2 iff Bernoulli number B_{n} has denominator 6 (cf. A051222). - _Vladeta Jovovic_, Feb 13 2002

%C 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

%C a(n) <= A141197(n). - _Reinhard Zumkeller_, Oct 06 2008

%C 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

%H T. D. Noe, <a href="/A067513/b067513.txt">Table of n, a(n) for n = 1..10000</a>

%H Yuchen Ding, <a href="https://arxiv.org/abs/2208.06704">On a conjecture of R. M. Murty and V. K. Murty</a>, arXiv:2208.06704 [math.NT], 2022.

%H Yuchen Ding, <a href="https://arxiv.org/abs/2209.01087">On a conjecture of R. M. Murty and V. K. Murty II</a>, arXiv:2209.01087 [math.NT], 2022-2023.

%F a(n) = A001221(A027760(n)). - _Enrique PĂ©rez Herrero_, Dec 23 2011

%F a(n) = Sum_{k = 1..A000005(n)} A010051(A027750(n,k)+1). - _Reinhard Zumkeller_, Jul 31 2012

%F a(n) = A001221(A185633(n)) = A001222(A322312(n)). - _Antti Karttunen_, Jul 12 2022

%e 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.

%p A067513 := proc(n)

%p local a,d;

%p a := 0 ;

%p for d in numtheory[divisors](n) do

%p if isprime(d+1) then

%p a := a+1 ;

%p end if;

%p end do:

%p a ;

%p end proc:

%p seq(A067513(n),n=1..100) ; # _R. J. Mathar_, Aug 07 2022

%t a[n_] := Length[Select[Divisors[n]+1, PrimeQ]]

%t Table[Count[Divisors[n],_?(PrimeQ[#+1]&)],{n,110}] (* _Harvey P. Dale_, Feb 29 2012 *)

%o (PARI) a(n)=sumdiv(n,d,isprime(d+1)) \\ _Charles R Greathouse IV_, Dec 23 2011

%o (Haskell)

%o a067513 = sum . map (a010051 . (+ 1)) . a027750_row

%o -- _Reinhard Zumkeller_, Jul 31 2012

%o (Python)

%o from sympy import divisors, isprime

%o def a(n): return sum(1 for d in divisors(n, generator=True) if isprime(d+1))

%o print([a(n) for n in range(1, 104)]) # _Michael S. Branicky_, Jul 12 2022

%Y Even-indexed terms give A046886.

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

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

%K easy,nonn,nice

%O 1,2

%A _Amarnath Murthy_, Feb 12 2002

%E Edited by _Dean Hickerson_, Feb 12 2002