A387397 Number of edges in the prime-intersection graph on the Boolean lattice of rank n.

0, 0, 0, 3, 28, 170, 866, 4025, 17704, 75108, 310812, 1263823, 5075104, 20198854, 79878696, 314426897, 1233391952, 4824992904, 18832070706, 73352680695, 285181117292, 1106813965234, 4288993897696, 16598629303781, 64176110700560, 247997873779100, 958343137325810

Offset: 0

Author

Pablo Cadena-Urzúa, Aug 28 2025

Keywords

• nonn
• new

Comments

In the present entry, the prime-intersection graph is the graph whose vertices are the subsets of {1,...,n}, and two subsets are adjacent when the cardinality of their intersection is a prime number.

If |A| = k then deg_n(k) = 2^(n-k) * Sum_{p prime, p <= k} binomial(k,p), minus 1 if k is prime.

a(n) is odd iff n == 3 (mod 4). Sketch: modulo 4, terms with n - p even vanish; when n is even, all remaining p are odd and binomial(n,p) is even (Lucas). When n is odd, only p=2 contributes, so a(n) == binomial(n,2) (mod 2), which is odd iff n == 3 (mod 4).

Examples

			For n=4, contributions are p=2: binomial(4,2)*(3^2-1)=48; p=3: binomial(4,3)*(3^1-1)=8; total (48+8)/2=28.
		

Links

• Pablo Cadena-Urzúa, Table of n, a(n) for n = 0..1000.

Crossrefs

Cf. A000040, A000079, A000244, A000720, A007318.

Programs

Mathematica

a[n_]:=Sum[Binomial[n,Prime[p]]*(3^(n-Prime[p])-1)/2,{p,PrimePi[n]}];Array[a,27,0] (* James C. McMahon, Sep 04 2025 *)

PARI

a(n) = {my(s=0); forprime(p=2,n,s+=binomial(n,p)*(3^(n-p)-1)); s/2};

Python

import sympy as sp
def a(n): return sum(sp.binomial(n,p)*(3**(n-p)-1) for p in sp.primerange(0,n+1))//2

Formula

a(n) = (1/2) * Sum_{p prime, p <= n} binomial(n,p) * (3^(n-p) - 1).

E.g.f.: ((exp(3*z) - exp(z))/2) * (Sum_{p prime} z^p/p!).

a(n) ~ 2^(2n-1)/log(n/4).