cp's OEIS Frontend

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

%I A387397 #24 Sep 04 2025 10:53:40
%S A387397 0,0,0,3,28,170,866,4025,17704,75108,310812,1263823,5075104,20198854,
%T A387397 79878696,314426897,1233391952,4824992904,18832070706,73352680695,
%U A387397 285181117292,1106813965234,4288993897696,16598629303781,64176110700560,247997873779100,958343137325810
%N A387397 Number of edges in the prime-intersection graph on the Boolean lattice of rank n.
%C A387397 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.
%C A387397 If |A| = k then deg_n(k) = 2^(n-k) * Sum_{p prime, p <= k} binomial(k,p), minus 1 if k is prime.
%C A387397 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).
%H A387397 Pablo Cadena-Urzúa, <a href="/A387397/b387397.txt">Table of n, a(n) for n = 0..1000</a>.
%F A387397 a(n) = (1/2) * Sum_{p prime, p <= n} binomial(n,p) * (3^(n-p) - 1).
%F A387397 E.g.f.: ((exp(3*z) - exp(z))/2) * (Sum_{p prime} z^p/p!).
%F A387397 a(n) ~ 2^(2n-1)/log(n/4).
%e A387397 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.
%t A387397 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 *)
%o A387397 (PARI) a(n) = {my(s=0); forprime(p=2,n,s+=binomial(n,p)*(3^(n-p)-1)); s/2};
%o A387397 (Python)
%o A387397 import sympy as sp
%o A387397 def a(n): return sum(sp.binomial(n,p)*(3**(n-p)-1) for p in sp.primerange(0,n+1))//2
%Y A387397 Cf. A000040, A000079, A000244, A000720, A007318.
%K A387397 nonn,new
%O A387397 0,4
%A A387397 _Pablo Cadena-Urzúa_, Aug 28 2025