cp's OEIS Frontend

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

%I A067513 #89 Jun 02 2025 17:23:34
%S A067513 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 A067513 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 A067513 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 A067513 Number of divisors d of n such that d+1 is prime.
%C A067513 1, 2 and 4 are the only numbers such that for every divisor d, d+1 is a prime.
%C A067513 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 A067513 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 A067513 T. D. Noe, <a href="/A067513/b067513.txt">Table of n, a(n) for n = 1..10000</a>
%H A067513 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 A067513 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.
%H A067513 Steve Fan and Carl Pomerance, <a href="https://arxiv.org/abs/2401.10427">Shifted-prime divisors</a>, arXiv:2401.10427 [math.NT], 2024.
%H A067513 Mikhail R. Gabdullin, <a href="https://arxiv.org/abs/2505.24050">Moments of the shifted prime divisor function</a>, arXiv preprint (2025). arXiv:2505.24050 [math.NT]
%H A067513 M. Ram Murty and V. Kumar Murty, <a href="https://doi.org/10.46298/hrj.2022.8343">A variant of the Hardy-Ramanujan theorem</a>, Hardy-Ramanujan Journal, Vol. 44 (2021), pp. 32-40.
%H A067513 Karl Prachar, <a href="https://doi.org/10.1007/BF01302992">Über die Anzahl der Teiler einer natürlichen Zahl, welche die Form p-1 haben</a>, Monatshefte für Mathematik, Vol. 59 (1955), pp. 91-97.
%F A067513 a(n) = 2 iff Bernoulli number B_{n} has denominator 6 (cf. A051222). - _Vladeta Jovovic_, Feb 13 2002
%F A067513 a(n) <= A141197(n). - _Reinhard Zumkeller_, Oct 06 2008
%F A067513 a(n) = A001221(A027760(n)). - _Enrique Pérez Herrero_, Dec 23 2011
%F A067513 a(n) = Sum_{k = 1..A000005(n)} A010051(A027750(n,k)+1). - _Reinhard Zumkeller_, Jul 31 2012
%F A067513 a(n) = A001221(A185633(n)) = A001222(A322312(n)). - _Antti Karttunen_, Jul 12 2022
%F A067513 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
%e A067513 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 A067513 := proc(n)
%p A067513     local a,d;
%p A067513     a := 0 ;
%p A067513     for d in numtheory[divisors](n) do
%p A067513         if isprime(d+1) then
%p A067513             a := a+1 ;
%p A067513         end if;
%p A067513     end do:
%p A067513     a ;
%p A067513 end proc:
%p A067513 seq(A067513(n),n=1..100) ; # _R. J. Mathar_, Aug 07 2022
%t A067513 a[n_] := Length[Select[Divisors[n]+1, PrimeQ]]
%t A067513 Table[Count[Divisors[n],_?(PrimeQ[#+1]&)],{n,110}] (* _Harvey P. Dale_, Feb 29 2012 *)
%t A067513 a[n_] := DivisorSum[n, 1 &, PrimeQ[# + 1] &]; Array[a, 100] (* _Amiram Eldar_, Jan 11 2025 *)
%o A067513 (PARI) a(n)=sumdiv(n,d,isprime(d+1)) \\ _Charles R Greathouse IV_, Dec 23 2011
%o A067513 (Haskell)
%o A067513 a067513 = sum . map (a010051 . (+ 1)) . a027750_row
%o A067513 -- _Reinhard Zumkeller_, Jul 31 2012
%o A067513 (Python)
%o A067513 from sympy import divisors, isprime
%o A067513 def a(n): return sum(1 for d in divisors(n, generator=True) if isprime(d+1))
%o A067513 print([a(n) for n in range(1, 104)]) # _Michael S. Branicky_, Jul 12 2022
%Y A067513 Even-indexed terms give A046886.
%Y A067513 Cf. A000005, A001221, A001222, A002202, A027750, A064097, A141197, A185633, A202727, A202728, A322312, A322976, A333123, A346467, A355452.
%Y A067513 Cf. A005408 (positions of 1's), A051222 (of 2's).
%K A067513 easy,nonn,nice
%O A067513 1,2
%A A067513 _Amarnath Murthy_, Feb 12 2002
%E A067513 Edited by _Dean Hickerson_, Feb 12 2002