A046886 -id:A046886 - cp's OEIS frontend

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

Amarnath Murthy, Feb 12 2002

1, 2 and 4 are the only numbers such that for every divisor d, d+1 is a prime.
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) 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

			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.

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.
Steve Fan and Carl Pomerance, Shifted-prime divisors, arXiv:2401.10427 [math.NT], 2024.
Mikhail R. Gabdullin, Moments of the shifted prime divisor function, arXiv preprint (2025). arXiv:2505.24050 [math.NT]
M. Ram Murty and V. Kumar Murty, A variant of the Hardy-Ramanujan theorem, Hardy-Ramanujan Journal, Vol. 44 (2021), pp. 32-40.
Karl Prachar, Über die Anzahl der Teiler einer natürlichen Zahl, welche die Form p-1 haben, Monatshefte für Mathematik, Vol. 59 (1955), pp. 91-97.

Even-indexed terms give A046886.
Cf. A000005, A001221, A001222, A002202, A027750, A064097, A141197, A185633, A202727, A202728, A322312, A322976, A333123, A346467, A355452.
Cf. A005408 (positions of 1's), A051222 (of 2's).

a067513 = sum . map (a010051 . (+ 1)) . a027750_row
-- Reinhard Zumkeller, Jul 31 2012

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

a[n_] := Length[Select[Divisors[n]+1, PrimeQ]]
Table[Count[Divisors[n],?(PrimeQ[#+1]&)],{n,110}] (* _Harvey P. Dale, Feb 29 2012 *)
a[n_] := DivisorSum[n, 1 &, PrimeQ[# + 1] &]; Array[a, 100] (* Amiram Eldar, Jan 11 2025 *)

a(n)=sumdiv(n,d,isprime(d+1)) \\ Charles R Greathouse IV, Dec 23 2011

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

a(n) = 2 iff Bernoulli number B_{n} has denominator 6 (cf. A051222). - Vladeta Jovovic, Feb 13 2002
a(n) <= A141197(n). - Reinhard Zumkeller, Oct 06 2008
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
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

Edited by Dean Hickerson, Feb 12 2002

A080092 Irregular triangle read by rows, giving prime sequences (p-1|2n) appearing in the n-th von Staudt-Clausen sum.

Original entry on oeis.org

2, 2, 3, 2, 3, 5, 2, 3, 7, 2, 3, 5, 2, 3, 11, 2, 3, 5, 7, 13, 2, 3, 2, 3, 5, 17, 2, 3, 7, 19, 2, 3, 5, 11, 2, 3, 23, 2, 3, 5, 7, 13, 2, 3, 2, 3, 5, 29, 2, 3, 7, 11, 31, 2, 3, 5, 17, 2, 3, 2, 3, 5, 7, 13, 19, 37, 2, 3, 2, 3, 5, 11, 41, 2, 3, 7, 43, 2, 3, 5, 23, 2, 3, 47, 2, 3, 5, 7, 13, 17, 2, 3

Offset: 1

Eric W. Weisstein, Jan 27 2003

From Gary W. Adamson & Mats Granvik, Aug 09 2008: (Start)
The von Staudt-Clausen theorem has two parts: generating denominators of the B_2n and the actual values. Both operations can be demonstrated in triangles A143343 and A080092 by following the procedures outlined in [Wikipedia - Bernoulli numbers] and summarized in A143343.
A046886(n-1) = number of terms in row n.
The same terms in A143343 may be extracted from triangle A138239.
Extract primes from even numbered rows of triangle A143343 but also include "2" as row 1. The rows are thus 1, 2, 4, 6, ..., generating denominators of B_1, B_2, B_4, ..., as well as B_1, B_2, B_4, ..., as two parts of the von Staudt-Clausen theorem.
The denominator of B_12 = 2730 = 2*3*5*7*13 = A027642(12) and A002445(6).
For example, B_12 = -691/2730 = (1 - 1/2 - 1/3 - 1/5 - 1/7 - 1/13).
The second operation is the von Staudt-Clausen representation of Bn, obtained by starting with "1" and then subtracting the reciprocals of terms in each row. (Cf. A143343 for a detailed explanation of the operations.) (End)

			First few rows of the triangle:
  2;
  2, 3;
  2, 3, 5;
  2, 3, 7;
  2, 3, 5;
  2, 3, 11;
  2, 3, 5, 7, 13;
  2, 3;
  ...
Sum for n=1 is 1/2 + 1/3, so terms are 2, 3;
sum for n=2 is 1/2 + 1/3 + 1/5, so terms are 2, 3, 5; etc.

Eric Weisstein's World of Mathematics, von Staudt-Clausen Theorem.
Wikipedia, Von Staudt-Clausen theorem.

Cf. A000146, A002445, A027642, A138239, A143343.

row[n_] := Select[ Prime /@ Range[n+1], Divisible[2n, # - 1] &]; Flatten[Table[row[n], {n, 0, 25}]] (* Jean-François Alcover, Oct 12 2011 *)

Edited by N. J. A. Sloane, Nov 01 2009 at the suggestion of R. J. Mathar

A079294 Number of distinct prime factors of the numerator of the 2n-th Bernoulli number.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 3, 2, 2, 3, 3, 3, 2, 1, 2, 2, 1, 5, 3, 3, 3, 5, 3, 4, 5, 3, 5, 2, 3, 6, 5, 2, 2, 3, 4, 5, 4, 5, 4, 4, 4, 4, 6, 5, 6, 5, 7, 5, 5, 3, 6, 4, 2, 5, 2, 3, 4, 9, 4, 6, 7, 4, 5, 4, 8, 8, 4, 2, 7, 7, 7, 7, 8, 5, 8, 6, 5, 8, 9, 6, 5, 3, 8

Offset: 0

Benoit Cloitre, Feb 09 2003

nonn

Amiram Eldar, Table of n, a(n) for n = 0..103
S. S. Wagstaff, Jr., Factors of Bernoulli numbers

Cf. A001221, A000367, A046886.

Table[PrimeNu[Numerator[BernoulliB[2n]]], {n, 0, 30}] (* Amiram Eldar, Feb 09 2020 *)

PARI
```
a(n)=omega(numerator(bernfrac(2*n)))
```

a(n) = A001221(abs(A000367(n))). - Amiram Eldar, Feb 09 2020

More terms from T. D. Noe, Feb 13 2004

A086668 Number of divisors d of n such that 2d+1 is a prime.

Original entry on oeis.org

1, 2, 2, 2, 2, 4, 1, 3, 3, 3, 2, 4, 1, 3, 4, 3, 1, 6, 1, 4, 3, 3, 2, 5, 2, 3, 3, 3, 2, 7, 1, 3, 4, 2, 3, 7, 1, 2, 3, 5, 2, 6, 1, 4, 5, 3, 1, 6, 1, 4, 3, 3, 2, 7, 3, 5, 2, 3, 1, 8, 1, 2, 5, 3, 3, 6, 1, 3, 4, 5, 1, 8, 1, 3, 5, 2, 2, 7, 1, 5, 4, 3, 2, 6, 2, 3, 3, 5, 2, 10, 1, 3, 2, 2, 3, 7, 1, 4, 6, 5

Offset: 1

Jon Perry, Jul 27 2003

nonn

From Antti Karttunen, Jun 15 2018: (Start)
Number of terms of A005097 that divide n.
For all n >= 1, a(n) > A156660(n). Specifically, a(p) = 2 for all p in A005384 (Sophie Germain primes), although 2's occur in other positions as well.
(End)

			10 has divisors 1,2,5 and 10 of which 2.1+1, 2.2+1 and 2.5+1 are prime, so a(10)=3

Antti Karttunen, Table of n, a(n) for n = 1..65537

One less than A046886.

Cf. A005097, A005384, A101264, A305818.

Table[Count[Divisors[n],?(PrimeQ[2#+1]&)],{n,100}] (* _Harvey P. Dale, Apr 29 2015 *)

for (n=2,100,s=0; fordiv(i=n,i,s+=isprime(2*i+1)); print1(","s))

A086668(n) = sumdiv(n,d,isprime(d+d+1)); \\ Antti Karttunen, Jun 15 2018

From Antti Karttunen, Jun 15 2018: (Start)
a(n) = Sum_{d|n} A101264(d).
a(n) = A305818(n) + A101264(n).
(End)

Definition modified by Harvey P. Dale, Apr 29 2015

A138239 Triangle read by rows: T(n,k) = A000040(k) if A002445(n) mod A000040(k) = 0, otherwise 1.

Original entry on oeis.org

1, 2, 3, 2, 3, 5, 2, 3, 1, 7, 2, 3, 5, 1, 1, 2, 3, 1, 1, 11, 1, 2, 3, 5, 7, 1, 13, 1, 2, 3, 1, 1, 1, 1, 1, 1, 2, 3, 5, 1, 1, 1, 17, 1, 1, 2, 3, 1, 7, 1, 1, 1, 19, 1, 1, 2, 3, 5, 1, 11, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 1, 1, 23, 1, 1, 1, 2, 3, 5, 7, 1, 13, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 0

Mats Granvik, Mar 07 2008

Row products give A002445.

A prime number appears in a column at every A130290-th row from the (A130290+1)-th row onwards. The prime numbers are, so to speak, equidistantly distributed in the columns. A130290 is essentially A005097. Counting terms > 1 in the rows gives A046886.

			First few rows of the triangle and row products are:
1 = 1
2*3 = 6
2*3*5 = 30
2*3*1*7 = 42
2*3*5*1*1 = 30
2*3*1*1*11*1 = 66
2*3*5*7*1*13*1 = 2730

Michel Marcus, Rows n=0..100 of triangle, flattened

Cf. A002445, A005097, A046886, A130290.

T:= (n, k)-> (p-> `if`(irem(denom(bernoulli(2*n)), p)=0, p, 1))(ithprime(k)):
seq(seq(T(n, k), k=1..n+1), n=0..20);  # Alois P. Heinz, Aug 27 2017

t[n_, k_] := If[Mod[Denominator[BernoulliB[2n]], (p = Prime[k])] == 0, p, 1];
Flatten[Table[t[n, k], {n, 0, 13}, {k, 1, n+1}]][[1 ;; 102]] (* Jean-François Alcover, Jun 16 2011 *)

tabl(nn) = {for (n=0, nn, dbn = denominator(bernfrac(2*n)); for (k=1, n+1, if (! (dbn % prime(k)), w = prime(k), w = 1); print1(w, ", "); ); print; ); } \\ Michel Marcus, Aug 27 2017

Definition edited by N. J. A. Sloane, Mar 18 2010

Offset corrected by Alois P. Heinz, Aug 27 2017

A165884 Irregular table of negated A080092 and a leading column of 1's.

Original entry on oeis.org

1, 1, -2, 1, -2, -3, 1, -2, -3, -5, 1, -2, -3, -7, 1, -2, -3, -5, 1, -2, -3, -11, 1, -2, -3, -5, -7, -13, 1, -2, -3, -1, -2, -3, -5, -17

Offset: 0

Paul Curtz, Sep 29 2009

The von Staudt-Clausen decomposition of nonzero Bernoulli numbers (see A164555 and A006954) states B(0)=1, B(1) = 1/2 = 1-1/2, B(2) = 1/6 = 1-1/2-1/3, B(4) = -1/30 = 1-1/2-1/3-1/5 etc.

We consider the denominators of the fractions in these sums, one sum per row. The first term in the sums is essentially the sequence of two 1's followed by A000146; this contributes a first column to this sequence here compared with table A080092.

			1;
1, -2;
1, -2, -3;
1, -2, -3, -5;
1, -2, -3, -7;
1, -2, -3, -5;
1, -2, -3, -11;
1, -2, -3, -5, -7, -13;
1, -2, -3;

Eric Weisstein, von Staudt-Clausen Theorem, MathWorld.

Cf. A046886 (row lengths minus 1), A000146.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A080092 Irregular triangle read by rows, giving prime sequences (p-1|2n) appearing in the n-th von Staudt-Clausen sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A079294 Number of distinct prime factors of the numerator of the 2n-th Bernoulli number.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A086668 Number of divisors d of n such that 2d+1 is a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A138239 Triangle read by rows: T(n,k) = A000040(k) if A002445(n) mod A000040(k) = 0, otherwise 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A165884 Irregular table of negated A080092 and a leading column of 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs