Pablo Cadena-Urzúa - cp's OEIS frontend

User: Pablo Cadena-Urzúa

Pablo Cadena-Urzúa has authored 3 sequences.

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

Pablo Cadena-Urzúa, Aug 28 2025

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

			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.

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

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

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

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

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

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

A387331 Least k such that n*k + 1 is a prime > 2 with 2 as a primitive root; a(n) = 0 if no such k exists.

Original entry on oeis.org

2, 1, 4, 1, 2, 2, 4, 0, 2, 1, 6, 1, 4, 2, 4, 0, 26, 1, 22, 3, 10, 3, 6, 0, 4, 2, 6, 1, 2, 2, 12, 0, 2, 13, 6, 1, 4, 11, 14, 0, 2, 5, 4, 15, 4, 3, 14, 0, 4, 2, 12, 1, 2, 3, 12, 0, 26, 1, 12, 1, 58, 6, 6, 0, 2, 1, 4, 9, 2, 3, 12, 0, 4, 2, 38, 25, 50, 7, 4, 0, 2

Offset: 1

Pablo Cadena-Urzúa, Aug 26 2025

If n is a multiple of 8 then a(n) = 0.
Proof: If n = 8*m, then any prime p = n*k+1 satisfies p == 1 (mod 8). Thus 2 is a quadratic residue modulo p, so ord_p(2) | (p-1)/2 and cannot equal p-1.
Computations show that for 1 <= n <= 2000 with 8 !| n, a(n) > 0. This agrees with Artin's conjecture: for each n with 8 !| n there should be infinitely many primes p == 1 (mod n) with 2 as a primitive root.

			a(1) = 2 since 1*2+1 = 3 is prime and 2 generates (Z/3Z)^*.
a(2) = 1 since 2*1+1 = 3 is prime and 2 is a primitive root modulo 3.
a(3) = 4 since 3*4+1 = 13 is prime and ord_13(2) = 12.
a(8) = 0 because every 8*k+1 == 1 (mod 8).

E. Artin, Collected Papers, Addison-Wesley, 1965.

Pablo Cadena-Urzua, Table of n, a(n) for n = 1..2000

Cf. A001122, A005596.

a := proc(n) local k, p;
  if n mod 8 = 0 then return 0 fi;
  for k from 1 do
    p := n*k+1;
    if isprime(p) and p>2 then
      if order(Mod(2, p)) = p-1 then return k fi;
    fi;
  od;
end;

a[n_] := If[Mod[n, 8]==0, 0, Module[{k=1, p, fac}, While[True,
  p=n*k+1;
  If[p>2 && PrimeQ[p], fac=FactorInteger[p-1][[All, 1]];
  If[And@@(PowerMod[2, (p-1)/#, p]!=1&/@fac), Return[k]]];
  k++]]]

from sympy import isprime, factorint
def is_primitive_root_base2(p):
    phi = p-1
    return all(pow(2, phi//q, p)!=1 for q in factorint(phi))
def a(n, kmax=10**7):
    if n%8==0: return 0
    for k in range(1, kmax+1):
        p = n*k+1
        if p>2 and isprime(p) and is_primitive_root_base2(p):
            return k
    return 0

a(n) = 0 if n == 0 (mod 8).

Otherwise, a(n) = min { k >= 1 : p = n*k+1 is prime > 2 and ord_p(2) = p-1 }.

A387305 Least k such that the Hamming weight (A000120) of n*k is prime.

Original entry on oeis.org

3, 3, 1, 3, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 19, 3, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 3, 19, 1, 3, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 9, 3, 1, 1, 1, 1, 7, 1, 5, 3, 1, 1, 3, 3, 1, 19, 1, 1, 67, 3, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 5, 1, 5, 3, 1, 1, 1, 1, 5, 1, 5, 3

Offset: 1

Pablo Cadena-Urzúa, Aug 25 2025

a(n) is always odd.

			a(1) = 3 because A000120(1) = 1 (not prime), A000120(2) = 1, and A000120(3) = 2 (prime).
a(11) = 1 because A000120(11) = 3 (prime).
a(15) = 19 since 15*19 = 285 and A000120(285) = 5 (prime); for 1 <= k < 19 the value A000120(15*k) is not prime.

Pablo Cadena-Urzúa, Table of n, a(n) for n = 1..10000

Cf. A000120, A052294.

A387305[n_] := Module[{k = -1}, While[!PrimeQ[DigitSum[(k += 2)*n, 2]]]; k];
Array[A387305, 100] (* Paolo Xausa, Sep 02 2025 *)

a(n) = {my(k=1); while(!isprime(hammingweight(n*k)), k++); k};
vector(100, n, a(n))  \\ first 100 terms

import sympy as sp
def a(n, kmax=10**6):
    for k in range(1, kmax + 1):
        if sp.isprime((n*k).bit_count()):
            return k
    return None
def A(N):
    return [a(n) for n in range(1, N + 1)]

a(n) = min{k >= 1 : A000120(n*k) is prime}.
a(n) = 1 if A000120(n) is prime (see A052294).
For all m >= 0, a(2^m) = 3.

cp's OEIS Frontend

User: Pablo Cadena-Urzúa

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A387331 Least k such that n*k + 1 is a prime > 2 with 2 as a primitive root; a(n) = 0 if no such k exists.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A387305 Least k such that the Hamming weight (A000120) of n*k is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula