A067513 - OEIS

%I #86 Jan 11 2025 03:13:31

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

%H Steve Fan and Carl Pomerance, <a href="https://arxiv.org/abs/2401.10427">Shifted-prime divisors</a>, arXiv:2401.10427 [math.NT], 2024.

%H 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 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 a(n) = 2 iff Bernoulli number B_{n} has denominator 6 (cf. A051222). - _Vladeta Jovovic_, Feb 13 2002

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

%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

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

%t a[n_] := DivisorSum[n, 1 &, PrimeQ[# + 1] &]; Array[a, 100] (* _Amiram Eldar_, Jan 11 2025 *)

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